upb/hash/int_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_INT_TABLE_H_
0009 #define UPB_HASH_INT_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;              // For entries that don't fit in the array part.
0018   const upb_tabval* array;  // Array part of the table. See const note above.
0019   size_t array_size;        // Array part size.
0020   size_t array_count;       // Array part number of elements.
0021 } upb_inttable;
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 // Initialize a table. If memory allocation failed, false is returned and
0028 // the table is uninitialized.
0029 bool upb_inttable_init(upb_inttable* table, upb_Arena* a);
0030
0031 // Returns the number of values in the table.
0032 size_t upb_inttable_count(const upb_inttable* t);
0033
0034 // Inserts the given key into the hashtable with the given value.
0035 // The key must not already exist in the hash table.
0036 // The value must not be UINTPTR_MAX.
0037 //
0038 // If a table resize was required but memory allocation failed, false is
0039 // returned and the table is unchanged.
0040 bool upb_inttable_insert(upb_inttable* t, uintptr_t key, upb_value val,
0041                          upb_Arena* a);
0042
0043 // Looks up key in this table, returning "true" if the key was found.
0044 // If v is non-NULL, copies the value for this key into *v.
0045 bool upb_inttable_lookup(const upb_inttable* t, uintptr_t key, upb_value* v);
0046
0047 // Removes an item from the table. Returns true if the remove was successful,
0048 // and stores the removed item in *val if non-NULL.
0049 bool upb_inttable_remove(upb_inttable* t, uintptr_t key, upb_value* val);
0050
0051 // Updates an existing entry in an inttable.
0052 // If the entry does not exist, returns false and does nothing.
0053 // Unlike insert/remove, this does not invalidate iterators.
0054 bool upb_inttable_replace(upb_inttable* t, uintptr_t key, upb_value val);
0055
0056 // Optimizes the table for the current set of entries, for both memory use and
0057 // lookup time. Client should call this after all entries have been inserted;
0058 // inserting more entries is legal, but will likely require a table resize.
0059 void upb_inttable_compact(upb_inttable* t, upb_Arena* a);
0060
0061 // Iteration over inttable:
0062 //
0063 //   intptr_t iter = UPB_INTTABLE_BEGIN;
0064 //   uintptr_t key;
0065 //   upb_value val;
0066 //   while (upb_inttable_next(t, &key, &val, &iter)) {
0067 //      // ...
0068 //   }
0069
0070 #define UPB_INTTABLE_BEGIN -1
0071
0072 bool upb_inttable_next(const upb_inttable* t, uintptr_t* key, upb_value* val,
0073                        intptr_t* iter);
0074 void upb_inttable_removeiter(upb_inttable* t, intptr_t* iter);
0075
0076 #ifdef __cplusplus
0077 } /* extern "C" */
0078 #endif
0079
0080 #include "upb/port/undef.inc"
0081
0082 #endif /* UPB_HASH_INT_TABLE_H_ */