home *** CD-ROM | disk | FTP | other *** search
/ Serving the Web / ServingTheWeb1995.disc1of1.iso / linux / slacksrce / d / libc / libc-4.6 / libc-4 / libc-linux / misc / hsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-13  |  5.8 KB  |  218 lines
  1. /* Copyright (C) 1993 Free Software Foundation, Inc.
  2.    This file is part of the GNU C Library.
  3.    Contributed by Ulrich Drepper <drepper@ira.uka.de>
  4.  
  5. The GNU C Library is free software; you can redistribute it and/or
  6. modify it under the terms of the GNU Library General Public License as
  7. published by the Free Software Foundation; either version 2 of the
  8. License, or (at your option) any later version.
  9.  
  10. The GNU C Library is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13. Library General Public License for more details.
  14.  
  15. You should have received a copy of the GNU Library General Public
  16. License along with the GNU C Library; see the file COPYING.LIB.  If
  17. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  18. Cambridge, MA 02139, USA.  */
  19.  
  20. #include <ansidecl.h>
  21. #include <malloc.h>
  22. #include <string.h>
  23.  
  24. #include <search.h>
  25.  
  26. /*
  27.  * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
  28.  * [Knuth]            The Art of Computer Programming, part 3 (6.4)
  29.  */
  30.  
  31.  
  32. /*
  33.  * We need a local static variable which contains the pointer to the
  34.  * allocated memory for the hash table. An entry in this table contains
  35.  * an ENTRY and a flag for usage.
  36.  */
  37.  
  38. typedef struct { 
  39.     int   used;
  40.     ENTRY entry;
  41. } _ENTRY;
  42.  
  43. static _ENTRY   * htable = NULL;
  44. static unsigned   hsize;
  45. static unsigned   filled;
  46.  
  47.  
  48. /* 
  49.  * For the used double hash method the table size has to be a prime. To
  50.  * correct the user given table size we need a prime test.  This trivial
  51.  * algorithm is adequate because
  52.  * a)  the code is (most probably) only called once per program run and
  53.  * b)  the number is small because the table must fit in the core
  54.  */
  55.  
  56. static int
  57. DEFUN(isprime, (number), unsigned number)
  58. {
  59.     /* no even number will be passed */
  60.     unsigned div = 3;
  61.  
  62.     while (div*div < number && number%div != 0)
  63.         div += 2;
  64.  
  65.     return number%div != 0;
  66. }
  67.  
  68.  
  69. /*
  70.  * Before using the hash table we must allocate memory for it.
  71.  * Test for an existing table are done. We allocate one element
  72.  * more as the found prime number says. This is done for more effective
  73.  * indexing as explained in the comment for the hsearch function.
  74.  * The contents of the table is zeroed, especially the field used 
  75.  * becomes zero.
  76.  */
  77.  
  78. int
  79. DEFUN(hcreate, (nel), unsigned nel)
  80. {
  81.     /* There is still another table active. Return with error. */
  82.     if (htable != NULL)
  83.     return 0;
  84.  
  85.     /* Change nel to the first prime number not smaller as nel. */
  86.     nel |= 1;      /* make odd */
  87.     while (!isprime(nel)) nel += 2;
  88.  
  89.     hsize  = nel;
  90.     filled = 0;
  91.  
  92.     /* allocate memory and zero out */
  93.     if ((htable = calloc(hsize+1, sizeof(_ENTRY))) == NULL)
  94.     return 0;
  95.  
  96.     /* everything went alright */
  97.     return 1;
  98. }
  99.  
  100.  
  101. /*
  102.  * After using the hash table it has to be destroyed. The used memory can
  103.  * be freed and the local static variable can be marked as not used.
  104.  */
  105.  
  106. void
  107. DEFUN_VOID(hdestroy)
  108. {
  109.     /* free used memory */
  110.     free(htable);
  111.  
  112.     /* the sign for an existing table is an value != NULL in htable */ 
  113.     htable = NULL;
  114. }
  115.  
  116.  
  117. /*
  118.  * This is the search function. It uses double hashing with open adressing.
  119.  * The argument item.key has to be a pointer to an zero terminated, most
  120.  * probably strings of chars. The function for generating a number of the
  121.  * strings is simple but fast. It can be replaced by a more complex function
  122.  * like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
  123.  *
  124.  * We use an trick to speed up the lookup. The table is created by hcreate
  125.  * with one more element available. This enables us to use the index zero
  126.  * special. This index will never be used because we store the first hash
  127.  * index in the field used where zero means not used. Every other value
  128.  * means used. The used field can be used as a first fast comparison for
  129.  * equality of the stored and the parameter value. This helps to prevent
  130.  * unnecessary expensive calls of strcmp.
  131.  */
  132.  
  133. ENTRY*
  134. DEFUN(hsearch, (item, action), ENTRY item AND ACTION action)
  135. {
  136.     register unsigned hval;
  137.     register unsigned hval2;
  138.     register unsigned count;
  139.     register unsigned len = strlen(item.key);
  140.     register unsigned idx;
  141.  
  142.     /*
  143.      * If table is full and another entry should be entered return with 
  144.      * error.
  145.      */
  146.     if (action == ENTER && filled == hsize) 
  147.         return NULL;
  148.       
  149.  
  150.     /* Compute an value for the given string. Perhaps use a better method. */
  151.     hval  = len;
  152.     count = len;
  153.     while (count-- > 0) {
  154.         hval <<= 4;
  155.     hval += item.key[count];
  156.     }
  157.  
  158.     /* First hash function: simply take the modul but prevent zero. */
  159.     hval %= hsize;
  160.     if (hval == 0) hval++;
  161.  
  162.     /* The first index tried. */
  163.     idx = hval;
  164.  
  165.     if (htable[idx].used) {
  166.  
  167.         /* Further action might be required according to the action value. */
  168.  
  169.         if (htable[idx].used == hval &&
  170.             strcmp(item.key, htable[idx].entry.key) == 0) {
  171.  
  172.             if (action == ENTER) 
  173.             htable[idx].entry.data = item.data;
  174.  
  175.         return &htable[idx].entry;
  176.         }
  177.  
  178.     /* Second hash function, as suggested in [Knuth] */
  179.         hval2 = 1 + hval % (hsize-2);
  180.     
  181.         do {
  182.         /* 
  183.          * Because hsize is prime this guarantees to step through all
  184.              * available indeces.
  185.          */
  186.             if (idx <= hval2)
  187.             idx = hsize+idx-hval2;
  188.         else
  189.             idx -= hval2;
  190.  
  191.             /* If entry is found use it. */
  192.             if (htable[idx].used == hval &&
  193.                 strcmp(item.key, htable[idx].entry.key) == 0) {
  194.  
  195.                 if (action == ENTER) 
  196.                 htable[idx].entry.data = item.data;
  197.  
  198.             return &htable[idx].entry;
  199.             }
  200.  
  201.  
  202.     } while (htable[idx].used);
  203.     }
  204.  
  205.     /* An empty bucket has been found. */
  206.     if (action == ENTER) {
  207.         htable[idx].used  = hval;
  208.         htable[idx].entry = item;
  209.  
  210.     filled++;
  211.  
  212.         return &htable[idx].entry;
  213.     } else
  214.         return NULL;
  215. }
  216.  
  217.  
  218.