Storing key-value pairs in plain C

Question

I am trying to find a way to store key, value pairs in C in an efficient way to quickly retrieve data. I look online and there seems to be no quick and easy way to store them, for example, in Java. I need to have access to frequency and frequent updates, as well as the ability to add new keys and sort them in order. I read about using qsort() and bsearch() to execute them, but I'm not sure which data structure to use to store it.

Answer 1

You are looking for an associative container. There is no “direct” way in C, since the standard library does not provide any data structure. You can try looking for a third-party library that provides functionality, or minimize your own solution.

Answer 2

I understand that this is an old thread, but I may have something that can help someone who is looking for a not-so-complicated solution.

I have done this several times in different ways. How this is done depends on several factors:

• Do you know the maximum number of key / value pairs that you need to track?
• Are all values ​​of the same type?
• How fast should it be?

If the answers to 1 and 2 are yes, then this can be pretty straightforward. When the answer to 3 is “not important” or when the maximum number of pairs is not too large, I use arrays or blocks of dynamically allocated memory, considered as arrays.

There are two arrays in this scheme: - an array of indices (not a key) - an array of structures of a key / value pair containing the key name and value

You also have a structure that keeps track of a list of keys / values, containing (minimum) pointers to arrays of index and key / value structures, the number of key / value pairs currently defined, and the maximum number of key / value pairs that can be stored.

Initially, the number of key / value pairs is 0, each element of the array in the index array contains an initial value (it can be zero, but this is usually what indicates that it is not used, for example -1), and all elements of the array of structures are key pairs / values ​​are reset (no name, no value).

The index array is maintained so that the index values ​​refer to the structures of the key / value pair in another array in the correct order. Insertions and deletions do not move any existing pair structure, but only indexes. When the key / value pair is removed, nullify the structure containing it.

When using qsort () or its siblings, the comparison function uses the indices in the index array to access the names of the corresponding key / value pairs, and your exchange function changes the index values ​​in the index array. The insert performs an overlay copy in place (from the end to the insertion point) to shuffle the key indices that appear after the new key has dropped one position in the index array, and the deletion does a similar upward shuffle to close the gap where the deleted key was .

A slightly faster version of this, which uses more memory for storage, uses a C connection to maintain the forward chain index in the unused elements of the key / value pair, and initialization combines them with the next “free” index in the context of the list. This prevents searching the list of free items when inserting a new pair. When you need a free key / value pair object, use the index stored in the "next free" for the new item and set the "next free" to the saved chain index in the newly declared free object. When you drop a pair, simply copy the “next free” value to the chain index in the freed object and set the index of the freed object as the new “next free” value.

An index array can also be implemented using pointers to key / value structures in memory. In this case, the “next free” and chain links in the list of free objects also become pointers.

The above diagram works well for small key size values ​​and values ​​and simple value types.

Answer 3

As Baltasark said, C has no data structure for this purpose. However, you can use an implementation based on a structure that should support: initializing, receiving, adding, and deleting operations. Some good designs are suggested here .

Answer 4

A very fast and efficient way of memory is to use Judy arrays. It is easy to use if you are not afraid of pointers.

http://judy.sourceforge.net/

It is licensed under LGPL

Can be installed on Debian / Ubuntu with: sudo apt-get install libjudy-dev

One caveat is that the word is the length of the processor's own word. This makes it fast, but can have portability between 32/64 bit machines when using Judy1 or JudyL.

The following types are available:

 Judy1 - maps an Index (word) to a bit JudyL - maps an Index (word) to a Value (word/pointer) JudySL - maps an Index (null terminated string) to a Value JudyHS - maps an Index (array-of-bytes) of Length to a Value 

Sample code using strings as keys (JudySL):

 #include <stdio.h> #include <Judy.h> #define DIE(x) { fprintf(stderr,"%s\n",x); exit(-1); } int main() { Pvoid_t PJArray = (PWord_t)NULL; // Judy array. PWord_t PValue; // Judy array element. Word_t Bytes; // size of JudySL array. uint8_t key[100]; //max len for key is 100 const char *value1="Value One"; const char *value2="Value Two"; JSLI(PValue, PJArray, "key1"); // Insert key if (PValue == PJERR) DIE("Out of memory\n"); *PValue=(Word_t)value1; // Set pointer to value JSLI(PValue, PJArray, "key2"); // Insert key if (PValue == PJERR) DIE("Out of memory\n"); *PValue=(Word_t)value2; // Set pointer to value key[0]='\0'; // start with smallest string. JSLF(PValue, PJArray, key); // get first key/value while (PValue != NULL) { printf("key=%s, value=%s\n",key,(char*)*PValue); JSLN(PValue, PJArray, key); // get next key/value } JSLG(PValue, PJArray, "key2"); // lookup a key printf("key2:%s\n",(char*)*PValue); JSLFA(Bytes, PJArray); // free array return 0; } 

compile with: gcc judy_sample.c -o judy_sample -lJudy