hashlib package

I released this under GPL some time ago, (2003-May) and have been 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 ==================

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)(void *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)(void *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.yourdata = 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.yourdata = 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)(void *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(myitem->yourkey); }

and we need two such functions, so:

unsigned long myrehash(void *item) { itemptr myitem = item; /* getting used to this? */ return hshstrehash(myitem->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: =========================

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(hshtbl *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(mytable, &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(mytable, &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(something); 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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
     USE worldnet address!