/* Symbol Table data structure -- functions * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published * by the Free Software Foundation; either version 2, or (at your * option) any later version. * * GNU Zebra is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ #include "misc.h" #include #include "symtab.h" #include "memory.h" /*============================================================================== * A symbol table maps symbol "names" to symbol "bodies" and, for each symbol, * has two ways of keeping track of references to the symbol. * * A symbol's "name" can be an arbitrary collection of bytes, or a string. All * names in a symbol table are unique. * * The symbol body is a void* -- whose contents are no concern of this code, * *except* that the "body" must point to or contain the name -- so that the * table function symbol_cmp_func can test whether a symbol has the given name. * * Once a name has been mapped to a symbol, the symbol can be referred to using * its address or via a symbol reference -- see below. * * A symbol table can be walked to visit all symbols, and there is support for * extracting a vector of all symbols which satisfy a given criterion, and * sorting same. * * A symbol table comprises: * * * symbol table structure -- containing all "red-tape" * * array of chain-bases -- for the hash table * * symbol entries -- each containing the value of a symbol * * The symbol table structure may only be dynamically allocated. * * A symbol table may point to its "parent". The symbol table code does not * use or need this -- it is for the convenience of the caller. * * The "name" of a symbol may be anything at all. As far as the symbol table * is concerned the name is defined by the symbol_hash_func and * symbol_cmp_func -- see symbol_table_new(). * * The array of chain-bases is dynamically allocated and will grow to maintain * an approximate given maximum number of symbols per chain base. This density * is set when the symbol table is initialised. The array does not * automatically reduce in size. * * The number of chain bases is always odd. The hash function returns an * unsigned value, which is mapped to the chain bases modulo their number. * Since that is odd, it is co-prime with the hash, so contributes to the hash * process. * * Each symbol in the table has a dynamically allocated entry, which includes: * * * symbol body -- void* (which includes the "name" in some way) * * reference count -- includes number of of reference objects * * list of reference objects * * While in the symbol table a symbol may *not* have a NULL body, because * the symbol table requires access to the name when searching the table. * The body may change, and a new body may be set. The only thing that * remains constant is that the symbol_cmp_func() works no matter what form * the body takes. * * When a symbol is created -- symbol_lookup(..., add) -- the body must be set * *immediately* and *before* any other symbol table operations on the table. * The reference count is zero. * * Wherever a pointer to the symbol is kept, either the reference count must * be incremented or a reference object set up (or the owner of the pointer * must have their own mechanism to know when the pointer is valid !). * * It is generally assumed that the body will only be accessed via the symbol. * Assuming that, the body may move around, provided symbol_set() is called * to keep the symbol up to date. * * Simple use of * * * When the count is reduced to zero the symbol is removed from the symbol * table, and the body will be destroyed -- symbol_free_func(). * * If there is an "owner" of the body of a symbol, when its value is emptied or * unset, the owner may call symbol_unset(). This is essentially the same as * symbol_dec_ref() -- balancing the implicit symbol_inc_ref() in the original * symbol_set(). Apart from the obvious symmetry, the unset function also * allows the caller to replace the body by one which is (say) empty *apart* * from the name. Note that it is up to the caller to ensure that different * forms of body can be distinguished by any code that accesses it via the * symbol. * * Note that the symbol table and symbols provide a number of facilities: * * (1) access by symbol name to the symbol body. * * The symbol table can be used this way without using any of the * reference facilities. * * When the symbol is added and the body set, the symbol comes into * existence. When the body has a value, then symbol_set() will * set the "symbol_set" state -- though this is optional. * * The symbol can then be looked up, and its body accessed, via one level * of indirection. * * When the symbol is unset -- symbol_unset() -- it will wink out of * existence and the body will be freed. * * NB: the one level of indirection means that the body can be moved * around between lookups. * * (2) access to the symbol body via saved pointer to the symbol. * * Having looked up a symbol, the user may hold on to a pointer to it, * so that subsequent access to the symbol body does not require a * lookup. * * The simple reference counting supports this use. * * It is the reference owner's responsibility to symbol_inc_ref() and * symbol_dec_ref() as required. * * Note that if "symbol_set" is not set, then a symbol and body can * come into existence simply to support named references to an empty * object, and will automatically disappear again if all references * are unset. * * If or when some real value is attached to the symbol, symbol_set() * sets the "symbol_set" state so that the symbol and the body are * preserved even if there are no references. If the value is later * dispantled, then symbol_unset() clears the "symbol_set" state, and * the symbol and body will disappear either immediately or when the * references drop to zero. * * Before doing symbol_unset(), the owner of the symbol might choose to * replace the symbol body by an "empty" one -- containing only the * name -- symbol_has_references() indicates whether that is required. * * This supports the notion of a named object, which exists, even if its * value is NULL, while there are references to it. Moreover, when the * value of the object changes, all "by name" references are implicitly * references to the latest value. * * (3) notification references * * Instead of saving a pointer to the symbol, it is possible to construct * a "notification reference" (symbol_nref). This itself contains a * pointer to the symbol, and so setting/unsetting an nref implicitly * increments/decrements the symbol reference count. In addition, the * "nref" is chained on to the symbol, so that all such references can be * walked when the owner of each reference needs to be informed about * some change to the symbol or its body. * * The nref belongs to the owner of the reference. So an nref may be * associated with different symbols at different times. * * It is the nref owner's responsibility to symbol_nref_set() and * symbol_nref_unset() as required. * * It is possible that these facilities should be unbundled. TBA ! TODO * * Finally, a symbol may be deleted -- symbol_delete(). This is brutal, and * should be used only if the holders of pointers to the symbol and/or nrefs * are aware that the symbol will have no body and no longer be associated * with a symbol table once it has been deleted. The symbol will persist * until its reference count drops to zero at which point it will wink out * of existence. */ /*============================================================================== * Symbol table operations */ static void symbol_table_new_bases(symbol_table table, uint new_base_count) ; static void symbol_table_extend_bases(symbol_table table) ; inline static uint symbol_base_index(symbol_table table, symbol_hash_t hash) ; /*------------------------------------------------------------------------------ * Allocate and initialise a new symbol table. * * Requires: * * parent -- address of some parent or other higher level data structure. * * This is not used by the symbol table code and may be NULL if * the caller has no use for it. * * bases -- number of list bases to start the symbol table at. * * Symbol table grows as required, but can set initial size if * have some expectations and wish to avoid growth steps. * * A minimum of SYMBOL_TABLE_BASES_MIN will be allocated. * * density -- %-age of entries/bases. 0 => use default. * 150 => 1.50 entries/base (for example) * * funcs -- address of struct symbol_funcs, filled in: * * hash -- symbol_hash_func* * * function to calculate symbol_hash_t from a given "name". * see, for example: symbol_hash_string(), below. * * cmp -- symbol_cmp_func* * * function to compare name of a given value with a given name. * * free -- symbol_free_func* * * function to be called when the number of references to a * symbol reduce to zero and the value is unset (or deleted). * * Returns: address of new symbol table */ extern symbol_table symbol_table_new(void* parent, uint base_count, uint density, symbol_funcs_c funcs) { symbol_table table ; assert(base_count <= SYMBOL_TABLE_BASES_MAX) ; table = XCALLOC(MTYPE_SYMBOL_TABLE, sizeof (struct symbol_table)) ; /* The XCALLOC sets: * * parent -- NULL -- set below * * bases -- NULL -- set below, by symbol_table_new_bases() * base_count -- 0 -- set below, ditto * * entry_count -- 0 -- table is empty ! * max_index -- 0 -- table is empty ! * extend_thresh -- 0 -- set below, by symbol_table_new_bases() * * density -- 0 -- set below * * func -- NULLs -- set below */ table->parent = parent ; if (density == 0) density = SYMBOL_TABLE_DEFAULT_DENSITY ; table->density = (float)density / 100.0 ; symbol_table_new_bases(table, base_count) ; table->func = *funcs ; /* Makes a *copy* */ return table ; } ; /*------------------------------------------------------------------------------ * Set "parent" of symbol table. */ extern void symbol_table_set_parent(symbol_table table, void* parent) { table->parent = parent ; } ; /*------------------------------------------------------------------------------ * Get "parent" of symbol table. */ extern void* symbol_table_get_parent(symbol_table table) { return table->parent ; } ; /*------------------------------------------------------------------------------ * Ream out given Symbol Table -- if any. * * This is a symbol_delete() for all symbols. Has the option to free or keep * each symbol's body. * * Returns the value of the next non-NULL symbol (if any). So may be used, for * example: * * symbol sym ; * ... * sym = NULL ; * while ((sym = symbol_table_ream(table, sym, free_it)) != NULL) * { * body = symbol_get_body(sym) ; * ... do what ever is required. May even unset or delete the * symbol, *provided* keep sym up to date -- because on next call * of symbol_table_ream(), will delete the symbol. * * ... note that need do nothing here, the symbol_table_ream() deletes * the symbol ! * } * * Note that deleting a symbol unsets any nrefs there are to it. * * Symbols which have one or more references when they are deleted are left as * orphans, which will be freed when all their references are unset. * * Returns NULL when the table is empty. * * Once the table is empty it may continue to be used, using the current * set of bases. To free the empty table: symbol_table_free(). To reset * the number of bases: symbol_table_reset(). * * NB: it is wise not to do anything else with the symbol table once reaming * has started and not to stop until this function returns NULL. However, * will cope if the given symbol or other symbols are deleted between * calls. Will even cope with symbols being added... but they will be * collected up and reamed out ! * * NB: it is the caller's responsibility to unset all references and release * any that need to be released -- either before or after this operation. * * Any symbols whose reference count does not drop to zero when the delete * is done remain -- but with NULL body (and NULL table) ! */ extern symbol symbol_table_ream(symbol_table table, symbol sym, free_keep_b free_body) { bool rescan ; uint index ; if (table == NULL) return NULL ; qassert((table->bases != NULL) && (table->base_count > 0)) ; /* Delete last symbol, if any. * * If not already deleted, must belong to the table in question ! */ if (sym != NULL) { qassert(table == sym->table) ; symbol_delete(sym, free_body) ; } ; /* Search for next entry. */ rescan = false ; index = table->max_index ; if (table->entry_count > 0) { while (1) { sym = table->bases[index] ; if (sym != NULL) { table->max_index = index ; return sym ; } ; if (index == 0) { /* This should not happen. * * If it does, either the table->entry_count is wrong, or the * table->max_index is. In case it is the later, will rescan * once, starting from the end. */ qassert(false) ; if (rescan) break ; rescan = true ; index = table->base_count ; } ; --index ; } ; } ; return NULL ; } ; /*------------------------------------------------------------------------------ * Free empty symbol table, if any. * * Reams the table first -- so any symbols with non-zero reference counts * (after any nref have been unset) will persist. Has the option to * free or keep each symbol's body. * * Zeroises the symbol table structure, to trap dangling references ASAP. * * Returns: NULL */ extern symbol_table symbol_table_free(symbol_table table, free_keep_b free_body) { if (table != NULL) { symbol sym ; sym = NULL ; while ((sym = symbol_table_ream(table, sym, free_body)) != NULL) ; XFREE(MTYPE_SYMBOL_BASES, table->bases) ; memset(table, 0, sizeof (struct symbol_table)) ; XFREE(MTYPE_SYMBOL_TABLE, table) ; /* table = NULL */ } ; return table ; } ; /*------------------------------------------------------------------------------ * Reset number of bases in given table, if any. * * This is for use when a table has grown and then shrunk, and it is felt to * be essential to recover space by reducing the number of chain bases. * * Sets the new number of bases to the number given, or such that the threshold * for the next reorganisation is about 1.25 * number of entries currently * have, whichever is the greater. */ extern void symbol_table_reset(symbol_table table, uint base_count) { uint new_base_count ; new_base_count = ((float)table->entry_count * (float)1.25) / table->density ; if (new_base_count < base_count) new_base_count = base_count ; symbol_table_new_bases(table, new_base_count) ; } ; /*------------------------------------------------------------------------------ * Extend the existing array of list bases. * * To be called when the number of entries exceeds the threshold. */ static void symbol_table_extend_bases(symbol_table table) { uint old_base_count ; uint new_base_count ; qassert((table->bases != NULL) && (table->base_count != 0)) ; /* Should be here because the number of entries in the table has exceeded * the threshold. * * Depending on how big the table is, we either double it or add a reasonable * chunk of bases. */ old_base_count = table->base_count ; new_base_count = (old_base_count | 1) - 1 ; /* trim enforced odd-ness */ if (new_base_count <= SYMBOL_TABLE_BASES_DOUBLE_MAX) new_base_count *= 2 ; else new_base_count += SYMBOL_TABLE_BASES_DOUBLE_MAX ; assert(new_base_count > old_base_count) ; /* check for overflow */ /* Do the hard work of rearranging the bases */ symbol_table_new_bases(table, new_base_count) ; } ; /*------------------------------------------------------------------------------ * Create and set new chain bases and threshold for next extension. * * Ensures that the base count used is at least the minimum and is odd. * * The minumum is the larger of the absolute SYMBOL_TABLE_BASES_MIN, or enough * for the number of entries to grow by 25% before the new threshold will be * exceeded. * * If there is an existing set of chain bases, transfers entries from old * to new chain bases, and frees the old bases. */ static void symbol_table_new_bases(symbol_table table, uint new_base_count) { uint new_minimum ; symbol* old_bases ; uint old_base_count ; uint old_entry_count ; /* Extract what we need to know about the old bases and create new ones. */ old_bases = table->bases ; old_base_count = table->base_count ; old_entry_count = table->entry_count ; new_minimum = ((float)table->entry_count * (float)1.25) / table->density ; if (new_minimum < SYMBOL_TABLE_BASES_MIN) new_minimum = SYMBOL_TABLE_BASES_MIN ; if (new_base_count < new_minimum) new_base_count = new_minimum ; new_base_count |= 1 ; /* ENSURE is odd */ table->bases = XCALLOC(MTYPE_SYMBOL_BASES, new_base_count * sizeof(symbol)) ; table->base_count = new_base_count ; table->extend_thresh = new_base_count * table->density ; table->max_index = 0 ; table->entry_count = 0 ; /* Finished if have just allocated the first set of bases. */ if (old_bases == NULL) { qassert((old_base_count == 0) && (old_entry_count == 0)) ; return ; } ; /* Rehome everything on the new chain bases. */ qassert(old_base_count != 0) ; while (old_base_count--) { symbol next ; next = old_bases[old_base_count] ; while (next != NULL) { symbol this ; uint index ; symbol* base ; this = next ; next = this->next ; index = symbol_base_index(table, this->hash) ; base = &table->bases[index] ; this->next = *base ; *base = this ; if (index > table->max_index) table->max_index = index ; ++table->entry_count ; } ; } ; qassert(table->entry_count == old_entry_count) ; /* Release the old chain bases, and we're done */ XFREE(MTYPE_SYMBOL_BASES, old_bases) ; } ; /*------------------------------------------------------------------------------ * Return chain base index for given hash value. */ inline static uint symbol_base_index(symbol_table table, symbol_hash_t hash) { return hash % table->base_count ; } ; /*============================================================================== * Symbol operations */ /*------------------------------------------------------------------------------ * Look-up name in given symbol table. Add if required. * * Returns NULL if not found and not required to add. * * If adds, the symbol returned will have a NULL body. That body MUST be * set BEFORE any further symbol table operations, and that body MUST have * the same "name" value as given here -- symbol_set_body(). * * If does not add, and symbol exists, the symbol returned will NOT have a NULL * body. * * NB: the name argument is passed to the symbol table's hash function. */ extern symbol symbol_lookup(symbol_table table, const void* name, add_b add) { struct symbol* this ; struct symbol** base ; uint index ; symbol_hash_t hash ; qassert((table != NULL) && (table->bases != NULL)) ; hash = table->func.hash(name) ; index = symbol_base_index(table, hash) ; base = &table->bases[index] ; this = *base ; while (this != NULL) { qassert((this->table == table) && (this->body != NULL)) ; if ((this->hash == hash) && (table->func.cmp(this->body, name) == 0)) return this ; this = this->next ; } ; /* Not found -- quit now if not required to add */ if (!add) return NULL ; /* Adding: first, carve a new, empty symbol entry * * XCALLOC sets: * * table = NULL -- set below * next = NULL * value = NULL * ref_list = NULL * ref_count = 0 * hash = 0 -- set below */ this = XCALLOC(MTYPE_SYMBOL, sizeof(struct symbol)) ; this->table = table ; this->hash = hash ; /* Second, if required, extend the array of list bases. We extend if * we have a collision *and* we exceed threshold of number of entries. * * Once extended, recalculate the index and select new base. */ if ((*base != NULL) && (table->entry_count > table->extend_thresh)) { symbol_table_extend_bases(table) ; index = symbol_base_index(table, hash) ; base = &table->bases[index] ; } ; /* Third, chain in the new entry */ this->next = *base ; *base = this ; /* Finally, count the new entry and update the max_index. */ if (index > table->max_index) table->max_index = index ; ++table->entry_count ; return this ; } ; /*============================================================================== * Symbol Value handling. */ static symbol symbol_remove(symbol sym, free_keep_b free_body) ; /*------------------------------------------------------------------------------ * Set the given symbol's body -- must NOT be NULL. * * If "set" is true, will symbol_set() the symbol -- after freeing any * existing body, if that is required (in case the free operation cares). * * If "set" is false, has *no* effect on the reference count -- see * symbol_unset() * * May be used after a new symbol is added to the symbol table -- in which case * the current body will be NULL. * * May be used to replace an existing symbol body -- in which case the current * body will be returned. It is the caller's responsibility to free it. * * May set the symbol body any number of times, but each time the "name" MUST * be the same as the original name. * * May be used to replace the body of a symbol just before unsetting it. * Caller may wish to check symbol_has_references() before bothering to do * this. */ extern void symbol_set_body(symbol sym, void* body, bool set, free_keep_b free_old) { qassert((sym->table != NULL) && (body != NULL)) ; if ((sym->body != NULL) && free_old) sym->table->func.free(sym->body) ; sym->body = body ; if (set) symbol_set(sym) ; } ; /*------------------------------------------------------------------------------ * Delete symbol -- set body and table to NULL * * Unsets any nrefs -- since nref structure does not belong to the symbol, does * not free the nref. So, deleting a symbol makes all nref point to NULL. * * Does symbol_unset() -- which will remove the symbol if there are no * remaining references. * * If the symbol still exists after reducing the reference count: remove it * from the symbol table and free the current body. * * After symbol_delete(), the caller should forget about the symbol, leaving it * up to the reference system to sweep up, as required. * * Returns: NULL * * NB: this operation leaves any existing references pointing at the orphan * symbol. If a new symbol is created, with the same name, those * references will NOT then point at the new value. * * NB: any existing references point to a symbol with a NULL table and a NULL * body. Because the body is NULL the symbol no longer even has a name ! * * NB: this will destroy any bookmarks there are on the nref_list... which the * nref_list walker has to look out for ! */ extern symbol symbol_delete(symbol sym, free_keep_b free_body) { if (sym == NULL) return NULL ; /* do nothing if already deleted */ symbol_inc_ref(sym) ; /* hold on to the symbol & body pro tem */ while (sym->nref_list != NULL) symbol_nref_unset(sym->nref_list, keep_it) ; symbol_unset(sym, keep_it) ; /* unset, as promised */ sym->ref_count -= symbol_ref_count_increment ; /* hand crank -- about to remove, and * may be keeping the body. */ return symbol_remove(sym, free_body) ; /* free the body (if required) and * remove from symbol table, leaving * orphan symbol. */ } ; /*------------------------------------------------------------------------------ * Zeroise the reference count -- and remove the symbol */ Private symbol symbol_zero_ref(symbol sym, free_keep_b free_body) { sym->ref_count = 0 ; qassert(sym->nref_list == NULL) ; return symbol_remove(sym, free_body) ; /* Returns NULL */ } ; /*------------------------------------------------------------------------------ * Remove symbol from its symbol table (if any). * * If there is a body, free it. * * If the reference count is zero, free the symbol. * * Returns: NULL <=> symbol has been freed * otherwise == the symbol * * NB: removing things from the symbol table does not change the chain bases * or anything like that... so table can be reamed and walked, without * worrying about that ! */ static symbol symbol_remove(symbol sym, free_keep_b free_body) { symbol_table table ; table = sym->table ; if (table != NULL) /* Deleted symbols have no parent table. */ { symbol* base ; symbol prev ; assert(table->entry_count != 0) ; base = &table->bases[symbol_base_index(table, sym->hash)] ; if (*base == sym) *base = sym->next ; else { prev = *base ; while (1) { assert(prev != NULL) ; if (prev->next == sym) break ; prev = prev->next ; } ; prev->next = sym->next ; } ; --table->entry_count ; sym->table = NULL ; sym->next = NULL ; sym->hash = 0 ; } ; if (sym->body != NULL) { qassert(table != NULL) ; if (free_body) table->func.free(sym->body) ; sym->body = NULL ; } ; if (sym->ref_count == 0) { qassert(sym->nref_list == NULL) ; XFREE(MTYPE_SYMBOL, sym) ; /* sets sym = NULL */ } ; return sym ; } ; /*============================================================================== * Simple hashing functions. * * The hash functions provided here use CRC32 as a hash. * * CRC32 is not intended as a hash function, and is not a perfect one. * However it is fast -- requiring a few simple operations per byte. Taken * with the secondary effect of using the hash produced modulo an odd number, * experience suggests this is sufficient. */ static u_int32_t crc_table[] ; /*------------------------------------------------------------------------------ * Simple hash function for '\0' terminated strings. * * Can be used directly in a struct symbol_funcs. */ extern symbol_hash_t symbol_hash_string(const void* string) { uint32_t h = 0x31415927 ; const u_int8_t* p = string ; while (*p != '\0') h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; return h ; } ; /*------------------------------------------------------------------------------ * Simple symbol byte vector hash function. */ extern symbol_hash_t symbol_hash_bytes(const void* bytes, size_t len) { uint32_t h = (uint32_t)len * 0x31415927 ; /* So strings of zeros don't CRC the same ! */ const u_int8_t* p = bytes ; const u_int8_t* e = p + len ; if ((len & 3) != 0) { if ((len & 2) != 0) { h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; } ; if ((len & 1) != 0) h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; } ; while (p < e) { h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; } ; return h ; } ; /*============================================================================== * Reference list handling. * * References are added at the head of the list -- which is significant when * adding references during a symbol reference walk. * * Implementation note: the next and prev pointers in the symbol_ref structure * are significant only if the sym pointer is not NULL. */ static inline void symbol_nref_list_add(symbol sym, symbol_nref nref) ; static inline void symbol_nref_list_del(symbol sym, symbol_nref nref) ; static inline bool symbol_nref_is_bookmark(symbol_nref nref) ; /*------------------------------------------------------------------------------ * Initialise symbol notify reference -- allocate if required. */ extern symbol_nref symbol_nref_init(symbol_nref nref) { if (nref == NULL) return XCALLOC(MTYPE_SYMBOL_REF, sizeof(struct symbol_nref)) ; else return memset(nref, 0, sizeof(struct symbol_nref)) ; } ; /*------------------------------------------------------------------------------ * Set symbol notify reference -- allocate if required (nref == NULL). * * Increments reference count on new symbol (if any) and decrements count on * old symbol (if any). * * NB: does nothing if reference already set to the given symbol. * * NB: unsets (but does not free) nref if was not NULL (and is not same as * symbol being set to) before setting new reference. * * Note that the old symbol may suddenly disappear ! * * NB: setting nref to NULL unsets any existing nref, but does NOT free the * nref structure. * * NB: if nref is allocated, the parent is set NULL and the tag is set 0. * * if nref is not allocated, the parent and tag are unchanged. */ extern symbol_nref symbol_nref_set(symbol_nref nref, symbol sym) { if (nref != NULL) { if (nref->sym == sym) return nref ; /* Nothing more to do if already set to given value */ if (nref->sym != NULL) symbol_nref_unset(nref, keep_it) ; } else nref = symbol_nref_init(NULL) ; qassert(nref->sym == NULL) ; if (sym != NULL) { symbol_nref_list_add(sym, nref) ; nref->sym = symbol_inc_ref(sym) ; } ; return nref ; } ; /*------------------------------------------------------------------------------ * Unset symbol notify reference. Free the structure if required. * * NB: does nothing if address of nref is NULL. * * NB: if nref is not freed, the parent and tag are unchanged. * * NB: removing the last reference to an symbol causes the symbol to be freed. * * NB: copes if the nref is already unset, of course. * * NB: this is called by symbol_delete(), and may be unsetting a bookmark !! * * this is also called by symbol_nref_walk_step(), also to unset a * bookmark. */ extern symbol_nref symbol_nref_unset(symbol_nref nref, free_keep_b free) { symbol sym ; if (nref == NULL) return nref ; if (symbol_nref_is_bookmark(nref)) { /* Get actual symbol for bookmark, and then set parent to NULL and * set sym as for normal nref... then it can be deleted along with * normal nrefs ! */ nref->sym = (symbol)nref->parent ; nref->parent = NULL ; qassert(!free) ; /* when symbol_delete() */ free = false ; } ; sym = nref->sym ; if (sym != NULL) /* NULL => reference already unset */ { symbol_nref_list_del(sym, nref) ; nref->sym = symbol_dec_ref(sym) ; /* sets nref->sym to NULL */ } ; if (free) XFREE(MTYPE_SYMBOL_REF, nref) ; /* nref is set to NULL */ return nref ; } ; /*------------------------------------------------------------------------------ * Insert symbol_nref at head of symbol's nref_list. * * NB: only affects sym->nref_list, nref->next and nref->prev */ static inline void symbol_nref_list_add(symbol sym, symbol_nref nref) { symbol_nref next ; next = sym->nref_list ; /* current first on list, if any */ sym->nref_list = nref ; /* new first on list */ nref->next = next ; /* point to old first on list */ nref->prev = (void*)sym ; /* mark as first on list */ if (next != NULL) next->prev = nref ; /* update old first on list */ } ; /*------------------------------------------------------------------------------ * Clip symbol_ref from symbol's list of references. * * If symbol_ref has already been deleted the prev pointer is NULL, and this * function copes -- and does not need the symbol to be valid (sym may be NULL). * * NB: only affects sym->nref_list, nref->next and nref->prev */ static inline void symbol_nref_list_del(symbol sym, symbol_nref nref) { symbol_nref prev = nref->prev ; symbol_nref next = nref->next ; if (prev != NULL) { if (prev == (void*)sym) { assert(sym->nref_list == nref) ; sym->nref_list = next ; /* remove from head of list */ } else prev->next = next ; /* remove from place in list */ if (next != NULL) next->prev = prev ; /* update next's prev ptr */ } ; nref->next = nref->prev = NULL ; } ; /*============================================================================== * Procedure for walking the notify references to a symbol: * * symbol_nref_t walk[1] ; * symbol sym ; * symbol_nref ref ; * * symbol_nref_walk_start(sym, walk) ; * while ((ref = symbol_nref_walk_step(walk)) != NULL) * .... whatever * symbol_nref_walk_end(walk) ; * * NB: it is *essential* to call symbol_nref_walk_end() exactly once at some * time after symbol_nref_walk_start. * * The symbol table walk uses a "bookmark" which is a special from of entry in * the symbol's nref_list. This mechanism: * * (a) prevents the symbol being freed while the reference walk is in * progress -- that may happen during symbol_ref_walk_end. * * (b) allows for the current and other nref to be set or unset. * * Setting an nref inserts it upstream of the bookmark -- so it will * not be visited during the walk. * * Unsetting an nref that has yet to be visited eliminates it from * the walk. * * Note that setting an nref to refer to the symbol it already refers to * has no effect at all. * * (c) allows the symbol to be reset, unset or set during am nref walk. * * If that triggers another symbol nref walk, then that will proceed * until it hits the point reached by the previous walk, and will * terminate that and proceed. * * Suppose the earlier walk was dealing with the value changing from * 'A' to 'B'. A later walk will deal with a change from 'B' to 'C' * until it meets the earlier one, in which point it will be dealing with * a change 'A' to 'C'. * * If that does not suit, don't fiddle with symbol values during a * symbol nref walk. */ /*------------------------------------------------------------------------------ * Start walk of symbol notify references * * NB: given walk symbol_nref may NOT be NULL. */ extern void symbol_nref_walk_start(symbol sym, symbol_nref walk) { assert(walk != NULL) ; symbol_nref_init(walk) ; /* keeping things tidy */ walk->sym = (void*)walk ; /* bookmark signature */ walk->parent = sym ; symbol_nref_list_add(sym, walk) ; /* insert bookmark at head of list */ symbol_inc_ref(sym) ; /* count in the bookmark */ } ; /*------------------------------------------------------------------------------ * Step walk and return the next reference (if any). */ extern symbol_nref symbol_nref_walk_step(symbol_nref walk) { symbol_nref nref ; /* It is possible for a symbol_delete() to have emptied out the nref_list, * including bookmarks. * * It is also possible that a later walk has removed this bookmark. * * Both set nref->sym to NULL */ if (walk->sym == NULL) return NULL ; /* walk terminated */ assert(symbol_nref_is_bookmark(walk)) ; /* must be a bookmark ! */ /* Deal with cases of (a) the next item is a bookmark, and (b) there are * no more items to deal with. */ while (1) { if (walk->next == NULL) { /* Have reached the end -- so unset self to close down the walk and * decrement the reference count. */ symbol_nref_unset(walk, keep_it) ; qassert(walk->sym == NULL) ; return NULL ; /* finished */ } ; if (!symbol_nref_is_bookmark(walk->next)) break ; symbol_nref_unset(walk->next, keep_it) ; } ; /* Now we move the bookmark one place forwards */ nref = walk->next ; qassert(nref->prev == walk) ; nref->prev = walk->prev ; walk->next = nref->next ; nref->next = walk ; walk->prev = nref ; /* Return the nref we just stepped past */ return nref ; } ; /*------------------------------------------------------------------------------ * End of symbol notify reference walk. * * Unset the bookmark, if it is still set. * * If the walk was run to completion, then there is, in fact, nothing to be * done here. */ extern void symbol_nref_walk_end(symbol_nref walk) { if (walk->sym != NULL) symbol_nref_unset(walk, keep_it) ; } ; /*------------------------------------------------------------------------------ * Bookmarks are symbol_ref structures, distinguished from ordinary symbol_ref * structures by setting the sym field to point at the bookmark symbol_ref * itself. * * (It would be nicer to use the parent field for this... but what is put * there in ordinary symbol_ref structures is not guaranteed...) */ static inline bool symbol_nref_is_bookmark(symbol_nref nref) { return (void*)nref->sym == (void*)nref ; } ; /*============================================================================== * Walking a symbol table * * Simple walk: visits all entries in the table, in the order they are hashed * to. Simple iterator. * * Extract: makes vector of pointers to selected entries, and sorts that * vector as required. */ /*------------------------------------------------------------------------------ * Walk the given symbol table. * * Usage: * * symbol_walker_t walker ; * symbol sym ; * .... * symbol_walk_start(table, walker) ; * while ((sym = symbol_walk_next(walker))) * .... * * NB: it is possible to change the current symbol while the walk is in * progress -- up to and including unsetting/deleting it. Any other * changes to the table must NOT be attempted. */ extern void symbol_walk_start(symbol_table table, symbol_walker walk) { assert(walk != NULL) ; walk->next = NULL ; walk->base = table->bases ; walk->base_count = table->base_count ; } ; /*------------------------------------------------------------------------------ * Walk to next symbol to consider */ extern symbol symbol_walk_next(symbol_walker walk) { symbol this = walk->next ; while (this == NULL) { if (walk->base_count == 0) return NULL ; --walk->base_count ; this = *(walk->base++) ; } ; walk->next = this->next ; return this ; } ; /*------------------------------------------------------------------------------ * Extract Symbols. * * Walk symbol table and select symbols to add to a new vector. Then sort the * vector, if required. Takes: * * -- selector: NULL => select all * -- p_val: pointer is passed to the select function (if any) * -- most: if there is a select function, this flag hints that most of * the symbols will be selected -- so it is worth preallocating * a vector big enough for all symbols. * -- sort: NULL => no sort (!) * * NB: the vector contains pointers to the selected symbols. It is the * caller's responsibility to avoid deleting any symbol whose pointer * in the vector they expect to rely on ! */ extern vector symbol_table_extract(symbol_table table, symbol_select_cmp* selector, const void* p_val, bool most, symbol_sort_cmp* sort) { vector extract ; symbol* base ; unsigned int count ; symbol sym ; extract = vector_init_new(NULL, (most || (selector == NULL)) ? table->entry_count : 8) ; base = table->bases ; if (base == NULL) return extract ; /* Quit if symbol table is "reset" */ count = table->base_count ; while (count--) { sym = *base++ ; while (sym != NULL) { if ((selector == NULL) || selector(sym, p_val)) vector_push_item(extract, sym) ; sym = sym->next ; } ; } ; if (sort != NULL) vector_sort(extract, (vector_sort_cmp*)sort) ; return extract ; } ; /*============================================================================== * Some common comparison functions for symbol table extracts. */ /*------------------------------------------------------------------------------ * Comparison function to sort names which are a mixture of digits and other * characters. * * Assumes that symbol_get_name() returns address of '\0' terminated string. * * This comparison treats substrings of digits as numbers, so "a10" is > "a1". */ extern int symbol_mixed_name_cmp(const char* a, const char* b) { const char* ap ; const char* bp ; int la, lb ; ap = a ; bp = b ; while (1) { if (isdigit(*ap) && isdigit(*bp)) { char* aq ; /* Required to stop the compiler whining */ char* bq ; ulong na = strtoul(ap, (char** restrict)&aq, 10) ; ulong nb = strtoul(bp, (char** restrict)&bq, 10) ; if (na != nb) return (na < nb) ? -1 : +1 ; ap = aq ; bp = bq ; } else { if (*ap != *bp) return (*ap < *bp) ? -1 : +1 ; if (*ap == '\0') break ; ++ap ; ++bp ; } } ; /* Looks like the names are equal. * But may be different lengths if have number part(s) with leading zeros, */ la = strlen(a) ; lb = strlen(b) ; if (la != lb) return (la < lb) ? -1 : +1 ; return 0 ; } ; /*============================================================================== * Table for generating CRC-32 -- Standard (0x1_04C1_1DB7 0xEDB8_8320) */ static u_int32_t crc_table[] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D, } ;