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

Question

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

Answer 1

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

 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 для добавления head в стек. Кроме того, в реализации есть дополнительная условная проверка, которая еще больше замедляет работу.

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