Quick Way to Implement Dictionary in C

Question

One of the things which I miss while writing programs in C is a dictionary data structure  What s the most convenient way to implement one in C  I am not looking for performance  but ease of coding it from scratch  I don t want it to be generic either -- something like char  int will do  But I do want it to be able to store an arbitrary number of items  This is intended more as an exercise  I know that there are 3rd party libraries available which one can use  But consider for a moment  that they don t exist  In such a situation what s the quickest way you can implement a dictionary satisfying the above requirements

User · Accepted Answer

Section 6 6 of The C Programming Language presents a simple dictionary  hashtable  data structure  I don t think a useful dictionary implementation could get any simpler than this  For your convenience  I reproduce the code here    struct nlist      table entry         struct nlist  next     next entry in chain        char  name     defined name        char  defn     replacement text         define HASHSIZE 101 static struct nlist  hashtab HASHSIZE      pointer table        hash  form hash value for string s    unsigned hash char  s        unsigned hashval      for  hashval   0   s      0   s          hashval    s   31   hashval      return hashval   HASHSIZE        lookup  look for s in hashtab    struct nlist  lookup char  s        struct nlist  np      for  np   hashtab hash s    np    NULL  np   np- gt next          if  strcmp s  np- gt name     0            return np     found        return NULL     not found       char  strdup char        install  put  name  defn  in hashtab    struct nlist  install char  name  char  defn        struct nlist  np      unsigned hashval      if   np   lookup name      NULL       not found            np    struct nlist    malloc sizeof  np            if  np    NULL     np- gt name   strdup name      NULL            return NULL          hashval   hash name           np- gt next   hashtab hashval           hashtab hashval    np        else    already there            free  void    np- gt defn     free previous defn        if   np- gt defn   strdup defn      NULL         return NULL      return np     char  strdup char  s     make a duplicate of s          char  p      p    char    malloc strlen s  1       1 for     0           if  p    NULL         strcpy p  s       return p      Note that if the hashes of two strings collide  it may lead to an O n  lookup time  You can reduce the likelihood of collisions by increasing the value of HASHSIZE  For a complete discussion of the data structure  please consult the book

User · Answer

GLib and gnulib  These are your likely best bets if you don t have more specific requirements  since they are widely available  portable and likely efficient    GLib  https   developer gnome org glib  by GNOME project  Several containers documented at  https   developer gnome org glib stable glib-data-types html including  Hash Tables  and  Balanced Binary Trees   License  LGPL gnulib  https   www gnu org software gnulib  by the GNU project  You are meant to copy paste the source into your code  Several containers documented at  https   www gnu org software gnulib MODULES html ansic ext container including  rbtree-list    linkedhash-list  and  rbtreehash-list   GPL license    See also  Are there any open source C libraries with common data structures

User · Answer

Create a simple hash function and some linked lists of structures   depending on the hash   assign which linked list to insert the value in   Use the hash for retrieving it as well    I did a simple implementation some time back          define K 16    chaining coefficient  struct dict       char  name     name of key        int val        value        struct dict  next     link field        typedef struct dict dict  dict  table K   int initialized   0    void  putval   char   int    void init dict            initialized   1      int i        for i 0 iname    char    malloc  strlen key name  1       ptr- val   sval      strcpy  ptr- name key name         ptr- next    struct dict   table hsh       table hsh    ptr       int getval   char  key name            int hsh   hash key name          dict  ptr      for  ptr   table hsh   ptr     dict    0          ptr    dict   ptr- next      if  strcmp  ptr- name key name     0          return ptr- val      return -1

User · Answer

Hashing is the key  I think use lookup table and hashing key for this  You can find many hashing function online

User · Answer

The quickest way would be to use an already-existing implementation  like uthash   And  if you really want to code it yourself  the algorithms from uthash can be examined and re-used  It s BSD-licensed so  other than the requirement to convey the copyright notice  you re pretty well unlimited in what you can do with it

User · Answer

For ease of implementation  it s hard to beat naively searching through an array  Aside from some error checking  this is a complete implementation  untested    typedef struct dict entry s       const char  key      int value    dict entry s   typedef struct dict s       int len      int cap      dict entry s  entry    dict s   dict t   int dict find index dict t dict  const char  key        for  int i   0  i  lt  dict- gt len  i              if   strcmp dict- gt entry i   key                 return i                      return -1     int dict find dict t dict  const char  key  int def        int idx   dict find index dict  key       return idx    -1   def   dict- gt entry idx  value     void dict add dict t dict  const char  key  int value       int idx   dict find index dict  key      if  idx    -1           dict- gt entry idx  value   value         return          if  dict- gt len    dict- gt cap           dict- gt cap    2         dict- gt entry   realloc dict- gt entry  dict- gt cap   sizeof dict entry s            dict- gt entry dict- gt len  key   strdup key      dict- gt entry dict- gt len  value   value     dict- gt len       dict t dict new void        dict s proto    0  10  malloc 10   sizeof dict entry s         dict t d   malloc sizeof dict s         d   proto      return d     void dict free dict t dict        for  int i   0  i  lt  dict- gt len  i              free dict- gt entry i  key             free dict- gt entry       free dict

User · Answer

Additionally  you can use Google CityHash   include  lt stdlib h gt   include  lt stddef h gt   include  lt stdio h gt   include  lt string h gt    include  lt byteswap h gt    include  quot city h quot   void swap uint32  a  uint32  b        int temp    a       a    b       b   temp      define PERMUTE3 a  b  c  swap  amp a   amp b   swap  amp a   amp c       Magic numbers for 32-bit hashing   Copied from Murmur3  static const uint32 c1   0xcc9e2d51  static const uint32 c2   0x1b873593   static uint32 UNALIGNED LOAD32 const char  p      uint32 result    memcpy  amp result  p  sizeof result      return result     static uint32 Fetch32 const char  p      return UNALIGNED LOAD32 p         A 32-bit to 32-bit integer hash copied from Murmur3  static uint32 fmix uint32 h      h    h  gt  gt  16    h    0x85ebca6b    h    h  gt  gt  13    h    0xc2b2ae35    h    h  gt  gt  16    return h     static uint32 Rotate32 uint32 val  int shift         Avoid shifting by 32  doing so yields an undefined result    return shift    0   val     val  gt  gt  shift     val  lt  lt   32 - shift        static uint32 Mur uint32 a  uint32 h         Helper from Murmur3 for combining two 32-bit values    a    c1    a   Rotate32 a  17     a    c2    h    a    h   Rotate32 h  19     return h   5   0xe6546b64     static uint32 Hash32Len13to24 const char  s  size t len      uint32 a   Fetch32 s - 4    len  gt  gt  1      uint32 b   Fetch32 s   4     uint32 c   Fetch32 s   len - 8     uint32 d   Fetch32 s    len  gt  gt  1      uint32 e   Fetch32 s     uint32 f   Fetch32 s   len - 4     uint32 h   len     return fmix Mur f  Mur e  Mur d  Mur c  Mur b  Mur a  h            static uint32 Hash32Len0to4 const char  s  size t len      uint32 b   0    uint32 c   9    for  size t i   0  i  lt  len  i          signed char v   s i       b   b   c1   v      c    b        return fmix Mur b  Mur len  c        static uint32 Hash32Len5to12 const char  s  size t len      uint32 a   len  b   len   5  c   9  d   b    a    Fetch32 s     b    Fetch32 s   len - 4     c    Fetch32 s     len  gt  gt  1   amp  4      return fmix Mur c  Mur b  Mur a  d         uint32 CityHash32 const char  s  size t len      if  len  lt   24        return len  lt   12            len  lt   4   Hash32Len0to4 s  len    Hash32Len5to12 s  len             Hash32Len13to24 s  len             len  gt  24   uint32 h   len  g   c1   len  f   g    uint32 a0   Rotate32 Fetch32 s   len - 4    c1  17    c2    uint32 a1   Rotate32 Fetch32 s   len - 8    c1  17    c2    uint32 a2   Rotate32 Fetch32 s   len - 16    c1  17    c2    uint32 a3   Rotate32 Fetch32 s   len - 12    c1  17    c2    uint32 a4   Rotate32 Fetch32 s   len - 20    c1  17    c2    h    a0    h   Rotate32 h  19     h   h   5   0xe6546b64    h    a2    h   Rotate32 h  19     h   h   5   0xe6546b64    g    a1    g   Rotate32 g  19     g   g   5   0xe6546b64    g    a3    g   Rotate32 g  19     g   g   5   0xe6546b64    f    a4    f   Rotate32 f  19     f   f   5   0xe6546b64    size t iters    len - 1    20    do       uint32 a0   Rotate32 Fetch32 s    c1  17    c2      uint32 a1   Fetch32 s   4       uint32 a2   Rotate32 Fetch32 s   8    c1  17    c2      uint32 a3   Rotate32 Fetch32 s   12    c1  17    c2      uint32 a4   Fetch32 s   16       h    a0      h   Rotate32 h  18       h   h   5   0xe6546b64      f    a1      f   Rotate32 f  19       f   f   c1      g    a2      g   Rotate32 g  18       g   g   5   0xe6546b64      h    a3   a1      h   Rotate32 h  19       h   h   5   0xe6546b64      g    a4      g   bswap 32 g    5      h    a4   5      h   bswap 32 h       f    a0      PERMUTE3 f  h  g       s    20      while  --iters    0     g   Rotate32 g  11    c1    g   Rotate32 g  17    c1    f   Rotate32 f  11    c1    f   Rotate32 f  17    c1    h   Rotate32 h   g  19     h   h   5   0xe6546b64    h   Rotate32 h  17    c1    h   Rotate32 h   f  19     h   h   5   0xe6546b64    h   Rotate32 h  17    c1    return h

User · Answer

I am surprised no one mentioned hsearch hcreate set of libraries which although is not available on windows  but is mandated by POSIX  and therefore available in Linux   GNU systems   The link has a simple and complete basic example that very well explains its usage   It even has thread safe variant  is easy to use and very performant

User · Answer

The quickest method would be using binary tree  Its worst case is also only O logn

User · Answer

here is a quick implement  i used it to get a  Matrix  sruct  from a string  you can have a bigger array and change its values on the run also   typedef struct    int   lines  int isDefined   mat  mat matA  matB  matC  matD  matE  matF      an auxilary struct to be used in a dictionary    typedef struct    char  str  mat  matrix   stringToMat      creating a  dictionary  for a mat name to its mat  lower case only     stringToMat matCases               mat a    amp matA           mat b    amp matB           mat c    amp matC           mat d    amp matD           mat e    amp matE           mat f    amp matF        mat  getMat char   str        stringToMat  pCase      mat   selected   NULL      if  str    NULL                   runing on the dictionary to get the mat selected            for pCase   matCases  pCase    matCases   sizeof matCases    sizeof matCases 0    pCase                           if  strcmp  pCase- gt str  str                   selected    pCase- gt matrix                     if  selected    NULL              printf   s is not a valid matrix name n   str             else         printf  expected matrix name  got NULL n        return selected

User · Answer

A hashtable is the traditional implementation of a simple  Dictionary    If you don t care about speed or size  just google for it   There are many freely available implementations    here s the first one I saw -- at a glance  it looks ok to me    it s pretty basic   If you really want it to hold an unlimited amount of data  then you ll need to add some logic to  realloc  the table memory as it grows    good luck

[c] Quick Way to Implement Dictionary in C

Examples related to c

Examples related to data-structures

Examples related to dictionary