1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#C hashtable#
ATTENTION: Consider this repository an archive. I have since used this hashtable
in some projects and added modifications as necessary. For newest
incarnation of this code see: https://git.koszko.org/hydrilla/tree/hashtable.c
This is a userspace C hashtable implementation. It:
- resolves collisions by chaining
- resizes automatically when number of entries increases or decreases
- does resize operation in parts, so that there isn't a single access with O(n) complexity
- uses malloc and calloc from stdlib
- stores keys and values as `void*`
- relies on user to provide hash and compare functions for keys other than strings
- compiles as c99 and c11
- consists of 2 files (.c and .h), that can be simply copied into some project
##Using##
####API####
Read [hashtable.h](hashtable.h).
You can also look into [example_use.c](example_use.c), where a console program showing the use of this hashtable is implemented.
####Using in a project#####
It you want to use this in your project, just add hashtable.c to your C source files and include hashtable.h wherever you use hashtables.
####Console example####
Run something like:
$`gcc hashtable.c example_use.c -std=c99 -Wall -O2 -o example_use`
And then start the program:
$`./example_use`
It understands the following kinds of commands fed to it's input:
`add <key> <value>`
`set <key> <value>`
`get <key> <value>`
`rem <key> <value>`
As well as:
`entries`
which prints the number of key→value pairs stored in the hashtable and
`print`
which prints all the mappings in the ht.
##Incomplete parts##
The example_use program can be used to manually play with the hashtable, but some automated tests would be useful to make sure nothing breaks when we use this in something bigger. Right now I don't have motivation to write this.
I compiled and run the example on i686 and x86_64 with glibc under gcc with `-std=c99 -Wall -pedantic` with no warnings, but I made no attempts on other platforms, so I'm not 100% sure it will work under a different setup.
While in sources I added comments I considered necessary, I admit, that API description in hashtable.h is not a full, formal description. E.g. it does not mention, that when using ht_map(), the hashtable shouldn't be modified by mapfunc(). I skipped details like this, becuase I think writing a full manual for such a short piece of code would be an overkill and also because I assume som things to be obvious or deducable for a programmer.
##Motivations##
I made a C hashtable long time ago as an exercise. A bit later, when writing something in C, I needed a hashtable and couldn't find anything suitable on the net. There are hashtables that are included in bigger projects one would rather not depend on, like GLib. There are some quick and dirty snippets on git repos, tutorial pages, etc., that are not really usable in their current state. Finally, some implementations lack stuff I consider important, like automatic resizing (in some cases fixed-size hashtables are preferred, just not everywhere). Back then I ended up using my own hashtable. Now, one year after, having some spare time I dug up my old hashtable with the intention of cleaning it up and sharing with others. I ended up almost completely rewriting it. This is the result :)
##Considerations##
I have thought about also writing a fixed-size, memory-allocation-schema-agnostic hashtable, that would be suitable for bare metal. Another interesting thing to do would be a thread-safe hashtable for use with pthread.
As to this version, it could also be improved in some ways. Maybe not call malloc for every single entry added, but rather allocate a block of "nodes" for later use?
I could use inline documentation with a tool like ROBODoc.
And, most important, I could write some proper tests for this ht...
Anyways, right now I'm not planning to do any of these. Moving onto sth else. I don't even know if anyone is ever going to make use of this code. Just in case, you can write to me at `echo a3dvanR1c0Bwcm90b25tYWlsLmNvbQo= | base64 -d`.
|
