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