Использование двойного указателя в реализации linux kernel.

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

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

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

Использование двойного указателя в реализации linux kernel.

Ответы

Ответ 1