Map like structure in C: use int and struct to determine a value

Question

I used to code in C++ and now I try to program in C.

Assume I have defined a struct

struct point{
    int x;
    int y;
}

Is there any data structure A in c that can support the following functionality: Given two integers, say i and j, and two points, say p1 and p2. A[i][j][p1][p2] can uniquely determine a value.

It sounds like a 4-d array. However, indexes are no longer a int, but user-defined struct.

Answer 1

I've been actively engaged in C++ and C programming for over a year. Lately, I've been intrigued by the idea of implementing a map-like structure in C, and I've come across an approach to tackle this challenge. The strategy involves utilizing a set of Binary Search Trees (BST) for creating a map structure:

struct Map{ struct Tree **t; };

In this method, a tree is defined as follows:

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;
};
struct Nod{
struct Pair *val;
struct Nod *dr,*st;
};
struct Tree{
struct Nod *top;
};

Moreover, there is a need for a make_hash function to generate a hash for a char* and a compare function for "comparing" two "strings":

//create the hash
int make_hash(char *s,int size){
//use unsigned long long because it starts from 0 after going past the limit.
unsigned long long hash=5813;
for(int i=0;s[i];i++) hash=hash*33+s[i];
return (hash%size);
};
//compare two "strings"
//note: my compare function returns -1 if both "strings" are equal 
int compare(char *a,char *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])
return 1;
if(!a[i]&&b[i])
return 0;
if(!a[i]&&!b[i]&&x==i)
return -1;
};

Finally, the implementation requires functions for adding and finding a char* and its corresponding value in our program:

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;
        }
    }
    else 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;
        }
    }
    else if(x==-1){
        nod->val->second=val;
        return;
    }
}
}
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;
    else if(x==0) nod=nod->st;
    else return nod;
}
return NULL;
};
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);
};
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 0;
return nod->val->second;
};

It's worth noting that there is room for improvement in this map implementation. With that in mind, let me now consolidate all the components:

#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);
};
struct Nod{
    struct Pair *val;
    struct Nod *dr,*st;
};
struct Tree{
    struct Nod *top;
};
int compare(char *a,char *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])
    return 1;
    if(!a[i]&&b[i])
    return 0;
    if(!a[i]&&!b[i]&&x==i)
    return -1;
};
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;
            }
        }
        else 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;
            }
        }
        else if(x==-1){
            nod->val->second=val;
            return;
        }
    }
}
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;
        else if(x==0) nod=nod->st;
        else return nod;
    }
    return NULL;
};
struct Map{
struct Tree **t;
int size;
};
struct Map *createMap(int size){
    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);
    };
    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 0;
        return nod->val->second;
    };

Answer 2

You'll probably have to make your own structure. The C Programming Language by Kernighan and Ritchie has an example of making an associate map in c, and what I'll detail below is based on what I remember from that.

Basically you'll need a struct Map that contains struct Key and struct Value.

struct Map {
    struct Key key;
    struct Value value;
};

struct Key contains elements that determine the value (in your case 2 points and 2 ints)

struct Key {
    struct point p1;
    struct point p2;
    int i;
    int j;
};

struct Value is whatever you want your key to point to (you didn't say)

You now have a struct Map that associates your four inputs with a value, but a single map isn't that useful. You're going to want a whole array of them.

struct Map map[SIZE_OF_MAP];

If you don't want to linearly search the array for the Map struct you're looking for, you can make a hashing function that will bring you directly to it. Just define a function that takes the key and uses its value to assign it an index in the array. Use the hash to place the Map in the array and retrieve it from the array. (Note: I'm unsure if this is a correct example of hashing, please correct if this is completely wrong)

int get_hash(Key *key)
{
    int result;
    /* combine all inputs in some way */
    result = key->i * key->i + (key->p1.x * key->p1.x) - (key->p2.x * key->p2.x)
    /* make sure result isn't out of bounds of the array */
    return (result % SIZE_OF_MAP);
}

If you use the hashing function you'll have to consider collisions (what happens when two keys give the same result for get_hash). When you use your array of Maps you'll need some form of collision resolution.