Next to the perfect or perfect hash of memory addresses in c

Question

I have a list of memory addresses from 0xc0003000 to 0xc04a0144, there are many spaces and <4096 entries in the list. This is known at compile time, and I want to make the perfect hash for this.

However, finding the perfect hash online gives me information mainly related to hashing strings, and they don't seem to translate well.

To be clear, I want to be able to get the memory address at runtime and check that it is in the hash quickly. I am currently using binary search, which on average contains about 8 loops to find the answer.

Any ideas what tree I need to bark?

Answer 1

Here is an example gperf program. I included NUL and a new line in the sample data to prove that they did not fail.

%{ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <inttypes.h> #include <arpa/inet.h> %} %% "\xc0\x01\x02\x03" "\xc0\xff\xff\xff" "\xc0\xff\x00\xff" "\xc0\x0a\xff\xff" %% int main(int argc, const char **argv) { int i; for(i=1;i<argc;++i) { uint32_t addr = ntohl(strtoul(argv[i], 0, 16)); if(in_word_set((char *)&addr, 4)) printf("0x%08"PRIx32" is in the list.\n", htonl(addr)); else printf("0x%08"PRIx32" is not in the list.\n", htonl(addr)); } return 0; } 

Save as addrs.gperf , compile and test with

 gperf -l addrs.gperf > addrs.c gcc addrs.c -o addrs ./addrs c0000000 c0010203 c0ffffff c00affff c0ff0aff c0ffff00 c0ff00ff