OSSP CVS Repository

ossp - ossp-pkg/act/act_hash_oh.c 1.5
Not logged in
[Honeypot]  [Browse]  [Directory]  [Home]  [Login
[Reports]  [Search]  [Ticket]  [Timeline
  [Raw

ossp-pkg/act/act_hash_oh.c 1.5
/* 
**  Act - Abstract Container Type Library
**  Copyright (c) 1999-2001 Ralf S. Engelschall <rse@engelschall.com>
**
**  This file is part of Act, a library for dealing with Abstract 
**  Container Types which can be found at http://www.ossp.org/pkg/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
};


CVSTrac 2.0.1