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