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_HASH_STR_TABLE_H_
9 #define UPB_HASH_STR_TABLE_H_
10
11 #include "upb/hash/common.h"
12
13 // Must be last.
14 #include "upb/port/def.inc"
15
16 typedef struct {
17 upb_table t;
18 } upb_strtable;
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24 // Initialize a table. If memory allocation failed, false is returned and
25 // the table is uninitialized.
26 bool upb_strtable_init(upb_strtable* table, size_t expected_size, upb_Arena* a);
27
28 // Returns the number of values in the table.
upb_strtable_count(const upb_strtable * t)29 UPB_INLINE size_t upb_strtable_count(const upb_strtable* t) {
30 return t->t.count;
31 }
32
33 void upb_strtable_clear(upb_strtable* t);
34
35 // Inserts the given key into the hashtable with the given value.
36 // The key must not already exist in the hash table. The key is not required
37 // to be NULL-terminated, and the table will make an internal copy of the key.
38 //
39 // If a table resize was required but memory allocation failed, false is
40 // returned and the table is unchanged. */
41 bool upb_strtable_insert(upb_strtable* t, const char* key, size_t len,
42 upb_value val, upb_Arena* a);
43
44 // Looks up key in this table, returning "true" if the key was found.
45 // If v is non-NULL, copies the value for this key into *v.
46 bool upb_strtable_lookup2(const upb_strtable* t, const char* key, size_t len,
47 upb_value* v);
48
49 // For NULL-terminated strings.
upb_strtable_lookup(const upb_strtable * t,const char * key,upb_value * v)50 UPB_INLINE bool upb_strtable_lookup(const upb_strtable* t, const char* key,
51 upb_value* v) {
52 return upb_strtable_lookup2(t, key, strlen(key), v);
53 }
54
55 // Removes an item from the table. Returns true if the remove was successful,
56 // and stores the removed item in *val if non-NULL.
57 bool upb_strtable_remove2(upb_strtable* t, const char* key, size_t len,
58 upb_value* val);
59
upb_strtable_remove(upb_strtable * t,const char * key,upb_value * v)60 UPB_INLINE bool upb_strtable_remove(upb_strtable* t, const char* key,
61 upb_value* v) {
62 return upb_strtable_remove2(t, key, strlen(key), v);
63 }
64
65 // Exposed for testing only.
66 bool upb_strtable_resize(upb_strtable* t, size_t size_lg2, upb_Arena* a);
67
68 /* Iteration over strtable:
69 *
70 * intptr_t iter = UPB_STRTABLE_BEGIN;
71 * upb_StringView key;
72 * upb_value val;
73 * while (upb_strtable_next2(t, &key, &val, &iter)) {
74 * // ...
75 * }
76 */
77
78 #define UPB_STRTABLE_BEGIN -1
79
80 bool upb_strtable_next2(const upb_strtable* t, upb_StringView* key,
81 upb_value* val, intptr_t* iter);
82 void upb_strtable_removeiter(upb_strtable* t, intptr_t* iter);
83 void upb_strtable_setentryvalue(upb_strtable* t, intptr_t iter, upb_value v);
84
85 /* DEPRECATED iterators, slated for removal.
86 *
87 * Iterators for string tables. We are subject to some kind of unusual
88 * design constraints:
89 *
90 * For high-level languages:
91 * - we must be able to guarantee that we don't crash or corrupt memory even if
92 * the program accesses an invalidated iterator.
93 *
94 * For C++11 range-based for:
95 * - iterators must be copyable
96 * - iterators must be comparable
97 * - it must be possible to construct an "end" value.
98 *
99 * Iteration order is undefined.
100 *
101 * Modifying the table invalidates iterators. upb_{str,int}table_done() is
102 * guaranteed to work even on an invalidated iterator, as long as the table it
103 * is iterating over has not been freed. Calling next() or accessing data from
104 * an invalidated iterator yields unspecified elements from the table, but it is
105 * guaranteed not to crash and to return real table elements (except when done()
106 * is true). */
107 /* upb_strtable_iter **********************************************************/
108
109 /* upb_strtable_iter i;
110 * upb_strtable_begin(&i, t);
111 * for(; !upb_strtable_done(&i); upb_strtable_next(&i)) {
112 * const char *key = upb_strtable_iter_key(&i);
113 * const upb_value val = upb_strtable_iter_value(&i);
114 * // ...
115 * }
116 */
117
118 typedef struct {
119 const upb_strtable* t;
120 size_t index;
121 } upb_strtable_iter;
122
str_tabent(const upb_strtable_iter * i)123 UPB_INLINE const upb_tabent* str_tabent(const upb_strtable_iter* i) {
124 return &i->t->t.entries[i->index];
125 }
126
127 void upb_strtable_begin(upb_strtable_iter* i, const upb_strtable* t);
128 void upb_strtable_next(upb_strtable_iter* i);
129 bool upb_strtable_done(const upb_strtable_iter* i);
130 upb_StringView upb_strtable_iter_key(const upb_strtable_iter* i);
131 upb_value upb_strtable_iter_value(const upb_strtable_iter* i);
132 void upb_strtable_iter_setdone(upb_strtable_iter* i);
133 bool upb_strtable_iter_isequal(const upb_strtable_iter* i1,
134 const upb_strtable_iter* i2);
135
136 #ifdef __cplusplus
137 } /* extern "C" */
138 #endif
139
140 #include "upb/port/undef.inc"
141
142 #endif /* UPB_HASH_STR_TABLE_H_ */
143