|
Packit |
6c4009 |
/* Implement simple hashing table with string based keys.
|
|
Packit |
6c4009 |
Copyright (C) 1994-2018 Free Software Foundation, Inc.
|
|
Packit |
6c4009 |
This file is part of the GNU C Library.
|
|
Packit |
6c4009 |
Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
This program is free software; you can redistribute it and/or modify
|
|
Packit |
6c4009 |
it under the terms of the GNU General Public License as published
|
|
Packit |
6c4009 |
by the Free Software Foundation; version 2 of the License, or
|
|
Packit |
6c4009 |
(at your option) any later version.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
This program is distributed in the hope that it will be useful,
|
|
Packit |
6c4009 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
6c4009 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit |
6c4009 |
GNU General Public License for more details.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
You should have received a copy of the GNU General Public License
|
|
Packit |
6c4009 |
along with this program; if not, see <http://www.gnu.org/licenses/>. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef HAVE_CONFIG_H
|
|
Packit |
6c4009 |
# include <config.h>
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <inttypes.h>
|
|
Packit |
6c4009 |
#include <stdio.h>
|
|
Packit |
6c4009 |
#include <stdlib.h>
|
|
Packit |
6c4009 |
#include <string.h>
|
|
Packit |
6c4009 |
#include <stdint.h>
|
|
Packit |
6c4009 |
#include <sys/types.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <obstack.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef HAVE_VALUES_H
|
|
Packit |
6c4009 |
# include <values.h>
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include "simple-hash.h"
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define obstack_chunk_alloc malloc
|
|
Packit |
6c4009 |
#define obstack_chunk_free free
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef BITSPERBYTE
|
|
Packit |
6c4009 |
# define BITSPERBYTE 8
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define hashval_t uint32_t
|
|
Packit |
6c4009 |
#include "hashval.h"
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <programs/xmalloc.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
typedef struct hash_entry
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
unsigned long used;
|
|
Packit |
6c4009 |
const void *key;
|
|
Packit |
6c4009 |
size_t keylen;
|
|
Packit |
6c4009 |
void *data;
|
|
Packit |
6c4009 |
struct hash_entry *next;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
hash_entry;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Prototypes for local functions. */
|
|
Packit |
6c4009 |
static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
|
|
Packit |
6c4009 |
unsigned long hval, size_t idx, void *data);
|
|
Packit |
6c4009 |
static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
|
|
Packit |
6c4009 |
unsigned long int hval);
|
|
Packit |
6c4009 |
static int is_prime (unsigned long int candidate);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
init_hash (hash_table *htab, unsigned long int init_size)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* We need the size to be a prime. */
|
|
Packit |
6c4009 |
init_size = next_prime (init_size);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Initialize the data structure. */
|
|
Packit |
6c4009 |
htab->size = init_size;
|
|
Packit |
6c4009 |
htab->filled = 0;
|
|
Packit |
6c4009 |
htab->first = NULL;
|
|
Packit |
6c4009 |
htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
|
|
Packit |
6c4009 |
if (htab->table == NULL)
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
obstack_init (&htab->mem_pool);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
delete_hash (hash_table *htab)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
free (htab->table);
|
|
Packit |
6c4009 |
obstack_free (&htab->mem_pool, NULL);
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
insert_entry (hash_table *htab, const void *key, size_t keylen, void *data)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
unsigned long int hval = compute_hashval (key, keylen);
|
|
Packit |
6c4009 |
hash_entry *table = (hash_entry *) htab->table;
|
|
Packit |
6c4009 |
size_t idx = lookup (htab, key, keylen, hval);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (table[idx].used)
|
|
Packit |
6c4009 |
/* We don't want to overwrite the old value. */
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* An empty bucket has been found. */
|
|
Packit |
6c4009 |
insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
|
|
Packit |
6c4009 |
keylen, hval, idx, data);
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
|
|
Packit |
6c4009 |
unsigned long int hval, size_t idx, void *data)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
hash_entry *table = (hash_entry *) htab->table;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
table[idx].used = hval;
|
|
Packit |
6c4009 |
table[idx].key = key;
|
|
Packit |
6c4009 |
table[idx].keylen = keylen;
|
|
Packit |
6c4009 |
table[idx].data = data;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* List the new value in the list. */
|
|
Packit |
6c4009 |
if ((hash_entry *) htab->first == NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
table[idx].next = &table[idx];
|
|
Packit |
6c4009 |
htab->first = &table[idx];
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
table[idx].next = ((hash_entry *) htab->first)->next;
|
|
Packit |
6c4009 |
((hash_entry *) htab->first)->next = &table[idx];
|
|
Packit |
6c4009 |
htab->first = &table[idx];
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
++htab->filled;
|
|
Packit |
6c4009 |
if (100 * htab->filled > 75 * htab->size)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Table is filled more than 75%. Resize the table.
|
|
Packit |
6c4009 |
Experiments have shown that for best performance, this threshold
|
|
Packit |
6c4009 |
must lie between 40% and 85%. */
|
|
Packit |
6c4009 |
unsigned long int old_size = htab->size;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
htab->size = next_prime (htab->size * 2);
|
|
Packit |
6c4009 |
htab->filled = 0;
|
|
Packit |
6c4009 |
htab->first = NULL;
|
|
Packit |
6c4009 |
htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
for (idx = 1; idx <= old_size; ++idx)
|
|
Packit |
6c4009 |
if (table[idx].used)
|
|
Packit |
6c4009 |
insert_entry_2 (htab, table[idx].key, table[idx].keylen,
|
|
Packit |
6c4009 |
table[idx].used,
|
|
Packit |
6c4009 |
lookup (htab, table[idx].key, table[idx].keylen,
|
|
Packit |
6c4009 |
table[idx].used),
|
|
Packit |
6c4009 |
table[idx].data);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
free (table);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
find_entry (const hash_table *htab, const void *key, size_t keylen,
|
|
Packit |
6c4009 |
void **result)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
hash_entry *table = (hash_entry *) htab->table;
|
|
Packit |
6c4009 |
size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (table[idx].used == 0)
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
*result = table[idx].data;
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
set_entry (hash_table *htab, const void *key, size_t keylen, void *newval)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
hash_entry *table = (hash_entry *) htab->table;
|
|
Packit |
6c4009 |
size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (table[idx].used == 0)
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
table[idx].data = newval;
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
int
|
|
Packit |
6c4009 |
iterate_table (const hash_table *htab, void **ptr, const void **key,
|
|
Packit |
6c4009 |
size_t *keylen, void **data)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (*ptr == NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (htab->first == NULL)
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
*ptr = (void *) ((hash_entry *) htab->first)->next;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (*ptr == htab->first)
|
|
Packit |
6c4009 |
return -1;
|
|
Packit |
6c4009 |
*ptr = (void *) (((hash_entry *) *ptr)->next);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
*key = ((hash_entry *) *ptr)->key;
|
|
Packit |
6c4009 |
*keylen = ((hash_entry *) *ptr)->keylen;
|
|
Packit |
6c4009 |
*data = ((hash_entry *) *ptr)->data;
|
|
Packit |
6c4009 |
return 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* References:
|
|
Packit |
6c4009 |
[Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
|
|
Packit |
6c4009 |
[Knuth] The Art of Computer Programming, part3 (6.4) */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static size_t
|
|
Packit |
6c4009 |
lookup (const hash_table *htab, const void *key, size_t keylen,
|
|
Packit |
6c4009 |
unsigned long int hval)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
unsigned long int hash;
|
|
Packit |
6c4009 |
size_t idx;
|
|
Packit |
6c4009 |
hash_entry *table = (hash_entry *) htab->table;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* First hash function: simply take the modul but prevent zero. */
|
|
Packit |
6c4009 |
hash = 1 + hval % htab->size;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
idx = hash;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (table[idx].used)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (table[idx].used == hval && table[idx].keylen == keylen
|
|
Packit |
6c4009 |
&& memcmp (table[idx].key, key, keylen) == 0)
|
|
Packit |
6c4009 |
return idx;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Second hash function as suggested in [Knuth]. */
|
|
Packit |
6c4009 |
hash = 1 + hval % (htab->size - 2);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
do
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (idx <= hash)
|
|
Packit |
6c4009 |
idx = htab->size + idx - hash;
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
idx -= hash;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* If entry is found use it. */
|
|
Packit |
6c4009 |
if (table[idx].used == hval && table[idx].keylen == keylen
|
|
Packit |
6c4009 |
&& memcmp (table[idx].key, key, keylen) == 0)
|
|
Packit |
6c4009 |
return idx;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
while (table[idx].used);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
return idx;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
unsigned long int
|
|
Packit |
6c4009 |
next_prime (unsigned long int seed)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Make it definitely odd. */
|
|
Packit |
6c4009 |
seed |= 1;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
while (!is_prime (seed))
|
|
Packit |
6c4009 |
seed += 2;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return seed;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static int
|
|
Packit |
6c4009 |
is_prime (unsigned long int candidate)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* No even number and none less than 10 will be passed here. */
|
|
Packit |
6c4009 |
unsigned long int divn = 3;
|
|
Packit |
6c4009 |
unsigned long int sq = divn * divn;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
while (sq < candidate && candidate % divn != 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
++divn;
|
|
Packit |
6c4009 |
sq += 4 * divn;
|
|
Packit |
6c4009 |
++divn;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return candidate % divn != 0;
|
|
Packit |
6c4009 |
}
|