diff options
Diffstat (limited to 'lib/symtab.c')
| -rw-r--r-- | lib/symtab.c | 1186 |
1 files changed, 1186 insertions, 0 deletions
diff --git a/lib/symtab.c b/lib/symtab.c new file mode 100644 index 00000000..57a49396 --- /dev/null +++ b/lib/symtab.c @@ -0,0 +1,1186 @@ +/* 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 <zebra.h> +#include <stddef.h> + +#include "symtab.h" +#include "memory.h" + +/* A symbol table maps symbol "names" to symbol values and, for each symbol, + * has two ways of keeping track of references to the symbol. + * + * The symbol name can be an arbitrary collection of bytes, or a string. All + * names in a symbol table are unique. + * + * The symbol value is a void* -- whose contents are no concern of this code. + * + * A symbol table comprises: + * + * * symbol table structure -- containing all "red-tape" + * * array of chain-bases -- for the hash table + * * symbol entries -- each containing name and value of a symbol + * + * The symbol table structure may be statically allocated, embedded in another + * structure, or allocated dynamically. In any case the symbol table operations + * require the address of the symbol table structure -- see typedef for + * symbol_table. + * + * A symbol table may point to its "parent" -- which could be an enclosing + * structure, or any other higher level data. The symbol table code does not + * use or need this -- it is for the convenience of the caller. + * + * A symbol table structure which is zeroised is implicitly an empty symbol + * table, using the default symbol name type -- a null terminated string. + * + * Each Symbol Table requires a hash function, which takes a pointer to + * whatever and returns a 32-bit hash value and a canonical form of the + * symbol "name". When a new symbol is created the canonical form of the name + * is copied to the symbol entry. + * + * 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 a 32-bit + * 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 value -- void* + * * symbol name + * * count of references + * * list of references + * + * Symbols may have the value NULL. Deleting a symbol is not the same as + * setting its value to NULL. If the value is set NULL and later set to + * something else, all references to the symbol will see the new value. If the + * symbol is deleted, all references will see its value set to NULL, but if a + * new symbol with the same name is later created, all references to the old + * symbol are unchanged, and continue to see the (orphan) NULL. + * + * Keeping track of references is important because it ensures that symbols + * can be deleted without leaving dangling references. When a symbol is + * deleted, it is removed from the symbol table and its value is set to NULL. + * If there are no references to the symbol, the symbol entry is released. + * If there are references to the symbol, it is preserved (as an orphan) until + * all references are unset. The value of an orphaned symbol should not be + * changed (but may be unset, since it is already unset). + * + * There are two, parallel mechanisms for keeping track of references to a + * symbol: + * + * 1. reference count -- this is for when all that is required is a pointer + * to the symbol, ie: + * + * * ptr_to_symbol = symbol_inc_ref(sym) -- set reference & count up + * * ptr_to_symbol = symbol_dec_ref(sym) -- unset reference & count down + * + * 2. list of references -- this is for when it is useful to visit all + * references to a given symbol, for example when the value of the symbol + * is set and all users of the symbol need to adjust to the new state. + * + * A symbol reference contains a pointer to the symbol, and lives on the + * list of references to the symbol. When the value is set, a call-back + * associated with the table is called (if it is set). That call-back may + * walk the list of references to the symbol. Each reference contains a + * pointer and a pointer/long int value, which may be used to identify the + * reference. + * + * A symbol reference may be statically allocated, embedded in another + * structure, or allocated dynamically. In any case the symbol reference + * operations require the address of the symbol reference structure -- see + * typedef for symbol_ref. + * + * Symbol references are the responsibility of of the owner of the reference, + * who must look after setting, unsetting and (if required) releasing them. + * + * It may seem profligate to have two mechanisms. However, it is simpler than + * having two types of symbol, or two types of symbol table. It may also be + * useful to have both simple references and references for dealing with + * value changes. Suppose, for instance, that the value of a symbol has a + * pointer to the symbol -- so that the value of the symbol can refer back to + * its name, for example. This requires only a simple reference, even if + * more generally a list of references is required. + * + * 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. + */ + +static void symbol_extend_bases(symbol_table table) ; +static void symbol_free(symbol sym) ; + +/* Return true iff there are no references to the given symbol */ +inline static int +symbol_no_references(symbol sym) +{ + return (sym->ref_count == 0) && (sym->ref_list == NULL) ; +} ; + +/* If symbol is an orphan with no references/bookmarks, free it. + * + * NB: if symbol is an orphan, then it implicitly has a NULL value, because + * to become an orphan it must have been deleted, which unsets the value. + */ +inline static void +symbol_free_if_redundant(symbol sym) +{ + if ((sym->table == NULL) && symbol_no_references(sym)) + symbol_free(sym) ; +} ; + +/* Return chain base for given hash value. */ +inline static symbol* +symbol_base(symbol_table table, u_int32_t hash) +{ + return &table->bases[hash % table->base_count] ; +} ; + +/* Initialise a new symbol table -- allocate if required. + * + * table -- address of table to initialise. NULL -> allocate. + * NB: if allocated, it is the caller's responsibility to free. + * + * 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. + * + * density -- %-age of entries/bases. 0 => use default. + * + * hash_function + * -- function to fill in symbol_hash from a given "name". + * see: description of struct symbol_hash and default function, + * symbol_hash_string, below. + * NULL => the names in this symbol table are null terminated + * strings, so use symbol_hash_string. + * + * value_call_back + * -- function to be called when the symbol value is set or unset. + * (Or the symbol is about to be deleted -- which starts by + * unsetting it). + * + * The function is passed the new state of the symbol and its + * previous value. + * + * The value of the symbol is a pointer to some data. If the + * data changes symbol_set_value() must be called if its + * address changes and may be called even if its address doesn't + * change. + * + * In any event, value_call_back is called when symbol_set_value() + * is called -- except where the symbol is being set to NULL and + * the value is already NULL. + * + * During the call-back the symbol may be set again or unset, + * which will cause the call-back to be called inside itself. + * Also, references may be set or unset. + * + * In the call-back the reference list may be walked to signal + * to all holders of the reference that something has changed. + * + * NB: A completely zeroized symbol_table structure is a valid, empty + * symbol table. The first time it is used it will be set up to default + * state -- in particular: symbol names are null terminated strings (a + * state which *cannot* then be changed). + * + * NB: when this is used to re-initialising an existing symbol table structure, + * any existing chain base array, symbols and symbol references are simply + * discarded -- which will leak memory and is probably a mistake. + */ +symbol_table +symbol_table_init_new(symbol_table table, + void* parent, + unsigned int base_count, + unsigned int density, + symbol_hash_function* hash_function, + symbol_call_back_function* value_call_back) +{ + assert(base_count <= SYMBOL_TABLE_BASES_MAX) ; + + if (table == NULL) + table = XCALLOC(MTYPE_SYMBOL_TABLE, sizeof (struct symbol_table)) ; + + table->parent = parent ; + + table->bases = NULL ; /* Allocated when required */ + table->base_count = base_count ; + + table->entry_count = 0 ; + table->extend_thresh = density ; /* Fixed up when required */ + + table->hash_function = hash_function ; + symbol_table_set_value_call_back(table, value_call_back) ; + + return table ; +} ; + +/* Set "parent" of symbol table. */ +void +symbol_table_set_parent(symbol_table table, void* parent) +{ + table->parent = parent ; +} ; + +/* Get "parent" of symbol table. */ +void* +symbol_table_get_parent(symbol_table table) +{ + return table->parent ; +} ; + +/* Set the value_call_back */ +void +symbol_table_set_value_call_back(symbol_table table, + symbol_call_back_function* value_call_back) +{ + table->value_call_back = value_call_back ; +} ; + +/* Create and set new chain bases and threshold for next extension. */ +/* */ +/* Ensures that the base count is at least the minimum and is odd, */ +/* and returns the value set. */ +static unsigned int +symbol_table_new_bases(symbol_table table, + unsigned int new_base_count, float density) +{ + if (new_base_count < SYMBOL_TABLE_BASES_MIN) + new_base_count = SYMBOL_TABLE_BASES_MIN ; + new_base_count |= 1 ; + + table->bases = XCALLOC(MTYPE_SYMBOL_BASES, new_base_count * sizeof(symbol)) ; + table->extend_thresh = new_base_count * density ; + return table->base_count = new_base_count ; +} ; + +/* Setup symbol table body for use. + * + * Used for "lazy" allocation of chain bases and allows symbol_lookup + * to operate on a completely zeroized symbol_table structure. + */ +static void +symbol_table_setup(symbol_table table) +{ + float density ; + + /* If density was set explicitly, extend_thresh entry is a %age. */ + + if (table->extend_thresh != 0) + density = (float)table->extend_thresh / (float)100 ; + else + density = (float)2 ; /* Default density */ + + /* Initialise the chain bases -- enforces minimum base_count and odd-ness */ + symbol_table_new_bases(table, table->base_count, density) ; + + /* make default hash_function explicit. */ + if (table->hash_function == NULL) + table->hash_function = (symbol_hash_function*)symbol_hash_string ; +} ; + +/* Reset symbol table. + * + * Free the symbol table body, and free the symbol table structure or reset it. + * + * Return NULL if frees symbol table structure, otherwise the address of same. + * + * NB: must only be done when the table is empty -- see assertion ! + */ +symbol_table +symbol_table_reset(symbol_table table, int free_structure) +{ + if (table== NULL) + return NULL ; /* allow for already freed table */ + + assert(table->entry_count == 0) ; + + if (table->bases) + XFREE(MTYPE_SYMBOL_BASES, table->bases); + + if (free_structure) + { + XFREE(MTYPE_VECTOR, table) ; + return NULL ; + } + else + return memset(table, 0, sizeof(struct symbol_table)) ; +} ; + +/* Remove symbol from its symbol table (if any). */ + +static void +symbol_remove(symbol sym) +{ + symbol_table table ; + symbol* base ; + symbol prev ; + + table = sym->table ; + if (table != NULL) /* Deleted symbols have no parent table. */ + { + assert(table->entry_count != 0) ; + + base = symbol_base(table, sym->hash) ; + if (*base == sym) + *base = sym->next ; + else + { + prev = *base ; + while (prev->next != sym) + prev = prev->next ; + prev->next = sym->next ; + } ; + + sym->table = NULL ; /* Symbol is now an orphan. */ + --table->entry_count ; + } ; +} ; + +/* Free symbol, removing it from the symbol table. + * + * NB: the value and all references MUST already have been unset, because: + * + * * any value may well need to be released, and have no idea how to do + * that here. + * + * * similarly, references may need to be released and should not, in + * any case, be left dangling. + */ +static void +symbol_free(symbol sym) +{ + assert((sym->value == NULL) && symbol_no_references(sym)) ; + + symbol_remove(sym) ; /* Remove from table, if any. */ + + XFREE(MTYPE_SYMBOL, sym) ; +} ; + +/* Ream out symbols. + * + * Delete symbols -- but do not invoke the value_call_back. + * + * When the table is (or becomes) empty, the chain bases are freed, and the + * structure freed or reset (depending on the free_structure argument). + * + * This is intended for use when the symbol table is being destroyed, and all + * references have been, or will be unset. + * + * Returns the value of the next non-NULL symbol (if any). So may be used, for + * example: + * + * xxxx* val ; + * ... + * while ((val = symbol_table_ream(table, free_structure)) != NULL) + * { + * ... do what's required to release the value ... + * } + * + * Noting that the symbol may already have been released when its value is + * returned. (If the symbol is required when the value is released, then the + * value should hold a simple reference to the symbol.) + * + * Returns NULL when the table is empty. + * + * 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. + * + * NB: do NOT attempt to do anything else with the symbol table once reaming + * has started. + * + * 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. + */ +void* +symbol_table_ream(symbol_table table, int free_structure) +{ + void* value ; + symbol sym ; + unsigned int i ; + + /* There are no actual bases until they have been allocated. */ + i = (table->bases != NULL) ? table->base_count : 0 ; + + while (i--) + { + while ((sym = table->bases[i]) != NULL) + { + assert(table->entry_count != 0) ; + + /* the following is effectively symbol_delete, but avoids the */ + /* value_call_back and returns only if the value is not NULL. */ + + table->bases[i] = sym->next ; /* remove from table */ + --table->entry_count ; /* count down */ + + sym->table = NULL ; /* orphan symbol */ + value = sym->value ; /* pick up value. */ + sym->value = NULL ; /* and set symbol undefined */ + + if (symbol_no_references(sym)) + symbol_free(sym) ; /* not in table, no value, no references */ + + if (value != NULL) + { + table->base_count = i + 1 ; /* where we've got to */ + return value ; /* <<< RETURN: caller must deal with value */ + } ; + } ; + } ; + + symbol_table_reset(table, free_structure) ; + /* asserts(table->entry_count == 0) */ + return NULL ; +} ; + +/* Look-up name in given symbol table. Add if required. + * + * Returns NULL if not found and not required to add. + * + * NB: the name argument is passed to the symbol table's hash function. That + * function is required to return with a 32-bit hash + * + * NB: if required to add, the caller cannot distinguish between a symbol + * which did not previously exist, and one which did exist but had no + * value and no references. Where that distinction matters, it is + * necessary to do an extra lookup. + */ +symbol +symbol_lookup(symbol_table table, const void* name, int add) +{ + struct symbol* this ; + struct symbol** base ; + struct symbol_hash hash ; + + assert(table != NULL) ; + if (table->bases == NULL) + symbol_table_setup(table) ; /* Lazy allocation of chain bases etc. */ + + table->hash_function(&hash, name) ; + + base = symbol_base(table, hash.hash) ; + this = *base ; + while (this) + { + if ((this->hash == hash.hash) + && (this->name_len == hash.name_len) + && (memcmp(this->name, hash.name, this->name_len) == 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 */ + this = XCALLOC(MTYPE_SYMBOL, sizeof(struct symbol) + hash.name_copy_len) ; + + this->table = table ; + this->value = NULL ; + this->ref_list = NULL ; + this->ref_count = 0 ; + this->hash = hash.hash ; + this->name_len = hash.name_len ; + memcpy(this->name, hash.name, hash.name_copy_len) ; + + /* Second, if required, extend the array of list bases. We extend if */ + /* we have a collision *and* we exceed threshold of number of entries. */ + if ((*base != NULL) && (table->entry_count > table->extend_thresh)) + { + symbol_extend_bases(table) ; + base = symbol_base(table, hash.hash) ; + } ; + + /* Third, chain in the new entry, count it in and return */ + this->next = *base ; + *base = this ; + + ++table->entry_count ; + + return this ; +} ; + +/* Delete symbol. + * + * The first effect of this is to set the symbol value to NULL, which may + * trigger a value_call_back etc. + * + * Then the symbol is removed from the table (and the symbol becomes an orphan). + * + * Then, if there are no (remaining) references the symbol is freed. Otherwise + * the symbol entry remains in existence until there are no more references + * (at which point it will finally be destroyed). + * + * Returns the last value of the symbol -- which may itself need to be + * destroyed -- noting that the symbol may already have been released. (If the + * symbol is required when the value is released, then the value should hold a + * simple reference to the symbol.) + * + * NB: the effect of deleting a symbol is to leave all remaining references + * pointing at an NULL value, orphaned symbol. + * + * If a new symbol is created with the same name, that will be a + * completely different symbol -- references to the old symbol will + * continue to be to the vestigial NULL value. + * + * This is different from setting the symbol value to NULL and later + * giving it a new value. + * + * NB: orphan symbols can be deleted. The effect is to free the symbol if + * possible. + */ +void* +symbol_delete(symbol sym) +{ + void* old_value = symbol_unset_value(sym) ; + + if (symbol_no_references(sym)) + symbol_free(sym) ; /* free symbol now if no references */ + else + symbol_remove(sym) ; /* else just remove it from the table -- will be */ + /* freed when all references are unset. */ + return old_value ; +} ; + +/* 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[] ; + +/* Standard symbol string hash function. */ +void +symbol_hash_string(symbol_hash p_hash, const char* string) { + u_int32_t h = 0 ; + const char* p = string ; + + while (*p != 0) + h = crc_table[(h & 0xFF) ^ (u_int8_t)*p++] ^ (h >> 8) ; + + assert((p - string) < 0xFFFF) ; + + p_hash->hash = h ; + p_hash->name = string ; + p_hash->name_len = (p - string) ; + p_hash->name_copy_len = p_hash->name_len + 1 ; +} ; + +/* Standard symbol byte vector hash function. */ +void +symbol_hash_bytes(symbol_hash p_hash, const void* bytes, size_t len) { + assert(len < 0xFFFF) ; + + u_int32_t h = len ; /* So strings of zeros don't CRC the same ! */ + const u_int8_t* p = bytes ; + const u_int8_t* e = p + len ; + + while (p < e) + h = crc_table[(h & 0xFF) ^ *p++] ^ (h >> 8) ; + + p_hash->hash = h ; + p_hash->name = (const void*)bytes ; + p_hash->name_len = len ; + p_hash->name_copy_len = len ; +} ; + +/* Extend the array of list bases. */ +static void +symbol_extend_bases(symbol_table table) +{ + symbol this ; + symbol next ; + symbol* old_bases ; + symbol* new_bases ; + symbol* base ; + unsigned int new_base_count ; + unsigned int old_base_count ; + + old_bases = table->bases ; + old_base_count = table->base_count ; + + assert((old_bases != NULL) && (old_base_count != 0)) ; + + /* TODO: should look out for overflowing base_count and requiring */ + /* impossible amounts of memory ?! */ + + new_base_count = (table->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 ; + + new_base_count = symbol_table_new_bases(table, new_base_count, + (float)table->extend_thresh / table->base_count) ; + + /* Rehome everything on the new chain bases. */ + new_bases = table->bases ; + while (old_base_count--) + { + next = old_bases[old_base_count] ; + while (next != NULL) + { + this = next ; + next = this->next ; + base = &new_bases[this->hash % new_base_count] ; + this->next = *base ; + *base = this ; + } ; + } ; + + /* Release the old chain bases, and we're done. */ + XFREE(MTYPE_SYMBOL_BASES, old_bases) ; +} ; + +/*============================================================================== + * Reference count handling. + * + * symbol_inc_ref(sym) -- declared Inline + * symbol_dec_ref(sym) -- declared Inline + */ + +/* Zeroise the reference count.*/ + +symbol +symbol_zero_ref(symbol sym, int force) +{ + assert((sym->ref_count == 1) || force) ; + + sym->ref_count = 0 ; + symbol_free_if_redundant(sym) ; + + return NULL ; +} ; + +/*============================================================================== + * Reference list handling. + * + * References are added at the head of the list -- which is significant when + * adding references during a symbol reference walk. + */ + +/* Insert symbol_ref at head of symbol's list of references. */ +static inline void +symbol_add_ref(symbol sym, symbol_ref ref) +{ + symbol_ref next = sym->ref_list ; + sym->ref_list = ref ; + if (next) + next->prev = ref ; + ref->next = next ; + ref->prev = (void*)sym ; /* marker for 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). + */ +static inline void +symbol_del_ref(symbol sym, symbol_ref ref) +{ + symbol_ref prev = ref->prev ; + symbol_ref next = ref->next ; + + if (prev != NULL) + { + if (prev == (void*)sym) + { + assert(sym->ref_list == ref) ; + sym->ref_list = next ; + } + else + prev->next = next ; + + if (next != NULL) + next->prev = prev ; + } ; + ref->next = ref->prev = NULL ; +} ; + +/*============================================================================== + * The value_call_back handling and symbol reference list walking. + * + * If there is one, the value_call_back function is called when the value of + * a symbol is set -- except when it is set NULL and is already NULL. Note + * that setting the same non-NULL value *does* invoke the value_call_back. + * + * The value_call_back function is passed the current state of the symbol, + * complete with new value, and the old value of the symbol. + * + * During the value_call_back the symbol reference list may be walked, so that + * users of the value may be updated. + * + * During the value_call_back the symbol may be set, unset or deleted, and + * references added or taken away. This may cause nested calls of the + * call-back. Note that each call-back holds a reference to the symbol, so if + * the symbol is deleted it won't be freed until the outermost call-back + * returns. + * + * Procedure for walking the references to a symbol: + * + * struct symbol_ref walk ; + * symbol sym ; + * symbol_ref ref ; + * symbol_ref_walk_start(sym, &walk) ; + * while ((ref = symbol_ref_walk_step(&walk)) != NULL) + * .... whatever + * symbol_ref_walk_end(&walk) ; + * + * NB: it is *essential* to call symbol_ref_walk_end() exactly once at some + * time after symbol_ref_walk_start. + * + * The symbol table walk uses a "bookmark" which is a special from of entry in + * the symbol's reference 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 references to be set or unset. + * + * Setting a reference inserts it upstream of the bookmark -- so it will + * not be visited during the walk. + * + * Unsetting a reference that has yet to be visited eliminates it from + * the walk. + * + * Note that setting a reference to refer to the symbol it already + * refers to has no effect at all. + * + * (c) allows the symbol to be defined, undefined or redefined during a + * symbol reference walk. + * + * If that triggers another symbol reference walk, then that walk will + * proceed until it hits the point reached by the walk it is nested + * inside, and then stop. + * + * Suppose the outer walk was dealing with the value having changed from + * 'A' to 'B'. The inner walk will do from 'B' to the latest value 'C' + * for the references that have already seen 'A' to 'B'. When the outer + * walk resumes, it will deal with the change 'A' to 'C', unaware of the + * intermediate step. + * + * If that does not suit, don't fiddle with symbol values during a + * symbol reference walk. + */ + +/* 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 int +symbol_ref_is_bookmark(symbol_ref ref) +{ + return (void*)ref->sym == (void*)ref ; +} ; + +/* Start walk of symbol references */ +void +symbol_ref_walk_start(symbol sym, symbol_ref walk) +{ + symbol_init_ref(walk) ; /* keeping things tidy */ + walk->sym = (void*)walk ; /* bookmark signature */ + walk->parent = sym ; + symbol_add_ref(sym, walk) ; /* insert bookmark at head of list */ +} ; + +/* Step walk and return the next reference (if any). */ +symbol_ref +symbol_ref_walk_step(symbol_ref walk) +{ + symbol_ref next_ref ; + + assert(symbol_ref_is_bookmark(walk)) ; /* must be a bookmark ! */ + + /* Pick up reference following the bookmark, before deleting it. */ + next_ref = walk->next ; + symbol_del_ref((symbol)walk->parent, walk) ; + + /* Stop immediately if bookmark was at the end of the list or the next */ + /* item is a bookmark (for a walk that started earlier). */ + if ((next_ref == NULL) || symbol_ref_is_bookmark(next_ref)) + return NULL ; + + /* Now we move the bookmark from where it is now to after next_ref. */ + + walk->next = next_ref->next ; + next_ref->next = walk ; + walk->prev = next_ref ; + if (walk->next != NULL) + walk->next->prev = walk ; + + /* Return the next real reference to be processed. */ + return next_ref ; +} ; + +/* End of symbol reference walk. + * + * NB: if the symbol is not defined and has no references or bookmarks it + * will now be freed. + */ +void +symbol_ref_walk_end(symbol_ref walk) +{ + assert(symbol_ref_is_bookmark(walk)) ; /* must be a bookmark ! */ + + symbol_del_ref((symbol)(walk->parent), walk) ; /* make sure */ + + symbol_free_if_redundant((symbol)(walk->parent)) ; +} ; + +/*============================================================================== + * Symbol Value handling. + */ + +/* Set symbol value. NB: setting to NULL == symbol_unset_value. + * NB: setting same value as currently looks like a change. + * (except for setting NULL to NULL !) + * + * Invokes change call-back, if any -- except when setting to NULL and is + * already NULL. + * + * It is possible for the call-back to set the value again, to unset it, to + * change references, etc. + * + * Returns previous value -- which may require releasing. + */ +void* +symbol_set_value(symbol sym, void* new_value) +{ + void* old_value ; + + old_value = sym->value ; + sym->value = new_value ; + + if (sym->table == NULL) /* watch out for orphans */ + { + assert((new_value == NULL) && (old_value == NULL)) ; + return NULL ; + } ; + + /* Invoke value_call_back (if any). */ + /* Note that the value_call_back may set/unset references and/or */ + /* define/undefine the value. */ + if (((sym)->table->value_call_back != NULL) + && ( (new_value != NULL) || (old_value != NULL) )) + { + symbol_inc_ref(sym) ; /* preserve until call-back returns */ + sym->table->value_call_back(sym, old_value) ; + symbol_dec_ref(sym) ; /* may now free if has been deleted */ + } ; + + return old_value ; +} ; + +/*============================================================================== + * Symbol Reference handling. + * + * Implementation note: the next and prev pointers in the symbol_ref structure + * are significant only if the sym pointer is not NULL. + */ + +/* Initialise symbol reference -- allocate if required. */ +symbol_ref +symbol_init_ref(symbol_ref ref) +{ + if (ref == NULL) + return XCALLOC(MTYPE_SYMBOL_REF, sizeof(struct symbol_ref)) ; + else + return memset(ref, 0, sizeof(struct symbol_ref)) ; +} ; + +/* Set symbol reference -- allocate if required (ref == NULL). + * + * NB: does nothing if reference already set to the given symbol. + * + * NB: unsets (but does not free) reference if was not NULL (and is not + * same as symbol being set to) before setting new reference. + * + * NB: setting reference to NULL unsets any existing reference, but does NOT + * release the reference structure. + * + * NB: if reference is allocated, the parent is set NULL and the tag is set + * NULL/0. + * + * if reference is not allocated, the parent and tag are unchanged. + */ +symbol_ref +symbol_set_ref(symbol_ref ref, struct symbol* sym) +{ + if (ref != NULL) + { + if (ref->sym == sym) + return ref ; /* Nothing more to do if already set to given value */ + if (ref->sym != NULL) + symbol_unset_ref_keep(ref) ; + } + else + ref = symbol_init_ref(NULL) ; + + ref->sym = sym ; + if (sym != NULL) + symbol_add_ref(sym, ref) ; + + return ref ; +} ; + +/* Unset symbol reference. Free the structure if required. + * + * NB: does nothing if address of reference is NULL. + * + * NB: if reference is not freed, the parent and tag are unchanged. + * + * NB: removing the last reference to an symbol that has been deleted causes + * the symbol to be freed. + * + * NB: copes if the reference is already unset, of course. + */ +symbol_ref +symbol_unset_ref(symbol_ref ref, int free_ref_structure) +{ + if (ref == NULL) return ref ; + + if (ref->sym != NULL) /* NULL => reference already unset */ + { + symbol_del_ref(ref->sym, ref) ; + symbol_free_if_redundant(ref->sym) ; + ref->sym = NULL ; + } ; + + if (free_ref_structure) + XFREE(MTYPE_SYMBOL_REF, ref) ; /* ref is set to NULL */ + + return ref ; +} ; + +/*============================================================================== + * 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: + * + * struct symbol_walker 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 deleting it. Any other changes to + * the table must NOT be attempted. + */ +void +symbol_walk_start(symbol_table table, struct symbol_walker* walker) +{ + walker->next = NULL ; + walker->base = table->bases ; + walker->base_count = table->base_count ; +} ; + +symbol +symbol_walk_next(struct symbol_walker* walker) +{ + symbol this = walker->next ; + + while (this == NULL) + { + if (walker->base_count == 0) + return NULL ; + --walker->base_count ; + this = *(walker->base++) ; + } ; + + walker->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 ! + */ +vector +symbol_table_extract(symbol_table table, + symbol_select_cmp* selector, const void* p_val, int 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. + * + * This comparison treats substrings of digits as numbers, so "a10" is > "a1". + */ +int +symbol_mixed_name_cmp(const symbol* p_a, + const symbol* p_b) +{ + const char* a = symbol_get_name(*p_a) ; + const char* b = symbol_get_name(*p_b) ; + int la, lb ; + + while (1) { + if (isdigit(*a) && isdigit(*b)) + { + char* as ; /* Required to stop the compiler whining */ + char* bs ; + unsigned long int na = strtoul(a, (char** restrict)&as, 10) ; + unsigned long int nb = strtoul(b, (char** restrict)&bs, 10) ; + if (na != nb) + return (na < nb) ? -1 : +1 ; + a = as ; + b = bs ; + } + else + { + if (*a != *b) + return (*a < *b) ? -1 : +1 ; + if (*a == '\0') + break ; + ++a ; + ++b ; + } + } ; + + /* Looks like the names are equal. + * But may be different lengths if have number part(s) with leading zeros, + */ + + la = symbol_get_name_len(*p_a) ; + lb = symbol_get_name_len(*p_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, +} ; |