Handmade Hero»Forums»Code
11 posts
An Attempt to write a generic map
Edited by Bits Please on

Hey everyone!

I've been trying to make a generic map for a while now and surprisingly enough, after hours of research, I got the basic functionality working. Here's how it looks like:

map.h

#include <stdlib.h>
#define Pair(type) \
struct {char *key; type value;}
#define Map(type) \
struct {Pair(type) *at; size_t len, cap;}
#define set_len(m,n) ((m).len = (n), set_cap((m), (m).len))
#define set_cap(m,n) ((m).cap < (n) ? \
((m).cap <<= 1, (((n) > (m).cap) ? (m).cap = (n) : 0), \
(m).at = realloc((m).at, (m).cap * sizeof(*(m).at))) : 0)
#define add_pair(m,k,v) (set_len((m), (m).len + 1), \
(m).at[/(m).len - 1].key = (k), (m).at[/(m).len - 1].value = (v))

With that, we can create a map of any type of our choosing and even add pairs to it, like so:

main.c

#include "map.h"
int main(int argc, char **argv) {
    Map(int) m = {0};
    add_pair(m, "abc", 1);
    add_pair(m, "abcd", 2);
    add_pair(m, "abcde", 3);
    return 0;
}

Now, I got a little stuck. As you can see, the functionality is really basic and I gotta take it up a notch. I gotta make a function that checks whether the key of the new pair I'm adding is in the collection or not and add it only if it's not present. This function would also allow me to remove any pair I want.

The problem is, how do I pass my map structure, whose type is unknown at compile time, as a function parameter? I also tried to turn that function into a macro but to no avail...

Your kind assistance here would be highly appreciated! <3

Simon Anciaux
1184 posts
An Attempt to write a generic map
Edited by Simon Anciaux on

Assuming you don't want to pass the type in each function call, I would suggest to store the size of the data type in the map, and use "void*" for the data pointer. If you think about it, the type of the data isn't important for the inner working of the map, it's only meaningful to the user.

#include <stdint.h>
#include <stdlib.h>

typedef struct map_t {
    uintptr_t capacity, count;
    char** keys;
    void* data_pointer;
    uintptr_t type_size;
} map_t;

#define map_make( type, capacity ) map_make_( ( capacity ), sizeof( type ) )

map_t map_make_( uintptr_t capacity, uintptr_t type_size ) {
    map_t map;
    map.capacity = capacity;
    map.count = 0;
    map.keys = malloc( capacity * sizeof( char* ) );
    map.data_pointer = malloc( capacity * type_size );
    map.type_size = type_size;
    return map;
}

#define map_item_pointer_type( map, key, type ) ( type* ) map_item_pointer( ( map ), ( key ) )

void* map_item_pointer( map_t* map, char* key ) {
    
    void* result = 0;
    
    for ( uintptr_t i = 0; i < map->count; i++ ) {
        if ( strcmp( key, map->keys[ i ] ) == 0 ) {
            result = ( ( uint8_t* ) map->data_pointer ) + ( map->type_size * i );
            break;
        }
    }
    
    return result;
}

int main( int argc, char **argv) {
    map_t m = map_make( int, 100 );
    
    int* x = ( int* ) map_item_pointer( &m, "abc" );
    int* y = map_item_pointer_type( &m, "abc", int );
    
    return 0;
}

By the way, your code doesn't compile, and even if it did, you don't access the correct element, you always write at 'at' which is the first element in the map.

Separating keys and data could potentially be better in term of performance because you will often want to iterate over the keys without touching the data part (for example to compare keys) and if they are in a pair, the cache usage will most likely not be optimal (keep that in mind if performance becomes an issue).

I would also suggest not to write everything in macros with statement separated by comas as that makes it harder to read.

A last point is to use a pointer to the struct instead of the struct directly in the functions/macros because it's likely that at some point you'll pass the structure to a function, and if you need to keep the modifications across function calls, you'll need to use pointers.

11 posts
An Attempt to write a generic map
Edited by Bits Please on
Replying to mrmixer (#25648)

Unfortunately, I only just now noticed that, for some reason, whenever I try using square brackets inside of the [code] tags, they disappear together with everything that was in them... I edited my comment the best I could to make the missing part appear:

#define add_pair(m,k,v) (set_len((m), (m).len + 1), \
(m).at[/(m).len - 1].key = (k), (m).at[/(m).len - 1].value = (v))

Now, you just need to remove the two forward slashes and the code will compile, sorry about that.

Anyway, thanks a bunch for useful info man! I'll definitely go back to the drawing board and apply all your tips <3

Mārtiņš Možeiko
2356 posts / 2 projects
An Attempt to write a generic map
Replying to Bits Please (#25649)

Use markdown ``` for code blocks - put ``` on new line before code, and then after the code.