Migrating from C ++ to C: an alternative to std :: map?

Question

I am looking for a minimalistic alternative for std :: map <long, int> that will go into the Windows kernel driver, so it should be pretty fast .. it is expected that it will be relatively small (~ 200 in the working set), the number of keys and a large number of inserts .

Looking for a solution that can reduce the cost of finding a key.

Answer 1

Already done for you.

See the calls to RtlXxxGenericTable and RtlXxxGenericTableAvl.

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

• RtlNumberGenericTableElements

• RtlInitializeElementGenericTableAvl

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

Answer 2

You can implement the semantics of std::map in C. Only this will not be a 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; } 

Answer 3

If the number of keys is very small, for example. 10 or something else, maybe you can just do a linear search. If you take care to keep the compression in the key memory in memory to maximize cache hits, it can be pretty fast and have very low overhead in terms of memory allocation, etc.

Answer 4

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

Answer 5

The STL map implementation is a red-black tree that I consider

http://en.wikipedia.org/wiki/Map_%28C%2B%2B%29

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Answer 6

You will need two companions in C: one for keys, the other for values. This will help if you can encapsulate these two so that users can adhere to map semantics.

Answer 7

If you need a simple implementation of a dictionary in C, it’s ridiculous to implement a dictionary in C one day ... but we don’t have time for this.

So, you can try to look at the iniparser one module , this is a small dictionary that can be used in the kernel and / or in the built-in world.