mirror of
https://github.com/phabrics/Run-Sun3-SunOS-4.1.1.git
synced 2026-04-29 19:12:58 -04:00
352 lines
9.0 KiB
C
352 lines
9.0 KiB
C
/* $Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $ */
|
|
|
|
/* libtme/hash.c - hash table support: */
|
|
|
|
/*
|
|
* Copyright (c) 2003 Matt Fredette
|
|
* All rights reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
* 3. All advertising materials mentioning features or use of this software
|
|
* must display the following acknowledgement:
|
|
* This product includes software developed by Matt Fredette.
|
|
* 4. The name of the author may not be used to endorse or promote products
|
|
* derived from this software without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
|
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
|
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
|
* DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
|
|
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
|
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
|
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
|
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
|
|
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
|
* POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#include <tme/common.h>
|
|
_TME_RCSID("$Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $");
|
|
|
|
/* includes: */
|
|
#include <tme/hash.h>
|
|
|
|
/* our hash table size array: */
|
|
static unsigned long _tme_hash_sizes[] = {
|
|
2,
|
|
3,
|
|
5,
|
|
7,
|
|
11,
|
|
17,
|
|
37,
|
|
83,
|
|
281,
|
|
421,
|
|
631,
|
|
947,
|
|
2131,
|
|
7193,
|
|
10789,
|
|
16183,
|
|
81929,
|
|
414763,
|
|
933217,
|
|
10629917,
|
|
35875969,
|
|
80720929,
|
|
};
|
|
|
|
/* this allocates and returns a new hash: */
|
|
tme_hash_t
|
|
tme_hash_new(tme_hash_func_t hash_func,
|
|
tme_compare_func_t compare_func,
|
|
tme_hash_data_t value_null)
|
|
{
|
|
tme_hash_t hash;
|
|
|
|
hash = tme_new0(struct _tme_hash, 1);
|
|
hash->_tme_hash_size = _tme_hash_sizes[0];
|
|
hash->_tme_hash_table =
|
|
tme_new0(struct _tme_hash_bucket *,
|
|
hash->_tme_hash_size);
|
|
hash->_tme_hash_count = 0;
|
|
hash->_tme_hash_hash = hash_func;
|
|
hash->_tme_hash_compare = compare_func;
|
|
hash->_tme_hash_null = value_null;
|
|
return (hash);
|
|
}
|
|
|
|
/* this destroys a hash: */
|
|
void
|
|
tme_hash_destroy(tme_hash_t hash)
|
|
{
|
|
struct _tme_hash_bucket *bucket, *bucket_next;
|
|
unsigned long bucket_i;
|
|
|
|
/* free all of the buckets in the hash table: */
|
|
for (bucket_i = 0;
|
|
bucket_i < hash->_tme_hash_size;
|
|
bucket_i++) {
|
|
for (bucket = hash->_tme_hash_table[bucket_i];
|
|
bucket != NULL;
|
|
bucket = bucket_next) {
|
|
bucket_next = bucket->_tme_hash_bucket_next;
|
|
tme_free(bucket);
|
|
}
|
|
}
|
|
tme_free(hash->_tme_hash_table);
|
|
tme_free(hash);
|
|
}
|
|
|
|
/* this does an internal lookup in a hash table: */
|
|
static struct _tme_hash_bucket *
|
|
_tme_hash_lookup_internal(tme_hash_t hash,
|
|
tme_hash_data_t key,
|
|
struct _tme_hash_bucket ***__bucket)
|
|
{
|
|
unsigned long bucket_i;
|
|
struct _tme_hash_bucket **_bucket, *bucket;
|
|
|
|
/* hash the key: */
|
|
bucket_i = (*hash->_tme_hash_hash)(key) % hash->_tme_hash_size;
|
|
|
|
/* walk the chain of buckets: */
|
|
for (_bucket = hash->_tme_hash_table + bucket_i;
|
|
(bucket = *_bucket) != NULL;
|
|
_bucket = &bucket->_tme_hash_bucket_next) {
|
|
|
|
/* compare the key in this bucket with the lookup key.
|
|
if it succeeds, return the bucket: */
|
|
if ((*hash->_tme_hash_compare)(key, bucket->_tme_hash_bucket_key)) {
|
|
if (__bucket != NULL) {
|
|
*__bucket = _bucket;
|
|
}
|
|
return (bucket);
|
|
}
|
|
}
|
|
|
|
/* the lookup failed. return where the bucket might be inserted: */
|
|
if (__bucket != NULL) {
|
|
*__bucket = _bucket;
|
|
}
|
|
return (NULL);
|
|
}
|
|
|
|
/* this inserts a value into a hash table: */
|
|
void
|
|
tme_hash_insert(tme_hash_t hash,
|
|
tme_hash_data_t key,
|
|
tme_hash_data_t value)
|
|
{
|
|
struct _tme_hash_bucket *bucket, *bucket_next, **_bucket;
|
|
struct _tme_hash hash_new;
|
|
int size_i;
|
|
unsigned long bucket_i;
|
|
|
|
/* if this key is not already present in the hash table: */
|
|
bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
|
|
if (bucket == NULL) {
|
|
|
|
/* if we need to resize this hash table: */
|
|
if ((hash->_tme_hash_count * 2) > hash->_tme_hash_size) {
|
|
|
|
/* make a copy of the top of the hash: */
|
|
hash_new = *hash;
|
|
|
|
/* set the new size of the hash: */
|
|
hash_new._tme_hash_size = hash->_tme_hash_count * 2;
|
|
for (size_i = 0;
|
|
_tme_hash_sizes[size_i] < hash_new._tme_hash_size;
|
|
size_i++) {
|
|
if (size_i + 1 == TME_ARRAY_ELS(_tme_hash_sizes)) {
|
|
abort();
|
|
}
|
|
}
|
|
hash_new._tme_hash_size = _tme_hash_sizes[size_i];
|
|
|
|
/* allocate the new hash table: */
|
|
hash_new._tme_hash_table =
|
|
tme_new0(struct _tme_hash_bucket *,
|
|
hash_new._tme_hash_size);
|
|
|
|
/* move everything from the old hash table into the new: */
|
|
for (bucket_i = 0;
|
|
bucket_i < hash->_tme_hash_size;
|
|
bucket_i++) {
|
|
for (bucket = hash->_tme_hash_table[bucket_i];
|
|
bucket != NULL;
|
|
bucket = bucket_next) {
|
|
bucket_next = bucket->_tme_hash_bucket_next;
|
|
_tme_hash_lookup_internal(&hash_new,
|
|
bucket->_tme_hash_bucket_key,
|
|
&_bucket);
|
|
bucket->_tme_hash_bucket_next = *_bucket;
|
|
*_bucket = bucket;
|
|
}
|
|
}
|
|
|
|
/* free the old hash table: */
|
|
tme_free(hash->_tme_hash_table);
|
|
|
|
/* set the new top of the hash: */
|
|
*hash = hash_new;
|
|
|
|
/* do the internal lookup again: */
|
|
_tme_hash_lookup_internal(hash, key, &_bucket);
|
|
}
|
|
|
|
/* create the new bucket and link it in: */
|
|
bucket = tme_new(struct _tme_hash_bucket, 1);
|
|
bucket->_tme_hash_bucket_next = *_bucket;
|
|
*_bucket = bucket;
|
|
|
|
/* increment the number of keys in the hash: */
|
|
hash->_tme_hash_count++;
|
|
}
|
|
|
|
/* set the key and value in the bucket: */
|
|
bucket->_tme_hash_bucket_key = key;
|
|
bucket->_tme_hash_bucket_value = value;
|
|
}
|
|
|
|
/* this looks up a key in the hash: */
|
|
tme_hash_data_t
|
|
tme_hash_lookup(tme_hash_t hash,
|
|
tme_hash_data_t key)
|
|
{
|
|
struct _tme_hash_bucket *bucket;
|
|
|
|
bucket = _tme_hash_lookup_internal(hash, key, NULL);
|
|
return (bucket != NULL
|
|
? bucket->_tme_hash_bucket_value
|
|
: hash->_tme_hash_null);
|
|
}
|
|
|
|
/* this removes a key in the hash: */
|
|
void
|
|
tme_hash_remove(tme_hash_t hash,
|
|
tme_hash_data_t key)
|
|
{
|
|
struct _tme_hash_bucket *bucket, **_bucket;
|
|
|
|
bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
|
|
if (bucket != NULL) {
|
|
*_bucket = bucket->_tme_hash_bucket_next;
|
|
tme_free(bucket);
|
|
hash->_tme_hash_count--;
|
|
}
|
|
}
|
|
|
|
/* this calls a function for each key and value in the hash: */
|
|
void
|
|
tme_hash_foreach(tme_hash_t hash,
|
|
tme_foreach_func_t func,
|
|
void *private)
|
|
{
|
|
struct _tme_hash_bucket *bucket;
|
|
unsigned long bucket_i;
|
|
|
|
/* walk all of the buckets in the hash table: */
|
|
for (bucket_i = 0;
|
|
bucket_i < hash->_tme_hash_size;
|
|
bucket_i++) {
|
|
for (bucket = hash->_tme_hash_table[bucket_i];
|
|
bucket != NULL;
|
|
bucket = bucket->_tme_hash_bucket_next) {
|
|
(*func)(bucket->_tme_hash_bucket_key,
|
|
bucket->_tme_hash_bucket_value,
|
|
private);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* this calls a function for each key and value in the hash.
|
|
if the function returns TRUE the entry is removed: */
|
|
unsigned long
|
|
tme_hash_foreach_remove(tme_hash_t hash,
|
|
tme_foreach_remove_func_t func,
|
|
void *private)
|
|
{
|
|
struct _tme_hash_bucket **_bucket, *bucket;
|
|
unsigned long bucket_i, count;
|
|
|
|
/* walk all of the buckets in the hash table: */
|
|
count = 0;
|
|
for (bucket_i = 0;
|
|
bucket_i < hash->_tme_hash_size;
|
|
bucket_i++) {
|
|
for (_bucket = &hash->_tme_hash_table[bucket_i];
|
|
(bucket = *_bucket) != NULL; ) {
|
|
if ((*func)(bucket->_tme_hash_bucket_key,
|
|
bucket->_tme_hash_bucket_value,
|
|
private)) {
|
|
*_bucket = bucket->_tme_hash_bucket_next;
|
|
tme_free(bucket);
|
|
hash->_tme_hash_count--;
|
|
count++;
|
|
}
|
|
else {
|
|
_bucket = &bucket->_tme_hash_bucket_next;
|
|
}
|
|
}
|
|
}
|
|
return (count);
|
|
}
|
|
|
|
/* this hashes a direct value: */
|
|
unsigned long
|
|
tme_direct_hash(tme_hash_data_t key)
|
|
{
|
|
return ((unsigned long) key);
|
|
}
|
|
|
|
/* this compares two direct values: */
|
|
int
|
|
tme_direct_compare(tme_hash_data_t key0,
|
|
tme_hash_data_t key1)
|
|
{
|
|
return (key0 == key1);
|
|
}
|
|
|
|
/* this hashes a string value: */
|
|
unsigned long
|
|
tme_string_hash(tme_hash_data_t key)
|
|
{
|
|
/* this is cribbed from the Dragon book: */
|
|
const char *p;
|
|
char c;
|
|
unsigned long h, g;
|
|
|
|
p = (const char *) key;
|
|
h = 0;
|
|
|
|
for (; (c = *(p++)) != '\0'; ) {
|
|
h = (h << 4) + c;
|
|
g = (h & 0xf0000000);
|
|
if (g) {
|
|
h = h ^ (g >> 24);
|
|
h = h ^ g;
|
|
}
|
|
}
|
|
|
|
return (h);
|
|
}
|
|
|
|
/* this compares two string values: */
|
|
int
|
|
tme_string_compare(tme_hash_data_t key0,
|
|
tme_hash_data_t key1)
|
|
{
|
|
return (!strcmp((const char *) key0, (const char *) key1));
|
|
}
|
|
|