Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

inc(FindInfo^.fiiBucket.bkDepth);

{инициализировать новую группу; она будет иметь такую же разрядную глубину, как и разбиваемая группа}

FillChar(NewBucket, sizeof(NewBucket), 0);

NewBucket.bkDepth := FindInfo^.fiiBucket.bkDepth;

{вычислить маску AND, которая будет использоваться для выяснения места помещения хеш-записей}

Mask := (1 shl NewBucket.bkDepth) - 1;

{вычислить значение, полученное в результате применения маски AND, для хеш-записей старой группы}

OldValue := ReverseBits (StartDirEntry, FDirectory.Depth) and Mask;

{считать старую группу и перенести в новую группу принадлежащие ей хеш - значения}

OldInx := 0;

NewInx := 0;

with FindInfo^.fiiBucket do

for Inx := 0 to pred(bkCount) do

begin

if (bkHashes [Inx].heHash and Mask) = OldValue then

begin

bkHashes[OldInx] := bkHashes[Inx];

inc(OldInx);

end

else begin

NewBucket.bkHashes[NewInx] := bkHashes[Inx];

inc(NewInx);

end;

end;

{установить счетчики для обеих групп}

FindInfo^.fiiBucket.bkCount := OldInx;

NewBucket.bkCount := NewInx;

{добавить новую группу в поток групп, обновить старую группу}

NewBucketNum := FBucketsAdd (NewBucket);

FBuckets.Write(FindInfo^.fiiBucketNum, FindInfo^.fiiBucket);

{установить все записи в новом диапазоне каталога в соответствие с новой группой}

for Inx := NewStartDirEntry to EndDirEntry do

FDirectory[ Inx ] := NewBucketNum;

end;

Прежде всего, выполняется проверка, равна ли разрядная глубина разбиваемой группы разрядной глубине каталога. Если да, то необходимо вдвое увеличить размер каталога и обеспечить обновление отслеживаемого значения записи каталога. Например, если запись FindInfo^.fiitiirEntry имела значение, равное 3, и мы вдвое увеличили размер каталога, то теперь она должна иметь значение, равное 6 (или, если быть точным, 7, поскольку обе новые записи каталога указывают на одну и ту же группу).

Теперь нужно выяснить диапазон записей каталога, которые указывают на разбиваемую группу. В соответствии с рисунком 7.1 (g), если бы пришлось разбивать запись 2?, диапазон был бы 4-7. Разбиваемая группа должна остаться в первой половине этого диапазона, а новая группа, которую предстоит заполнить, будет занимать вторую половину диапазона записей каталога.

Поскольку мы разбиваем группу, ее разрядную глубину следует увеличить (мы уже обеспечили, чтобы это можно сделать без превышения разрядной глубины каталога"). Поскольку новая группа дополняет данную, она будет иметь такую же разрядную глубину.

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

Желательно разработать метод, с помощью которого можно было бы непосредственно определить, в какую группу должно помещаться хеш-значение. Предположим, что имеет место следующая ситуация: разрядная глубина каталога равна 3, но разрядная глубина группы равна 2. Записи 4 и 5 каталога указывают на группу A, которая заполнена, а записи 6 и 7 - на пустую группу B. Куда Должно быть помещено данное хеш-значение? Прежде всего, следует осознать, что группа А содержит только те хеш-значения, последними разрядами которых являются 001, 101, 011 или 111 (чтобы убедиться в этом, проинвертируйте разряды для получения записей 4, 5, 6 и 7 каталога). Если хеш-значение имеет окончание 001 или 101, оно будет помещено в группу A. Если оно имеет окончание 011 или 111, оно будет помещено в группу B. Все еще не понятно, не так ли? Что ж, первые две комбинации заканчиваются разрядами 01, в то время как две вторые комбинации - разрядами 11. Почему учитываются только два разряда? Вспомним, что разрядная глубина группы равна 2. Идея состоит в том, чтобы вычислить запись каталога, соответствующую началу диапазона (которое нам известно), проинвертировать разряды, соответствующие разрядной глубине каталога, и выполнить операцию AND для полученного результата и маски, которая была сгенерирована из значения разрядной глубины группы. Затем эту маску можно использовать для разбиения хеш-значений по категориям. Именно эти действия и выполняются в среднем разделе подпрограммы.

Все остальные действия являются тривиальными и особого интереса не представляют - выполняется проверка правильности значений счетчиков групп, добавление новой группы, обновление исходной группы и обеспечение того, чтобы записи каталога, которые требуют изменения, указывали на новую группу.