stb_ds.h

stb_ds.h is a public-domain single-header-file C library for type-safe manipulation of two basic container types: dynamic arrays and hash tables. (The code also works in C++, although if you do not need C/C++ interoperation you'd probably want to use something template-based like vector<>.)

Arrays

Dynamic arrays are accessed using a pointer to the type of data you want in the array.

Here's some sample code for creating and manipulating a dynamic array:

 int main(void)
 {
   int *array = NULL;
   arrput(array, 2);
   arrput(array, 3);
   arrput(array, 5);
   for (int i=0; i < arrlen(array); ++i)
     printf("%d ", array[i]);
 }

arrput pushes the value onto the end of the dynamic array (like std::vector.push_back), so the above code will print 2 3 5.

Note that these macros write to the array variable if the array has to be resized. This means that if you pass a dynamic array into a function which increases its length, you need to return the updated array from the function to its caller. In other words, the semantics are the same as any realloc()-ed pointer, and are unlike the semantics of things like std::vector<>, where the core object is stable even if the array elements aren't.

The following functions are defined:

arrlen - the length of the dynamic array
arrlenu - the length of the dynamic array as an unsigned type
arrput - copy an object into the dynamic array
arrfree - free the entire array
arraddn - adds n uninitialized values to the dynamic array
arrsetlen - sets the length of the array (leaves new slots uninitialized)
arrlast - the last item in the array as an lvalue
arrins - inserts an item in the middle of the array
arrdel - deletes an item from the middle of the array, moving the following items over
arrswapdel - deletes an item from the middle of the array, replacing it with the formerly last item
arrcap - returns the internal capacity, the maximum length the array can be without reallocating it
arrsetcap - sets the internal capacity. it is not possible to shrink the capacity (currently)

The name 'arrpush' is an alias for 'arrput' for compatibility with older stb libraries.

Hash map

Hash maps (i.e. hash tables) are created by defining a structure with a key field and a value field. Here's some sample code for creating and manipulating a hash table:

 int main(void)
 {
   float f;
   struct { float key; char value; } *hash = NULL;
   f=10.5; hmput(hash, f, 'h');
   f=20.4; hmput(hash, f, 'e');
   f=50.3; hmput(hash, f, 'l');
   f=40.6; hmput(hash, f, 'X');
   f=30.9; hmput(hash, f, 'o');

   f=40.6; printf("%c - ", hmget(hash, f));

   f=40.6; hmput(hash, f, 'l');
   for (int i=0; i < hmlen(hash); ++i)
     printf("%c ", hash[i].value);
 }

hmput appends new entries to the end of the array, but updates existing ones, so the above code will print X - h e l l o. Note that if there are deletions, the table will become reordered (using swap-delete), so you typically should not make assumptions about the order of items in the table; this is just convenient for the simple demonstration above.

Note that on Visual Studio, the hash key provided to hmput must be an lvalue so the library can take the address of it. In practice this is not normally a burden, but on GCC and Clang, this limitation is eliminated, so you can write:

 int main(void)
 {
   float f;
   struct { float key; char value; } *hash = NULL;
   hmput(hash, 10.5, 'h');
   hmput(hash, 20.4, 'e');
   hmput(hash, 50.3, 'l');
   hmput(hash, 40.6, 'X');
   hmput(hash, 30.9, 'o');

   printf("%c - ", hmget(hash, 40.6));

   hmput(hash, 40.6, 'l');
   for (int i=0; i < hmlen(hash); ++i)
     printf("%c ", hash[i].value);
 }

You can specify a default value which is returned when you try to get a key that's not in the map. The default value is all-bits-0.

 int main(void)
 {
   int i,n;
   struct { int key; char value; } *hash = NULL;

   hmdefault(hash, 'l');
   i=0; hmput(hash, i, 'h');
   i=1; hmput(hash, i, 'e');
   i=4; hmput(hash, i, 'o');
   for (int i=0; i <= 4; ++i)
     printf("%c ", hmget(hash,i));
 }

The above code prints h e l l o.

Keys are arbitrary

The key can be any type we want; two keys are considered equal if they are bit-identical, so this may or may not be what you want for pointers, and is definitely not what you want for strings. For example:

 typedef struct { int x,y; } pair;
 
 int main(void)
 {
   int i;
   pair p;
   struct { pair key; char value; } *hash = NULL;
   p = (pair){2,3}; hmput(hash, p, 'h');
   p = (pair){7,4}; hmput(hash, p, 'e');
   p = (pair){1,1}; hmput(hash, p, 'l');
   p = (pair){5,5}; hmput(hash, p, 'x');
   p = (pair){3,5}; hmput(hash, p, 'o');

   p = (pair){5,5}; hmput(hash, p, 'l');
   for (int i=0; i < hmlen(hash); ++i)
     printf("%c ", hash[i].value);
 }

The basic hashmap functions are:

hmlen - The length of the hashmap array data for iterating the hashmap contents
hmlenu - As above, but unsigned
hmget - Get the value corresponding to a key, or return the default
hmgeti - Return the index into the array of a given key, or -1
hmput - Update an existing key,value pair, or add a new one if the key isn't present
hmdel - Delete a key,value pair if the key is present
hmdefault - Set the default value used by hmget

Structures can have more fields

In addition, structures can contain multiple value fields. The only requirement is that there is a key field. To do this, you must use structure values explicitly.

 typedef struct { int key; float my_val; char *my_string; } my_struct;
 int main(void)
 {
   my_struct *hash = NULL;
   my_struct s;
   s = (my_struct) { 20, 5.0 , "hello " };
   hmputs(hash, s);
   s = (my_struct) { 40, 2.5 , "failure"};
   hmputs(hash, s);
   s = (my_struct) { 40, 1.1 , "world!" };
   hmputs(hash, s);
   s = (my_struct) { 0,0,0 };
   printf("%s", hmgets(hash, 20).my_string);
   printf("%s", hmgets(hash, 40).my_string);
 }

Because the structure value is copied into the hash table by hmputs, the above code prints hello world!.

The hashmap functions for manipulating structures without a value field are:

hmlen - The length of the hashmap array data for iterating the hashmap contents
hmgets - Get the value corresponding to a key, or return the default
hmgeti - Return the index into the array of a given key, or -1
hmputs - Update an existing structure, or add a new one if the key isn't present
hmdel - Delete a structure if the key is present
hmdefaults - Set the default struct used by hmget

String hashmaps

A separate set of functions are provided for when the key is a char* pointer. In this case the keys do not need to be lvalues in Visual Studio.

 int main(void)
 {
   struct { char *key; char value; } *hash = NULL;
   shput(hash, "bob"   , 'h');
   shput(hash, "sally" , 'e');
   shput(hash, "fred"  , 'l');
   shput(hash, "jen"   , 'x');
   shput(hash, "doug"  , 'o');

   char name[4] = "jen";
   shput(hash, name    , 'l');

   for (int i=0; i < shlen(hash); ++i)
     printf("%c ", hash[i].value);
 }

Even though the original `"jen"` and the final shput() of name have different addresses, the code above will print h e l l o.

Here is sample code to count duplicate lines in a file.

 int main(int argc, char **argv)
 {
   struct { char *key; int value; } *hash = NULL;
   int i,n;
   char **dict = stb_stringfile(argv[1], &n);
   for (i=0; i < n; ++i) {
     int z = shget(hash, dict[i]); // default value is 0
     shput(hash, dict[i], z+1);
   }
   for (i=0; i < shlen(hash); ++i)
     if (hash[i].value > 1)
       printf("%4d %s\n", hash[i].value, hash[i].key);
 }

Note that by default shput stores whatever char* pointer was passed in. Using a string stored on the stack as in the earlier "jen" code will not usually work, since the string will be overwritten later. To address this, string hashmaps provide two optional facilities for storing permanent strings.

You can have the internal copy of keys each be allocated separately with malloc:

 struct { char *key; char *value } *hash;
 sh_new_strdup(hash);
 char name[4] = "bob";
 shput(hash, name, "hi there");
 name[0] = x;
 printf("%s", shget(hash, "bob").value);

Or you can have string keys be stored in an arena private to this hash table:

 struct { char *key; char *value } *hash;
 sh_new_arena(hash);
 char name[4] = "bob";
 shput(hash, name, "hi there");
 name[0] = x;
 printf("%s", shget(hash, "bob").value);

Each of the above code fragments will print hi there.

Use sh_new_arena for hash tables if you never delete keys. Using sh_new_strdup is slower, because the strings must be allocated and freed on each shput and shdel, whereas sh_new_arena bundles multiple allocations together to minimize memory allocations. However, if you use shdel with sh_new_arena, the memory for the deleted string will be wasted until you delete the entire table with shfree.

The string hashmap also provides structure functions shgets and shputs. These functions should not be used when using sh_new_arena and sh_new_strdup, as the string found in the structure will always be used. You can do strdup() yourself on keys. A simple string arena API is also provided that you can use as well.

The complete set of string hashmap functions is:

shlen - The length of the hashmap array data for iterating the hashmap contents
shlenu - As above, but unsigned
shget - Get the value corresponding to a key, or return the default
shgets - Get the value corresponding to a key, or return the default
shgeti - Return the index into the array of a given key, or -1
shput - Update an existing key,value pair, or add a new one if the key isn't present
shputs - Update an existing structure, or add a new one if the key isn't present
shdel - Delete a key,value pair if the key is present
shdefault - Set the default value used by hmget
shdefaults - Set the default struct used by hmget
sh_new_arena - Overwrites pointer with a new hashmap using a string arena for string management
sh_new_strdup - Overwrites pointer with a new hashmap using strdup for string management

In addition, the string arena has two functions:

stbds_stralloc - Allocates a string in a string arena
stbds_strreset - Frees all the strings in a string arena

Implementation notes

All data structures use the trick of storing extra data "before" the pointed-to-array. In the case of dynamic arrays this includes the length and capacity of the array. For hash tables, a pointer is stored to a separately allocated hash table. The array part of the hash table is actually valid from -1..`hmlen`, with -1 storing the default value from hmdefault.

The code uses size_t as an unsigned type and ptrdiff_t as a signed type. These are usually the same size as pointers (i.e. uintptr_t, but with compatibility with older compilers), which are usually the same size as registers. However, there are some compilation models in which pointers are only 32-bits on 64-bit architectures, in which case these types gain an advantage for size overhead, but lose the ability to compute hashes 64-bits-at-a-time.

String hashing is done with a simple but relatively good hash function which circular shifts and adds characters, with a final mix.

Binary data hashing uses hard-coded fast-and-decent hash functions for 4- and 8-byte data (8-byte is only on 64-bit platforms). All other data is hashed using a weakened form of Siphash. If you define STBDS_SIPHASH_2_4 on 64-bit platforms, correct SipHash-2-4 will be used for all keys.

Hash tables are bucketed and cache-aligned for performance. However, because they use open addressing with power-of-two table sizes, there will be performance spikes when the table is resized.

The string arena begins by allocating blocks of size 512 bytes to minimize wastage, but doubles these block sizes up to a size of 1MB to minimize the number of memory allocations which must be performed.