Использование двойного указателя в реализации Хэш-списка ядра Linux

Question

Использование двойного указателя в реализации Хэш-списка ядра Linux

Я пытаюсь понять реализацию Ядра Linux связанного списка и хеш-таблицы. Ссылка на реализацию здесь. Я понял реализацию связанного списка. Но я мало смущен того, почему двойные указатели используются в hlist (** pprev). Ссылка для hlist здесь. Я понимаю, что hlist используется в реализации хеш-таблицы, так как заголовок списка требует только одного указателя, и это оставляет свободное место. Почему наклон это быть сделанным с помощью единственного указателя (просто *предыдущий как связанный список)?Пожалуйста, помогите мне.

19

c linux linux-kernel

задан macfij 30 July 2014 в 14:07

1 ответ

Другие вопросы по тегам:

c linux linux-kernel

Похожие вопросы:

score 21 · Accepted Answer

Причину можно найти в одном из комментариев:

 547/*
 548 * Double linked lists with a single pointer list head.
 549 * Mostly useful for hash tables where the two pointer list head is
 550 * too wasteful.
 551 * You lose the ability to access the tail in O(1).
 552 */

Если у вас было * prev вместо ** pprev, и поскольку мы пытаемся сохранить память, мы не включаем * prev в заголовке, тогда наша реализация hlist выглядит так:

struct hlist_head {
  struct hlist_node *first = null;
};

struct hlist_node {
  struct hlist_node *next;
  struct hlist_node *prev;
};

Обратите внимание, что указатель prev не может указывать на голову, или head-> first (в отличие от ** pprev ). Это усложняет реализацию hlist, как вы увидите, когда мы реализуем hlist_add_before () :

void
hlist_init(struct hlist_head *head) {
  head->first = null;  
}

void
hlist_add_head(struct hlist_head *head, struct hlist_node *node) {
  struct hlist_node *next = head->first;

  head->first = node;
  node->next = next;
  node->prev = NULL;
  if (next) {
    next->prev = node;
  }
}

Обратите внимание, что prev не на что указывает в приведенной выше реализации hlist_add_head () . Итак, теперь, когда вы реализуете hlist_add_before () , это выглядит так:

void
hlist_add_before(struct hlist_head *head,
                 struct hlist_node *node,
                 struct hlist_next *next) {
  hlist_node *prev = next->prev;

  node->next = next;
  node->prev = prev;
  next->prev = node;

  if (prev) {
    prev->next = node;
  } else {
    head->first = node;
  }
}

Обратите внимание, что теперь нам нужно передать head , а также hlist_add_before () , что требует дополнительной инструкции push для проталкивания головы в стек. Кроме того, в реализации есть дополнительная условная проверка, которая еще больше замедляет работу.

Теперь попробуйте реализовать другие операции hlist с * prev вместо ** pprev , и вы обнаружите, что ваша реализация будет медленнее, чем то, что вы видели в ядре linux.