rx/rxhash.c

   1 /*      Copyright (C) 1995, 1996 Tom Lord
   2  *
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU Library General Public License as published by
   5  * the Free Software Foundation; either version 2, or (at your option)
   6  * any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public License
  14  * along with this software; see the file COPYING.  If not, write to
  15  * the Free Software Foundation, 59 Temple Place - Suite 330,
  16  * Boston, MA 02111-1307, USA.
  17  */
  18
  19 \f
  20 /*
  21  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  22  */
  23 \f
  24
  25 #include "rxall.h"
  26 #include "rxhash.h"
  27
  28 \f
  29
  30 #ifdef __STDC__
  31 static struct rx_hash *
  32 default_hash_alloc (struct rx_hash_rules * rules)
  33 #else
  34 static struct rx_hash *
  35 default_hash_alloc (rules)
  36      struct rx_hash_rules * rules;
  37 #endif
  38 {
  39   return (struct rx_hash *)malloc (sizeof (struct rx_hash));
  40 }
  41
  42
  43 #ifdef __STDC__
  44 static struct rx_hash_item *
  45 default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
  46 #else
  47 static struct rx_hash_item *
  48 default_hash_item_alloc (rules, value)
  49      struct rx_hash_rules * rules;
  50      void * value;
  51 #endif
  52 {
  53   struct rx_hash_item * it;
  54   it = (struct rx_hash_item *)malloc (sizeof (*it));
  55   if (it)
  56     {
  57       it->data = value;
  58       it->binding = 0;
  59     }
  60   return it;
  61 }
  62
  63
  64 #ifdef __STDC__
  65 static void
  66 default_free_hash (struct rx_hash * tab,
  67                     struct rx_hash_rules * rules)
  68 #else
  69 static void
  70 default_free_hash (tab, rules)
  71      struct rx_hash * tab;
  72      struct rx_hash_rules * rules;
  73 #endif
  74 {
  75   free ((char *)tab);
  76 }
  77
  78
  79 #ifdef __STDC__
  80 static void
  81 default_free_hash_item (struct rx_hash_item * item,
  82                          struct rx_hash_rules * rules)
  83 #else
  84 static void
  85 default_free_hash_item (item, rules)
  86      struct rx_hash_item * item;
  87      struct rx_hash_rules * rules;
  88 #endif
  89 {
  90   free ((char *)item);
  91 }
  92
  93 #ifdef __STDC__
  94 static int
  95 default_eq (void * va, void * vb)
  96 #else
  97 static int
  98 default_eq (va, vb)
  99      void * va;
 100      void * vb;
 101 #endif
 102 {
 103   return va == vb;
 104 }
 105
 106 \f
 107
 108 #define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq)
 109 #define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc)
 110 #define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash)
 111 #define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) ? rules->hash_item_alloc : default_hash_item_alloc)
 112 #define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) ? rules->free_hash_item : default_free_hash_item)
 113
 114 \f
 115 static unsigned long rx_hash_masks[4] =
 116 {
 117   0x12488421,
 118   0x96699669,
 119   0xbe7dd7eb,
 120   0xffffffff
 121 };
 122
 123 /* hash to bucket */
 124 #define JOIN_BYTE(H, B)  (((H) + ((H) << 3) + (B)) & 0xf)
 125
 126 #define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))
 127
 128 #define BKTS 16
 129
 130 /* Hash tables */
 131 #ifdef __STDC__
 132 struct rx_hash_item *
 133 rx_hash_find (struct rx_hash * table,
 134               unsigned long hash,
 135               void * value,
 136               struct rx_hash_rules * rules)
 137 #else
 138 struct rx_hash_item *
 139 rx_hash_find (table, hash, value, rules)
 140      struct rx_hash * table;
 141      unsigned long hash;
 142      void * value;
 143      struct rx_hash_rules * rules;
 144 #endif
 145 {
 146   rx_hash_eq eq = EQ (rules);
 147   int maskc = 0;
 148   long mask = rx_hash_masks [0];
 149   int bucket = H2B(hash & mask);
 150
 151   while (RX_bitset_member (&table->nested_p, bucket))
 152     {
 153       table = (struct rx_hash *)(table->children [bucket]);
 154       ++maskc;
 155       mask = rx_hash_masks[maskc];
 156       bucket = H2B (hash & mask);
 157     }
 158
 159   {
 160     struct rx_hash_item * it;
 161     it = (struct rx_hash_item *)(table->children[bucket]);
 162     while (it)
 163       if (eq (it->data, value))
 164         return it;
 165       else
 166         it = it->next_same_hash;
 167   }
 168
 169   return 0;
 170 }
 171
 172
 173 #ifdef __STDC__
 174 static int
 175 listlen (struct rx_hash_item * bucket)
 176 #else
 177 static int
 178 listlen (bucket)
 179      struct rx_hash_item * bucket;
 180 #endif
 181 {
 182   int i;
 183   for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
 184     ;
 185   return i;
 186 }
 187
 188 #ifdef __STDC__
 189 static int
 190 overflows (struct rx_hash_item * bucket)
 191 #else
 192 static int
 193 overflows (bucket)
 194      struct rx_hash_item * bucket;
 195 #endif
 196 {
 197   return !(   bucket
 198            && bucket->next_same_hash
 199            && bucket->next_same_hash->next_same_hash
 200            && bucket->next_same_hash->next_same_hash->next_same_hash);
 201 }
 202
 203
 204 #ifdef __STDC__
 205 struct rx_hash_item *
 206 rx_hash_store (struct rx_hash * table,
 207                unsigned long hash,
 208                void * value,
 209                struct rx_hash_rules * rules)
 210 #else
 211 struct rx_hash_item *
 212 rx_hash_store (table, hash, value, rules)
 213      struct rx_hash * table;
 214      unsigned long hash;
 215      void * value;
 216      struct rx_hash_rules * rules;
 217 #endif
 218 {
 219   rx_hash_eq eq = EQ (rules);
 220   int maskc = 0;
 221   long mask = rx_hash_masks [0];
 222   int bucket = H2B(hash & mask);
 223   int depth = 0;
 224
 225   while (RX_bitset_member (&table->nested_p, bucket))
 226     {
 227       table = (struct rx_hash *)(table->children [bucket]);
 228       ++maskc;
 229       mask = rx_hash_masks[maskc];
 230       bucket = H2B(hash & mask);
 231       ++depth;
 232     }
 233
 234   {
 235     struct rx_hash_item * it;
 236     it = (struct rx_hash_item *)(table->children[bucket]);
 237     while (it)
 238       if (eq (it->data, value))
 239         return it;
 240       else
 241         it = it->next_same_hash;
 242   }
 243
 244   {
 245     if (   (depth < 3)
 246         && (overflows ((struct rx_hash_item *)table->children [bucket])))
 247       {
 248         struct rx_hash * newtab;
 249         newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
 250         if (!newtab)
 251           goto add_to_bucket;
 252         rx_bzero ((char *)newtab, sizeof (*newtab));
 253         newtab->parent = table;
 254         {
 255           struct rx_hash_item * them;
 256           unsigned long newmask;
 257           them = (struct rx_hash_item *)table->children[bucket];
 258           newmask = rx_hash_masks[maskc + 1];
 259           while (them)
 260             {
 261               struct rx_hash_item * save = them->next_same_hash;
 262               int new_buck = H2B(them->hash & newmask);
 263               them->next_same_hash = ((struct rx_hash_item *)
 264                                       newtab->children[new_buck]);
 265               ((struct rx_hash_item **)newtab->children)[new_buck] = them;
 266               them->table = newtab;
 267               them = save;
 268               ++newtab->refs;
 269               --table->refs;
 270             }
 271           ((struct rx_hash **)table->children)[bucket] = newtab;
 272           RX_bitset_enjoin (&table->nested_p, bucket);
 273           ++table->refs;
 274           table = newtab;
 275           bucket = H2B(hash & newmask);
 276         }
 277       }
 278   }
 279  add_to_bucket:
 280   {
 281     struct rx_hash_item  * it = ((struct rx_hash_item *)
 282                                  ITEM_ALLOC(rules) (rules, value));
 283     if (!it)
 284       return 0;
 285     it->hash = hash;
 286     it->table = table;
 287     /* DATA and BINDING are to be set in hash_item_alloc */
 288     it->next_same_hash = (struct rx_hash_item *)table->children [bucket];
 289     ((struct rx_hash_item **)table->children)[bucket] = it;
 290     ++table->refs;
 291     return it;
 292   }
 293 }
 294
 295
 296 #ifdef __STDC__
 297 void
 298 rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
 299 #else
 300 void
 301 rx_hash_free (it, rules)
 302      struct rx_hash_item * it;
 303      struct rx_hash_rules * rules;
 304 #endif
 305 {
 306   if (it)
 307     {
 308       struct rx_hash * table = it->table;
 309       unsigned long hash = it->hash;
 310       int depth = (table->parent
 311                    ? (table->parent->parent
 312                       ? (table->parent->parent->parent
 313                          ? 3
 314                          : 2)
 315                       : 1)
 316                    : 0);
 317       int bucket = H2B (hash & rx_hash_masks [depth]);
 318       struct rx_hash_item ** pos
 319         = (struct rx_hash_item **)&table->children [bucket];
 320
 321       while (*pos != it)
 322         pos = &(*pos)->next_same_hash;
 323       *pos = it->next_same_hash;
 324       FREE_HASH_ITEM(rules) (it, rules);
 325       --table->refs;
 326       while (!table->refs && depth)
 327         {
 328           struct rx_hash * save = table;
 329           table = table->parent;
 330           --depth;
 331           bucket = H2B(hash & rx_hash_masks [depth]);
 332           --table->refs;
 333           table->children[bucket] = 0;
 334           RX_bitset_remove (&table->nested_p, bucket);
 335           FREE_HASH (rules) (save, rules);
 336         }
 337     }
 338 }
 339
 340 #ifdef __STDC__
 341 void
 342 rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
 343                     struct rx_hash_rules * rules)
 344 #else
 345 void
 346 rx_free_hash_table (tab, freefn, rules)
 347      struct rx_hash * tab;
 348      rx_hash_freefn freefn;
 349      struct rx_hash_rules * rules;
 350 #endif
 351 {
 352   int x;
 353
 354   for (x = 0; x < BKTS; ++x)
 355     if (RX_bitset_member (&tab->nested_p, x))
 356       {
 357         rx_free_hash_table ((struct rx_hash *)tab->children[x],
 358                             freefn, rules);
 359         FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules);
 360       }
 361     else
 362       {
 363         struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x];
 364         while (them)
 365           {
 366             struct rx_hash_item * that = them;
 367             them = that->next_same_hash;
 368             freefn (that);
 369             FREE_HASH_ITEM (rules) (that, rules);
 370           }
 371       }
 372 }
 373
 374
 375
 376 #ifdef __STDC__
 377 int
 378 rx_count_hash_nodes (struct rx_hash * st)
 379 #else
 380 int
 381 rx_count_hash_nodes (st)
 382      struct rx_hash * st;
 383 #endif
 384 {
 385   int x;
 386   int count = 0;
 387   for (x = 0; x < BKTS; ++x)
 388     count += ((RX_bitset_member (&st->nested_p, x))
 389               ? rx_count_hash_nodes ((struct rx_hash *)st->children[x])
 390               : listlen ((struct rx_hash_item *)(st->children[x])));
 391
 392   return count;
 393 }
 394