1: /* Copyright (C) 1993,1995-1997,2002,2005,2007 Free Software Foundation, Inc.
    2:    This file is part of the GNU C Library.
    3:    Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
    4: 
    5:    The GNU C Library is free software; you can redistribute it and/or
    6:    modify it under the terms of the GNU Lesser General Public
    7:    License as published by the Free Software Foundation; either
    8:    version 2.1 of the 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:    Lesser General Public License for more details.
   14: 
   15:    You should have received a copy of the GNU Lesser General Public
   16:    License along with the GNU C Library; if not, write to the Free
   17:    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   18:    02111-1307 USA.  */
   19: 
   20: #include <errno.h>
   21: #include <malloc.h>
   22: #include <string.h>
   23: 
   24: #include <search.h>
   25: 
   26: /* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
   27:    [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
   28: 
   29: 
   30: /* The reentrant version has no static variables to maintain the state.
   31:    Instead the interface of all functions is extended to take an argument
   32:    which describes the current status.  */
   33: typedef struct _ENTRY
   34: {
   35:   unsigned int used;
   36:   ENTRY entry;
   37: }
   38: _ENTRY;
   39: 
   40: 
   41: /* For the used double hash method the table size has to be a prime. To
   42:    correct the user given table size we need a prime test.  This trivial
   43:    algorithm is adequate because
   44:    a)  the code is (most probably) called a few times per program run and
   45:    b)  the number is small because the table must fit in the core  */
   46: static int
   47: isprime (unsigned int number)
   48: {
   49:   /* no even number will be passed */
   50:   unsigned int div = 3;
   51: 
   52:   while (div * div < number && number % div != 0)
   53:     div += 2;
   54: 
   55:   return number % div != 0;
   56: }
   57: 
   58: 
   59: /* Before using the hash table we must allocate memory for it.
   60:    Test for an existing table are done. We allocate one element
   61:    more as the found prime number says. This is done for more effective
   62:    indexing as explained in the comment for the hsearch function.
   63:    The contents of the table is zeroed, especially the field used
   64:    becomes zero.  */
   65: int
   66: hcreate_r (nel, htab)
   67:      size_t nel;
   68:      struct hsearch_data *htab;
   69: {
   70:   /* Test for correct arguments.  */
   71:   if (htab == NULL)
   72:     {
   73:       __set_errno (EINVAL);
   74:       return 0;
   75:     }
   76: 
   77:   /* There is still another table active. Return with error. */
   78:   if (htab->table != NULL)
   79:     return 0;
   80: 
   81:   /* Change nel to the first prime number not smaller as nel. */
   82:   nel |= 1;      /* make odd */
   83:   while (!isprime (nel))
   84:     nel += 2;
   85: 
   86:   htab->size = nel;
   87:   htab->filled = 0;
   88: 
   89:   /* allocate memory and zero out */
   90:   htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY));
   91:   if (htab->table == NULL)
   92:     return 0;
   93: 
   94:   /* everything went alright */
   95:   return 1;
   96: }
   97: libc_hidden_def (hcreate_r)
   98: 
   99: 
  100: /* After using the hash table it has to be destroyed. The used memory can
  101:    be freed and the local static variable can be marked as not used.  */
  102: void
  103: hdestroy_r (htab)
  104:      struct hsearch_data *htab;
  105: {
  106:   /* Test for correct arguments.  */
  107:   if (htab == NULL)
  108:     {
  109:       __set_errno (EINVAL);
  110:       return;
  111:     }
  112: 
  113:   /* Free used memory.  */
  114:   free (htab->table);
  115: 
  116:   /* the sign for an existing table is an value != NULL in htable */
  117:   htab->table = NULL;
  118: }
  119: libc_hidden_def (hdestroy_r)
  120: 
  121: 
  122: /* This is the search function. It uses double hashing with open addressing.
  123:    The argument item.key has to be a pointer to an zero terminated, most
  124:    probably strings of chars. The function for generating a number of the
  125:    strings is simple but fast. It can be replaced by a more complex function
  126:    like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
  127: 
  128:    We use an trick to speed up the lookup. The table is created by hcreate
  129:    with one more element available. This enables us to use the index zero
  130:    special. This index will never be used because we store the first hash
  131:    index in the field used where zero means not used. Every other value
  132:    means used. The used field can be used as a first fast comparison for
  133:    equality of the stored and the parameter value. This helps to prevent
  134:    unnecessary expensive calls of strcmp.  */
  135: int
  136: hsearch_r (item, action, retval, htab)
  137:      ENTRY item;
  138:      ACTION action;
  139:      ENTRY **retval;
  140:      struct hsearch_data *htab;
  141: {
  142:   unsigned int hval;
  143:   unsigned int count;
  144:   unsigned int len = strlen (item.key);
  145:   unsigned int idx;
  146: 
  147:   /* Compute an value for the given string. Perhaps use a better method. */
  148:   hval = len;
  149:   count = len;
  150:   while (count-- > 0)
  151:     {
  152:       hval <<= 4;
  153:       hval += item.key[count];
  154:     }
  155: 
  156:   /* First hash function: simply take the modul but prevent zero. */
  157:   hval %= htab->size;
  158:   if (hval == 0)
  159:     ++hval;
  160: 
  161:   /* The first index tried. */
  162:   idx = hval;
  163: 
  164:   if (htab->table[idx].used)
  165:     {
  166:       /* Further action might be required according to the action value. */
  167:       unsigned hval2;
  168: 
  169:       if (htab->table[idx].used == hval
  170:           && strcmp (item.key, htab->table[idx].entry.key) == 0)
  171:         {
  172:           *retval = &htab->table[idx].entry;
  173:           return 1;
  174:         }
  175: 
  176:       /* Second hash function, as suggested in [Knuth] */
  177:       hval2 = 1 + hval % (htab->size - 2);
  178: 
  179:       do
  180:         {
  181:           /* Because SIZE is prime this guarantees to step through all
  182:              available indeces.  */
  183:           if (idx <= hval2)
  184:             idx = htab->size + idx - hval2;
  185:           else
  186:             idx -= hval2;
  187: 
  188:           /* If we visited all entries leave the loop unsuccessfully.  */
  189:           if (idx == hval)
  190:             break;
  191: 
  192:             /* If entry is found use it. */
  193:           if (htab->table[idx].used == hval
  194:               && strcmp (item.key, htab->table[idx].entry.key) == 0)
  195:             {
  196:               *retval = &htab->table[idx].entry;
  197:               return 1;
  198:             }
  199:         }
  200:       while (htab->table[idx].used);
  201:     }
  202: 
  203:   /* An empty bucket has been found. */
  204:   if (action == ENTER)
  205:     {
  206:       /* If table is full and another entry should be entered return
  207:          with error.  */
  208:       if (htab->filled == htab->size)
  209:         {
  210:           __set_errno (ENOMEM);
  211:           *retval = NULL;
  212:           return 0;
  213:         }
  214: 
  215:       htab->table[idx].used  = hval;
  216:       htab->table[idx].entry = item;
  217: 
  218:       ++htab->filled;
  219: 
  220:       *retval = &htab->table[idx].entry;
  221:       return 1;
  222:     }
  223: 
  224:   __set_errno (ESRCH);
  225:   *retval = NULL;
  226:   return 0;
  227: }
  228: libc_hidden_def (hsearch_r)