ossp-pkg/act/act_hash_oh.c
/*
** OSSP act - Abstract Container Types
** Copyright (c) 1999-2003 Ralf S. Engelschall <rse@engelschall.com>
** Copyright (c) 1999-2003 The OSSP Project <http://www.ossp.org/>
**
** This file is part of OSSP act, an abstract container type library
** which can be found at http://www.ossp.org/pkg/lib/act/.
**
** Permission to use, copy, modify, and distribute this software for
** any purpose with or without fee is hereby granted, provided that
** the above copyright notice and this permission notice appear in all
** copies.
**
** THIS SOFTWARE IS PROVIDED ``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 THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
** 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;
}
/* find out the size of the hash table */
static int
act_hash_oh_status(
act_ctx_t *ctx, act_hash_oh_t *h, char *pstatus, int *nstatus)
{
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_status_t) act_hash_oh_status,
(act_hash_free_t) act_hash_oh_free
};
