dictionary/map/key-value pairs data structure in C

Question

How does one construct and access a set of key-value pairs in C? To use a silly simple example, let's say I want to create a table which translates between an integer and its square root.

If I were writing javascript, I could just do this:

var squareRoots = {
   4: 2,
   9: 3,
   16: 4,
   25: 5
}

and then access them like:

var squareRootOf25 = squareRoots[5]

How do I do this in C? What if I want to use one type of enum as the key and another type of enum as the value?

Answer 1

This problem could be solved using a map. Unfortunately, there is no data structure in C that is quite alike to a map (A map is a container that stores elements in a key-value pair fashion. Each element has a unique key that is used to access the corresponding value. Maps are typically implemented as balanced binary search trees, which provide efficient lookup and insertion operations). That means you should implement it yourself. Although this might not be the optimal approach to this challenge, I have implemented a map using Binary Search Tree structure, not ensuring the fact that the worst time complexity is not linear. Another data structure which ensures that the worst time complexity is still O(log2(n)) is the self-balancing Red-Black Tree. I will next present my attempt in implementing the requested so-called map.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Pair{
    char *first;
    int second;
};
struct Pair *make_pair(char *a,int b){
    struct Pair *x=(struct Pair *)malloc(sizeof(struct Pair));
    x->first=strdup(a);
    x->second=b;
    return x;
};
int make_hash(char *s,int size){
    unsigned long long hash=5813;
    for(int i=0;s[i];i++) hash=hash*33+s[i];
    return (hash%size);
}
int compare(char *a,char *b){
    //Hello! I am the compare function and I:
    // return -1, if a and b are the same.
    // return 0, if a "<" b.
    // return 1, if a ">" b.
    int i=0,x=0;
    for(;a[i]&&b[i];i++){
        if(b[i]>a[i]) return 0;
        if(b[i]==a[i])x++;
    }
    if(!a[i]&&!b[i]&&x==i)
    return -1;
    if(!a[i]&&b[i])
    return 0;
    return 1;
};
struct Nod{
    struct Pair *val;
    struct Nod *st,*dr;
};
struct Tree{
    struct Nod *top;
};
void addtotree(struct Tree *t,char *s,int val){
    if(!t->top){
        t->top=(struct Nod *)malloc(sizeof(struct Nod));
        t->top->val=make_pair(s,val);
        t->top->st=NULL;
        t->top->dr=NULL;
        return;
    };
    struct Nod *nod=t->top;
    while(nod){
        int x=compare(s,nod->val->first);
        if(x==1){
            if(nod->dr){
                nod=nod->dr;
            }
            else{
                nod->dr=(struct Nod *)malloc(sizeof(struct Nod));
                nod->dr->val=make_pair(s,val);
                nod->dr->dr=NULL;
                nod->dr->st=NULL;
                return;
            }
        }
        if(x==0){
            if(nod->st){
                nod=nod->st;
            }
            else{
                nod->st=(struct Nod *)malloc(sizeof(struct Nod));
                nod->st->val=make_pair(s,val);
                nod->st->dr=NULL;
                nod->st->st=NULL;
                return;
            }
        }
        if(x==-1){
            nod->val->second=val;
            return;
        }
    }
}
void poptotree(struct Tree *t,char *s){
    if(!t->top) return;
    int u=0;
    struct Nod *nod=t->top,*p=NULL,*te=NULL;
    while(nod){
        te=nod;
        int x=compare(s,nod->val->first);
        if(x==1) nod=nod->dr,u=1;
        if(x==0) nod=nod->st,u=0;
        if(x==-1){
            if(nod->st&&nod->dr){
                struct Nod *search=nod->st,*pa=NULL;
                while(search->dr) pa=search,search=search->dr;
                if(pa){
                    pa->st=search->st;
                    pa->dr=NULL;
                    nod->val=make_pair(search->val->first,search->val->second);
                    free(search->val);
                    free(search);
                }
                else{
                    nod->st=nod->st->st;
                    nod->val=make_pair(search->val->first,search->val->second);
                    free(search->val);
                    free(search);
                }
                return;
            }
            else if(!nod->st&&nod->dr){
                if(p){
                    if(u){
                        p->dr=nod->dr;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=nod->dr;
                        free(nod->val);
                        free(nod);
                    }
                }
                else{
                    t->top=nod->dr;
                    free(nod->val);
                    free(nod);
                }
                return;
            }
            else if(nod->st&&!nod->dr){
                if(p){
                    if(u){
                        p->dr=nod->st;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=nod->st;
                        free(nod->val);
                        free(nod);
                    }
                    return;
                }
                else{
                    t->top=nod->st;
                    free(nod->val);
                    free(nod);
                    return;
                }
            }
            else{
                if(p){
                    if(u){
                        p->dr=NULL;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=NULL;
                        free(nod->val);
                        free(nod);
                    }
                }
                else{
                    free(t->top->val);
                    free(t->top);
                    t->top=NULL;
                }
            }
            return;
            }
        p=te;
    }
}
struct Nod *findtotree(struct Tree *t,char *s){
    struct Nod *nod=t->top;
    while(nod){
        int x=compare(s,nod->val->first);
        if(x==1)nod=nod->dr;
        if(x==0)nod=nod->st;
        if(x==-1){
            return nod;
        }
    }
    return NULL;
}
struct Map{
    struct Tree **t;
    int size;
};
struct Map *createMap(int size){
    if(size<=0) return NULL;
    struct Map *m=(struct Map *)malloc(sizeof(struct Map));
    m->size=size;
    m->t=(struct Tree **)calloc(size,sizeof(struct Tree *));
    for(int i=0;i<size;i++) m->t[i]=NULL;
    return m;
};
void add(struct Map *m,char *s,int val){
    int hash=make_hash(s,m->size);
    if(!m->t[hash]){
        m->t[hash]=(struct Tree *)malloc(sizeof(struct Tree));
        m->t[hash]->top=NULL;
    };
    addtotree(m->t[hash],s,val);
};
void pop(struct Map *m,char *s){
    int hash=make_hash(s,m->size);
    if(!m->t[hash]) return;
    poptotree(m->t[hash],s);
};
int find(struct Map *m,char *s){
    int hash=make_hash(s,m->size);
    if(!m->t[hash]) return 0;
    struct Nod *nod=findtotree(m->t[hash],s);
    if(nod) return nod->val->second;
    return 0;
};
int main()
{
    return 0;
}

Answer 2

You could also use the libghthash for general purpose hashes. They are quite easy to use, and incorporate in your application. However, it is a third party API - so if that's a problem, you would have to implement your own.

There's no built in associate array/hash tables in C.

The array initialization (C99) is probably the best way to go unless you have non-numeric keys:

T hash[] = {
    [1] = tObj,
    [255] = tObj2,
};

Answer 3

You can use map implemented as part of clib library

Answer 4

There is no built-in way to do this unless you count initializing an array like this in C99:

double squareRoots[] =
{
     [4] = 2.0,
     [9] = 3.0,
    [16] = 4.0,
    [25] = 5.0,
};

However, this allocates 26 elements in the array; the other values are all zeroes.

Assuming you didn't mean this, then look at C Interfaces and Implementations by D R Hanson; it shows a way of implementing associative arrays (aka hashes or dictionaries).

Answer 5

You could consider hash implementation in C language to achieve this. For basics of hash refer to Wikipedia. Refer to this question for more details and links.

This link gives good overview and implementation details.