Проблема проектирования: реализация двухсторонней таблицы поиска в C

Question

Я хочу реализовать таблицу двустороннего поиска. MAC-адрес -> MAC-адрес

Означает, что один ключ может использоваться для доступа к значению на стороне восходящего потока. А в нисходящем направлении это значение можно использовать для доступа к ключу.

Память является ограничением, поэтому я не могу использовать две хеш-таблицы, я с нетерпением жду возможности использовать одни и те же узлы хеш-таблицы как для восходящего, так и для нисходящего поиска.

Время выполнения также является ограничением, поэтому будет работать только стратегия хеш-таблицы.

Язык является ограничением, поэтому я могу использовать только язык C (поэтому я не могу использовать C ++ Boost bimap)

Пожалуйста, поделитесь своими идеями о том, как этого можно достичь. Заранее спасибо.

Answer 1

Как вы предлагаете, вы можете использовать одни и те же узлы как для восходящего, так и для нижнего сегментов. Это не спасет вас огромное количество (конечно, меньше, чем в 2 раза), но все поможет.

struct bucket {
  struct bucket *next_upstream;
  struct bucket *next_downstream;
  char upstream_mac[6];
  char downstream_mac[6];
}
struct bucket **upstream_table = malloc(sizeof(struct bucket*) * N);
struct bucket **downstream_table = malloc(sizeof(struct bucket*) * N);
void insert(char *upstream_mac, char *downstream_mac) {
  struct bucket *b = malloc(sizeof(*b));
  memcpy(b->upstream_mac, upstream_mac, 6);
  memcpy(b->downstream_mac, downstream_mac, 6);
  int uh = hash(upstream_mac);
  int dh = hash(downstream_mac);
  b->next_upstream = upstream_table[uh];
  upstream_table[uh] = b;
  b->next_downstream = downstream_table[dh];
  downstream_tbale[dh] = b;
}

Answer 2

Не могли бы вы использовать два параллельных массива? Т.е.,

// assuming no reallocation required
#define BUFFERSIZE some-gigantic-number
char upstream[BUFFERSIZE];
char downstream[BUFFERSIZE];

Затем расположите каждый список MAC-адресов в виде последовательных символов. Например:

upstream:

"01:23:45:67:89:ab\000:0d:93:81:d9:7c\0..."
 |_______________|  |_______________|
         |                  |
   first address      second address   ...

downstream:

"00:0a:95:d1:52:30\001:45:c3:2d:65:b5\0..."
 |_______________|  |_______________|
         |                  |
   first address      second address   ...

Расположите и upstream, и downstream таким образом, чтобы парные MAC-адреса были в одном порядке.

Теперь, чтобы найти спаренный MAC-адрес, просто используйте strcmp() или аналогичный, чтобы проверить каждый MAC-адрес в одном массиве. Как только ключ найден, этот же индекс в дополнительном массиве является значением.

Почему это так? Это почти не требует вспомогательной памяти и очень эффективно кеширует.

Answer 3

Кроме того, вы можете объединить два массива указателей головы в один.Это просто делает цепочки длиннее, а код - короче.Часть кода, которая должна извлекать узлы из связанных списков, должна в любом случае проверять одно из полей mac1 [] или mac2 [] (игнорируя другое)