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 __FBSDID("$FreeBSD$");
  28
  29 #include <errno.h>
  30 #include <limits.h>
  31 #include <search.h>
  32 #include <stdint.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include "hsearch.h"
  37
  38 /*
  39  * Look up an unused entry in the hash table for a given hash. For this
  40  * implementation we use quadratic probing. Quadratic probing has the
  41  * advantage of preventing primary clustering.
  42  */
  43 static ENTRY *
  44 hsearch_lookup_free(struct __hsearch *hsearch, size_t hash)
  45 {
  46         size_t index, i;
  47
  48         for (index = hash, i = 0;; index += ++i) {
  49                 ENTRY *entry = &hsearch->entries[index & hsearch->index_mask];
  50                 if (entry->key == NULL)
  51                         return (entry);
  52         }
  53 }
  54
  55 /*
  56  * Computes an FNV-1a hash of the key. Depending on the pointer size, this
  57  * either uses the 32- or 64-bit FNV prime.
  58  */
  59 static size_t
  60 hsearch_hash(size_t offset_basis, const char *str)
  61 {
  62         size_t hash;
  63
  64         hash = offset_basis;
  65         while (*str != '\0') {
  66                 hash ^= (uint8_t)*str++;
  67                 if (sizeof(size_t) * CHAR_BIT <= 32)
  68                         hash *= UINT32_C(16777619);
  69                 else
  70                         hash *= UINT64_C(1099511628211);
  71         }
  72         return (hash);
  73 }
  74
  75 int
  76 hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
  77 {
  78         struct __hsearch *hsearch;
  79         ENTRY *entry, *old_entries, *new_entries;
  80         size_t hash, index, i, old_hash, old_count, new_count;
  81
  82         hsearch = htab->__hsearch;
  83         hash = hsearch_hash(hsearch->offset_basis, item.key);
  84
  85         /*
  86          * Search the hash table for an existing entry for this key.
  87          * Stop searching if we run into an unused hash table entry.
  88          */
  89         for (index = hash, i = 0;; index += ++i) {
  90                 entry = &hsearch->entries[index & hsearch->index_mask];
  91                 if (entry->key == NULL)
  92                         break;
  93                 if (strcmp(entry->key, item.key) == 0) {
  94                         *retval = entry;
  95                         return (1);
  96                 }
  97         }
  98
  99         /* Only perform the insertion if action is set to ENTER. */
 100         if (action == FIND) {
 101                 errno = ESRCH;
 102                 return (0);
 103         }
 104
 105         if (hsearch->entries_used * 2 >= hsearch->index_mask) {
 106                 /* Preserve the old hash table entries. */
 107                 old_count = hsearch->index_mask + 1;
 108                 old_entries = hsearch->entries;
 109
 110                 /*
 111                  * Allocate and install a new table if insertion would
 112                  * yield a hash table that is more than 50% used. By
 113                  * using 50% as a threshold, a lookup will only take up
 114                  * to two steps on average.
 115                  */
 116                 new_count = (hsearch->index_mask + 1) * 2;
 117                 new_entries = calloc(new_count, sizeof(ENTRY));
 118                 if (new_entries == NULL)
 119                         return (0);
 120                 hsearch->entries = new_entries;
 121                 hsearch->index_mask = new_count - 1;
 122
 123                 /* Copy over the entries from the old table to the new table. */
 124                 for (i = 0; i < old_count; ++i) {
 125                         entry = &old_entries[i];
 126                         if (entry->key != NULL) {
 127                                 old_hash = hsearch_hash(hsearch->offset_basis,
 128                                     entry->key);
 129                                 *hsearch_lookup_free(hsearch, old_hash) =
 130                                     *entry;
 131                         }
 132                 }
 133
 134                 /* Destroy the old hash table entries. */
 135                 free(old_entries);
 136
 137                 /*
 138                  * Perform a new lookup for a free table entry, so that
 139                  * we insert the entry into the new hash table.
 140                  */
 141                 hsearch = htab->__hsearch;
 142                 entry = hsearch_lookup_free(hsearch, hash);
 143         }
 144
 145         /* Insert the new entry into the hash table. */
 146         *entry = item;
 147         ++hsearch->entries_used;
 148         *retval = entry;
 149         return (1);
 150 }