How to Implement Dictionary in C

This article will demonstrate multiple methods about how to implement a dictionary in C.

Use hcreate, hsearch and hdestroy to Implement Dictionary Functionality in C

Generally, the C standard library does not include a built-in dictionary data structure, but the POSIX standard specifies hash table management routines that can be utilized to implement dictionary functionality. Namely, hcreate, hsearch and hdestroy provide the features like creating a hash table, inserting items into it, searching the item in a table, and deallocating the whole data structure. Even though the implemented functionality is the bare minimum, it can solve many problem scenarios.

At first, the hcreate function needs to be called to create a hash table with a given maximum number of elements, which is passed as the only argument. Note that capacity can’t be modified after the hcreate call; thus, the user needs to factor this issue into the code structure. Once the table is created, the hsearch function can be called to add items into it. It takes 2 arguments; the first one is of type ENTRY, defined as struct of char* for the key and void* for corresponding data. The second parameter is of type ACTION, which is essentially an enum consisting of two elements, FIND and ENTER. The latter values are used to indicate what operation to conduct on the table.

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  e.key = "Intel";
  ep = hsearch(e, FIND);
  printf("%s -> %s\n", e.key, (char *)ep->data);

  hdestroy();
  exit(EXIT_SUCCESS);
}

Output:

Intel -> Willow Cove

Notice that the code examples demonstrate the key-value pairs represented by clear text, but the user may employ hashing algorithms to create keys and store those in the table. In this case, we added 6 items to the table using the simple iteration and skipped the last two elements. The next for loop, though, queries every item from the original array and prints the corresponding data.

The hdestroy function is used to free hash table memory, but it does not free the buffers in the ENTRY objects, which is usually created by the user. Thus, if pointers in these objects point to dynamic memory, the caller is responsible for keeping the handles for them and deallocating before the program exit. Mind that individual entries can not be deleted from the table.

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  for (size_t i = 0; i < capacity; i++) {
    e.key = companies[i];
    ep = hsearch(e, FIND);

    ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
       : printf("%s -> %s\n", e.key, "Entry not found");
  }

  hdestroy();
  exit(EXIT_SUCCESS);
}

Output:

Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found