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 #pragma ident "%Z%%M% %I% %E% SMI" 36 37 /* 38 * The following macro can be used to prototype or define a 39 * function that deletes the data of a symbol-table entry. 40 * 41 * Input: 42 * app_data void * The _new_HashTable() app_data argument. 43 * code int The Symbol::code argument. 44 * sym_data void * The Symbol::data argument to be deleted. 45 * Output: 46 * return void * The deleted data (always return NULL). 47 */ 48 #define SYM_DEL_FN(fn) void *(fn)(void *app_data, int code, void *sym_data) 49 50 /* 51 * The following macro can be used to prototype or define a 52 * function that deletes the application-data of a hash-table. 53 * 54 * Input: 55 * data void * The _new_HashTable() 'app_data' argument to be 56 * deleted. 57 * Output: 58 * return void * The deleted data (always return NULL). 59 */ 60 #define HASH_DEL_FN(fn) void *(fn)(void *app_data) 61 62 /* 63 * The following is a container for recording the context 64 * of a symbol in a manner that is independant of the particular 65 * symbol-table implementation. Each hash-table entry contains 66 * the following user supplied parameters: 67 * 68 * 1. An optional integral parameter 'code'. This is useful for 69 * enumerating a symbol or for describing what type of data 70 * or function is stored in the symbol. 71 * 72 * 2. An optional generic function pointer. This is useful for 73 * associating functions with names. The user is responsible 74 * for casting between the generic function type and the 75 * actual function type. The code field could be used to 76 * enumerate what type of function to cast to. 77 * 78 * 3. An optional generic pointer to a static or heap-allocated 79 * object. It is up to the user to cast this back to the 80 * appropriate object type. Again, the code field could be used 81 * to describe what type of object is stored there. 82 * If the object is dynamically allocated and should be discarded 83 * when the symbol is deleted from the symbol table, send a 84 * destructor function to have it deleted automatically. 85 */ 86 typedef struct { 87 char *name; /* The name of the symbol */ 88 int code; /* Application supplied integral code */ 89 void (*fn)(void); /* Application supplied generic function */ 90 void *data; /* Application supplied context data */ 91 SYM_DEL_FN(*del_fn); /* Data destructor function */ 92 } Symbol; 93 94 /* 95 * HashNode's and HashTable's are small objects. Separately allocating 96 * many such objects would normally cause memory fragmentation. To 97 * counter this, HashMemory objects are used. These contain 98 * dedicated free-lists formed from large dynamically allocated arrays 99 * of objects. One HashMemory object can be shared between multiple hash 100 * tables (within a single thread). 101 */ 102 typedef struct HashMemory HashMemory; 103 104 /* Create a free-list for allocation of hash tables and their nodes */ 105 106 HashMemory *_new_HashMemory(int hash_count, int node_count); 107 108 /* Delete a redundant free-list if not being used */ 109 110 HashMemory *_del_HashMemory(HashMemory *mem, int force); 111 112 /* 113 * Declare an alias for the private HashTable structure defined in 114 * hash.c. 115 */ 116 typedef struct HashTable HashTable; 117 118 /* 119 * Enumerate case-sensitivity options. 120 */ 121 typedef enum { 122 IGNORE_CASE, /* Ignore case when looking up symbols */ 123 HONOUR_CASE /* Honor case when looking up symbols */ 124 } HashCase; 125 126 /* Create a new hash-table */ 127 128 HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase, 129 void *app_data, HASH_DEL_FN(*del_fn)); 130 131 /* Delete a reference to a hash-table */ 132 133 HashTable *_del_HashTable(HashTable *hash); 134 135 /* Add an entry to a hash table */ 136 137 Symbol *_new_HashSymbol(HashTable *hash, const char *key, int code, 138 void (*fn)(void), void *data, SYM_DEL_FN(*del_fn)); 139 140 /* Remove and delete all the entries in a given hash table */ 141 142 int _clear_HashTable(HashTable *hash); 143 144 /* Remove and delete a given hash-table entry */ 145 146 Symbol *_del_HashSymbol(HashTable *hash, const char *key); 147 148 /* Lookup a given hash-table entry */ 149 150 Symbol *_find_HashSymbol(HashTable *hash, const char *key); 151 152 /* Execute a given function on each entry of a hash table, returning */ 153 /* before completion if the specified function returns non-zero. */ 154 155 #define HASH_SCAN_FN(fn) int (fn)(Symbol *sym, void *context) 156 157 int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context); 158 159 #endif 160