-/* hash - implement simple hashing table with string based keys.
- Copyright (C) 1994, 1995, 1996 Free Software Foundation, Inc.
+/* Implement simple hashing table with string based keys.
+ Copyright (C) 1994-2015 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; version 2 of the License, or
+ (at your option) any later version.
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, see <http://www.gnu.org/licenses/>. */
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
+#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include <stdint.h>
#include <sys/types.h>
-#if HAVE_OBSTACK
-# include <obstack.h>
-#else
-# include "obstack.h"
-#endif
+#include <obstack.h>
#ifdef HAVE_VALUES_H
# include <values.h>
#include "simple-hash.h"
-#define obstack_chunk_alloc xmalloc
+#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
#ifndef BITSPERBYTE
# define BITSPERBYTE 8
#endif
-#ifndef LONGBITS
-# define LONGBITS (sizeof (long) * BITSPERBYTE)
-#endif
-
#ifndef bcopy
# define bcopy(s, d, n) memcpy ((d), (s), (n))
#endif
-void *xmalloc __P ((size_t __n));
+#define hashval_t uint32_t
+#include "hashval.h"
+
+#include <programs/xmalloc.h>
typedef struct hash_entry
{
hash_entry;
/* Prototypes for local functions. */
-static void insert_entry_2 __P ((hash_table *htab, const void *key,
- size_t keylen, unsigned long hval,
- size_t idx, void *data));
-static size_t lookup __P ((hash_table *htab, const void *key, size_t keylen,
- unsigned long int hval));
-static size_t lookup_2 __P ((hash_table *htab, const void *key,
- size_t keylen, unsigned long int hval));
-static unsigned long compute_hashval __P ((const void *key, size_t keylen));
-static int is_prime __P ((unsigned long int candidate));
+static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
+ unsigned long hval, size_t idx, void *data);
+static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
+ unsigned long int hval);
+static int is_prime (unsigned long int candidate);
int
htab->size = init_size;
htab->filled = 0;
htab->first = NULL;
- htab->table = (void *) xmalloc ((init_size + 1) * sizeof (hash_entry));
+ htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
if (htab->table == NULL)
return -1;
- memset (htab->table, '\0', (init_size + 1) * sizeof (hash_entry));
obstack_init (&htab->mem_pool);
return 0;
if ((hash_entry *) htab->first == NULL)
{
table[idx].next = &table[idx];
- *(hash_entry **) &htab->first = &table[idx];
+ htab->first = &table[idx];
}
else
{
table[idx].next = ((hash_entry *) htab->first)->next;
((hash_entry *) htab->first)->next = &table[idx];
- *(hash_entry **) &htab->first = &table[idx];
+ htab->first = &table[idx];
}
++htab->filled;
- if (100 * htab->filled > 90 * htab->size)
+ if (100 * htab->filled > 75 * htab->size)
{
- /* Table is filled more than 90%. Resize the table. */
+ /* Table is filled more than 75%. Resize the table.
+ Experiments have shown that for best performance, this threshold
+ must lie between 40% and 85%. */
unsigned long int old_size = htab->size;
htab->size = next_prime (htab->size * 2);
htab->filled = 0;
htab->first = NULL;
- htab->table = (void *) xmalloc ((1 + htab->size)
- * sizeof (hash_entry));
- memset (htab->table, '\0', (1 + htab->size) * sizeof (hash_entry));
+ htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
for (idx = 1; idx <= old_size; ++idx)
if (table[idx].used)
insert_entry_2 (htab, table[idx].key, table[idx].keylen,
table[idx].used,
- lookup_2 (htab, table[idx].key, table[idx].keylen,
- table[idx].used),
+ lookup (htab, table[idx].key, table[idx].keylen,
+ table[idx].used),
table[idx].data);
free (table);
int
find_entry (htab, key, keylen, result)
- hash_table *htab;
+ const hash_table *htab;
const void *key;
size_t keylen;
void **result;
int
iterate_table (htab, ptr, key, keylen, data)
- hash_table *htab;
+ const hash_table *htab;
void **ptr;
const void **key;
size_t *keylen;
}
-static size_t
-lookup (htab, key, keylen, hval)
- hash_table *htab;
- const void *key;
- size_t keylen;
- unsigned long hval;
-{
- unsigned long hash;
- size_t idx;
- hash_entry *table = (hash_entry *) htab->table;
-
- /* First hash function: simply take the modul but prevent zero. */
- hash = 1 + hval % htab->size;
-
- idx = hash;
-
- if (table[idx].used)
- {
- if (table[idx].used == hval && table[idx].keylen == keylen
- && memcmp (key, table[idx].key, keylen) == 0)
- return idx;
-
- /* Second hash function as suggested in [Knuth]. */
- hash = 1 + hval % (htab->size - 2);
-
- do
- {
- if (idx <= hash)
- idx = htab->size + idx - hash;
- else
- idx -= hash;
-
- /* If entry is found use it. */
- if (table[idx].used == hval && table[idx].keylen == keylen
- && memcmp (key, table[idx].key, keylen) == 0)
- return idx;
- }
- while (table[idx].used);
- }
- return idx;
-}
-
-
/* References:
[Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
[Knuth] The Art of Computer Programming, part3 (6.4) */
static size_t
-lookup_2 (htab, key, keylen, hval)
- hash_table *htab;
+lookup (htab, key, keylen, hval)
+ const hash_table *htab;
const void *key;
size_t keylen;
unsigned long int hval;
}
-static unsigned long
-compute_hashval (key, keylen)
- const void *key;
- size_t keylen;
-{
- size_t cnt;
- unsigned long int hval, g;
-
- /* Compute the hash value for the given string. The algorithm
- is taken from [Aho,Sethi,Ullman]. */
- cnt = 0;
- hval = keylen;
- while (cnt < keylen)
- {
- hval <<= 4;
- hval += (unsigned long int) *(((char *) key) + cnt++);
- g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
- if (g != 0)
- {
- hval ^= g >> (LONGBITS - 8);
- hval ^= g;
- }
- }
- return hval != 0 ? hval : ~((unsigned long) 0);
-}
-
-
-unsigned long
+unsigned long int
next_prime (seed)
unsigned long int seed;
{
projects / thirdparty / glibc.git / blobdiff