/* Copyright (c) 2013-2014, David Anderson
All rights reserved.
Redistribution and use in source and binary forms, with
or without modification, are permitted provided that the
following conditions are met:
Redistributions of source code must retain the above
copyright notice, this list of conditions and the following
disclaimer.
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 THE COPYRIGHT HOLDERS AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS 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 COPYRIGHT HOLDER OR
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.
*/
/* The interfaces follow tsearch (See the Single
Unix Specification) but the implementation is
written without reference to the source of any
version of tsearch or any hashing code.
An additional interface is added (compared to
a real tsearch) to let the caller identify a
'hash' function with each hash table (called
a tree below, but that is a misnomer).
So read 'tree' below as hash table.
See http://www.prevanders.net/tsearch.html
for information and an example of use.
Based on Knuth, chapter 6.4
This uses a hash based on the key.
Collision resolution is by chaining.
twalk() and tdestroy() walk in a random order.
The 'preorder' etc labels mean nothing in a hash, so everything
is called a leaf.
*/
#include "config.h"
#include "dwarf_incl.h"
#include "stdlib.h" /* for free() etc */
#include <stdio.h> /* for printf() */
#include "dwarf_tsearch.h"
/* A table of primes used to size and resize the hash table.
From public sources of prime numbers, arbitrarily chosen
to approximately double in size at each step.
*/
static unsigned long long primes[] =
{
#if 0 /* for testing only */
5,11, 17,23, 31, 47, 53,
#endif
79,
1009,
5591,
10007,
21839,
41413,
99907,
199967,
400009,
800029,
1600141,
3000089,
6000121,
12000257,
24000143,
48000203,
100000127,
200001611,
400000669,
800000573,
0 /* Here we are giving up */
};
static unsigned long allowed_fill_percent = 90;
struct hs_base {
unsigned long tablesize_;
unsigned long tablesize_entry_index_;
unsigned long allowed_fill_;
/* Record_count means number of active records,
counting all records on chains.
When the record_count is > 90% of a full
tablesize_ we redo the table before adding
a new entry. */
unsigned long record_count_;
/* hashtab_ is an array of hs_entry,
indexes 0 through tablesize_ -1. */
struct ts_entry * hashtab_;
DW_TSHASHTYPE (*hashfunc_)(const void *key);
};
struct ts_entry {
const void * keyptr;
/* So that a keyptr of 0 (if added) is
not confused with an empty hash slot,
we must mark used slots as used in the hash tab */
unsigned char entryused;
struct ts_entry *next;
};
enum search_intent_t
{
want_insert,
only_find,
want_delete
};
static struct ts_entry *
tsearch_inner( const void *key, struct hs_base* head,
int (*compar)(const void *, const void *),
const enum search_intent_t intent, int*inserted,
struct ts_entry **parent_ptr);
static void
dwarf_tdestroy_inner(struct hs_base*h,
void (*free_node)(void *nodep),
int depth);
/* A trivial integer-based percentage calculation.
Percents >100 are reasonable for a hash-with-chains
situation (even if they might not be the best choice
for performance). */
static unsigned long
calculate_allowed_fill(unsigned long fill_percent, unsigned long ct)
{
unsigned long v = 0;
if(ct < 100000) {
unsigned long v2 = (ct *fill_percent)/100;
return v2;
}
v = (ct /100)*fill_percent;
return v;
}
/* Initialize the hash and pass in the hash function.
If the entry count needed is unknown, pass in 0 as a count estimate,
but if the number of hash entries needed can be estimated,
pass in the estimate (which need not be prime, we actually use
the nearest higher prime from the above table).
If the estimated count is
Return the tree base, or return NULL if insufficient memory. */
void *
dwarf_initialize_search_hash( void **treeptr,
DW_TSHASHTYPE(*hashfunc)(const void *key),
unsigned long size_estimate)
{
unsigned long prime_to_use =primes[0];
unsigned entry_index = 0;
unsigned k = 0;
struct hs_base *base = 0;
base = *(struct hs_base **)treeptr;
if(base) {
/* initalized already. */
return base ;
}
base = calloc(sizeof(struct hs_base),1);
if(!base) {
/* Out of memory. */
return NULL ;
}
prime_to_use = primes[0];
while(size_estimate && (size_estimate > prime_to_use)) {
k = k +1;
prime_to_use = primes[k];
if(prime_to_use == 0) {
/* Oops. Too large. */
free(base);
return NULL;
}
entry_index = k;
}
base->tablesize_ = prime_to_use;
base->allowed_fill_ = calculate_allowed_fill(allowed_fill_percent,
prime_to_use);
if( base->allowed_fill_< (base->tablesize_/2)) {
/* Oops. We are in trouble. Coding mistake here. */
return NULL;
}
base->record_count_ = 0;
base->tablesize_entry_index_ = entry_index;
/* hashtab_ is an array of hs_entry,
indexes 0 through tablesize_ -1. */
base->hashfunc_ = hashfunc;
base->hashtab_ = calloc(sizeof(struct ts_entry),base->tablesize_);
if(!base->hashtab_) {
free(base);
return NULL;
}
*treeptr = base;
return base;
}
static void print_entry(struct ts_entry *t,const char *descr,
char *(* keyprint)(const void *),
unsigned long hashpos,
unsigned long chainpos)
{
char *v = 0;
if(!t->entryused) {
return;
}
v = keyprint(t->keyptr);
printf(
"[%4lu.%02lu] 0x%08lx <keyptr 0x%08lx> <key %s> %s\n",
hashpos,chainpos,
(unsigned long)t,
(unsigned long)t->keyptr,
v,
descr);
}
/* For debugging */
static void
dumptree_inner(const struct hs_base *h,
char *(* keyprint)(const void *),
const char *descr, int printdetails)
{
unsigned long ix = 0;
unsigned long tsize = h->tablesize_;
struct ts_entry *p = &h->hashtab_[0];
unsigned long hashused = 0;
unsigned long maxchainlength = 0;
unsigned long chainsgt1 = 0;
printf("dumptree head ptr : 0x%08lx size %lu entries %lu allowed %lu %s\n",
(unsigned long)h,
(unsigned long)h->tablesize_,
(unsigned long)h->record_count_,
(unsigned long)h->allowed_fill_,
descr);
for( ; ix < tsize; ix++,p++) {
unsigned long chainlength = 0;
struct ts_entry*n = 0;
int chainpos = 0;
if(p->entryused) {
++hashused;
chainlength = 1;
if(printdetails) {
print_entry(p,"head",keyprint,ix,chainpos);
}
}
chainpos++;
for(n = p->next; n ; n = n->next) {
chainlength++;
if(printdetails) {
print_entry(n,"chain",keyprint,ix,chainpos);
}
}
if(chainlength > maxchainlength) {
maxchainlength = chainlength;
}
if (chainlength > 1) {
chainsgt1++;
}
}
printf("Hashtable: %lu of %lu hash entries used.\n",hashused,tsize);
printf("Hashtable: %lu chains length longer than 1. \n",chainsgt1);
printf("Hashtable: %lu is maximum chain length.\n",maxchainlength);
}
/* Dumping the tree.
*/
void
dwarf_tdump(const void*headp_in,
char *(* keyprint)(const void *),
const char *msg)
{
const struct hs_base *head = (const struct hs_base *)headp_in;
if(!head) {
printf("dumptree null tree ptr : %s\n",msg);
return;
}
dumptree_inner(head,keyprint,msg,1);
}
static struct ts_entry *
allocate_ts_entry(const void *key)
{
struct ts_entry *e = (struct ts_entry *)
malloc(sizeof(struct ts_entry));
if(!e) {
return NULL;
}
e->keyptr = key;
e->entryused = 1;
e->next = 0;
return e;
}
static void
resize_table(struct hs_base *head,
int (*compar)(const void *, const void *))
{
struct hs_base newhead;
unsigned new_entry_index = 0;
unsigned long prime_to_use = 0;
/* Copy the values we have. */
newhead = *head;
/* But drop the hashtab_ from new. calloc below. */
newhead.hashtab_ = 0;
newhead.record_count_ = 0;
new_entry_index = head->tablesize_entry_index_ +1;
prime_to_use = primes[new_entry_index];
if(prime_to_use == 0) {
/* Oops, too large. Leave table size as is, though
it will get slow as it overfills. */
return;
}
newhead.tablesize_ = prime_to_use;
newhead.allowed_fill_ = calculate_allowed_fill(allowed_fill_percent,
prime_to_use);
if( newhead.allowed_fill_< (newhead.tablesize_/2)) {
/* Oops. We are in trouble. */
return;
}
newhead.tablesize_entry_index_ = new_entry_index;
newhead.hashtab_ = calloc(sizeof(struct ts_entry),newhead.tablesize_);
if(!newhead.hashtab_) {
/* Oops, too large. Leave table size as is, though
things will get slow as it overfills. */
free(newhead.hashtab_);
return;
}
{
/* Insert all the records from the old table into
the new table. */
int fillnewfail = 0;
unsigned long ix = 0;
unsigned long tsize = head->tablesize_;
struct ts_entry *p = &head->hashtab_[0];
for( ; ix < tsize; ix++,p++) {
int inserted = 0;
struct ts_entry*n = 0;
if(fillnewfail) {
break;
}
if(p->keyptr) {
tsearch_inner(p->keyptr,
&newhead,compar,
want_insert,
&inserted,
0);
if(!inserted) {
fillnewfail = 1;
break;
}
}
for(n = p->next; n ; n = n->next) {
inserted = 0;
tsearch_inner(n->keyptr,
&newhead,compar,
want_insert,
&inserted,
0);
if(!inserted) {
fillnewfail = 1;
break;
}
}
}
if(fillnewfail) {
free(newhead.hashtab_);
return;
}
}
/* Now get rid of the chain entries of the old table. */
dwarf_tdestroy_inner(head,0,0);
/* Now get rid of the old table itself. */
free(head->hashtab_);
head->hashtab_ = 0;
*head = newhead;
return;
}
/* Inner search of the hash and synonym chains.
*/
static struct ts_entry *
tsearch_inner( const void *key, struct hs_base* head,
int (*compar)(const void *, const void *),
const enum search_intent_t intent, int*inserted,
/* owner_ptr used for delete. Only set
if the to-be-deleted item is on a chain,
not in the hashtab. Points to the item
pointing to the to-be-deleted-item.*/
struct ts_entry **owner_ptr)
{
struct ts_entry *s =0;
struct ts_entry *c =0;
struct ts_entry *q =0;
int kc = 0;
DW_TSHASHTYPE keyhash = 0;
DW_TSHASHTYPE hindx = 0;
struct ts_entry *chain_parent = 0;
if(! head->hashfunc_) {
/* Not fully initialized. */
return NULL;
}
keyhash = head->hashfunc_(key);
if (intent == want_insert) {
if( head->record_count_ > head->allowed_fill_) {
resize_table(head,compar);
}
}
hindx = keyhash%head->tablesize_;
s = &head->hashtab_[hindx];
if(!s->entryused) {
/* Not found. */
if(intent != want_insert) {
return NULL;
}
/* Insert in the base hash table in an
empty slot. */
*inserted = 1;
head->record_count_++;
s->keyptr = (const void *)key;
s->entryused = 1;
s->next = 0;
return s;
}
kc = compar(key,s->keyptr);
if(kc == 0 ) {
/* found! */
if(want_delete) {
*owner_ptr = 0;
}
return (void *)&(s->keyptr);
}
chain_parent = s;
for(c = s->next; c; c = c->next) {
kc = compar(key,c->keyptr);
if(kc == 0 ) {
/* found! */
if(want_delete) {
*owner_ptr = chain_parent;
}
return (void *)&(c->keyptr);
}
chain_parent = c;
}
if(intent != want_insert) {
return NULL;
}
/* Insert following head record of the chain. */
q = allocate_ts_entry(key);
if (!q) {
return q;
}
q->next = s->next;
s->next = q;
head->record_count_++;
*inserted = 1;
return q;
}
/* Search and, if missing, insert. */
void *
dwarf_tsearch(const void *key, void **headin,
int (*compar)(const void *, const void *))
{
struct hs_base **rootp = (struct hs_base **)headin;
struct hs_base *head = *rootp;
struct ts_entry *r = 0;
int inserted = 0;
/* nullme won't be set. */
struct ts_entry *nullme = 0;
if (!head) {
/* something is wrong here, not initialized. */
return NULL;
}
r = tsearch_inner(key,head,compar,want_insert,&inserted,&nullme);
if (!r) {
return NULL;
}
return (void *)&(r->keyptr);
}
/* Search. */
void *
dwarf_tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *))
{
/* Nothing will change, but we discard const
so we can use tsearch_inner(). */
struct hs_base **proot = (struct hs_base **)rootp;
struct hs_base *head = *proot;
struct ts_entry *r = 0;
/* inserted flag won't be set. */
int inserted = 0;
/* nullme won't be set. */
struct ts_entry * nullme = 0;
/* Get to actual tree. */
if (!head) {
return NULL;
}
r = tsearch_inner(key,head,compar,only_find,&inserted,&nullme);
if(!r) {
return NULL;
}
return (void *)(&(r->keyptr));
}
/* Unlike the simple binary tree case,
a fully-empty hash situation does not null the *rootp
*/
void *
dwarf_tdelete(const void *key, void **rootp,
int (*compar)(const void *, const void *))
{
struct hs_base **proot = (struct hs_base **)rootp;
struct hs_base *head = *proot;
struct ts_entry *found = 0;
/* inserted flag won't be set. */
int inserted = 0;
struct ts_entry * parentp = 0;
if (!head) {
return NULL;
}
found = tsearch_inner(key,head,compar,want_delete,&inserted,
&parentp);
if(found) {
if(parentp) {
/* Delete a chain entry. */
head->record_count_--;
parentp->next = found->next;
/* We free our storage. It would be up
to caller to do a tfind to find
a record and delete content if necessary. */
free(found);
return (void *)&(parentp->keyptr);
}
/* So found is the head of a chain. */
if(found->next) {
/* Delete a chain entry, pull up to hash tab, freeing
up the chain entry. */
struct ts_entry *pullup = found->next;
*found = *pullup;
free(pullup);
head->record_count_--;
return (void *)&(found->keyptr);
} else {
/* Delete a main hash table entry.
Problem: what the heck to return as a keyptr pointer?
Well, we return NULL. As in the standard
tsearch, returning NULL does not mean
failure! Here it just means 'empty chain somewhere'.
*/
head->record_count_--;
found->next = 0;
found->keyptr = 0;
found->entryused = 0;
return NULL;
}
}
return NULL;
}
static void
dwarf_twalk_inner(const struct hs_base *h,
struct ts_entry *p,
void (*action)(const void *nodep, const DW_VISIT which, const int depth),
UNUSEDARG unsigned level)
{
unsigned long ix = 0;
unsigned long tsize = h->tablesize_;
for( ; ix < tsize; ix++,p++) {
struct ts_entry*n = 0;
if(p->keyptr) {
action((void *)(&(p->keyptr)),dwarf_leaf,level);
}
for(n = p->next; n ; n = n->next) {
action((void *)(&(n->keyptr)),dwarf_leaf,level);
}
}
}
void
dwarf_twalk(const void *rootp,
void (*action)(const void *nodep, const DW_VISIT which, const int depth))
{
const struct hs_base *head = (const struct hs_base *)rootp;
struct ts_entry *root = 0;
if(!head) {
return;
}
root = head->hashtab_;
/* Get to actual tree. */
dwarf_twalk_inner(head,root,action,0);
}
static void
dwarf_tdestroy_inner(struct hs_base*h,
void (*free_node)(void *nodep),
int depth)
{
unsigned long ix = 0;
unsigned long tsize = h->tablesize_;
struct ts_entry *p = &h->hashtab_[0];
for( ; ix < tsize; ix++,p++) {
struct ts_entry*n = 0;
struct ts_entry*prev = 0;
if(p->keyptr && p->entryused) {
if(free_node) {
free_node((void *)(p->keyptr));
}
--h->record_count_;
}
/* Now walk and free up the chain entries. */
for(n = p->next; n ; ) {
if(free_node) {
free_node((void *)(n->keyptr));
}
--h->record_count_;
prev = n;
n = n->next;
free(prev);
}
}
}
/* Walk the tree, freeing all space in the tree
and calling the user's callback function on each node.
It is up to the caller to zero out anything pointing to
head (ie, that has the value rootp holds) after this
returns.
*/
void
dwarf_tdestroy(void *rootp, void (*free_node)(void *nodep))
{
struct hs_base *head = (struct hs_base *)rootp;
struct ts_entry *root = 0;
if(!head) {
return;
}
root = head->hashtab_;
dwarf_tdestroy_inner(head,free_node,0);
free(root);
free(head);
}