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/collections/map.h"
29
30 #include <string.h>
31
32 #include "upb/collections/map_internal.h"
33 #include "upb/mem/arena.h"
34
35 // Must be last.
36 #include "upb/port/def.inc"
37
38 // Strings/bytes are special-cased in maps.
39 char _upb_Map_CTypeSizeTable[12] = {
40 [kUpb_CType_Bool] = 1,
41 [kUpb_CType_Float] = 4,
42 [kUpb_CType_Int32] = 4,
43 [kUpb_CType_UInt32] = 4,
44 [kUpb_CType_Enum] = 4,
45 [kUpb_CType_Message] = sizeof(void*),
46 [kUpb_CType_Double] = 8,
47 [kUpb_CType_Int64] = 8,
48 [kUpb_CType_UInt64] = 8,
49 [kUpb_CType_String] = UPB_MAPTYPE_STRING,
50 [kUpb_CType_Bytes] = UPB_MAPTYPE_STRING,
51 };
52
upb_Map_New(upb_Arena * a,upb_CType key_type,upb_CType value_type)53 upb_Map* upb_Map_New(upb_Arena* a, upb_CType key_type, upb_CType value_type) {
54 return _upb_Map_New(a, _upb_Map_CTypeSize(key_type),
55 _upb_Map_CTypeSize(value_type));
56 }
57
upb_Map_Size(const upb_Map * map)58 size_t upb_Map_Size(const upb_Map* map) { return _upb_Map_Size(map); }
59
upb_Map_Get(const upb_Map * map,upb_MessageValue key,upb_MessageValue * val)60 bool upb_Map_Get(const upb_Map* map, upb_MessageValue key,
61 upb_MessageValue* val) {
62 return _upb_Map_Get(map, &key, map->key_size, val, map->val_size);
63 }
64
upb_Map_Clear(upb_Map * map)65 void upb_Map_Clear(upb_Map* map) { _upb_Map_Clear(map); }
66
upb_Map_Insert(upb_Map * map,upb_MessageValue key,upb_MessageValue val,upb_Arena * arena)67 upb_MapInsertStatus upb_Map_Insert(upb_Map* map, upb_MessageValue key,
68 upb_MessageValue val, upb_Arena* arena) {
69 UPB_ASSERT(arena);
70 return (upb_MapInsertStatus)_upb_Map_Insert(map, &key, map->key_size, &val,
71 map->val_size, arena);
72 }
73
upb_Map_Delete(upb_Map * map,upb_MessageValue key,upb_MessageValue * val)74 bool upb_Map_Delete(upb_Map* map, upb_MessageValue key, upb_MessageValue* val) {
75 upb_value v;
76 const bool ok = _upb_Map_Delete(map, &key, map->key_size, &v);
77 if (val) val->uint64_val = v.val;
78 return ok;
79 }
80
upb_Map_Next(const upb_Map * map,upb_MessageValue * key,upb_MessageValue * val,size_t * iter)81 bool upb_Map_Next(const upb_Map* map, upb_MessageValue* key,
82 upb_MessageValue* val, size_t* iter) {
83 upb_StringView k;
84 upb_value v;
85 const bool ok = upb_strtable_next2(&map->table, &k, &v, (intptr_t*)iter);
86 if (ok) {
87 _upb_map_fromkey(k, key, map->key_size);
88 _upb_map_fromvalue(v, val, map->val_size);
89 }
90 return ok;
91 }
92
upb_MapIterator_Next(const upb_Map * map,size_t * iter)93 bool upb_MapIterator_Next(const upb_Map* map, size_t* iter) {
94 return _upb_map_next(map, iter);
95 }
96
upb_MapIterator_Done(const upb_Map * map,size_t iter)97 bool upb_MapIterator_Done(const upb_Map* map, size_t iter) {
98 upb_strtable_iter i;
99 UPB_ASSERT(iter != kUpb_Map_Begin);
100 i.t = &map->table;
101 i.index = iter;
102 return upb_strtable_done(&i);
103 }
104
105 // Returns the key and value for this entry of the map.
upb_MapIterator_Key(const upb_Map * map,size_t iter)106 upb_MessageValue upb_MapIterator_Key(const upb_Map* map, size_t iter) {
107 upb_strtable_iter i;
108 upb_MessageValue ret;
109 i.t = &map->table;
110 i.index = iter;
111 _upb_map_fromkey(upb_strtable_iter_key(&i), &ret, map->key_size);
112 return ret;
113 }
114
upb_MapIterator_Value(const upb_Map * map,size_t iter)115 upb_MessageValue upb_MapIterator_Value(const upb_Map* map, size_t iter) {
116 upb_strtable_iter i;
117 upb_MessageValue ret;
118 i.t = &map->table;
119 i.index = iter;
120 _upb_map_fromvalue(upb_strtable_iter_value(&i), &ret, map->val_size);
121 return ret;
122 }
123
124 // EVERYTHING BELOW THIS LINE IS INTERNAL - DO NOT USE /////////////////////////
125
_upb_Map_New(upb_Arena * a,size_t key_size,size_t value_size)126 upb_Map* _upb_Map_New(upb_Arena* a, size_t key_size, size_t value_size) {
127 upb_Map* map = upb_Arena_Malloc(a, sizeof(upb_Map));
128 if (!map) return NULL;
129
130 upb_strtable_init(&map->table, 4, a);
131 map->key_size = key_size;
132 map->val_size = value_size;
133
134 return map;
135 }
136