Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 6fab2616d5
Fetching contributors…

Cannot retrieve contributors at this time

301 lines (268 sloc) 5.946 kb
/* -*- c -*- */
/*
* chash.c
*
* chpp
*
* Copyright (C) 1995-1997 Herbert Poetzl
*
* 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
* 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.
*
* 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., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#include <string.h>
#include <stdlib.h>
#include "memory.h"
#include "chash.h"
#ifndef TRUE
#define TRUE (0==0)
#endif
#ifndef FALSE
#define FALSE (1==0)
#endif
#define DELETED ((char *)-1)
char *_copy_string(const char *string)
{
char *copy = NULL;
if (string) {
int len = strlen(string);
copy = (char *)memXAllocAtomic(len+1);
if (copy) {
memcpy(copy, string, len+1);
}
}
return copy;
}
long _hashcode_ascii(const char *key)
{
long h, c;
h = 0;
while ((c = *key++))
{
h += c + (c<<5) + (h<<3);
}
return h;
}
struct hash_entry *_hash_find(hash table, const char *key)
{
long pos, hashcode;
struct hash_entry *place, *start;
hashcode = _hashcode_ascii(key);
pos = (table->mask & hashcode);
place = &(table->data[pos]);
start = place;
while (place->key != NULL) {
if (hashcode == place->hashcode) {
if (place->key != DELETED) {
if (strcmp(key, place->key) == 0) {
return place;
}
}
}
place++;
if (place == table->wall) place = table->data;
if (place == start) break;
}
return NULL;
}
void _hash_place(hash table, struct hash_entry *entry, int check)
{
long pos;
struct hash_entry *place;
pos = (table->mask & entry->hashcode);
place = &(table->data[pos]);
while (place->key != NULL) {
if (place->key == DELETED) break;
if (check) {
if (entry->hashcode == place->hashcode) {
if (strcmp(entry->key, place->key) == 0) {
place->value = entry->value;
return;
}
}
}
place++;
if (place == table->wall) place = table->data;
}
table->entries++;
memcpy(place, entry, sizeof(struct hash_entry));
return;
}
int _hash_grow(hash table)
{
struct hash_control *new;
new = hash_new(2<<table->sizelog);
if (new) {
long i,n;
for (i=0, n=1<<table->sizelog; i<n; i++) {
if (table->data[i].key != NULL)
_hash_place(new, &(table->data[i]), FALSE);
}
memFree(table->data);
memcpy(table, new, sizeof(struct hash_control));
memFree(new);
return (TRUE);
}
return (FALSE);
}
int _hash_cramped(hash table)
{
long bound;
bound = 101*(1 << table->sizelog)/143;
if (table->entries > bound) return (TRUE);
return (FALSE);
}
hash hash_new(long capacity)
{
struct hash_control *new;
long n,s;
new = (struct hash_control *)
memXAlloc(sizeof(struct hash_control));
if (new) {
for (n=0,s=1; s<capacity; n++,s <<= 1);
new->sizelog = n;
new->mask = s-1;
new->memsize = sizeof(struct hash_entry)*s;
new->data = (struct hash_entry *)
memXAlloc(new->memsize);
if (new->data) {
new->wall = new->data+s;
hash_empty(new);
}
else {
memFree(new);
new = NULL;
}
}
return (hash)new;
}
void hash_free(hash table)
{
if (table) {
memFree(table->data);
memFree(table);
}
return;
}
void hash_empty(hash table)
{
table->entries = 0;
memset(table->data, 0, table->memsize);
return;
}
int hash_inject(hash table, const char *key, void *value)
{
if (table && key) {
struct hash_entry place;
if (_hash_cramped(table)) {
_hash_grow(table);
}
place.key = (char *)key;
place.value = value;
place.hashcode = _hashcode_ascii(key);
_hash_place(table, &place, (FALSE));
return (TRUE);
}
return (FALSE);
}
int hash_insert(hash table, const char *key, void *value)
{
if (table && key) {
struct hash_entry place;
if (_hash_cramped(table)) {
_hash_grow(table);
}
place.key = _copy_string(key);
place.value = value;
place.hashcode = _hashcode_ascii(key);
_hash_place(table, &place, (TRUE));
return (TRUE);
}
return (FALSE);
}
void * hash_replace(hash table, const char *key, void *value)
{
void *oldvalue;
struct hash_entry *entry;
if (key) {
entry = _hash_find(table, key);
if (entry) {
oldvalue = entry->value;
entry->value = value;
return oldvalue;
}
}
return NULL;
}
void * hash_delete(hash table, const char *key)
{
void *oldvalue = NULL;
struct hash_entry *entry;
if (key) {
entry = _hash_find(table, key);
if (entry) {
oldvalue = entry->value;
memFree(entry->key);
entry->key = DELETED;
table->entries--;
}
}
return oldvalue;
}
void * hash_lookup(hash table, const char *key)
{
struct hash_entry *entry;
if (key) {
entry = _hash_find(table, key);
if (entry) {
return entry->value;
}
}
return NULL;
}
hstate hash_state(hash table)
{
hstate state;
state.hashpos = 0;
state.table = table;
state.sflags.active = TRUE;
return state;
}
void * hash_next(hstate *state, char **key)
{
long pos;
char *lkey;
void *value = NULL;
if (state) {
hash table = state->table;
if (state->sflags.active) {
while ((pos = state->hashpos++)
< (1 << table->sizelog)) {
lkey = table->data[pos].key;
if ((lkey != DELETED) && (lkey)) {
value = table->data[pos].value;
if (key) *key = lkey;
break;
}
}
if (pos == (1 << table->sizelog))
state->sflags.active = FALSE;
}
}
return value;
}
int hash_count(hash table)
{
if (table) return table->entries;
return 0;
}
Jump to Line
Something went wrong with that request. Please try again.