head 1.7; access; symbols act_first:1.1.1.1 act:1.1.1; locks; strict; comment @ * @; 1.7 date 2003.01.06.12.10.58; author rse; state Exp; branches; next 1.6; 1.6 date 2002.01.02.17.05.53; author rse; state Exp; branches; next 1.5; 1.5 date 2001.03.21.15.59.01; author rse; state Exp; branches; next 1.4; 1.4 date 2000.08.20.13.57.53; author rse; state Exp; branches; next 1.3; 1.3 date 2000.08.18.15.58.09; author rse; state Exp; branches; next 1.2; 1.2 date 2000.08.18.15.35.57; author rse; state Exp; branches; next 1.1; 1.1 date 99.11.12.20.37.19; author rse; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 99.11.12.20.37.19; author rse; state Exp; branches; next ; desc @@ 1.7 log @cleanup source tree @ text @/* ** OSSP act - Abstract Container Types ** Copyright (c) 1999-2003 Ralf S. Engelschall ** Copyright (c) 1999-2003 The OSSP Project ** ** 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 #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 }; @ 1.6 log @bump copyright year @ text @d1 4 a4 3 /* ** Act - Abstract Container Type Library ** Copyright (c) 1999-2002 Ralf S. Engelschall d6 2 a7 2 ** 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/. d89 1 a89 1 static int d91 1 a91 1 act_ctx_t *ctx, act_hash_oh_t *h, void *keyptr, int keylen, d98 1 a98 1 static int d100 1 a100 1 act_ctx_t *ctx, act_hash_oh_t *h, d107 1 a107 1 static int d115 1 a115 1 static int d138 1 a138 1 static int d146 1 a146 1 static int @ 1.5 log @*** empty log message *** @ text @d3 1 a3 1 ** Copyright (c) 1999-2001 Ralf S. Engelschall @ 1.4 log @*** empty log message *** @ text @d3 1 a3 1 ** Copyright (c) 1999-2000 Ralf S. Engelschall @ 1.3 log @*** empty log message *** @ text @d136 8 d179 1 @ 1.2 log @*** empty log message *** @ text @d1 27 a27 29 /* ==================================================================== * 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. * ==================================================================== */ a29 2 ** act_hash_oh.c -- Open Hashing (static) ** @ 1.1 log @Initial revision @ text @d2 1 a2 1 * Copyright (c) 1999 Ralf S. Engelschall. All rights reserved. @ 1.1.1.1 log @ @ text @@