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