xorp

hash.h

00001 #ifndef hash_h
00002 #define hash_h
00003 
00004 /*
00005  * Copyright (c) 2000, 2001 by Martin C. Shepherd.
00006  * 
00007  * All rights reserved.
00008  * 
00009  * Permission is hereby granted, free of charge, to any person obtaining a
00010  * copy of this software and associated documentation files (the
00011  * "Software"), to deal in the Software without restriction, including
00012  * without limitation the rights to use, copy, modify, merge, publish,
00013  * distribute, and/or sell copies of the Software, and to permit persons
00014  * to whom the Software is furnished to do so, provided that the above
00015  * copyright notice(s) and this permission notice appear in all copies of
00016  * the Software and that both the above copyright notice(s) and this
00017  * permission notice appear in supporting documentation.
00018  * 
00019  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
00020  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00021  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
00022  * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
00023  * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
00024  * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
00025  * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
00026  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
00027  * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00028  * 
00029  * Except as contained in this notice, the name of a copyright holder
00030  * shall not be used in advertising or otherwise to promote the sale, use
00031  * or other dealings in this Software without prior written authorization
00032  * of the copyright holder.
00033  */
00034 
00035 /*
00036  * The following macro can be used to prototype or define a
00037  * function that deletes the data of a symbol-table entry.
00038  *
00039  * Input:
00040  *  app_data void *  The _new_HashTable() app_data argument.
00041  *  code      int    The Symbol::code argument.
00042  *  sym_data void *  The Symbol::data argument to be deleted.
00043  * Output:
00044  *  return  void * The deleted data (always return NULL).
00045  */
00046 #define SYM_DEL_FN(fn) void *(fn)(void *app_data, int code, void *sym_data)
00047 
00048 /*
00049  * The following macro can be used to prototype or define a
00050  * function that deletes the application-data of a hash-table.
00051  *
00052  * Input:
00053  *  data    void * The _new_HashTable() 'app_data' argument to be
00054  *                 deleted.
00055  * Output:
00056  *  return  void * The deleted data (always return NULL).
00057  */
00058 #define HASH_DEL_FN(fn) void *(fn)(void *app_data)
00059 
00060 /*
00061  * The following is a container for recording the context
00062  * of a symbol in a manner that is independant of the particular
00063  * symbol-table implementation. Each hash-table entry contains
00064  * the following user supplied parameters:
00065  *
00066  * 1. An optional integral parameter 'code'. This is useful for
00067  *    enumerating a symbol or for describing what type of data
00068  *    or function is stored in the symbol.
00069  *
00070  * 2. An optional generic function pointer. This is useful for
00071  *    associating functions with names. The user is responsible
00072  *    for casting between the generic function type and the
00073  *    actual function type. The code field could be used to
00074  *    enumerate what type of function to cast to.
00075  *
00076  * 3. An optional generic pointer to a static or heap-allocated
00077  *    object. It is up to the user to cast this back to the
00078  *    appropriate object type. Again, the code field could be used
00079  *    to describe what type of object is stored there.
00080  *    If the object is dynamically allocated and should be discarded
00081  *    when the symbol is deleted from the symbol table, send a
00082  *    destructor function to have it deleted automatically.
00083  */
00084 typedef struct {
00085   char *name;           /* The name of the symbol */
00086   int code;             /* Application supplied integral code */
00087   void (*fn)(void);     /* Application supplied generic function */
00088   void *data;           /* Application supplied context data */
00089   SYM_DEL_FN(*del_fn);  /* Data destructor function */
00090 } Symbol;
00091 
00092 /*
00093  * HashNode's and HashTable's are small objects. Separately allocating
00094  * many such objects would normally cause memory fragmentation. To
00095  * counter this, HashMemory objects are used. These contain
00096  * dedicated free-lists formed from large dynamically allocated arrays
00097  * of objects. One HashMemory object can be shared between multiple hash
00098  * tables (within a single thread).
00099  */
00100 typedef struct HashMemory HashMemory;
00101 
00102   /* Create a free-list for allocation of hash tables and their nodes */
00103 
00104 HashMemory *_new_HashMemory(int hash_count, int node_count);
00105 
00106   /* Delete a redundant free-list if not being used */
00107 
00108 HashMemory *_del_HashMemory(HashMemory *mem, int force);
00109 
00110 /*
00111  * Declare an alias for the private HashTable structure defined in
00112  * hash.c.
00113  */
00114 typedef struct HashTable HashTable;
00115 
00116 /*
00117  * Enumerate case-sensitivity options.
00118  */
00119 typedef enum {
00120   IGNORE_CASE,     /* Ignore case when looking up symbols */
00121   HONOUR_CASE      /* Honor case when looking up symbols */
00122 } HashCase;
00123 
00124   /* Create a new hash-table */
00125 
00126 HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase,
00127              void *app_data, HASH_DEL_FN(*del_fn));
00128 
00129   /* Delete a reference to a hash-table */
00130 
00131 HashTable *_del_HashTable(HashTable *hash);
00132 
00133   /* Add an entry to a hash table */
00134 
00135 Symbol *_new_HashSymbol(HashTable *hash, const char *key, int code,
00136             void (*fn)(void), void *data, SYM_DEL_FN(*del_fn));
00137 
00138   /* Remove and delete all the entries in a given hash table */
00139 
00140 int _clear_HashTable(HashTable *hash);
00141 
00142   /* Remove and delete a given hash-table entry */
00143 
00144 Symbol *_del_HashSymbol(HashTable *hash, const char *key);
00145 
00146   /* Lookup a given hash-table entry */
00147 
00148 Symbol *_find_HashSymbol(HashTable *hash, const char *key);
00149 
00150   /* Execute a given function on each entry of a hash table, returning */
00151   /*  before completion if the specified function returns non-zero. */
00152 
00153 #define HASH_SCAN_FN(fn)  int (fn)(Symbol *sym, void *context)
00154 
00155 int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context);
00156 
00157 #endif
 All Classes Namespaces Functions Variables Typedefs Enumerations