index 8e6158fcefbff31d5d6bcff14d499d5d621a5b77..8aaa522a45bae64530243a8fa031f42b4b035b4f 100644 (file)
--- a/src/shared/hashtable.pas
+++ b/src/shared/hashtable.pas
type TEquFn = function (constref a, b: KeyT): Boolean;
type TIteratorFn = function (constref k: KeyT; constref v: ValueT): Boolean is nested; // return `true` to stop
- private
type
PEntry = ^TEntry;
TEntry = record
+ public
key: KeyT;
value: ValueT;
+ private
hash: LongWord; // key hash or 0
nextFree: PEntry; // next free entry
end;
- TValEnumerator = class
- private
- mEntries: PEntry;
- mFirstEntry, mLastEntry, cur: Integer;
- public
- constructor Create (aents: PEntry; afirst, alast: Integer);
- function MoveNext: Boolean;
- function getCurrent (): ValueT;
- property Current: ValueT read getCurrent;
- end;
+ private
+ type
+ TEntryArray = array of TEntry;
+
+ TValEnumerator = record
+ private
+ mEntries: TEntryArray;
+ mFirstEntry, mLastEntry, cur: Integer;
+ public
+ constructor Create (const aents: TEntryArray; afirst, alast: Integer);
+ function MoveNext (): Boolean; inline;
+ function getCurrent (): ValueT; inline;
+ property Current: ValueT read getCurrent;
+ end;
+
+ TKeyEnumerator = record
+ private
+ mEntries: TEntryArray;
+ mFirstEntry, mLastEntry, cur: Integer;
+ public
+ constructor Create (const aents: TEntryArray; afirst, alast: Integer);
+ function MoveNext (): Boolean; inline;
+ function getCurrent (): KeyT; inline;
+ property Current: KeyT read getCurrent;
+ end;
+
+ TKeyValEnumerator = record
+ private
+ mEntries: TEntryArray;
+ mFirstEntry, mLastEntry, cur: Integer;
+ public
+ constructor Create (const aents: TEntryArray; afirst, alast: Integer);
+ function MoveNext (): Boolean; inline;
+ function getCurrent (): PEntry; inline;
+ property Current: PEntry read getCurrent;
+ end;
private
hashfn: THashFn;
equfn: TEquFn;
mBuckets: array of PEntry; // entries, points to mEntries elements
mBucketsUsed: Integer;
- mEntries: array of TEntry;
+ mEntries: TEntryArray;
{$IFDEF RBHASH_SANITY_CHECKS}
mEntriesUsed: Integer;
{$ENDIF}
//WARNING! don't modify table in iterator (queries are ok, though)
function forEach (it: TIteratorFn): Boolean;
+ // default `for ... in` enums values
function GetEnumerator (): TValEnumerator;
+ function byKey (): TKeyEnumerator;
+ function byValue (): TValEnumerator;
+ function byKeyValue (): TKeyValEnumerator; // PEntry
property count: Integer read mBucketsUsed;
property capacity: Integer read getCapacity;
type
THashIntInt = specialize THashBase<Integer, Integer>;
+ THashStrInt = specialize THashBase<AnsiString, Integer>;
+ THashStrStr = specialize THashBase<AnsiString, AnsiString>;
function hashNewIntInt (): THashIntInt;
+function hashNewStrInt (): THashStrInt;
+function hashNewStrStr (): THashStrStr;
function u32Hash (a: LongWord): LongWord; inline;
function nextPOT (x: LongWord): LongWord; inline;
+// for integer keys
+function hiiequ (constref a, b: Integer): Boolean;
+function hiihash (constref k: Integer): LongWord;
+function hsiequ (constref a, b: AnsiString): Boolean;
+function hsihash (constref k: AnsiString): LongWord;
+
+
implementation
uses
// ////////////////////////////////////////////////////////////////////////// //
function hiiequ (constref a, b: Integer): Boolean; begin result := (a = b); end;
+function hsiequ (constref a, b: AnsiString): Boolean; begin result := (a = b); end;
{$PUSH}
{$RANGECHECKS OFF}
function hiihash (constref k: Integer): LongWord;
begin
- result := k;
+ result := LongWord(k);
result -= (result shl 6);
result := result xor (result shr 17);
result -= (result shl 9);
result := result xor (result shl 10);
result := result xor (result shr 15);
end;
+
+function hsihash (constref k: AnsiString): LongWord;
+begin
+ if (Length(k) > 0) then result := fnvHash(PAnsiChar(k)^, Length(k)) else result := 0;
+end;
{$POP}
end;
+function hashNewStrInt (): THashStrInt;
+begin
+ result := THashStrInt.Create(hsihash, hsiequ);
+end;
+
+
+function hashNewStrStr (): THashStrStr;
+begin
+ result := THashStrStr.Create(hsihash, hsiequ);
+end;
+
+
// ////////////////////////////////////////////////////////////////////////// //
{$PUSH}
{$RANGECHECKS OFF}
end;
+// enumerators
function THashBase.GetEnumerator (): TValEnumerator;
begin
- if (Length(mEntries) > 0) then
+ if (Length(mEntries) > 0) then result := TValEnumerator.Create(mEntries, mFirstEntry, mLastEntry)
+ else result := TValEnumerator.Create(nil, -1, -1);
+end;
+
+function THashBase.byKey (): TKeyEnumerator;
+begin
+ if (Length(mEntries) > 0) then result := TKeyEnumerator.Create(mEntries, mFirstEntry, mLastEntry)
+ else result := TKeyEnumerator.Create(nil, -1, -1);
+end;
+
+function THashBase.byValue (): TValEnumerator;
+begin
+ if (Length(mEntries) > 0) then result := TValEnumerator.Create(mEntries, mFirstEntry, mLastEntry)
+ else result := TValEnumerator.Create(nil, -1, -1);
+end;
+
+function THashBase.byKeyValue (): TKeyValEnumerator; // PEntry
+begin
+ if (Length(mEntries) > 0) then result := TKeyValEnumerator.Create(mEntries, mFirstEntry, mLastEntry)
+ else result := TKeyValEnumerator.Create(nil, -1, -1);
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TValEnumerator.Create (const aents: TEntryArray; afirst, alast: Integer);
+begin
+ mEntries := aents;
+ mFirstEntry := afirst;
+ mLastEntry := alast;
+ cur := mFirstEntry-1;
+end;
+
+function THashBase.TValEnumerator.MoveNext (): Boolean; inline;
+begin
+ Inc(cur);
+ while (cur <= mLastEntry) do
begin
- result := TValEnumerator.Create(@mEntries[0], mFirstEntry, mLastEntry);
- end
- else
+ if (mEntries[cur].hash <> 0) then begin result := true; exit; end;
+ end;
+ result := false;
+end;
+
+function THashBase.TValEnumerator.getCurrent (): ValueT; inline;
+begin
+ result := mEntries[cur].value;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TKeyEnumerator.Create (const aents: TEntryArray; afirst, alast: Integer);
+begin
+ mEntries := aents;
+ mFirstEntry := afirst;
+ mLastEntry := alast;
+ cur := mFirstEntry-1;
+end;
+
+function THashBase.TKeyEnumerator.MoveNext (): Boolean; inline;
+begin
+ Inc(cur);
+ while (cur <= mLastEntry) do
begin
- result := TValEnumerator.Create(nil, -1, -1);
+ if (mEntries[cur].hash <> 0) then begin result := true; exit; end;
end;
+ result := false;
end;
-constructor THashBase.TValEnumerator.Create (aents: PEntry; afirst, alast: Integer);
+function THashBase.TKeyEnumerator.getCurrent (): KeyT; inline;
+begin
+ result := mEntries[cur].key;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TKeyValEnumerator.Create (const aents: TEntryArray; afirst, alast: Integer);
begin
mEntries := aents;
mFirstEntry := afirst;
cur := mFirstEntry-1;
end;
-function THashBase.TValEnumerator.MoveNext: Boolean;
+function THashBase.TKeyValEnumerator.MoveNext (): Boolean; inline;
begin
Inc(cur);
while (cur <= mLastEntry) do
result := false;
end;
-function THashBase.TValEnumerator.getCurrent (): ValueT;
+function THashBase.TKeyValEnumerator.getCurrent (): PEntry; inline;
begin
- result := mEntries[cur].value;
+ result := @mEntries[cur];
end;