upb/hash/str_table.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_HASH_STR_TABLE_H_
0009 #define UPB_HASH_STR_TABLE_H_
0010
0011 #include <stddef.h>
0012 #include <stdint.h>
0013 #include <string.h>
0014
0015 #include "upb/base/string_view.h"
0016 #include "upb/hash/common.h"
0017 #include "upb/mem/arena.h"
0018
0019 // Must be last.
0020 #include "upb/port/def.inc"
0021
0022 typedef struct {
0023   upb_table t;
0024 } upb_strtable;
0025
0026 #ifdef __cplusplus
0027 extern "C" {
0028 #endif
0029
0030 // Initialize a table. If memory allocation failed, false is returned and
0031 // the table is uninitialized.
0032 bool upb_strtable_init(upb_strtable* table, size_t expected_size, upb_Arena* a);
0033
0034 // Returns the number of values in the table.
0035 UPB_INLINE size_t upb_strtable_count(const upb_strtable* t) {
0036   return t->t.count;
0037 }
0038
0039 void upb_strtable_clear(upb_strtable* t);
0040
0041 // Inserts the given key into the hashtable with the given value.
0042 // The key must not already exist in the hash table. The key is not required
0043 // to be NULL-terminated, and the table will make an internal copy of the key.
0044 //
0045 // If a table resize was required but memory allocation failed, false is
0046 // returned and the table is unchanged. */
0047 bool upb_strtable_insert(upb_strtable* t, const char* key, size_t len,
0048                          upb_value val, upb_Arena* a);
0049
0050 // Looks up key in this table, returning "true" if the key was found.
0051 // If v is non-NULL, copies the value for this key into *v.
0052 bool upb_strtable_lookup2(const upb_strtable* t, const char* key, size_t len,
0053                           upb_value* v);
0054
0055 // For NULL-terminated strings.
0056 UPB_INLINE bool upb_strtable_lookup(const upb_strtable* t, const char* key,
0057                                     upb_value* v) {
0058   return upb_strtable_lookup2(t, key, strlen(key), v);
0059 }
0060
0061 // Removes an item from the table. Returns true if the remove was successful,
0062 // and stores the removed item in *val if non-NULL.
0063 bool upb_strtable_remove2(upb_strtable* t, const char* key, size_t len,
0064                           upb_value* val);
0065
0066 UPB_INLINE bool upb_strtable_remove(upb_strtable* t, const char* key,
0067                                     upb_value* v) {
0068   return upb_strtable_remove2(t, key, strlen(key), v);
0069 }
0070
0071 // Exposed for testing only.
0072 bool upb_strtable_resize(upb_strtable* t, size_t size_lg2, upb_Arena* a);
0073
0074 /* Iteration over strtable:
0075  *
0076  *   intptr_t iter = UPB_STRTABLE_BEGIN;
0077  *   upb_StringView key;
0078  *   upb_value val;
0079  *   while (upb_strtable_next2(t, &key, &val, &iter)) {
0080  *      // ...
0081  *   }
0082  */
0083
0084 #define UPB_STRTABLE_BEGIN -1
0085
0086 bool upb_strtable_next2(const upb_strtable* t, upb_StringView* key,
0087                         upb_value* val, intptr_t* iter);
0088 void upb_strtable_removeiter(upb_strtable* t, intptr_t* iter);
0089 void upb_strtable_setentryvalue(upb_strtable* t, intptr_t iter, upb_value v);
0090
0091 /* DEPRECATED iterators, slated for removal.
0092  *
0093  * Iterators for string tables.  We are subject to some kind of unusual
0094  * design constraints:
0095  *
0096  * For high-level languages:
0097  *  - we must be able to guarantee that we don't crash or corrupt memory even if
0098  *    the program accesses an invalidated iterator.
0099  *
0100  * For C++11 range-based for:
0101  *  - iterators must be copyable
0102  *  - iterators must be comparable
0103  *  - it must be possible to construct an "end" value.
0104  *
0105  * Iteration order is undefined.
0106  *
0107  * Modifying the table invalidates iterators.  upb_{str,int}table_done() is
0108  * guaranteed to work even on an invalidated iterator, as long as the table it
0109  * is iterating over has not been freed.  Calling next() or accessing data from
0110  * an invalidated iterator yields unspecified elements from the table, but it is
0111  * guaranteed not to crash and to return real table elements (except when done()
0112  * is true). */
0113 /* upb_strtable_iter **********************************************************/
0114
0115 /*   upb_strtable_iter i;
0116  *   upb_strtable_begin(&i, t);
0117  *   for(; !upb_strtable_done(&i); upb_strtable_next(&i)) {
0118  *     const char *key = upb_strtable_iter_key(&i);
0119  *     const upb_value val = upb_strtable_iter_value(&i);
0120  *     // ...
0121  *   }
0122  */
0123
0124 typedef struct {
0125   const upb_strtable* t;
0126   size_t index;
0127 } upb_strtable_iter;
0128
0129 UPB_INLINE const upb_tabent* str_tabent(const upb_strtable_iter* i) {
0130   return &i->t->t.entries[i->index];
0131 }
0132
0133 void upb_strtable_begin(upb_strtable_iter* i, const upb_strtable* t);
0134 void upb_strtable_next(upb_strtable_iter* i);
0135 bool upb_strtable_done(const upb_strtable_iter* i);
0136 upb_StringView upb_strtable_iter_key(const upb_strtable_iter* i);
0137 upb_value upb_strtable_iter_value(const upb_strtable_iter* i);
0138 void upb_strtable_iter_setdone(upb_strtable_iter* i);
0139 bool upb_strtable_iter_isequal(const upb_strtable_iter* i1,
0140                                const upb_strtable_iter* i2);
0141
0142 #ifdef __cplusplus
0143 } /* extern "C" */
0144 #endif
0145
0146 #include "upb/port/undef.inc"
0147
0148 #endif /* UPB_HASH_STR_TABLE_H_ */