include/ntuple/hash_table.h

0001 /*
0002  *  hash_table.h  --
0003  *  Macro implementation of a self growing hash table.
0004  *  - Keys are strings
0005  *  - Data is of type HashData ( should be a define of a typedef )
0006  *  Data is not owned by the table.
0007  *
0008  *  Original:  6-Dec-1995 15:28
0009  *
0010  *  Author:   Maarten Ballintijn <Maarten.Ballintijn@cern.ch>
0011  *
0012  *  $Id$
0013  *
0014  *  $Log$
0015  *  Revision 1.7  1996/05/14 12:23:23  maartenb
0016  *  - Fix prototypes.
0017  *
0018  *  - Fix static bool conversions
0019  *
0020  *  Revision 1.6  1996/04/23 18:37:58  maartenb
0021  *  - Add RCS keywords
0022  *
0023  *
0024  */
0025
0026 #include    "cern_types.h"
0027 #include    "qp_report.h"
0028 #include    "kuip_interface.h"
0029
0030
0031 #define KEY_FREE    ((char *) 0)
0032 #define KEY_DELETED ((char *) 1)
0033
0034 #if !defined(HASH_PREF) || !defined(HashData)
0035 #error  Please define HASH_PREF (A prefix for the datatype) and \
0036     HashData the dataype associated with the key.
0037 #endif
0038
0039 #define _HC(a,b)    a ## b
0040 #define HC(a,b)     _HC(a,b)
0041 #define _ST(a)      #a
0042 #define ST(a)       _ST(a)
0043
0044
0045 #define HashSlot    HC(HASH_PREF,_slot)
0046
0047 typedef struct {
0048     char        *fKey;
0049     HashData    fData;
0050 } HashSlot;
0051
0052
0053 #define HashTable   HC(HASH_PREF,Table)
0054 #define HashTableStruct HC(HASH_PREF,TableStruct)
0055 typedef struct {
0056     int     fBits;
0057     int     fEntries;
0058     HashSlot *  fTab;
0059 } HashTableStruct;
0060
0061 typedef HashTableStruct *HashTable;
0062
0063 #define HashNew     HC(HASH_PREF,_new)
0064 #define HashGrow    HC(HASH_PREF,_grow)
0065 #define HashHash    HC(HASH_PREF,_hash)
0066 #define HashAdd     HC(HASH_PREF,_add)
0067 #define HashRemove  HC(HASH_PREF,_remove)
0068 #define HashFind    HC(HASH_PREF,_find)
0069 #define HashDel     HC(HASH_PREF,_del)
0070
0071
0072
0073 extern HashTable
0074 HashNew( int n );
0075
0076 extern bool
0077 HashGrow( HashTable t );
0078
0079 extern void
0080 HashHash( HashTable t, const char * const key, int *h1, int *h2 );
0081
0082 extern bool
0083 HashAdd( HashTable t, char * key, HashData d );
0084
0085 extern bool
0086 HashRemove( HashTable t, char * key );
0087
0088 extern bool
0089 HashFind( HashTable t, char * key, HashData * d );
0090
0091 extern void
0092 HashDel( HashTable t );
0093
0094
0095 #if defined(HASH_IMPLEMENT)
0096
0097 #include    <ctype.h>
0098 #include    <stdlib.h>
0099
0100
0101 HashTable
0102 HashNew( int n )
0103 {
0104     HashTable   t;
0105     int     bits, size;
0106
0107     t = (HashTable) calloc( sizeof( HashTableStruct ), 1 );
0108     if ( t == 0 ) return 0;
0109
0110     for( bits=2 ; (size = (1<<bits)) < n ; bits++ ) {}
0111
0112     t->fTab = (HashSlot *) calloc( sizeof(HashSlot), size );
0113     if ( t->fTab == 0 ) {
0114         free( (void *) t );
0115         return 0;
0116     }
0117
0118     t->fBits = bits;
0119
0120     return t;
0121 }
0122
0123
0124 bool
0125 HashGrow( HashTable t )
0126 {
0127     HashSlot    *old_tab, *new_tab;
0128     int     old_size, new_size, i;
0129
0130     old_size = 1 << (t->fBits);
0131     new_size = 1 << (t->fBits + 1);
0132     new_tab = (HashSlot *) calloc( sizeof(HashSlot), new_size );
0133     if ( new_tab == 0 ) {
0134         return FALSE;
0135     }
0136
0137     old_tab = t->fTab;
0138     t->fTab = new_tab;
0139     t->fBits += 1;
0140     t->fEntries = 0;
0141
0142     for ( i=0 ; i < old_size ; i++ ) {
0143         if ( old_tab[i].fKey != KEY_DELETED &&
0144             old_tab[i].fKey != KEY_FREE
0145         ) {
0146             HashAdd( t, old_tab[i].fKey, old_tab[i].fData );
0147         }
0148     }
0149
0150     free( (void *) old_tab );
0151
0152     return TRUE;
0153 }
0154
0155
0156 void
0157 HashHash(
0158     HashTable       t,
0159     const char * const  key,
0160     int *           h1,
0161     int *           h2
0162 ) {
0163     register const char *p;
0164     register unsigned   h, g, c;
0165     int         u, m;
0166
0167     h = 0;
0168     for( p = key; *p != 0 ; p++ ) {
0169         if ( isupper(*p) )
0170             c = tolower( *p );
0171         else
0172             c = *p;
0173         h = (h << 4) + c;
0174         if ( (g = (h & 0xf0000000U)) ) {
0175             h = h ^ (g >> 24);
0176             h = h ^ g;
0177         }
0178     }
0179
0180     m =  ((1 << t->fBits ) - 1);
0181
0182     u = ( ( m - 2 - h ) % ( m - 2 ) ) | 0x1; /* make the step odd */
0183
0184     *h1 =  h & m;
0185     *h2 =  u;
0186
0187 }
0188
0189 bool
0190 HashAdd(
0191     HashTable   t,
0192     char *      key,
0193     HashData    d
0194 ) {
0195     int i, step, j, m;
0196
0197     m =  1 << t->fBits;
0198
0199     if ( t->fEntries > 0.75 * m ) {     /* auto grow */
0200         if ( ! HashGrow( t ) )
0201             return FALSE;
0202     }
0203
0204     HashHash( t, key, &i, &step );
0205     for( j=0; j < m ; j++ ) {
0206         if ( ( t->fTab[i].fKey == KEY_FREE) ||
0207             ( t->fTab[i].fKey == KEY_DELETED) ) {
0208              t->fTab[i].fKey = key;
0209              t->fTab[i].fData = d;
0210             t->fEntries += 1;
0211             return TRUE;
0212         }
0213         i = ( i + step ) % m;
0214     }
0215
0216     qp_abort( ST(HashAdd) ": Table Full ??\n" );
0217     return FALSE;/*AV: make compiler happy*/
0218 }
0219
0220
0221 bool
0222 HashRemove(
0223     HashTable   t,
0224     char *      key
0225 ) {
0226     int i, step, j, m;
0227
0228     m =  1 << t->fBits;
0229
0230     HashHash( t, key, &i, &step );
0231
0232     for( j=0; j < m ; j++ ) {
0233         if ( t->fTab[i].fKey == KEY_FREE ) {
0234             return FALSE;
0235         }
0236
0237         if ( t->fTab[i].fKey != KEY_DELETED ) {
0238             if ( strcasecmp( t->fTab[i].fKey, key ) == 0 ) {
0239                 t->fTab[i].fKey = KEY_DELETED;
0240                 t->fEntries -= 1;
0241                 return TRUE;
0242             }
0243         }
0244         i = ( i + step ) % m;
0245     }
0246     qp_abort( ST(HashRemove) ": Table Full ??\n" );
0247     return FALSE;/*AV: make compiler happy*/
0248 }
0249
0250
0251 bool
0252 HashFind( HashTable t, char * key, HashData * d )
0253 {
0254     int i, step, j, m;
0255
0256     m =  1 << t->fBits;
0257
0258     HashHash( t, key, &i, &step );
0259
0260     for( j=0; j < m ; j++ ) {
0261         if ( t->fTab[i].fKey == KEY_FREE ) {
0262             return FALSE;
0263         }
0264
0265         if ( t->fTab[i].fKey != KEY_DELETED ) {
0266             if ( strcasecmp( t->fTab[i].fKey, key ) == 0 ) {
0267                 *d = t->fTab[i].fData;
0268                 return TRUE;
0269             }
0270         }
0271         i = ( i + step ) % m;
0272     }
0273     qp_abort( ST(HashFind) ": Table Full ??\n" );
0274     return FALSE;/*AV: make compiler happy*/
0275 }
0276
0277
0278 void
0279 HashDel( HashTable t )
0280 {
0281     free( (void *) t->fTab );
0282     free( (void *) t );
0283 }
0284
0285
0286 #endif  /* defined(HASH_IMPLEMENT) */
0287
0288
0289 #undef HC
0290 #undef _HC
0291 #undef HashSlot
0292 #undef HashTable
0293 #undef HashTableStruct
0294
0295 #undef HashNew
0296 #undef HashGrow
0297 #undef HashHash
0298 #undef HashAdd
0299 #undef HashRemove
0300 #undef HashFind
0301 #undef HashDel
0302
0303 #undef HASH_PREF
0304 #undef HashData
0305 #ifdef HASH_IMPLEMENT
0306 #undef HASH_IMPLEMENT
0307 #endif