contrib/top/hash.m4c

   1 /*
   2  * Copyright (c) 1984 through 2008, William LeFebvre
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  *     * Redistributions in binary form must reproduce the above
  12  * copyright notice, this list of conditions and the following disclaimer
  13  * in the documentation and/or other materials provided with the
  14  * distribution.
  15  *
  16  *     * Neither the name of William LeFebvre nor the names of other
  17  * contributors may be used to endorse or promote products derived from
  18  * this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  24  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  26  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 /* hash.m4c */
  34
  35 /* The file hash.c is generated from hash.m4c via the preprocessor M4 */
  36
  37 /*
  38  * Hash table functions:  init, add, lookup, first, next, sizeinfo.
  39  * This is a conventional "bucket hash".  The key is hashed in to a number
  40  * less than or equal to the number of buckets and the result is used
  41  * to index in to the array of buckets.  Each bucket is a linked list
  42  * that contains all the key/value pairs which hashed to that index.
  43  */
  44
  45 #include "config.h"
  46
  47 #if STDC_HEADERS
  48 #include <string.h>
  49 #include <stdlib.h>
  50 #define memzero(a, b)           memset((a), 0, (b))
  51 #else /* !STDC_HEADERS */
  52 #ifdef HAVE_MEMCPY
  53 #define memzero(a, b)           memset((a), 0, (b))
  54 #else
  55 #define memcpy(a, b, c)         bcopy((b), (a), (c))
  56 #define memzero(a, b)           bzero((a), (b))
  57 #define memcmp(a, b, c)         bcmp((a), (b), (c))
  58 #endif /* HAVE_MEMCPY */
  59 #ifdef HAVE_STRINGS_H
  60 #include <strings.h>
  61 #else
  62 #ifdef HAVE_STRING_H
  63 #include <string.h>
  64 #endif
  65 #endif
  66 void *malloc();
  67 void free();
  68 char *strdup();
  69 #endif /* !STDC_HEADERS */
  70
  71 /* After all that there are still some systems that don't have NULL defined */
  72 #ifndef NULL
  73 #define NULL 0
  74 #endif
  75
  76 #ifdef HAVE_MATH_H
  77 #include <math.h>
  78 #endif
  79
  80 #if !HAVE_PID_T
  81 typedef long pid_t;
  82 #endif
  83 #if !HAVE_ID_T
  84 typedef long id_t;
  85 #endif
  86
  87 #include "hash.h"
  88
  89 dnl # The m4 code uses MALLOC, FREE, and STRDUP for dynamic allocation.
  90 dnl # You can change what these get mapped to here:
  91
  92 define(`MALLOC', `malloc($1)')
  93 define(`FREE', `free($1)')
  94 define(`STRDUP', `strdup($1)')
  95
  96 static int
  97 next_prime(int x)
  98
  99 {
 100     double i, j;
 101     int f;
 102
 103     i = x;
 104     while (i++)
 105     {
 106         f=1;
 107         for (j=2; j<i; j++)
 108         {
 109             if ((i/j)==floor(i/j))
 110             {
 111                 f=0;
 112                 break;
 113             }
 114         }
 115         if (f)
 116         {
 117             return (int)i;
 118         }
 119     }
 120     return 1;
 121 }
 122
 123 /* string hashes */
 124
 125 static int
 126 string_hash(hash_table *ht, char *key)
 127
 128 {
 129     unsigned long s = 0;
 130     unsigned char ch;
 131     int shifting = 24;
 132
 133     while ((ch = (unsigned char)*key++) != '\0')
 134     {
 135         if (shifting == 0)
 136         {
 137             s = s + ch;
 138             shifting = 24;
 139         }
 140         else
 141         {
 142             s = s + (ch << shifting);
 143             shifting -= 8;
 144         }
 145     }
 146
 147     return (s % ht->num_buckets);
 148 }
 149
 150 void ll_init(llist *q)
 151
 152 {
 153     q->head = NULL;
 154     q->count = 0;
 155 }
 156
 157 llistitem *ll_newitem(int size)
 158
 159 {
 160     llistitem *qi;
 161
 162     qi = (llistitem *)MALLOC(sizeof(llistitem) + size);
 163     qi->datum = ((void *)qi + sizeof(llistitem));
 164     return qi;
 165 }
 166
 167 void ll_freeitem(llistitem *li)
 168
 169 {
 170     FREE(li);
 171 }
 172
 173 void ll_add(llist *q, llistitem *new)
 174
 175 {
 176     new->next = q->head;
 177     q->head = new;
 178     q->count++;
 179 }
 180
 181 void ll_extract(llist *q, llistitem *qi, llistitem *last)
 182
 183 {
 184     if (last == NULL)
 185     {
 186         q->head = qi->next;
 187     }
 188     else
 189     {
 190         last->next = qi->next;
 191     }
 192     qi->next = NULL;
 193     q->count--;
 194 }
 195
 196 #define LL_FIRST(q) ((q)->head)
 197 llistitem *
 198 ll_first(llist *q)
 199
 200 {
 201     return q->head;
 202 }
 203
 204 #define LL_NEXT(q, qi)  ((qi) != NULL ? (qi)->next : NULL)
 205 llistitem *
 206 ll_next(llist *q, llistitem *qi)
 207
 208 {
 209     return (qi != NULL ? qi->next : NULL);
 210 }
 211
 212 #define LL_ISEMPTY(ll)  ((ll)->count == 0)
 213 int
 214 ll_isempty(llist *ll)
 215
 216 {
 217     return (ll->count == 0);
 218 }
 219
 220 /*
 221  * hash_table *hash_create(int num)
 222  *
 223  * Creates a hash table structure with at least "num" buckets.
 224  */
 225
 226 hash_table *
 227 hash_create(int num)
 228
 229 {
 230     hash_table *result;
 231     bucket_t *b;
 232     int bytes;
 233     int i;
 234
 235     /* create the resultant structure */
 236     result = (hash_table *)MALLOC(sizeof(hash_table));
 237
 238     /* adjust bucket count to be prime */
 239     num = next_prime(num);
 240
 241     /* create the buckets */
 242     bytes = sizeof(bucket_t) * num;
 243     result->buckets = b = (bucket_t *)MALLOC(bytes);
 244     result->num_buckets = num;
 245
 246     /* create each bucket as a linked list */
 247     i = num;
 248     while (--i >= 0)
 249     {
 250         ll_init(&(b->list));
 251         b++;
 252     }
 253
 254     return result;
 255 }
 256
 257 /*
 258  * unsigned int hash_count(hash_table *ht)
 259  *
 260  * Return total number of elements contained in hash table.
 261  */
 262
 263 unsigned int
 264 hash_count(hash_table *ht)
 265
 266 {
 267     register int i = 0;
 268     register int cnt = 0;
 269     register bucket_t *bucket;
 270
 271     bucket = ht->buckets;
 272     while (i++ < ht->num_buckets)
 273     {
 274         cnt += bucket->list.count;
 275         bucket++;
 276     }
 277
 278     return cnt;
 279 }
 280
 281 /*
 282  * void hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
 283  *
 284  * Fill in "sizes" with information about bucket lengths in hash
 285  * table "max".
 286  */
 287
 288 void
 289 hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
 290
 291 {
 292     register int i;
 293     register int idx;
 294     register bucket_t *bucket;
 295
 296     memzero(sizes, max * sizeof(unsigned int));
 297
 298     bucket = ht->buckets;
 299     i = 0;
 300     while (i++ < ht->num_buckets)
 301     {
 302         idx = bucket->list.count;
 303         sizes[idx >= max ? max-1 : idx]++;
 304         bucket++;
 305     }
 306 }
 307
 308 dnl # HASH_TABLE_TMPL(suffix, keytype, to_hash, to_cmp, to_alloc, to_free)
 309 dnl #
 310 dnl # This generates hash table functions suitable for keys
 311 dnl # of type "keytype".  The function names all end with "suffix".
 312 dnl # "to_hash" is an expression that generates a hash index (this
 313 dnl # expression can include key and ht).  "to_cmp" is an expression
 314 dnl # that compares "key" to "k1".  "to_alloc" is an expression that
 315 dnl # allocates space for "key", or empty if no allocation is needed.
 316 dnl # "to_free" is an expression that frees "key", or empty if no
 317 dnl # allocation is needed.
 318
 319 define(`HASH_TABLE_TMPL', `
 320
 321 /*
 322  * void hash_add_$1(hash_table *ht, $2 key, void *value)
 323  *
 324  * Add an element to table "ht".  The element is described by
 325  * "key" and "value".  Return NULL on success.  If the key
 326  * already exists in the table, then no action is taken and
 327  * the data for the existing element is returned.
 328  * Key type is $2
 329  */
 330
 331 void *
 332 hash_add_$1(hash_table *ht, $2 key, void *value)
 333
 334 {
 335     bucket_t *bucket;
 336     hash_item_$1 *hi;
 337     hash_item_$1 *h;
 338     llist *ll;
 339     llistitem *li;
 340     llistitem *newli;
 341     $2 k1;
 342
 343     /* allocate the space we will need */
 344     newli = ll_newitem(sizeof(hash_item_$1));
 345     hi = (hash_item_$1 *)newli->datum;
 346
 347     /* fill in the values */
 348     hi->key = ifelse($5, , key, $5);
 349     hi->value = value;
 350
 351     /* hash to the bucket */
 352     bucket = &(ht->buckets[$3]);
 353
 354     /* walk the list to make sure we do not have a duplicate */
 355     ll = &(bucket->list);
 356     li = LL_FIRST(ll);
 357     while (li != NULL)
 358     {
 359         h = (hash_item_$1 *)li->datum;
 360         k1 = h->key;
 361         if ($4)
 362         {
 363             /* found one */
 364             break;
 365         }
 366         li = LL_NEXT(ll, li);
 367     }
 368     li = NULL;
 369
 370     /* is there already one there? */
 371     if (li == NULL)
 372     {
 373         /* add the unique element to the buckets list */
 374         ll_add(&(bucket->list), newli);
 375         return NULL;
 376     }
 377     else
 378     {
 379         /* free the stuff we just allocated */
 380         ll_freeitem(newli);
 381         return ((hash_item_$1 *)(li->datum))->value;
 382     }
 383 }
 384
 385 /*
 386  * void *hash_replace_$1(hash_table *ht, $2 key, void *value)
 387  *
 388  * Replace an existing value in the hash table with a new one and
 389  * return the old value.  If the key does not already exist in
 390  * the hash table, add a new element and return NULL.
 391  * Key type is $2
 392  */
 393
 394 void *
 395 hash_replace_$1(hash_table *ht, $2 key, void *value)
 396
 397 {
 398     bucket_t *bucket;
 399     hash_item_$1 *hi;
 400     llist *ll;
 401     llistitem *li;
 402     void *result = NULL;
 403     $2 k1;
 404
 405     /* find the bucket */
 406     bucket = &(ht->buckets[$3]);
 407
 408     /* walk the list until we find the existing item */
 409     ll = &(bucket->list);
 410     li = LL_FIRST(ll);
 411     while (li != NULL)
 412     {
 413         hi = (hash_item_$1 *)li->datum;
 414         k1 = hi->key;
 415         if ($4)
 416         {
 417             /* found it: now replace the value with the new one */
 418             result = hi->value;
 419             hi->value = value;
 420             break;
 421         }
 422         li = LL_NEXT(ll, li);
 423     }
 424
 425     /* if the element wasnt found, add it */
 426     if (result == NULL)
 427     {
 428         li = ll_newitem(sizeof(hash_item_$1));
 429         hi = (hash_item_$1 *)li->datum;
 430         hi->key = ifelse($5, , key, $5);
 431         hi->value = value;
 432         ll_add(&(bucket->list), li);
 433     }
 434
 435     /* return the old value (so it can be freed) */
 436     return result;
 437 }
 438
 439 /*
 440  * void *hash_lookup_$1(hash_table *ht, $2 key)
 441  *
 442  * Look up "key" in "ht" and return the associated value.  If "key"
 443  * is not found, return NULL.  Key type is $2
 444  */
 445
 446 void *
 447 hash_lookup_$1(hash_table *ht, $2 key)
 448
 449 {
 450     bucket_t *bucket;
 451     llist *ll;
 452     llistitem *li;
 453     hash_item_$1 *h;
 454     void *result;
 455     $2 k1;
 456
 457     result = NULL;
 458     if ((bucket = &(ht->buckets[$3])) != NULL)
 459     {
 460         ll = &(bucket->list);
 461         li = LL_FIRST(ll);
 462         while (li != NULL)
 463         {
 464             h = (hash_item_$1 *)li->datum;
 465             k1 = h->key;
 466             if ($4)
 467             {
 468                 result = h->value;
 469                 break;
 470             }
 471             li = LL_NEXT(ll, li);
 472         }
 473     }
 474     return result;
 475 }
 476
 477 /*
 478  * void *hash_remove_$1(hash_table *ht, $2 key)
 479  *
 480  * Remove the element associated with "key" from the hash table
 481  * "ht".  Return the value or NULL if the key was not found.
 482  */
 483
 484 void *
 485 hash_remove_$1(hash_table *ht, $2 key)
 486
 487 {
 488     bucket_t *bucket;
 489     llist *ll;
 490     llistitem *li;
 491     llistitem *lilast;
 492     hash_item_$1 *hi;
 493     void *result;
 494     $2 k1;
 495
 496     result = NULL;
 497     if ((bucket = &(ht->buckets[$3])) != NULL)
 498     {
 499         ll = &(bucket->list);
 500         li = LL_FIRST(ll);
 501         lilast = NULL;
 502         while (li != NULL)
 503         {
 504             hi = (hash_item_$1 *)li->datum;
 505             k1 = hi->key;
 506             if ($4)
 507             {
 508                 ll_extract(ll, li, lilast);
 509                 result = hi->value;
 510                 key = hi->key;
 511                 $6;
 512                 ll_freeitem(li);
 513                 break;
 514             }
 515             lilast = li;
 516             li = LL_NEXT(ll, li);
 517         }
 518     }
 519     return result;
 520 }
 521
 522 /*
 523  * hash_item_$1 *hash_first_$1(hash_table *ht, hash_pos *pos)
 524  *
 525  * First function to call when iterating through all items in the hash
 526  * table.  Returns the first item in "ht" and initializes "*pos" to track
 527  * the current position.
 528  */
 529
 530 hash_item_$1 *
 531 hash_first_$1(hash_table *ht, hash_pos *pos)
 532
 533 {
 534     /* initialize pos for first item in first bucket */
 535     pos->num_buckets = ht->num_buckets;
 536     pos->hash_bucket = ht->buckets;
 537     pos->curr = 0;
 538     pos->ll_last = NULL;
 539
 540     /* find the first non-empty bucket */
 541     while(pos->hash_bucket->list.count == 0)
 542     {
 543         pos->hash_bucket++;
 544         if (++pos->curr >= pos->num_buckets)
 545         {
 546             return NULL;
 547         }
 548     }
 549
 550     /* set and return the first item */
 551     pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
 552     return (hash_item_$1 *)pos->ll_item->datum;
 553 }
 554
 555
 556 /*
 557  * hash_item_$1 *hash_next_$1(hash_pos *pos)
 558  *
 559  * Return the next item in the hash table, using "pos" as a description
 560  * of the present position in the hash table.  "pos" also identifies the
 561  * specific hash table.  Return NULL if there are no more elements.
 562  */
 563
 564 hash_item_$1 *
 565 hash_next_$1(hash_pos *pos)
 566
 567 {
 568     llistitem *li;
 569
 570     /* move item to last and check for NULL */
 571     if ((pos->ll_last = pos->ll_item) == NULL)
 572     {
 573         /* are we really at the end of the hash table? */
 574         if (pos->curr >= pos->num_buckets)
 575         {
 576             /* yes: return NULL */
 577             return NULL;
 578         }
 579         /* no: regrab first item in current bucket list (might be NULL) */
 580         li = LL_FIRST(&(pos->hash_bucket->list));
 581     }
 582     else
 583     {
 584         /* get the next item in the llist */
 585         li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
 586     }
 587
 588     /* if its NULL we have to find another bucket */
 589     while (li == NULL)
 590     {
 591         /* locate another bucket */
 592         pos->ll_last = NULL;
 593
 594         /* move to the next one */
 595         pos->hash_bucket++;
 596         if (++pos->curr >= pos->num_buckets)
 597         {
 598             /* at the end of the hash table */
 599             pos->ll_item = NULL;
 600             return NULL;
 601         }
 602
 603         /* get the first element (might be NULL) */
 604         li = LL_FIRST(&(pos->hash_bucket->list));
 605     }
 606
 607     /* li is the next element to dish out */
 608     pos->ll_item = li;
 609     return (hash_item_$1 *)li->datum;
 610 }
 611
 612 /*
 613  * void *hash_remove_pos_$1(hash_pos *pos)
 614  *
 615  * Remove the hash table entry pointed to by position marker "pos".
 616  * The data from the entry is returned upon success, otherwise NULL.
 617  */
 618
 619
 620 void *
 621 hash_remove_pos_$1(hash_pos *pos)
 622
 623 {
 624     llistitem *li;
 625     void *ans;
 626     hash_item_$1 *hi;
 627     $2 key;
 628
 629     /* sanity checks */
 630     if (pos == NULL || pos->ll_last == pos->ll_item)
 631     {
 632         return NULL;
 633     }
 634
 635     /* at this point pos contains the item to remove (ll_item)
 636        and its predecesor (ll_last) */
 637     /* extract the item from the llist */
 638     li = pos->ll_item;
 639     ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
 640
 641     /* retain the data */
 642     hi = (hash_item_$1 *)li->datum;
 643     ans = hi->value;
 644
 645     /* free up the space */
 646     key = hi->key;
 647     $6;
 648     ll_freeitem(li);
 649
 650     /* back up to previous item */
 651     /* its okay for ll_item to be null: hash_next will detect it */
 652     pos->ll_item = pos->ll_last;
 653
 654     return ans;
 655 }
 656 ')
 657
 658 dnl # create hash talbe functions for unsigned int and for strings */
 659
 660 HASH_TABLE_TMPL(`uint', `unsigned int', `(key % ht->num_buckets)', `key == k1', ,)
 661 HASH_TABLE_TMPL(`pid', `pid_t', `(key % ht->num_buckets)', `key == k1', ,)
 662 HASH_TABLE_TMPL(`string', `char *', `string_hash(ht, key)', `strcmp(key, k1) == 0', `STRDUP(key)', `FREE(key)')
 663 HASH_TABLE_TMPL(`pidthr', `pidthr_t', `((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)', `(key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)', ,)
 664 #if HAVE_LWPID_T
 665 HASH_TABLE_TMPL(`lwpid', `lwpid_t', `(key % ht->num_buckets)', `key == k1', ,)
 666 #endif