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 <string.h>
0013
0014 #include "upb/base/descriptor_constants.h"
0015 #include "upb/base/string_view.h"
0016 #include "upb/hash/str_table.h"
0017 #include "upb/mem/arena.h"
0018
0019 // Must be last.
0020 #include "upb/port/def.inc"
0021
0022 typedef enum {
0023   kUpb_MapInsertStatus_Inserted = 0,
0024   kUpb_MapInsertStatus_Replaced = 1,
0025   kUpb_MapInsertStatus_OutOfMemory = 2,
0026 } upb_MapInsertStatus;
0027
0028 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
0029
0030 struct upb_Map {
0031   // Size of key and val, based on the map type.
0032   // Strings are represented as '0' because they must be handled specially.
0033   char key_size;
0034   char val_size;
0035   bool UPB_PRIVATE(is_frozen);
0036
0037   upb_strtable table;
0038 };
0039
0040 #ifdef __cplusplus
0041 extern "C" {
0042 #endif
0043
0044 UPB_INLINE void UPB_PRIVATE(_upb_Map_ShallowFreeze)(struct upb_Map* map) {
0045   map->UPB_PRIVATE(is_frozen) = true;
0046 }
0047
0048 UPB_API_INLINE bool upb_Map_IsFrozen(const struct upb_Map* map) {
0049   return map->UPB_PRIVATE(is_frozen);
0050 }
0051
0052 // Converting between internal table representation and user values.
0053 //
0054 // _upb_map_tokey() and _upb_map_fromkey() are inverses.
0055 // _upb_map_tovalue() and _upb_map_fromvalue() are inverses.
0056 //
0057 // These functions account for the fact that strings are treated differently
0058 // from other types when stored in a map.
0059
0060 UPB_INLINE upb_StringView _upb_map_tokey(const void* key, size_t size) {
0061   if (size == UPB_MAPTYPE_STRING) {
0062     return *(upb_StringView*)key;
0063   } else {
0064     return upb_StringView_FromDataAndSize((const char*)key, size);
0065   }
0066 }
0067
0068 UPB_INLINE void _upb_map_fromkey(upb_StringView key, void* out, size_t size) {
0069   if (size == UPB_MAPTYPE_STRING) {
0070     memcpy(out, &key, sizeof(key));
0071   } else {
0072     memcpy(out, key.data, size);
0073   }
0074 }
0075
0076 UPB_INLINE bool _upb_map_tovalue(const void* val, size_t size,
0077                                  upb_value* msgval, upb_Arena* a) {
0078   if (size == UPB_MAPTYPE_STRING) {
0079     upb_StringView* strp = (upb_StringView*)upb_Arena_Malloc(a, sizeof(*strp));
0080     if (!strp) return false;
0081     *strp = *(upb_StringView*)val;
0082     *msgval = upb_value_ptr(strp);
0083   } else {
0084     memcpy(msgval, val, size);
0085   }
0086   return true;
0087 }
0088
0089 UPB_INLINE void _upb_map_fromvalue(upb_value val, void* out, size_t size) {
0090   if (size == UPB_MAPTYPE_STRING) {
0091     const upb_StringView* strp = (const upb_StringView*)upb_value_getptr(val);
0092     memcpy(out, strp, sizeof(upb_StringView));
0093   } else {
0094     memcpy(out, &val, size);
0095   }
0096 }
0097
0098 UPB_INLINE void* _upb_map_next(const struct upb_Map* map, size_t* iter) {
0099   upb_strtable_iter it;
0100   it.t = &map->table;
0101   it.index = *iter;
0102   upb_strtable_next(&it);
0103   *iter = it.index;
0104   if (upb_strtable_done(&it)) return NULL;
0105   return (void*)str_tabent(&it);
0106 }
0107
0108 UPB_INLINE void _upb_Map_Clear(struct upb_Map* map) {
0109   UPB_ASSERT(!upb_Map_IsFrozen(map));
0110
0111   upb_strtable_clear(&map->table);
0112 }
0113
0114 UPB_INLINE bool _upb_Map_Delete(struct upb_Map* map, const void* key,
0115                                 size_t key_size, upb_value* val) {
0116   UPB_ASSERT(!upb_Map_IsFrozen(map));
0117
0118   upb_StringView k = _upb_map_tokey(key, key_size);
0119   return upb_strtable_remove2(&map->table, k.data, k.size, val);
0120 }
0121
0122 UPB_INLINE bool _upb_Map_Get(const struct upb_Map* map, const void* key,
0123                              size_t key_size, void* val, size_t val_size) {
0124   upb_value tabval;
0125   upb_StringView k = _upb_map_tokey(key, key_size);
0126   bool ret = upb_strtable_lookup2(&map->table, k.data, k.size, &tabval);
0127   if (ret && val) {
0128     _upb_map_fromvalue(tabval, val, val_size);
0129   }
0130   return ret;
0131 }
0132
0133 UPB_INLINE upb_MapInsertStatus _upb_Map_Insert(struct upb_Map* map,
0134                                                const void* key, size_t key_size,
0135                                                void* val, size_t val_size,
0136                                                upb_Arena* a) {
0137   UPB_ASSERT(!upb_Map_IsFrozen(map));
0138
0139   upb_StringView strkey = _upb_map_tokey(key, key_size);
0140   upb_value tabval = {0};
0141   if (!_upb_map_tovalue(val, val_size, &tabval, a)) {
0142     return kUpb_MapInsertStatus_OutOfMemory;
0143   }
0144
0145   // TODO: add overwrite operation to minimize number of lookups.
0146   bool removed =
0147       upb_strtable_remove2(&map->table, strkey.data, strkey.size, NULL);
0148   if (!upb_strtable_insert(&map->table, strkey.data, strkey.size, tabval, a)) {
0149     return kUpb_MapInsertStatus_OutOfMemory;
0150   }
0151   return removed ? kUpb_MapInsertStatus_Replaced
0152                  : kUpb_MapInsertStatus_Inserted;
0153 }
0154
0155 UPB_INLINE size_t _upb_Map_Size(const struct upb_Map* map) {
0156   return map->table.t.count;
0157 }
0158
0159 // Strings/bytes are special-cased in maps.
0160 extern char _upb_Map_CTypeSizeTable[12];
0161
0162 UPB_INLINE size_t _upb_Map_CTypeSize(upb_CType ctype) {
0163   return _upb_Map_CTypeSizeTable[ctype];
0164 }
0165
0166 // Creates a new map on the given arena with this key/value type.
0167 struct upb_Map* _upb_Map_New(upb_Arena* a, size_t key_size, size_t value_size);
0168
0169 #ifdef __cplusplus
0170 } /* extern "C" */
0171 #endif
0172
0173 #include "upb/port/undef.inc"
0174
0175 #endif /* UPB_MESSAGE_INTERNAL_MAP_H_ */