message/internal/map.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2023 Google LLC.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 #ifndef UPB_MESSAGE_INTERNAL_MAP_H_
0009 #define UPB_MESSAGE_INTERNAL_MAP_H_
0010
0011 #include <stddef.h>
0012 #include <stdint.h>
0013 #include <string.h>
0014
0015 #include "upb/base/descriptor_constants.h"
0016 #include "upb/base/string_view.h"
0017 #include "upb/hash/common.h"
0018 #include "upb/hash/int_table.h"
0019 #include "upb/hash/str_table.h"
0020 #include "upb/mem/arena.h"
0021
0022 // Must be last.
0023 #include "upb/port/def.inc"
0024
0025 typedef enum {
0026   kUpb_MapInsertStatus_Inserted = 0,
0027   kUpb_MapInsertStatus_Replaced = 1,
0028   kUpb_MapInsertStatus_OutOfMemory = 2,
0029 } upb_MapInsertStatus;
0030
0031 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
0032
0033 union upb_Map_Table {
0034   upb_strtable strtable;
0035   upb_inttable inttable;
0036 };
0037
0038 struct upb_Map {
0039   // Size of key and val, based on the map type.
0040   // Strings are represented as '0' because they must be handled specially.
0041   char key_size;
0042   char val_size;
0043   bool UPB_PRIVATE(is_frozen);
0044   bool UPB_PRIVATE(is_strtable);
0045
0046   union upb_Map_Table t;
0047 };
0048
0049 #ifdef __cplusplus
0050 extern "C" {
0051 #endif
0052
0053 UPB_INLINE void UPB_PRIVATE(_upb_Map_ShallowFreeze)(struct upb_Map* map) {
0054   map->UPB_PRIVATE(is_frozen) = true;
0055 }
0056
0057 UPB_API_INLINE bool upb_Map_IsFrozen(const struct upb_Map* map) {
0058   return map->UPB_PRIVATE(is_frozen);
0059 }
0060
0061 // Converting between internal table representation and user values.
0062 //
0063 // _upb_map_tokey() and _upb_map_fromkey() are inverses.
0064 // _upb_map_tovalue() and _upb_map_fromvalue() are inverses.
0065 //
0066 // These functions account for the fact that strings are treated differently
0067 // from other types when stored in a map.
0068
0069 UPB_INLINE upb_StringView _upb_map_tokey(const void* key, size_t size) {
0070   if (size == UPB_MAPTYPE_STRING) {
0071     return *(upb_StringView*)key;
0072   } else {
0073     return upb_StringView_FromDataAndSize((const char*)key, size);
0074   }
0075 }
0076
0077 UPB_INLINE uintptr_t _upb_map_tointkey(const void* key, size_t key_size) {
0078   uintptr_t intkey = 0;
0079   memcpy(&intkey, key, key_size);
0080   return intkey;
0081 }
0082
0083 UPB_INLINE void _upb_map_fromkey(upb_StringView key, void* out, size_t size) {
0084   if (size == UPB_MAPTYPE_STRING) {
0085     memcpy(out, &key, sizeof(key));
0086   } else {
0087     memcpy(out, key.data, size);
0088   }
0089 }
0090
0091 UPB_INLINE bool _upb_map_tovalue(const void* val, size_t size,
0092                                  upb_value* msgval, upb_Arena* a) {
0093   if (size == UPB_MAPTYPE_STRING) {
0094     upb_StringView* strp = (upb_StringView*)upb_Arena_Malloc(a, sizeof(*strp));
0095     if (!strp) return false;
0096     *strp = *(upb_StringView*)val;
0097     *msgval = upb_value_ptr(strp);
0098   } else {
0099     memcpy(msgval, val, size);
0100   }
0101   return true;
0102 }
0103
0104 UPB_INLINE void _upb_map_fromvalue(upb_value val, void* out, size_t size) {
0105   if (size == UPB_MAPTYPE_STRING) {
0106     const upb_StringView* strp = (const upb_StringView*)upb_value_getptr(val);
0107     memcpy(out, strp, sizeof(upb_StringView));
0108   } else {
0109     memcpy(out, &val, size);
0110   }
0111 }
0112
0113 UPB_INLINE bool _upb_map_next(const struct upb_Map* map, size_t* iter) {
0114   if (map->UPB_PRIVATE(is_strtable)) {
0115     upb_strtable_iter it;
0116     it.t = &map->t.strtable;
0117     it.index = *iter;
0118     upb_strtable_next(&it);
0119     *iter = it.index;
0120     return !upb_strtable_done(&it);
0121   } else {
0122     uintptr_t key;
0123     upb_value val;
0124     intptr_t int_iter = 0;
0125     memcpy(&int_iter, iter, sizeof(intptr_t));
0126     upb_inttable_next(&map->t.inttable, &key, &val, &int_iter);
0127     memcpy(iter, &int_iter, sizeof(size_t));
0128     return !upb_inttable_done(&map->t.inttable, int_iter);
0129   }
0130 }
0131
0132 UPB_INLINE void _upb_Map_Clear(struct upb_Map* map) {
0133   UPB_ASSERT(!upb_Map_IsFrozen(map));
0134
0135   if (map->UPB_PRIVATE(is_strtable)) {
0136     upb_strtable_clear(&map->t.strtable);
0137   } else {
0138     upb_inttable_clear(&map->t.inttable);
0139   }
0140 }
0141
0142 UPB_INLINE bool _upb_Map_Delete(struct upb_Map* map, const void* key,
0143                                 size_t key_size, upb_value* val) {
0144   UPB_ASSERT(!upb_Map_IsFrozen(map));
0145
0146   if (map->UPB_PRIVATE(is_strtable)) {
0147     upb_StringView k = _upb_map_tokey(key, key_size);
0148     return upb_strtable_remove2(&map->t.strtable, k.data, k.size, val);
0149   } else {
0150     uintptr_t intkey = _upb_map_tointkey(key, key_size);
0151     return upb_inttable_remove(&map->t.inttable, intkey, val);
0152   }
0153 }
0154
0155 UPB_INLINE bool _upb_Map_Get(const struct upb_Map* map, const void* key,
0156                              size_t key_size, void* val, size_t val_size) {
0157   upb_value tabval = {0};
0158   bool ret;
0159   if (map->UPB_PRIVATE(is_strtable)) {
0160     upb_StringView k = _upb_map_tokey(key, key_size);
0161     ret = upb_strtable_lookup2(&map->t.strtable, k.data, k.size, &tabval);
0162   } else {
0163     uintptr_t intkey = _upb_map_tointkey(key, key_size);
0164     ret = upb_inttable_lookup(&map->t.inttable, intkey, &tabval);
0165   }
0166   if (ret && val) {
0167     _upb_map_fromvalue(tabval, val, val_size);
0168   }
0169   return ret;
0170 }
0171
0172 UPB_INLINE upb_MapInsertStatus _upb_Map_Insert(struct upb_Map* map,
0173                                                const void* key, size_t key_size,
0174                                                void* val, size_t val_size,
0175                                                upb_Arena* a) {
0176   UPB_ASSERT(!upb_Map_IsFrozen(map));
0177
0178   // Prep the value.
0179   upb_value tabval = {0};
0180   if (!_upb_map_tovalue(val, val_size, &tabval, a)) {
0181     return kUpb_MapInsertStatus_OutOfMemory;
0182   }
0183
0184   bool removed;
0185   if (map->UPB_PRIVATE(is_strtable)) {
0186     upb_StringView strkey = _upb_map_tokey(key, key_size);
0187     // TODO: add overwrite operation to minimize number of lookups.
0188     removed =
0189         upb_strtable_remove2(&map->t.strtable, strkey.data, strkey.size, NULL);
0190     if (!upb_strtable_insert(&map->t.strtable, strkey.data, strkey.size, tabval,
0191                              a)) {
0192       return kUpb_MapInsertStatus_OutOfMemory;
0193     }
0194   } else {
0195     uintptr_t intkey = _upb_map_tointkey(key, key_size);
0196     removed = upb_inttable_remove(&map->t.inttable, intkey, NULL);
0197     if (!upb_inttable_insert(&map->t.inttable, intkey, tabval, a)) {
0198       return kUpb_MapInsertStatus_OutOfMemory;
0199     }
0200   }
0201   return removed ? kUpb_MapInsertStatus_Replaced
0202                  : kUpb_MapInsertStatus_Inserted;
0203 }
0204
0205 UPB_INLINE size_t _upb_Map_Size(const struct upb_Map* map) {
0206   if (map->UPB_PRIVATE(is_strtable)) {
0207     return map->t.strtable.t.count;
0208   } else {
0209     return upb_inttable_count(&map->t.inttable);
0210   }
0211 }
0212
0213 // Strings/bytes are special-cased in maps.
0214 extern char _upb_Map_CTypeSizeTable[12];
0215
0216 UPB_INLINE size_t _upb_Map_CTypeSize(upb_CType ctype) {
0217   return _upb_Map_CTypeSizeTable[ctype];
0218 }
0219
0220 // Creates a new map on the given arena with this key/value type.
0221 struct upb_Map* _upb_Map_New(upb_Arena* a, size_t key_size, size_t value_size);
0222
0223 #ifdef __cplusplus
0224 } /* extern "C" */
0225 #endif
0226
0227 #include "upb/port/undef.inc"
0228
0229 #endif /* UPB_MESSAGE_INTERNAL_MAP_H_ */