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