Going down from C++ to C: alternative to std::map?

Question

I am looking for minimalistic alternative for std::map<long, int>, which would go into Windows kernel driver, so it should be quite fast.. it is expected to hold a relatively small (~200 in working set) amount of keys and a large amount of inserts.

Looking for solution that can cut key search cost.

Answer 1

Already done for you.

See the RtlXxxGenericTable and RtlXxxGenericTableAvl calls.

• RtlInitializeElementGenericTable
• RtlDeleteElementGenericTable
• RtlEnumerateGenericTable
• RtlEnumerateGenericTableWithoutSplaying
• RtlGetElementGenericTable
• RtlInsertElementGenericTable
• RtlLookupElementGenericTable

• RtlNumberGenericTableElements

• RtlInitializeElementGenericTableAvl

• RtlDeleteElementGenericTableAvl
• RtlEnumerateGenericTableAvl
• RtlGetElementGenericTableAvl
• RtlInitializeGenericTable
• RtlInsertElementGenericTableAvl
• RtlLookupElementGenericTableAvl
• RtlNumberGenericTableElementsAvl

Answer 2

If the number of keys is very small, e.g. 10 or something, perhaps you can get away with just a linear search. If you take care to keep the key-space compressed in memory to maximise cache hits, it can be pretty fast and have very low overhead in terms of memory allocations and so on.

Answer 3

In the past, for maps with less than a few thousand objects, I've found that creating a std::vector sorted on the key value that is then searched for using a binary search is significantly faster than using a std::map.

Answer 4

You could implement std::map semantics in C as well. Only that it will not be template.

Here is the start:

struct KeyValuePair
{
   KeyType key;
   ValueType value;
};

struct Map
{
   KeyValuePair *list; //it can be linkedlist as well
};

//these are the interfaces which operate on map
void Insert(Map * map, KeyType key, ValueType value);
void Update(Map * map, KeyType key, ValueType value);
int Find(Map * map, KeyType key, ValueType *outValue);

//Implement Get in terms of Find
ValueType Get(Map * map, KeyType key)
{
     ValueType value;
     Find(map, key, &value);
     return value;
}