ossp-pkg/act/act_hash_oh.c
1.2
/* ====================================================================
* Copyright (c) 1999-2000 Ralf S. Engelschall. 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.
*
* THIS SOFTWARE IS PROVIDED BY RALF S. ENGELSCHALL ``AS IS'' AND ANY
* EXPRESSED 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 RALF S. ENGELSCHALL OR
* ITS CONTRIBUTORS 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.
* ====================================================================
*/
/*
** act_hash_oh.c -- Open Hashing (static)
**
** This module implements a Static Hash Table, based on the Open
** Hashing algorithm with Double Hashing to solve collisions. That is,
** keys are hased into a static hash table and collisions are solved
** within the table itself. This limits the usage to a fixed set of
** elements, but uses less memory then the Linear Hashing method.
*/
#include <stdio.h>
#include "act_p.h"
/* the per-element structure */
typedef struct element_st element_t;
struct element_st {
element_t *e_next; /* pointer to next element in collision chain */
unsigned long e_hash; /* cached hash value of element (rehashing optimization) */
void *e_keyptr; /* pointer to key (= also pointer to key+data memory chunk) */
void *e_datptr; /* pointer to data in key+data memory chunk */
void *e_endptr; /* pointer to end of key+data memory chunk */
};
/* the top-level structure */
typedef struct act_hash_oh_st act_hash_oh_t;
struct act_hash_oh_st {
act_ctx_t *h_ctx; /* context structure */
act_hash_fct_t h_func; /* hash function (copied from context) */
int h_size; /* hash table size */
element_t *h_table; /* hash table */
};
/* create a new hash table */
static act_hash_oh_t *
act_hash_oh_new(
act_ctx_t *ctx)
{
act_hash_oh_t *h;
/* allocate hash structure */
if ((h = (act_hash_oh_t *)act_mem_alloc_ctx(ctx, sizeof(struct act_hash_oh_st))) == NULL)
return NULL;
h->h_ctx = ctx;
/* inline values from context (for performance reasons only) */
if (!act_ctx_get(ctx, ACT_HASH_FUNC, &h->h_func))
h->h_func = act_hash_fct(djbx33a);
if (!act_ctx_get(ctx, ACT_HASH_TABLESIZE, &h->h_size))
h->h_size = 128;
/* allocate and clear hash table */
if ((h->h_table = (element_t *)act_mem_alloc_ctx(ctx, h->h_size * sizeof(element_t))) == NULL) {
errno_safe( act_mem_free_ctx(ctx, h) );
return NULL;
}
act_mem_set(h->h_table, 0, h->h_size * sizeof(element_t));
return h;
}
/* insert an element into hash table */
static int
act_hash_oh_insert(
act_ctx_t *ctx, act_hash_oh_t *h, void *keyptr, int keylen,
void *datptr, int datlen, int override)
{
return TRUE;
}
/* lookup an element in hash table */
static int
act_hash_oh_lookup(
act_ctx_t *ctx, act_hash_oh_t *h,
void *keyptr, int keylen, void **datptr, int *datlen)
{
return FALSE;
}
/* delete an element from hash table */
static int
act_hash_oh_delete(
act_ctx_t *ctx, act_hash_oh_t *h, void *keyptr, int keylen)
{
return TRUE;
}
/* find out the size of the hash table */
static int
act_hash_oh_size(
act_ctx_t *ctx, act_hash_oh_t *h, long *pbytes, long *pelements)
{
long bytes, elements;
/* argument consistency check */
if (h == NULL)
return_errno(FALSE, EINVAL);
/* start with 0 bytes and elements */
bytes = 0;
elements = 0;
/* add bytes for top-level structure and hash table */
bytes += sizeof(struct act_hash_oh_st);
bytes += h->h_size * sizeof(element_t *);
/* ...XXX... */
return TRUE;
}
/* free the hash table structure */
static int
act_hash_oh_free(
act_ctx_t *ctx, act_hash_oh_t *h)
{
unsigned int i;
/* argument consistency check */
if (h == NULL)
return_errno(FALSE, EINVAL);
/* deallocate all segment's entries */
for (i = 0; i < h->h_size; i++) {
if (h->h_table[i].e_keyptr == NULL)
continue;
act_mem_free_ctx(ctx, h->h_table[i].e_keyptr);
}
/* deallocate hash table */
act_mem_free_ctx(ctx, h->h_table);
/* deallocate hash table top-level structure */
act_mem_free_ctx(ctx, h);
return TRUE;
}
/* the ACT dispatch structure for the hashing API */
intern act_hash_method_t act_hash_oh = {
ACT_HASH_METHOD_TAG,
(act_hash_new_t) act_hash_oh_new,
(act_hash_insert_t) act_hash_oh_insert,
(act_hash_lookup_t) act_hash_oh_lookup,
(act_hash_delete_t) act_hash_oh_delete,
(act_hash_size_t) act_hash_oh_size,
(act_hash_free_t) act_hash_oh_free
};