1 /*
2 * Copyright (c) 2009-2021, Google LLC
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google LLC nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT,
20 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "upb/base/log2.h"
29 #include "upb/collections/map_sorter_internal.h"
30
31 // Must be last.
32 #include "upb/port/def.inc"
33
_upb_mapsorter_getkeys(const void * _a,const void * _b,void * a_key,void * b_key,size_t size)34 static void _upb_mapsorter_getkeys(const void* _a, const void* _b, void* a_key,
35 void* b_key, size_t size) {
36 const upb_tabent* const* a = _a;
37 const upb_tabent* const* b = _b;
38 upb_StringView a_tabkey = upb_tabstrview((*a)->key);
39 upb_StringView b_tabkey = upb_tabstrview((*b)->key);
40 _upb_map_fromkey(a_tabkey, a_key, size);
41 _upb_map_fromkey(b_tabkey, b_key, size);
42 }
43
_upb_mapsorter_cmpi64(const void * _a,const void * _b)44 static int _upb_mapsorter_cmpi64(const void* _a, const void* _b) {
45 int64_t a, b;
46 _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
47 return a < b ? -1 : a > b;
48 }
49
_upb_mapsorter_cmpu64(const void * _a,const void * _b)50 static int _upb_mapsorter_cmpu64(const void* _a, const void* _b) {
51 uint64_t a, b;
52 _upb_mapsorter_getkeys(_a, _b, &a, &b, 8);
53 return a < b ? -1 : a > b;
54 }
55
_upb_mapsorter_cmpi32(const void * _a,const void * _b)56 static int _upb_mapsorter_cmpi32(const void* _a, const void* _b) {
57 int32_t a, b;
58 _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
59 return a < b ? -1 : a > b;
60 }
61
_upb_mapsorter_cmpu32(const void * _a,const void * _b)62 static int _upb_mapsorter_cmpu32(const void* _a, const void* _b) {
63 uint32_t a, b;
64 _upb_mapsorter_getkeys(_a, _b, &a, &b, 4);
65 return a < b ? -1 : a > b;
66 }
67
_upb_mapsorter_cmpbool(const void * _a,const void * _b)68 static int _upb_mapsorter_cmpbool(const void* _a, const void* _b) {
69 bool a, b;
70 _upb_mapsorter_getkeys(_a, _b, &a, &b, 1);
71 return a < b ? -1 : a > b;
72 }
73
_upb_mapsorter_cmpstr(const void * _a,const void * _b)74 static int _upb_mapsorter_cmpstr(const void* _a, const void* _b) {
75 upb_StringView a, b;
76 _upb_mapsorter_getkeys(_a, _b, &a, &b, UPB_MAPTYPE_STRING);
77 size_t common_size = UPB_MIN(a.size, b.size);
78 int cmp = memcmp(a.data, b.data, common_size);
79 if (cmp) return -cmp;
80 return a.size < b.size ? -1 : a.size > b.size;
81 }
82
83 static int (*const compar[kUpb_FieldType_SizeOf])(const void*, const void*) = {
84 [kUpb_FieldType_Int64] = _upb_mapsorter_cmpi64,
85 [kUpb_FieldType_SFixed64] = _upb_mapsorter_cmpi64,
86 [kUpb_FieldType_SInt64] = _upb_mapsorter_cmpi64,
87
88 [kUpb_FieldType_UInt64] = _upb_mapsorter_cmpu64,
89 [kUpb_FieldType_Fixed64] = _upb_mapsorter_cmpu64,
90
91 [kUpb_FieldType_Int32] = _upb_mapsorter_cmpi32,
92 [kUpb_FieldType_SInt32] = _upb_mapsorter_cmpi32,
93 [kUpb_FieldType_SFixed32] = _upb_mapsorter_cmpi32,
94 [kUpb_FieldType_Enum] = _upb_mapsorter_cmpi32,
95
96 [kUpb_FieldType_UInt32] = _upb_mapsorter_cmpu32,
97 [kUpb_FieldType_Fixed32] = _upb_mapsorter_cmpu32,
98
99 [kUpb_FieldType_Bool] = _upb_mapsorter_cmpbool,
100
101 [kUpb_FieldType_String] = _upb_mapsorter_cmpstr,
102 [kUpb_FieldType_Bytes] = _upb_mapsorter_cmpstr,
103 };
104
_upb_mapsorter_resize(_upb_mapsorter * s,_upb_sortedmap * sorted,int size)105 static bool _upb_mapsorter_resize(_upb_mapsorter* s, _upb_sortedmap* sorted,
106 int size) {
107 sorted->start = s->size;
108 sorted->pos = sorted->start;
109 sorted->end = sorted->start + size;
110
111 if (sorted->end > s->cap) {
112 s->cap = upb_Log2CeilingSize(sorted->end);
113 s->entries = realloc(s->entries, s->cap * sizeof(*s->entries));
114 if (!s->entries) return false;
115 }
116
117 s->size = sorted->end;
118 return true;
119 }
120
_upb_mapsorter_pushmap(_upb_mapsorter * s,upb_FieldType key_type,const upb_Map * map,_upb_sortedmap * sorted)121 bool _upb_mapsorter_pushmap(_upb_mapsorter* s, upb_FieldType key_type,
122 const upb_Map* map, _upb_sortedmap* sorted) {
123 int map_size = _upb_Map_Size(map);
124
125 if (!_upb_mapsorter_resize(s, sorted, map_size)) return false;
126
127 // Copy non-empty entries from the table to s->entries.
128 const void** dst = &s->entries[sorted->start];
129 const upb_tabent* src = map->table.t.entries;
130 const upb_tabent* end = src + upb_table_size(&map->table.t);
131 for (; src < end; src++) {
132 if (!upb_tabent_isempty(src)) {
133 *dst = src;
134 dst++;
135 }
136 }
137 UPB_ASSERT(dst == &s->entries[sorted->end]);
138
139 // Sort entries according to the key type.
140 qsort(&s->entries[sorted->start], map_size, sizeof(*s->entries),
141 compar[key_type]);
142 return true;
143 }
144
_upb_mapsorter_cmpext(const void * _a,const void * _b)145 static int _upb_mapsorter_cmpext(const void* _a, const void* _b) {
146 const upb_Message_Extension* const* a = _a;
147 const upb_Message_Extension* const* b = _b;
148 uint32_t a_num = (*a)->ext->field.number;
149 uint32_t b_num = (*b)->ext->field.number;
150 assert(a_num != b_num);
151 return a_num < b_num ? -1 : 1;
152 }
153
_upb_mapsorter_pushexts(_upb_mapsorter * s,const upb_Message_Extension * exts,size_t count,_upb_sortedmap * sorted)154 bool _upb_mapsorter_pushexts(_upb_mapsorter* s,
155 const upb_Message_Extension* exts, size_t count,
156 _upb_sortedmap* sorted) {
157 if (!_upb_mapsorter_resize(s, sorted, count)) return false;
158
159 for (size_t i = 0; i < count; i++) {
160 s->entries[sorted->start + i] = &exts[i];
161 }
162
163 qsort(&s->entries[sorted->start], count, sizeof(*s->entries),
164 _upb_mapsorter_cmpext);
165 return true;
166 }
167