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_INT_TABLE_H_ 29 #define UPB_HASH_INT_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; // For entries that don't fit in the array part. 38 const upb_tabval* array; // Array part of the table. See const note above. 39 size_t array_size; // Array part size. 40 size_t array_count; // Array part number of elements. 41 } upb_inttable; 42 43 #ifdef __cplusplus 44 extern "C" { 45 #endif 46 47 // Initialize a table. If memory allocation failed, false is returned and 48 // the table is uninitialized. 49 bool upb_inttable_init(upb_inttable* table, upb_Arena* a); 50 51 // Returns the number of values in the table. 52 size_t upb_inttable_count(const upb_inttable* t); 53 54 // Inserts the given key into the hashtable with the given value. 55 // The key must not already exist in the hash table. 56 // The value must not be UINTPTR_MAX. 57 // 58 // If a table resize was required but memory allocation failed, false is 59 // returned and the table is unchanged. 60 bool upb_inttable_insert(upb_inttable* t, uintptr_t key, upb_value val, 61 upb_Arena* a); 62 63 // Looks up key in this table, returning "true" if the key was found. 64 // If v is non-NULL, copies the value for this key into *v. 65 bool upb_inttable_lookup(const upb_inttable* t, uintptr_t key, upb_value* v); 66 67 // Removes an item from the table. Returns true if the remove was successful, 68 // and stores the removed item in *val if non-NULL. 69 bool upb_inttable_remove(upb_inttable* t, uintptr_t key, upb_value* val); 70 71 // Updates an existing entry in an inttable. 72 // If the entry does not exist, returns false and does nothing. 73 // Unlike insert/remove, this does not invalidate iterators. 74 bool upb_inttable_replace(upb_inttable* t, uintptr_t key, upb_value val); 75 76 // Optimizes the table for the current set of entries, for both memory use and 77 // lookup time. Client should call this after all entries have been inserted; 78 // inserting more entries is legal, but will likely require a table resize. 79 void upb_inttable_compact(upb_inttable* t, upb_Arena* a); 80 81 // Iteration over inttable: 82 // 83 // intptr_t iter = UPB_INTTABLE_BEGIN; 84 // uintptr_t key; 85 // upb_value val; 86 // while (upb_inttable_next(t, &key, &val, &iter)) { 87 // // ... 88 // } 89 90 #define UPB_INTTABLE_BEGIN -1 91 92 bool upb_inttable_next(const upb_inttable* t, uintptr_t* key, upb_value* val, 93 intptr_t* iter); 94 void upb_inttable_removeiter(upb_inttable* t, intptr_t* iter); 95 96 #ifdef __cplusplus 97 } /* extern "C" */ 98 #endif 99 100 #include "upb/port/undef.inc" 101 102 #endif /* UPB_HASH_INT_TABLE_H_ */ 103