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 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
29 
30 #ifndef UPB_COLLECTIONS_MAP_INTERNAL_H_
31 #define UPB_COLLECTIONS_MAP_INTERNAL_H_
32 
33 #include "upb/base/string_view.h"
34 #include "upb/collections/map.h"
35 #include "upb/hash/str_table.h"
36 #include "upb/mem/arena.h"
37 
38 // Must be last.
39 #include "upb/port/def.inc"
40 
41 struct upb_Map {
42   // Size of key and val, based on the map type.
43   // Strings are represented as '0' because they must be handled specially.
44   char key_size;
45   char val_size;
46 
47   upb_strtable table;
48 };
49 
50 #ifdef __cplusplus
51 extern "C" {
52 #endif
53 
54 // Converting between internal table representation and user values.
55 //
56 // _upb_map_tokey() and _upb_map_fromkey() are inverses.
57 // _upb_map_tovalue() and _upb_map_fromvalue() are inverses.
58 //
59 // These functions account for the fact that strings are treated differently
60 // from other types when stored in a map.
61 
_upb_map_tokey(const void * key,size_t size)62 UPB_INLINE upb_StringView _upb_map_tokey(const void* key, size_t size) {
63   if (size == UPB_MAPTYPE_STRING) {
64     return *(upb_StringView*)key;
65   } else {
66     return upb_StringView_FromDataAndSize((const char*)key, size);
67   }
68 }
69 
_upb_map_fromkey(upb_StringView key,void * out,size_t size)70 UPB_INLINE void _upb_map_fromkey(upb_StringView key, void* out, size_t size) {
71   if (size == UPB_MAPTYPE_STRING) {
72     memcpy(out, &key, sizeof(key));
73   } else {
74     memcpy(out, key.data, size);
75   }
76 }
77 
_upb_map_tovalue(const void * val,size_t size,upb_value * msgval,upb_Arena * a)78 UPB_INLINE bool _upb_map_tovalue(const void* val, size_t size,
79                                  upb_value* msgval, upb_Arena* a) {
80   if (size == UPB_MAPTYPE_STRING) {
81     upb_StringView* strp = (upb_StringView*)upb_Arena_Malloc(a, sizeof(*strp));
82     if (!strp) return false;
83     *strp = *(upb_StringView*)val;
84     *msgval = upb_value_ptr(strp);
85   } else {
86     memcpy(msgval, val, size);
87   }
88   return true;
89 }
90 
_upb_map_fromvalue(upb_value val,void * out,size_t size)91 UPB_INLINE void _upb_map_fromvalue(upb_value val, void* out, size_t size) {
92   if (size == UPB_MAPTYPE_STRING) {
93     const upb_StringView* strp = (const upb_StringView*)upb_value_getptr(val);
94     memcpy(out, strp, sizeof(upb_StringView));
95   } else {
96     memcpy(out, &val, size);
97   }
98 }
99 
_upb_map_next(const upb_Map * map,size_t * iter)100 UPB_INLINE void* _upb_map_next(const upb_Map* map, size_t* iter) {
101   upb_strtable_iter it;
102   it.t = &map->table;
103   it.index = *iter;
104   upb_strtable_next(&it);
105   *iter = it.index;
106   if (upb_strtable_done(&it)) return NULL;
107   return (void*)str_tabent(&it);
108 }
109 
_upb_Map_Clear(upb_Map * map)110 UPB_INLINE void _upb_Map_Clear(upb_Map* map) {
111   upb_strtable_clear(&map->table);
112 }
113 
_upb_Map_Delete(upb_Map * map,const void * key,size_t key_size,upb_value * val)114 UPB_INLINE bool _upb_Map_Delete(upb_Map* map, const void* key, size_t key_size,
115                                 upb_value* val) {
116   upb_StringView k = _upb_map_tokey(key, key_size);
117   return upb_strtable_remove2(&map->table, k.data, k.size, val);
118 }
119 
_upb_Map_Get(const upb_Map * map,const void * key,size_t key_size,void * val,size_t val_size)120 UPB_INLINE bool _upb_Map_Get(const upb_Map* map, const void* key,
121                              size_t key_size, void* val, size_t val_size) {
122   upb_value tabval;
123   upb_StringView k = _upb_map_tokey(key, key_size);
124   bool ret = upb_strtable_lookup2(&map->table, k.data, k.size, &tabval);
125   if (ret && val) {
126     _upb_map_fromvalue(tabval, val, val_size);
127   }
128   return ret;
129 }
130 
_upb_Map_Insert(upb_Map * map,const void * key,size_t key_size,void * val,size_t val_size,upb_Arena * a)131 UPB_INLINE upb_MapInsertStatus _upb_Map_Insert(upb_Map* map, const void* key,
132                                                size_t key_size, void* val,
133                                                size_t val_size, upb_Arena* a) {
134   upb_StringView strkey = _upb_map_tokey(key, key_size);
135   upb_value tabval = {0};
136   if (!_upb_map_tovalue(val, val_size, &tabval, a)) {
137     return kUpb_MapInsertStatus_OutOfMemory;
138   }
139 
140   // TODO(haberman): add overwrite operation to minimize number of lookups.
141   bool removed =
142       upb_strtable_remove2(&map->table, strkey.data, strkey.size, NULL);
143   if (!upb_strtable_insert(&map->table, strkey.data, strkey.size, tabval, a)) {
144     return kUpb_MapInsertStatus_OutOfMemory;
145   }
146   return removed ? kUpb_MapInsertStatus_Replaced
147                  : kUpb_MapInsertStatus_Inserted;
148 }
149 
_upb_Map_Size(const upb_Map * map)150 UPB_INLINE size_t _upb_Map_Size(const upb_Map* map) {
151   return map->table.t.count;
152 }
153 
154 // Strings/bytes are special-cased in maps.
155 extern char _upb_Map_CTypeSizeTable[12];
156 
_upb_Map_CTypeSize(upb_CType ctype)157 UPB_INLINE size_t _upb_Map_CTypeSize(upb_CType ctype) {
158   return _upb_Map_CTypeSizeTable[ctype];
159 }
160 
161 // Creates a new map on the given arena with this key/value type.
162 upb_Map* _upb_Map_New(upb_Arena* a, size_t key_size, size_t value_size);
163 
164 #ifdef __cplusplus
165 } /* extern "C" */
166 #endif
167 
168 #include "upb/port/undef.inc"
169 
170 #endif /* UPB_COLLECTIONS_MAP_INTERNAL_H_ */
171