advertising it occasionally here, where it seemed applicable. I
have received no bug reports.
I have just gotten around to writing a usage manual for it, which
follows. I would like some opinions on it. Please don't quote the
whole thing back at me, a short excerpt followed by your pithy
commentary will do nicely. I am off for an operation Monday,
so I won't be available for a while after that, and you might as
well hold things after Saturday.
HOW TO USE hashlib
=============== ===
<http://cbfalconer.home .att.net/download/hashlib.zip>
To use this easily you should also have a copy of hashlib.h
printed out, or easily available in another editor window. It
describes the complete interface to hashlib, and this is just an
explanation of the functions, why they exist, etc. hashlib.h
is extensively commented.
What is it for?
==============
You may be wondering "for what is hashlib useful". The answer
is that it is a storage facility. You can hand it things, and
it will tuck them away, and make it easy for you to find them
later.
A major point is that the time it takes to store, find, delete,
or retrieve an item is almost constant no matter how big the
table gets. Also, you don't have to worry about the table size,
because it will automatically adapt itself. It may hold 5 items
or millions. The limit is your memory.
What does it do?
===============
For a list of the things it will do, you should have the file
"hashlib.h" handy. This details all the things you can do, and
how to customize the system to your data. The interface
functions are:
hshinit, hshkill Make or destroy a hashtable
hshfind, hshinsert, hshdelete Insert, find, take out items
hshwalk For advanced usage, later
hshstatus Such things as how many stored
Customizing to your data:
=============== =========
In order to use a table, the first thing you have to do is to
create it with hshinit. At that time you tell hashlib how to
process your data. I will return to this later.
Your actual data takes some form, which is entirely up to you.
It must be possible to refer to a complete data item by a
single pointer. Your data also will have some sort of key, or
even multiple keys. It can have whatever auxiliary data you
like. This implies you must define a structure somewhere for
your own benefit:
typedef struct hashitem {
sometype yourkey;
otherstuff yourdata;
} item, *itemptr;
The field names, structure name, typedef'd names, etc are
entirely up to you. Somewhere in your program you will have
at least one of these things. hashlib will make more of them
in which to store copies of the data you insert.
Equality
========
Since hashlib works on all forms of data, it obviously can't
read your data description. So you have to tell it how to
find out that two data items have the identical key. This
introduces the type (defined in hashlib.h):
typedef int (*hshcmpfn)(voi d *litem, void *ritem);
which is a function you will design and program, and one of
the items you pass in the hshinit call is a pointer to that
function. Let us assume that in the item definition above
sometype is int (such as the typedef below under copying).
Then your comparison function could be:
mycmp(void *litem, void *ritem)
{
itemptr left = litem;
itemptr right = ritem;
int lvalue, rvalue;
lvalue = left->yourkey;
rvalue = right->yourkey;
return lvalue == rvalue;
}
NOTE: I have made this function more complex than it need
be, in order to emphasize how it goes about it.
The left and right pointers come from hashlib, and hashlib
doesn't know about your data type. Therefore it converts them
into the C universal pointer, a "void *". When you get them
back you have to convert them back into itemptr, so you can
access the fields of your data.
All hashlib cares about is "are they equal", so the above
returns only 0 or 1, for notequal and equal. The comparison
routine will be useful for other things if you make it return
-1, 0, or +1 for less, equal, greater. To do this you could
make the return statement say:
return (lvalue > rvalue) - (lvalue < rvalue);
which will turn out to be 1-0, 0-0, 0-1 for the three cases.
The point is not to return (lvalue - rvalue), because this
can run into overflow and give erroneous results.
Copying
=======
When you pass an item to hashlib you don't want to worry about
who owns the space it takes. Therefore the principle is
"hashlib owns all the items it stores". Thus hashlib makes a
copy of any data item it inserts into the table. Once more,
only you know how to do this, and you have to tell hashlib.
typedef void *(*hshdupfn)(vo id *item);
in hashlib.h specifies what this function must look like. For
the simple structure above, all it would have to do is malloc
space for a copy, and copy the fields. Remember it is dealing
with pointer to data, and the first thing you have to do is
make the item pointer into a pointer to your structure.
Lets make the simple data structure above more concrete:
typedef struct hashitem {
int yourkey;
int yourdata;
} item, *itemptr;
Then the hshdupefn (notice how the function is defined by
editing the typedef for hshdupfn) could be:
void *mydupe(void *item)
{
itemptr myitem = item;
itemptr newitem;
if (newitem = malloc(sizeof *newitem) {
newitem.yourkey = myitem.yourkey;
newitem.yourdat a = myitem.yourdata ;
/* or "*newitem = *myitem" in this case */
}
return newitem;
}
Notice again that only your code knows what is in the items to
be stored, and thus how to copy them. Your item can be as
complicated as you wish. So lets make it store strings:
typedef struct hashitem {
char *yourkey;
int yourdata;
} item, *itemptr;
and see how it affects the hshdupefn. Yourkey is now just a
pointer to a string somewhere, which may want to be modified
or used in some manner. So we have do what is called a deep
copy.
void *mydupe(void *item)
{
itemptr myitem = item;
itemptr newitem;
if (newitem = malloc(sizeof *newitem) {
if (newitem->yourkey =
malloc(1+strlen (myitem->yourkey) {
strcpy(newitem->yourkey, myitem->yourkey;
newitem.yourdat a = myitem.yourdata ;
}
else { /* we ran out of memory, release and fail */
free(newitem)
newitem = NULL
}
}
return newitem;
}
Notice how it returns NULL if malloc fails to secure the
necessary memory anywhere. This allows hashlib to do the
right things under nasty cases, such as exhausting memory.
The need for a deep copy is generally signalled by having
pointers in your data type description. All those pointers have
to be resolved to data that can belong to the hash table.
Letting Go
==========
Once you have thrown a whole mess of data at hashlib, and it is
keeping track, you may decide to release it all. While you
could often just abandon it, and let the operating system clean
up after you when your program ends, this is not a good
practice. Besides, your program may not end. So you have to
tell hashlib how to get rid of one item, which it will use to
get rid of all of them when you use the hshkill function
(described later).
typedef void (*hshfreefn)(vo id *item);
in hashlib.h describes that function. Now we will assume the
complex hshdupefn last described above, and the corresponding
type definition for an item. Again, we build the function
header by editing the typedef and converting the passed void*
pointer:
void myundupe(void *item)
{
itemptr myitem = item;
free(myitem->yourkey); /* First, because this won't */
free(myitem); /* exist after this one. */
}
thus returning all the allocated memory. Notice how it undoes
everything that mydupe did. The mydupe/myundupe pair could even
open and close files, but you will rarely want to handle
thousands of open files at once.
Hashing
=======
This is fundamental to the efficient operation of a hashtable,
although hashlib can put up with pretty rotten hashing and still
grind out answers (but it may take a long time). What we need
to do is calculate a single unsigned long value from the key.
What these functions are is basically black magic, therefore
hashlib contains a couple of utility functions usable for
hashing strings. There are also examples of hashing integers
in the hashtest.c program along with some references to the
subject of creating hash functions.
Because of the efficient way hashlib handles overflows (it
basically just corrects them) it is necessary to have two
hash functions. For the above item type with strings, they
would be:
typedef unsigned long (*hshfn)(void *item);
for reference, which we edit again and get:
unsigned long myhash(void *item)
{
itemptr myitem = item; /* getting used to this? */
return hshstrhash(myit em->yourkey);
}
and we need two such functions, so:
unsigned long myrehash(void *item)
{
itemptr myitem = item; /* getting used to this? */
return hshstrehash(myi tem->yourkey);
}
which basically differ only in their names and in the
convenience hash function they call.
Now we have finally customized the system to our own data
format. We will tell hashlib about these functions when
we create a hashtable with hshinit.
Using hashlib
=============
First, we need some way to refer to the table. So we must
have a data item of type hshtbl* to hold it. We will initialize
that by calling hshinit. This is much like opening a file. For
convenience here is the prototype for hshinit again:
/* initialize and return a pointer to the data base */
hshtbl *hshinit(hshfn hash, hshfn rehash,
hshcmpfn cmp,
hshdupfn dupe, hshfreefn undupe,
int hdebug);
Now this following is a fragment from your code:
hshtbl *mytable;
/* initialize and return a pointer to the data base */
mytable = hshinit(myhash, myrehash,
mycmp,
mydupe, myundupe,
0);
which tells hashlib all about the customizing functions you have
created. Note that all those functions can be static, unless
you have other uses for them outside your source file. You can
use those functions yourself as you please.
Don't forget the final 0 in the call to hshinit. That parameter
provides for future extensions and debugging abilities, and
passing a zero here will maintain compatibility.
You can create more than one hash table if you desire. If they
handle the same data format you can just do exactly the same
call as above, except you will need a new variable of type
hshtbl* to hold the table identification. If they don't hold
the same data type you can supply different functions to
hshinit. It is up to you.
hshtbl *mysecondtable;
mysecondtable = hshinit(....); /* as before */
These tables will live until you exterminate them. Meanwhile
you can store, find, delete, etc. items from the table. You
destroy the table by calling hshkill with the pointer that
hshinit returned.
hshkill(mytable ); /* all gone */
but until that is done, lets use the functions:
Inserting (storing) data:
=============== ==========
From here on I am assuming you have opened the hash table with
mytable = hshinit(...), and that you have defined your data
with:
typedef struct hashitem {
char *yourkey;
int yourdata;
} item, *itemptr;
Surprise, you store data by calling hshinsert. Here is the
prototype, for reference:
void * hshinsert(hshtb l *master, void *item);
and you call it with a pointer to the table in which to insert
the item, and a pointer to the item to insert.
You may have a variable of type item (after all, you know what
it is, even if hashlib does not). So the critical items are:
hshtable *mytable;
item myitem;
item *something;
You will put the data you want into myitem, filling its fields
as needed. Then you call:
something = hshinsert(mytab le, &myitem);
If, after this, 'something' is NULL, the insertion failed
(probably because you ran out of memory). Otherwise 'something'
points to the piece of memory owned by hshlib which stores a
copy of myitem. You can use something to modify the stored
copy, but you MUST NOT do anything that would change the value
of the key, and thus change what a hshfn such as myhash or
myrehash returns when passed that item. NEVER EVER do that.
One thing you might want to do is have a field in an item that
holds a count. You could have the dupe function zero this
field, so that you know how it is initialized. Then, when
hshinsert returns an itemptr you can use that to increment
that field. That way you can keep track of how many times a
given key has been inserted.
NOTE: If hshinsert finds an item already stored, it simply
returns a pointer to that storage. It does not use the dupe
function to make another copy.
Finding a data item by the key:
=============== ===============
Again we have the same variables as above for insertion. We
simply call:
something = hshfind(mytable , &item);
and if 'something' is NULL the item is not present, otherwise
it is a pointer to the memory holding it. The same cautions
as for hshinsert hold, i.e. you MUST NOT do anything that
affects the key and thus the hash functions. Being present
means only that 'something' and &item have identical keys, as
defined by mycmp() function.
Deleting stored items:
=============== ======
Again, we have the same variables. Surprise, the calling format
is the same:
something = hshdelete(mytab le, &item);
but now there is a significant difference. The hash table no
longer owns the memory that stored that item, you do. So you
have to do something with it, assuming it isn't NULL (meaning
that the value in item was never stored in the table). What
you do is up to you, but sooner or later you should release
it by:
myundupe(someth ing);
which you designed specifically for this purpose.
Other abilities
===============
I plan to add information about walking the entire contents of
the table, and performing operations on each stored item. There
are illustrations of these operations in the demonstration
applications (markov and wdfreq) in the hashlib package.
--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
