lib/libc/stdlib/hsearch_r.c

   1 /*-
   2  * Copyright (c) 2015 Nuxi, https://nuxi.nl/
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 #include <errno.h>
  28 #include <limits.h>
  29 #include <search.h>
  30 #include <stdint.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include "hsearch.h"
  35
  36 /*
  37  * Look up an unused entry in the hash table for a given hash. For this
  38  * implementation we use quadratic probing. Quadratic probing has the
  39  * advantage of preventing primary clustering.
  40  */
  41 static ENTRY *
  42 hsearch_lookup_free(struct __hsearch *hsearch, size_t hash)
  43 {
  44         size_t index, i;
  45
  46         for (index = hash, i = 0;; index += ++i) {
  47                 ENTRY *entry = &hsearch->entries[index & hsearch->index_mask];
  48                 if (entry->key == NULL)
  49                         return (entry);
  50         }
  51 }
  52
  53 /*
  54  * Computes an FNV-1a hash of the key. Depending on the pointer size, this
  55  * either uses the 32- or 64-bit FNV prime.
  56  */
  57 static size_t
  58 hsearch_hash(size_t offset_basis, const char *str)
  59 {
  60         size_t hash;
  61
  62         hash = offset_basis;
  63         while (*str != '\0') {
  64                 hash ^= (uint8_t)*str++;
  65                 if (sizeof(size_t) * CHAR_BIT <= 32)
  66                         hash *= UINT32_C(16777619);
  67                 else
  68                         hash *= UINT64_C(1099511628211);
  69         }
  70         return (hash);
  71 }
  72
  73 int
  74 hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
  75 {
  76         struct __hsearch *hsearch;
  77         ENTRY *entry, *old_entries, *new_entries;
  78         size_t hash, index, i, old_hash, old_count, new_count;
  79
  80         hsearch = htab->__hsearch;
  81         hash = hsearch_hash(hsearch->offset_basis, item.key);
  82
  83         /*
  84          * Search the hash table for an existing entry for this key.
  85          * Stop searching if we run into an unused hash table entry.
  86          */
  87         for (index = hash, i = 0;; index += ++i) {
  88                 entry = &hsearch->entries[index & hsearch->index_mask];
  89                 if (entry->key == NULL)
  90                         break;
  91                 if (strcmp(entry->key, item.key) == 0) {
  92                         *retval = entry;
  93                         return (1);
  94                 }
  95         }
  96
  97         /* Only perform the insertion if action is set to ENTER. */
  98         if (action == FIND) {
  99                 errno = ESRCH;
 100                 return (0);
 101         }
 102
 103         if (hsearch->entries_used * 2 >= hsearch->index_mask) {
 104                 /* Preserve the old hash table entries. */
 105                 old_count = hsearch->index_mask + 1;
 106                 old_entries = hsearch->entries;
 107
 108                 /*
 109                  * Allocate and install a new table if insertion would
 110                  * yield a hash table that is more than 50% used. By
 111                  * using 50% as a threshold, a lookup will only take up
 112                  * to two steps on average.
 113                  */
 114                 new_count = (hsearch->index_mask + 1) * 2;
 115                 new_entries = calloc(new_count, sizeof(ENTRY));
 116                 if (new_entries == NULL)
 117                         return (0);
 118                 hsearch->entries = new_entries;
 119                 hsearch->index_mask = new_count - 1;
 120
 121                 /* Copy over the entries from the old table to the new table. */
 122                 for (i = 0; i < old_count; ++i) {
 123                         entry = &old_entries[i];
 124                         if (entry->key != NULL) {
 125                                 old_hash = hsearch_hash(hsearch->offset_basis,
 126                                     entry->key);
 127                                 *hsearch_lookup_free(hsearch, old_hash) =
 128                                     *entry;
 129                         }
 130                 }
 131
 132                 /* Destroy the old hash table entries. */
 133                 free(old_entries);
 134
 135                 /*
 136                  * Perform a new lookup for a free table entry, so that
 137                  * we insert the entry into the new hash table.
 138                  */
 139                 hsearch = htab->__hsearch;
 140                 entry = hsearch_lookup_free(hsearch, hash);
 141         }
 142
 143         /* Insert the new entry into the hash table. */
 144         *entry = item;
 145         ++hsearch->entries_used;
 146         *retval = entry;
 147         return (1);
 148 }