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 <stddef.h>
0012 #include <stdint.h>
0013
0014 #include "upb/hash/common.h"
0015 #include "upb/mem/arena.h"
0016
0017 // Must be last.
0018 #include "upb/port/def.inc"
0019
0020 typedef struct {
0021   upb_table t;  // For entries that don't fit in the array part.
0022   // Array part of the table.
0023   // Pointers on this table are const so we can create static initializers for
0024   // tables.  We cast away const sometimes, but *only* when the containing
0025   // upb_table is known to be non-const.  This requires a bit of care, but
0026   // the subtlety is confined to table.c.
0027   const upb_value* array;
0028   // Track presence in the array part. Each bit at index (key % 8) at the
0029   // presence_mask[key/8] indicates if the element is present in the array part.
0030   const uint8_t* presence_mask;
0031   uint32_t array_size;   // Array part size.
0032   uint32_t array_count;  // Array part number of elements.
0033 } upb_inttable;
0034
0035 #ifdef __cplusplus
0036 extern "C" {
0037 #endif
0038
0039 // Initialize a table. If memory allocation failed, false is returned and
0040 // the table is uninitialized.
0041 bool upb_inttable_init(upb_inttable* table, upb_Arena* a);
0042
0043 // Returns the number of values in the table.
0044 size_t upb_inttable_count(const upb_inttable* t);
0045
0046 // Inserts the given key into the hashtable with the given value.
0047 // The key must not already exist in the hash table.
0048 // The value must not be UINTPTR_MAX.
0049 //
0050 // If a table resize was required but memory allocation failed, false is
0051 // returned and the table is unchanged.
0052 bool upb_inttable_insert(upb_inttable* t, uintptr_t key, upb_value val,
0053                          upb_Arena* a);
0054
0055 // Looks up key in this table, returning "true" if the key was found.
0056 // If v is non-NULL, copies the value for this key into *v.
0057 bool upb_inttable_lookup(const upb_inttable* t, uintptr_t key, upb_value* v);
0058
0059 // Removes an item from the table. Returns true if the remove was successful,
0060 // and stores the removed item in *val if non-NULL.
0061 bool upb_inttable_remove(upb_inttable* t, uintptr_t key, upb_value* val);
0062
0063 // Updates an existing entry in an inttable.
0064 // If the entry does not exist, returns false and does nothing.
0065 // Unlike insert/remove, this does not invalidate iterators.
0066 bool upb_inttable_replace(upb_inttable* t, uintptr_t key, upb_value val);
0067
0068 // Optimizes the table for the current set of entries, for both memory use and
0069 // lookup time. Client should call this after all entries have been inserted;
0070 // inserting more entries is legal, but will likely require a table resize.
0071 // Returns false if reallocation fails.
0072 bool upb_inttable_compact(upb_inttable* t, upb_Arena* a);
0073
0074 // Clears the table.
0075 void upb_inttable_clear(upb_inttable* t);
0076
0077 // Iteration over inttable:
0078 //
0079 //   intptr_t iter = UPB_INTTABLE_BEGIN;
0080 //   uintptr_t key;
0081 //   upb_value val;
0082 //   while (upb_inttable_next(t, &key, &val, &iter)) {
0083 //      // ...
0084 //   }
0085
0086 #define UPB_INTTABLE_BEGIN -1
0087
0088 bool upb_inttable_next(const upb_inttable* t, uintptr_t* key, upb_value* val,
0089                        intptr_t* iter);
0090 void upb_inttable_removeiter(upb_inttable* t, intptr_t* iter);
0091 void upb_inttable_setentryvalue(upb_inttable* t, intptr_t iter, upb_value v);
0092 bool upb_inttable_done(const upb_inttable* t, intptr_t i);
0093 uintptr_t upb_inttable_iter_key(const upb_inttable* t, intptr_t iter);
0094 upb_value upb_inttable_iter_value(const upb_inttable* t, intptr_t iter);
0095
0096 UPB_INLINE bool upb_inttable_arrhas(const upb_inttable* t, uintptr_t key) {
0097   return (t->presence_mask[key / 8] & (1 << (key % 8))) != 0;
0098 }
0099
0100 #ifdef __cplusplus
0101 } /* extern "C" */
0102 #endif
0103
0104 #include "upb/port/undef.inc"
0105
0106 #endif /* UPB_HASH_INT_TABLE_H_ */