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