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.

Why not just create a hashing function for your points and use that as an index? — Kep
– Kep, Commented Feb 22, 2014 at 18:11
There is no fancy data structure in C. You have to reinvent the wheel for yourself or go back to C++ ! — hivert
– hivert, Commented Feb 22, 2014 at 18:18
There is nothing like this in C. You can't define operators in C. The closest thing you can have is a custom hash function that you use to index into an array, or something similar. The point is: you are pretty much tied to built-in types and have to invent everything yourself. — Filipe Gonçalves
– Filipe Gonçalves, Commented Feb 22, 2014 at 18:20
As others have said: Either go looking for "hashtable code in C", or look up the basics of hashtables and implement one de novo. It isn't that difficult; I've implemented them several times. The main difference from the user's point of view will be that rather than saying myHashTable.put(key,value) you'll need to say putToHashTable(myHashTable,key,value) and so on. (Unless you want to really reinvent OO and start building method dispatch into your objects -- which is possible but overkill for this simple case.) — keshlam
– keshlam, Commented Feb 22, 2014 at 18:34

gslavin · Accepted Answer · 2014-02-22 18:47:09Z

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.

Captainhook244 · Accepted Answer · 2024-01-05 15:51:29Z

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;
    };

Well I defined a "string" a to be char *a, having in sight the fact that there are no strings in C, although there is the library <string.h>.
Unfortunately, as there are no predefined strings, you should create your own using malloc. Example: char* string=(char*)malloc(sizeof(char)*string_size)) where string_size is an integer. If you are interested, I used strdup in make_pair so it it possible to use the same pointer for different values (changing the value and then reuse it). If I am not clear enough, I might as well explain that I used strdup with the intention of making sure that make_pair(s,2) and make_pair(s,4) have different "string" pointers.
The mechanisms for making strings are well known. None of that explains how the struct point data is ever involved.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related