Porting std::map to C?

Question

I am porting some c++ code to c. What is a viable equivalent of std::map in c? I know there is no equivalent in c.

This is what I am thinking of using:

In c++:

std::map< uint, sTexture > m_Textures;

In c:

typedef struct
{
  uint* intKey;
  sTexture* textureValue;
} sTMTextureMap;

Is that viable or am I simplifying map too much? Just in case you did not get the purpose its a Texture Map.

Answer 1

Many C implementations support tsearch(3) or hsearch(3). tsearch(3) is a binary tree and you can provide a comparator callback. I think that's about as close as you're going to get to a std::map.

Here's some c99 example code

#include <search.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef struct
{
      int key;
      char* value;
} intStrMap;

int compar(const void *l, const void *r)
{
    const intStrMap *lm = l;
    const intStrMap *lr = r;
    return lm->key - lr->key;
}

int main(int argc, char **argv)
{
    void *root = 0;

    intStrMap *a = malloc(sizeof(intStrMap));
    a->key = 2;
    a->value = strdup("two");
    tsearch(a, &root, compar); /* insert */

    intStrMap *find_a = malloc(sizeof(intStrMap));
    find_a->key = 2;

    void *r = tfind(find_a, &root, compar); /* read */
    printf("%s", (*(intStrMap**)r)->value);

    return 0;
}

Answer 2

Why don't you just wrap a C interface around std::map? Ie write a few C++ functions in their own module:

typedef std::map<int, char*> Map;

extern "C" {

void* map_create() {
  return reinterpret_cast<void*> (new Map);
}

void map_put(void* map, int k, char* v) {
  Map* m = reinterpret_cast<Map*> (map);
  m->insert(std::pair<int, char*>(k, v));
}

// etc...

} // extern "C"

And then link into your C app.

Answer 3

That is certainly one possible implementation. You might want to consider how you'll implement the indexing and what performance impact that will have. For example, you could have the intKey list be a sorted list of the keys. Looking up a key would be O(log N) time, but inserting a new item would be O(N).

You could implement it as a tree (like std::map), and then you'd have O(log N) insertion and lookup.

Another alternative would be to implement it as a hash table, which would have better runtime performance, assuming a good hash function and a sparse enough intKey array.

Answer 4

You can implement it however you choose. If you use a linked-list approach your insertion will be O(1) but your retrieval and deletion will be O(n). If you use something more complex like a red-black tree you'll have much better average performance.

If you're implementing it yourself linked-list is probably the easiest, otherwise grabbing some appropriately licensed red-black or other type of tree from the internet would be the best option. Implementing your own red-black tree is not recommended... I've done this and would prefer not to do it again.

And to answer a question you didn't ask: maybe you should reexamine whether porting to C from C++ really provides all the benefits you wanted. Certainly there are situations where it could be necessary, but there aren't many.