Since the book explains its design and implementation in a very comprehensive way, not to mention the copyright issues, it is nothing but waste to repeat it here, so I finish this document by giving introduction to the library; how to use the facilities is deeply explained in files that define them.
The Hash Library reserves identifiers starting with hash_
and HASH_
, and imports the Assertion Library (which requires the Exception Handling Library) and the Memory Management Library.
The Hash Library provides one global hash table, so that there is no function that creates a table or destroy it. A user can start to use the hash table without its creation just by putting data to it using an appropriate function: hash_string() for C strings, hash_int() for signed integers and hash_new() for other arbitrary forms of data. Of course, since the library internally allocates storage to manage hash keys and values, functions to remove a certain key from the table and to completely clean up the table are offered: hash_free() and hash_reset(). In addition, since strings are very often used to generate hash keys for them, hash_vload() and hash_aload() are provided and useful especially when preloading several strings onto the table.
mytable
a string key and its relevant value:
char *key, *val;
...
table_put(mytable, key, val);
This code, however, does not work because the second argument to table_put() should be a hash key not a raw string. Thus, the correct one should be:
table_put(mytable, hash_string(key), val);
One more thing to note is that hash_string() and similar functions to generate a hash key is an actual function. If a hash key obtained from your data is frequently used in code, it is better for efficiency to have it in a variable rather than to call hash_string() several times.
If your compiler rejects to compile the library with a diagnostic including "scatter[] assumes UCHAR_MAX < 256!" which says CHAR_BIT
(the number of bits in a byte) in your environment is larger than 8, you have to add elements to the array scatter
to make its total number match the number of characters in your implementation. scatter
is used to map a character to a random number. For how to generate the array, see the explanation given for the array in code.
Any comments about the library are welcomed. If you have a proposal or question on the library just email me, and then I will reply as soon as possible.
Copyright (c) 1994,1995,1996,1997 by David R. Hanson.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
For the parts I added or modified, the following applies:
Copyright (C) 2009-2011 by Jun Woong.
This package is a hash table implementation by Jun Woong. The implementation was written so as to conform with the Standard C published by ISO 9899:1990 and ISO 9899:1999.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THIS SOFTWARE IS PROVIDED ``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 AUTHOR 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.