1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "upb/message/internal/map_sorter.h"
9
10 #include <stdint.h>
11 #include <string.h>
12
13 #include "upb/base/descriptor_constants.h"
14 #include "upb/base/internal/log2.h"
15 #include "upb/base/string_view.h"
16 #include "upb/mem/alloc.h"
17 #include "upb/message/map.h"
18 #include "upb/message/message.h"
19 #include "upb/mini_table/extension.h"
20
21 // Must be last.
22 #include "upb/port/def.inc"
23
_upb_mapsorter_getkeys(const void * _a,const void * _b,void * a_key,void * b_key,size_t size)24 static void _upb_mapsorter_getkeys(const void* _a, const void* _b, void* a_key,
25 void* b_key, size_t size) {
26 const upb_tabent* const* a = _a;
27 const upb_tabent* const* b = _b;
28 upb_StringView a_tabkey = upb_tabstrview((*a)->key);
29 upb_StringView b_tabkey = upb_tabstrview((*b)->key);
30 _upb_map_fromkey(a_tabkey, a_key, size);
31 _upb_map_fromkey(b_tabkey, b_key, size);
32 }
33
_upb_mapsorter_cmpi64(const void * _a,const void * _b)34 static int _upb_mapsorter_cmpi64(const void* _a, const void* _b) {
35 int64_t a, b;
36 _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
37 return a < b ? -1 : a > b;
38 }
39
_upb_mapsorter_cmpu64(const void * _a,const void * _b)40 static int _upb_mapsorter_cmpu64(const void* _a, const void* _b) {
41 uint64_t a, b;
42 _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
43 return a < b ? -1 : a > b;
44 }
45
_upb_mapsorter_cmpi32(const void * _a,const void * _b)46 static int _upb_mapsorter_cmpi32(const void* _a, const void* _b) {
47 int32_t a, b;
48 _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
49 return a < b ? -1 : a > b;
50 }
51
_upb_mapsorter_cmpu32(const void * _a,const void * _b)52 static int _upb_mapsorter_cmpu32(const void* _a, const void* _b) {
53 uint32_t a, b;
54 _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
55 return a < b ? -1 : a > b;
56 }
57
_upb_mapsorter_cmpbool(const void * _a,const void * _b)58 static int _upb_mapsorter_cmpbool(const void* _a, const void* _b) {
59 bool a, b;
60 _upb_mapsorter_getkeys(_a, _b, &a, &b, 1);
61 return a < b ? -1 : a > b;
62 }
63
_upb_mapsorter_cmpstr(const void * _a,const void * _b)64 static int _upb_mapsorter_cmpstr(const void* _a, const void* _b) {
65 upb_StringView a, b;
66 _upb_mapsorter_getkeys(_a, _b, &a, &b, UPB_MAPTYPE_STRING);
67 size_t common_size = UPB_MIN(a.size, b.size);
68 int cmp = memcmp(a.data, b.data, common_size);
69 if (cmp) return -cmp;
70 return a.size < b.size ? -1 : a.size > b.size;
71 }
72
73 static int (*const compar[kUpb_FieldType_SizeOf])(const void*, const void*) = {
74 [kUpb_FieldType_Int64] = _upb_mapsorter_cmpi64,
75 [kUpb_FieldType_SFixed64] = _upb_mapsorter_cmpi64,
76 [kUpb_FieldType_SInt64] = _upb_mapsorter_cmpi64,
77
78 [kUpb_FieldType_UInt64] = _upb_mapsorter_cmpu64,
79 [kUpb_FieldType_Fixed64] = _upb_mapsorter_cmpu64,
80
81 [kUpb_FieldType_Int32] = _upb_mapsorter_cmpi32,
82 [kUpb_FieldType_SInt32] = _upb_mapsorter_cmpi32,
83 [kUpb_FieldType_SFixed32] = _upb_mapsorter_cmpi32,
84 [kUpb_FieldType_Enum] = _upb_mapsorter_cmpi32,
85
86 [kUpb_FieldType_UInt32] = _upb_mapsorter_cmpu32,
87 [kUpb_FieldType_Fixed32] = _upb_mapsorter_cmpu32,
88
89 [kUpb_FieldType_Bool] = _upb_mapsorter_cmpbool,
90
91 [kUpb_FieldType_String] = _upb_mapsorter_cmpstr,
92 [kUpb_FieldType_Bytes] = _upb_mapsorter_cmpstr,
93 };
94
_upb_mapsorter_resize(_upb_mapsorter * s,_upb_sortedmap * sorted,int size)95 static bool _upb_mapsorter_resize(_upb_mapsorter* s, _upb_sortedmap* sorted,
96 int size) {
97 sorted->start = s->size;
98 sorted->pos = sorted->start;
99 sorted->end = sorted->start + size;
100
101 if (sorted->end > s->cap) {
102 const int oldsize = s->cap * sizeof(*s->entries);
103 s->cap = upb_Log2CeilingSize(sorted->end);
104 const int newsize = s->cap * sizeof(*s->entries);
105 s->entries = upb_grealloc(s->entries, oldsize, newsize);
106 if (!s->entries) return false;
107 }
108
109 s->size = sorted->end;
110 return true;
111 }
112
_upb_mapsorter_pushmap(_upb_mapsorter * s,upb_FieldType key_type,const upb_Map * map,_upb_sortedmap * sorted)113 bool _upb_mapsorter_pushmap(_upb_mapsorter* s, upb_FieldType key_type,
114 const upb_Map* map, _upb_sortedmap* sorted) {
115 int map_size = _upb_Map_Size(map);
116 UPB_ASSERT(map_size);
117
118 if (!_upb_mapsorter_resize(s, sorted, map_size)) return false;
119
120 // Copy non-empty entries from the table to s->entries.
121 const void** dst = &s->entries[sorted->start];
122 const upb_tabent* src = map->table.t.entries;
123 const upb_tabent* end = src + upb_table_size(&map->table.t);
124 for (; src < end; src++) {
125 if (!upb_tabent_isempty(src)) {
126 *dst = src;
127 dst++;
128 }
129 }
130 UPB_ASSERT(dst == &s->entries[sorted->end]);
131
132 // Sort entries according to the key type.
133 qsort(&s->entries[sorted->start], map_size, sizeof(*s->entries),
134 compar[key_type]);
135 return true;
136 }
137
_upb_mapsorter_cmpext(const void * _a,const void * _b)138 static int _upb_mapsorter_cmpext(const void* _a, const void* _b) {
139 const upb_Extension* const* a = _a;
140 const upb_Extension* const* b = _b;
141 uint32_t a_num = upb_MiniTableExtension_Number((*a)->ext);
142 uint32_t b_num = upb_MiniTableExtension_Number((*b)->ext);
143 assert(a_num != b_num);
144 return a_num < b_num ? -1 : 1;
145 }
146
_upb_mapsorter_pushexts(_upb_mapsorter * s,const upb_Extension * exts,size_t count,_upb_sortedmap * sorted)147 bool _upb_mapsorter_pushexts(_upb_mapsorter* s, const upb_Extension* exts,
148 size_t count, _upb_sortedmap* sorted) {
149 if (!_upb_mapsorter_resize(s, sorted, count)) return false;
150
151 for (size_t i = 0; i < count; i++) {
152 s->entries[sorted->start + i] = &exts[i];
153 }
154
155 qsort(&s->entries[sorted->start], count, sizeof(*s->entries),
156 _upb_mapsorter_cmpext);
157 return true;
158 }
159