1 #ifndef hash_h 2 #define hash_h 3 4 /* 5 * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd. 6 * 7 * All rights reserved. 8 * 9 * Permission is hereby granted, free of charge, to any person obtaining a 10 * copy of this software and associated documentation files (the 11 * "Software"), to deal in the Software without restriction, including 12 * without limitation the rights to use, copy, modify, merge, publish, 13 * distribute, and/or sell copies of the Software, and to permit persons 14 * to whom the Software is furnished to do so, provided that the above 15 * copyright notice(s) and this permission notice appear in all copies of 16 * the Software and that both the above copyright notice(s) and this 17 * permission notice appear in supporting documentation. 18 * 19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 20 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT 22 * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 23 * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL 24 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING 25 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 26 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION 27 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 28 * 29 * Except as contained in this notice, the name of a copyright holder 30 * shall not be used in advertising or otherwise to promote the sale, use 31 * or other dealings in this Software without prior written authorization 32 * of the copyright holder. 33 */ 34 35 /* 36 * The following macro can be used to prototype or define a 37 * function that deletes the data of a symbol-table entry. 38 * 39 * Input: 40 * app_data void * The _new_HashTable() app_data argument. 41 * code int The Symbol::code argument. 42 * sym_data void * The Symbol::data argument to be deleted. 43 * Output: 44 * return void * The deleted data (always return NULL). 45 */ 46 #define SYM_DEL_FN(fn) void *(fn)(void *app_data, int code, void *sym_data) 47 48 /* 49 * The following macro can be used to prototype or define a 50 * function that deletes the application-data of a hash-table. 51 * 52 * Input: 53 * data void * The _new_HashTable() 'app_data' argument to be 54 * deleted. 55 * Output: 56 * return void * The deleted data (always return NULL). 57 */ 58 #define HASH_DEL_FN(fn) void *(fn)(void *app_data) 59 60 /* 61 * The following is a container for recording the context 62 * of a symbol in a manner that is independant of the particular 63 * symbol-table implementation. Each hash-table entry contains 64 * the following user supplied parameters: 65 * 66 * 1. An optional integral parameter 'code'. This is useful for 67 * enumerating a symbol or for describing what type of data 68 * or function is stored in the symbol. 69 * 70 * 2. An optional generic function pointer. This is useful for 71 * associating functions with names. The user is responsible 72 * for casting between the generic function type and the 73 * actual function type. The code field could be used to 74 * enumerate what type of function to cast to. 75 * 76 * 3. An optional generic pointer to a static or heap-allocated 77 * object. It is up to the user to cast this back to the 78 * appropriate object type. Again, the code field could be used 79 * to describe what type of object is stored there. 80 * If the object is dynamically allocated and should be discarded 81 * when the symbol is deleted from the symbol table, send a 82 * destructor function to have it deleted automatically. 83 */ 84 typedef struct { 85 char *name; /* The name of the symbol */ 86 int code; /* Application supplied integral code */ 87 void (*fn)(void); /* Application supplied generic function */ 88 void *data; /* Application supplied context data */ 89 SYM_DEL_FN(*del_fn); /* Data destructor function */ 90 } Symbol; 91 92 /* 93 * HashNode's and HashTable's are small objects. Separately allocating 94 * many such objects would normally cause memory fragmentation. To 95 * counter this, HashMemory objects are used. These contain 96 * dedicated free-lists formed from large dynamically allocated arrays 97 * of objects. One HashMemory object can be shared between multiple hash 98 * tables (within a single thread). 99 */ 100 typedef struct HashMemory HashMemory; 101 102 /* Create a free-list for allocation of hash tables and their nodes */ 103 104 HashMemory *_new_HashMemory(int hash_count, int node_count); 105 106 /* Delete a redundant free-list if not being used */ 107 108 HashMemory *_del_HashMemory(HashMemory *mem, int force); 109 110 /* 111 * Declare an alias for the private HashTable structure defined in 112 * hash.c. 113 */ 114 typedef struct HashTable HashTable; 115 116 /* 117 * Enumerate case-sensitivity options. 118 */ 119 typedef enum { 120 IGNORE_CASE, /* Ignore case when looking up symbols */ 121 HONOUR_CASE /* Honor case when looking up symbols */ 122 } HashCase; 123 124 /* Create a new hash-table */ 125 126 HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase, 127 void *app_data, HASH_DEL_FN(*del_fn)); 128 129 /* Delete a reference to a hash-table */ 130 131 HashTable *_del_HashTable(HashTable *hash); 132 133 /* Add an entry to a hash table */ 134 135 Symbol *_new_HashSymbol(HashTable *hash, const char *key, int code, 136 void (*fn)(void), void *data, SYM_DEL_FN(*del_fn)); 137 138 /* Remove and delete all the entries in a given hash table */ 139 140 int _clear_HashTable(HashTable *hash); 141 142 /* Remove and delete a given hash-table entry */ 143 144 Symbol *_del_HashSymbol(HashTable *hash, const char *key); 145 146 /* Lookup a given hash-table entry */ 147 148 Symbol *_find_HashSymbol(HashTable *hash, const char *key); 149 150 /* Execute a given function on each entry of a hash table, returning */ 151 /* before completion if the specified function returns non-zero. */ 152 153 #define HASH_SCAN_FN(fn) int (fn)(Symbol *sym, void *context) 154 155 int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context); 156 157 #endif 158