Зачем использовать цикл while в кеше levelDB (функция Resize)?

Question

Зачем использовать цикл while в кеше levelDB (функция Resize)?

Когда я вижу реализацию кеша levelDB, адрес. Я не могу понять, почему он использует цикл while для цикла (в функции Resize), и я думаю, что он может заменить оператор if. Я надеюсь, что кто-то может помочь мне.

 void Resize() {
uint32_t new_length = 4;
while (new_length < elems_) {
new_length *= 2;
}
LRUHandle** new_list = new LRUHandle*[new_length];
memset(new_list, 0, sizeof(new_list[0]) * new_length);
uint32_t count = 0;
for (uint32_t i = 0; i < length_; i++) {
LRUHandle* h = list_[i];
while (h != NULL) {
LRUHandle* next = h->next_hash;
uint32_t hash = h->hash;
LRUHandle** ptr = &new_list[hash & (new_length - 1)];
h->next_hash = *ptr;
*ptr = h;
h = next;
count++;
}
}
assert(elems_ == count);
delete[] list_;
list_ = new_list;
length_ = new_length;
}
};

0

c++caching leveldb while-loop

Решение

Другие решения

Похоже, list_ — это динамический массив односвязных списков.

Я предполагаю, что list_ выглядит примерно так

list_[0]-> node_1 -> node_2 -> null
list_[1]-> node_3 -> null
list_[2]-> null
....
list_[n]-> node_m-1 -> node_m -> null

Чтобы правильно скопировать все элементы в new_list, вам нужно использовать цикл while. В противном случае любой элемент, который не является напрямую адресуемым из list_, не будет скопирован / хеширован в new_list. На приведенной выше диаграмме это означало бы, что node_2 и node_m + 1 не будут добавлены в new_list.

New_list будет сохранять ту же форму, но должен иметь меньше коллизий.

Используя оператор if, new_list будет выглядеть примерно так:

new_list[0]-> node_1 -> null
new_list[1]-> null
new_list[2]-> node_2 -> null
...
new_list[p-1]-> node_k -> null
new_list[p] -> null

То есть каждый элемент в new_list будет указывать на список из 1 или ноль элементов.
Обратите внимание, узел_1 на этой диаграмме не обязательно совпадает с узлом 1 на диаграмме выше.

Использование оператора If вместо цикла while также приведет к утечке памяти, поскольку вы больше не сможете получить доступ ко всем элементам.

1

переменная list_[i] имеет подсписок, while внутри for цикл зацикливается на подсписок.

0

Источник

Accepted Answer

list_ по-видимому, массив связанных списков. while (h != NULL), в сочетании с h = next (где next является h->next_hash), означает, что цикл while будет работать со всеми элементами каждого связанного списка, останавливаясь только при достижении последнего элемента (когда h становится NULLлибо потому, что список был пуст, либо потому, что next_hash элемента был NULL).

Если вы заменили его на if (h != NULL), он будет работать только на первом элементе связанного списка.

1