/* * Copyright (c) 2009-2021, Google LLC * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Google LLC nor the * names of its contributors may be used to endorse or promote products * derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* * upb_table Implementation * * Implementation is heavily inspired by Lua's ltable.c. */ #include "upb/internal/table.h" #include <string.h> /* Must be last. */ #include "upb/port_def.inc" #define UPB_MAXARRSIZE … /* From Chromium. */ #define ARRAY_SIZE(x) … static const double MAX_LOAD = …; /* The minimum utilization of the array part of a mixed hash/array table. This * is a speed/memory-usage tradeoff (though it's not straightforward because of * cache effects). The lower this is, the more memory we'll use. */ static const double MIN_DENSITY = …; static bool is_pow2(uint64_t v) { … } static upb_value _upb_value_val(uint64_t val) { … } static int log2ceil(uint64_t v) { … } char* upb_strdup2(const char* s, size_t len, upb_Arena* a) { … } /* A type to represent the lookup key of either a strtable or an inttable. */ lookupkey_t; static lookupkey_t strkey2(const char* str, size_t len) { … } static lookupkey_t intkey(uintptr_t key) { … } hashfunc_t; eqlfunc_t; /* Base table (shared code) ***************************************************/ static uint32_t upb_inthash(uintptr_t key) { … } static const upb_tabent* upb_getentry(const upb_table* t, uint32_t hash) { … } static bool upb_arrhas(upb_tabval key) { … } static bool isfull(upb_table* t) { … } static bool init(upb_table* t, uint8_t size_lg2, upb_Arena* a) { … } static upb_tabent* emptyent(upb_table* t, upb_tabent* e) { … } static upb_tabent* getentry_mutable(upb_table* t, uint32_t hash) { … } static const upb_tabent* findentry(const upb_table* t, lookupkey_t key, uint32_t hash, eqlfunc_t* eql) { … } static upb_tabent* findentry_mutable(upb_table* t, lookupkey_t key, uint32_t hash, eqlfunc_t* eql) { … } static bool lookup(const upb_table* t, lookupkey_t key, upb_value* v, uint32_t hash, eqlfunc_t* eql) { … } /* The given key must not already exist in the table. */ static void insert(upb_table* t, lookupkey_t key, upb_tabkey tabkey, upb_value val, uint32_t hash, hashfunc_t* hashfunc, eqlfunc_t* eql) { … } static bool rm(upb_table* t, lookupkey_t key, upb_value* val, upb_tabkey* removed, uint32_t hash, eqlfunc_t* eql) { … } static size_t next(const upb_table* t, size_t i) { … } static size_t begin(const upb_table* t) { … } /* upb_strtable ***************************************************************/ /* A simple "subclass" of upb_table that only adds a hash function for strings. */ static upb_tabkey strcopy(lookupkey_t k2, upb_Arena* a) { … } /* Adapted from ABSL's wyhash. */ static uint64_t UnalignedLoad64(const void* p) { … } static uint32_t UnalignedLoad32(const void* p) { … } #if defined(_MSC_VER) && defined(_M_X64) #include <intrin.h> #endif /* Computes a * b, returning the low 64 bits of the result and storing the high * 64 bits in |*high|. */ static uint64_t upb_umul128(uint64_t v0, uint64_t v1, uint64_t* out_high) { … } static uint64_t WyhashMix(uint64_t v0, uint64_t v1) { … } static uint64_t Wyhash(const void* data, size_t len, uint64_t seed, const uint64_t salt[]) { … } const uint64_t kWyhashSalt[5] = …; uint32_t _upb_Hash(const void* p, size_t n, uint64_t seed) { … } static uint32_t _upb_Hash_NoSeed(const char* p, size_t n) { … } static uint32_t strhash(upb_tabkey key) { … } static bool streql(upb_tabkey k1, lookupkey_t k2) { … } bool upb_strtable_init(upb_strtable* t, size_t expected_size, upb_Arena* a) { … } void upb_strtable_clear(upb_strtable* t) { … } bool upb_strtable_resize(upb_strtable* t, size_t size_lg2, upb_Arena* a) { … } bool upb_strtable_insert(upb_strtable* t, const char* k, size_t len, upb_value v, upb_Arena* a) { … } bool upb_strtable_lookup2(const upb_strtable* t, const char* key, size_t len, upb_value* v) { … } bool upb_strtable_remove2(upb_strtable* t, const char* key, size_t len, upb_value* val) { … } /* Iteration */ void upb_strtable_begin(upb_strtable_iter* i, const upb_strtable* t) { … } void upb_strtable_next(upb_strtable_iter* i) { … } bool upb_strtable_done(const upb_strtable_iter* i) { … } upb_StringView upb_strtable_iter_key(const upb_strtable_iter* i) { … } upb_value upb_strtable_iter_value(const upb_strtable_iter* i) { … } void upb_strtable_iter_setdone(upb_strtable_iter* i) { … } bool upb_strtable_iter_isequal(const upb_strtable_iter* i1, const upb_strtable_iter* i2) { … } /* upb_inttable ***************************************************************/ /* For inttables we use a hybrid structure where small keys are kept in an * array and large keys are put in the hash table. */ static uint32_t inthash(upb_tabkey key) { … } static bool inteql(upb_tabkey k1, lookupkey_t k2) { … } static upb_tabval* mutable_array(upb_inttable* t) { … } static upb_tabval* inttable_val(upb_inttable* t, uintptr_t key) { … } static const upb_tabval* inttable_val_const(const upb_inttable* t, uintptr_t key) { … } size_t upb_inttable_count(const upb_inttable* t) { … } static void check(upb_inttable* t) { … } bool upb_inttable_sizedinit(upb_inttable* t, size_t asize, int hsize_lg2, upb_Arena* a) { … } bool upb_inttable_init(upb_inttable* t, upb_Arena* a) { … } bool upb_inttable_insert(upb_inttable* t, uintptr_t key, upb_value val, upb_Arena* a) { … } bool upb_inttable_lookup(const upb_inttable* t, uintptr_t key, upb_value* v) { … } bool upb_inttable_replace(upb_inttable* t, uintptr_t key, upb_value val) { … } bool upb_inttable_remove(upb_inttable* t, uintptr_t key, upb_value* val) { … } void upb_inttable_compact(upb_inttable* t, upb_Arena* a) { … } /* Iteration. */ static const upb_tabent* int_tabent(const upb_inttable_iter* i) { … } static upb_tabval int_arrent(const upb_inttable_iter* i) { … } void upb_inttable_begin(upb_inttable_iter* i, const upb_inttable* t) { … } void upb_inttable_next(upb_inttable_iter* iter) { … } bool upb_inttable_next2(const upb_inttable* t, uintptr_t* key, upb_value* val, intptr_t* iter) { … } void upb_inttable_removeiter(upb_inttable* t, intptr_t* iter) { … } bool upb_strtable_next2(const upb_strtable* t, upb_StringView* key, upb_value* val, intptr_t* iter) { … } void upb_strtable_removeiter(upb_strtable* t, intptr_t* iter) { … } bool upb_inttable_done(const upb_inttable_iter* i) { … } uintptr_t upb_inttable_iter_key(const upb_inttable_iter* i) { … } upb_value upb_inttable_iter_value(const upb_inttable_iter* i) { … } void upb_inttable_iter_setdone(upb_inttable_iter* i) { … } bool upb_inttable_iter_isequal(const upb_inttable_iter* i1, const upb_inttable_iter* i2) { … }
Codebase Browser
chromium