Back to index

glibc  2.9
hsearch_r.c
Go to the documentation of this file.
00001 /* Copyright (C) 1993,1995-1997,2002,2005,2007,2008
00002    Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019    02111-1307 USA.  */
00020 
00021 #include <errno.h>
00022 #include <malloc.h>
00023 #include <string.h>
00024 
00025 #include <search.h>
00026 
00027 /* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
00028    [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
00029 
00030 
00031 /* The reentrant version has no static variables to maintain the state.
00032    Instead the interface of all functions is extended to take an argument
00033    which describes the current status.  */
00034 typedef struct _ENTRY
00035 {
00036   unsigned int used;
00037   ENTRY entry;
00038 }
00039 _ENTRY;
00040 
00041 
00042 /* For the used double hash method the table size has to be a prime. To
00043    correct the user given table size we need a prime test.  This trivial
00044    algorithm is adequate because
00045    a)  the code is (most probably) called a few times per program run and
00046    b)  the number is small because the table must fit in the core  */
00047 static int
00048 isprime (unsigned int number)
00049 {
00050   /* no even number will be passed */
00051   unsigned int div = 3;
00052 
00053   while (div * div < number && number % div != 0)
00054     div += 2;
00055 
00056   return number % div != 0;
00057 }
00058 
00059 
00060 /* Before using the hash table we must allocate memory for it.
00061    Test for an existing table are done. We allocate one element
00062    more as the found prime number says. This is done for more effective
00063    indexing as explained in the comment for the hsearch function.
00064    The contents of the table is zeroed, especially the field used
00065    becomes zero.  */
00066 int
00067 hcreate_r (nel, htab)
00068      size_t nel;
00069      struct hsearch_data *htab;
00070 {
00071   /* Test for correct arguments.  */
00072   if (htab == NULL)
00073     {
00074       __set_errno (EINVAL);
00075       return 0;
00076     }
00077 
00078   /* There is still another table active. Return with error. */
00079   if (htab->table != NULL)
00080     return 0;
00081 
00082   /* Change nel to the first prime number not smaller as nel. */
00083   nel |= 1;      /* make odd */
00084   while (!isprime (nel))
00085     nel += 2;
00086 
00087   htab->size = nel;
00088   htab->filled = 0;
00089 
00090   /* allocate memory and zero out */
00091   htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY));
00092   if (htab->table == NULL)
00093     return 0;
00094 
00095   /* everything went alright */
00096   return 1;
00097 }
00098 libc_hidden_def (hcreate_r)
00099 
00100 
00101 /* After using the hash table it has to be destroyed. The used memory can
00102    be freed and the local static variable can be marked as not used.  */
00103 void
00104 hdestroy_r (htab)
00105      struct hsearch_data *htab;
00106 {
00107   /* Test for correct arguments.  */
00108   if (htab == NULL)
00109     {
00110       __set_errno (EINVAL);
00111       return;
00112     }
00113 
00114   /* Free used memory.  */
00115   free (htab->table);
00116 
00117   /* the sign for an existing table is an value != NULL in htable */
00118   htab->table = NULL;
00119 }
00120 libc_hidden_def (hdestroy_r)
00121 
00122 
00123 /* This is the search function. It uses double hashing with open addressing.
00124    The argument item.key has to be a pointer to an zero terminated, most
00125    probably strings of chars. The function for generating a number of the
00126    strings is simple but fast. It can be replaced by a more complex function
00127    like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
00128 
00129    We use an trick to speed up the lookup. The table is created by hcreate
00130    with one more element available. This enables us to use the index zero
00131    special. This index will never be used because we store the first hash
00132    index in the field used where zero means not used. Every other value
00133    means used. The used field can be used as a first fast comparison for
00134    equality of the stored and the parameter value. This helps to prevent
00135    unnecessary expensive calls of strcmp.  */
00136 int
00137 hsearch_r (item, action, retval, htab)
00138      ENTRY item;
00139      ACTION action;
00140      ENTRY **retval;
00141      struct hsearch_data *htab;
00142 {
00143   unsigned int hval;
00144   unsigned int count;
00145   unsigned int len = strlen (item.key);
00146   unsigned int idx;
00147 
00148   /* Compute an value for the given string. Perhaps use a better method. */
00149   hval = len;
00150   count = len;
00151   while (count-- > 0)
00152     {
00153       hval <<= 4;
00154       hval += item.key[count];
00155     }
00156 
00157   /* First hash function: simply take the modul but prevent zero. */
00158   idx = hval % htab->size + 1;
00159 
00160   if (htab->table[idx].used)
00161     {
00162       /* Further action might be required according to the action value. */
00163       if (htab->table[idx].used == hval
00164          && strcmp (item.key, htab->table[idx].entry.key) == 0)
00165        {
00166          *retval = &htab->table[idx].entry;
00167          return 1;
00168        }
00169 
00170       /* Second hash function, as suggested in [Knuth] */
00171       unsigned int hval2 = 1 + hval % (htab->size - 2);
00172       unsigned int first_idx = idx;
00173 
00174       do
00175        {
00176          /* Because SIZE is prime this guarantees to step through all
00177              available indeces.  */
00178           if (idx <= hval2)
00179            idx = htab->size + idx - hval2;
00180          else
00181            idx -= hval2;
00182 
00183          /* If we visited all entries leave the loop unsuccessfully.  */
00184          if (idx == first_idx)
00185            break;
00186 
00187             /* If entry is found use it. */
00188           if (htab->table[idx].used == hval
00189              && strcmp (item.key, htab->table[idx].entry.key) == 0)
00190            {
00191              *retval = &htab->table[idx].entry;
00192              return 1;
00193            }
00194        }
00195       while (htab->table[idx].used);
00196     }
00197 
00198   /* An empty bucket has been found. */
00199   if (action == ENTER)
00200     {
00201       /* If table is full and another entry should be entered return
00202         with error.  */
00203       if (htab->filled == htab->size)
00204        {
00205          __set_errno (ENOMEM);
00206          *retval = NULL;
00207          return 0;
00208        }
00209 
00210       htab->table[idx].used  = hval;
00211       htab->table[idx].entry = item;
00212 
00213       ++htab->filled;
00214 
00215       *retval = &htab->table[idx].entry;
00216       return 1;
00217     }
00218 
00219   __set_errno (ESRCH);
00220   *retval = NULL;
00221   return 0;
00222 }
00223 libc_hidden_def (hsearch_r)