index b847720ba90a3ed86977b6adbc2531a4c4ce4b9c..f3331d816e68d994a3bd234972172c3733184554 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;
+ private
+ type
+ TValEnumerator = record
+ 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;
+
+ TKeyEnumerator = record
+ private
+ mEntries: PEntry;
+ mFirstEntry, mLastEntry, cur: Integer;
+ public
+ constructor Create (aents: PEntry; afirst, alast: Integer);
+ function MoveNext: Boolean;
+ function getCurrent (): KeyT;
+ property Current: KeyT read getCurrent;
+ end;
+
+ TKeyValEnumerator = record
+ private
+ mEntries: PEntry;
+ mFirstEntry, mLastEntry, cur: Integer;
+ public
+ constructor Create (aents: PEntry; afirst, alast: Integer);
+ function MoveNext: Boolean;
+ function getCurrent (): PEntry;
+ property Current: PEntry read getCurrent;
+ end;
+
private
hashfn: THashFn;
equfn: TEquFn;
//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;
end;
-
type
TJoaatHasher = record
private
procedure reset (); inline; overload;
procedure reset (aseed: LongWord); inline; overload;
- procedure put (const buf; len: LongWord);
+ procedure put (constref buf; len: LongWord);
// current hash value
// you can continue putting data, as this is not destructive
function u32Hash (a: LongWord): LongWord; inline;
-function fnvHash (const buf; len: LongWord): LongWord;
-function joaatHash (const buf; len: LongWord): LongWord;
+function fnvHash (constref buf; len: LongWord): LongWord;
+function joaatHash (constref buf; len: LongWord): LongWord;
function nextPOT (x: LongWord): LongWord; inline;
end;
-procedure TJoaatHasher.put (const buf; len: LongWord);
+procedure TJoaatHasher.put (constref buf; len: LongWord);
var
bytes: PByte;
h: LongWord;
{$POP}
-function joaatHash (const buf; len: LongWord): LongWord;
+function joaatHash (constref buf; len: LongWord): LongWord;
var
h: TJoaatHasher;
begin
h := TJoaatHasher.Create(0);
- h.put(buf, len);
+ h.put(PByte(@buf)^, len);
result := h.value;
end;
{$PUSH}
{$RANGECHECKS OFF}
// fnv-1a: http://www.isthe.com/chongo/tech/comp/fnv/
-function fnvHash (const buf; len: LongWord): LongWord;
+function fnvHash (constref buf; len: LongWord): LongWord;
var
b: PByte;
begin
end;
+// enumerators
+function THashBase.GetEnumerator (): TValEnumerator;
+begin
+ if (Length(mEntries) > 0) then result := TValEnumerator.Create(@mEntries[0], mFirstEntry, mLastEntry)
+ else result := TValEnumerator.Create(nil, -1, -1);
+end;
+
+function THashBase.byKey (): TKeyEnumerator;
+begin
+ if (Length(mEntries) > 0) then result := TKeyEnumerator.Create(@mEntries[0], mFirstEntry, mLastEntry)
+ else result := TKeyEnumerator.Create(nil, -1, -1);
+end;
+
+function THashBase.byValue (): TValEnumerator;
+begin
+ if (Length(mEntries) > 0) then result := TValEnumerator.Create(@mEntries[0], 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[0], mFirstEntry, mLastEntry)
+ else result := TKeyValEnumerator.Create(nil, -1, -1);
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TValEnumerator.Create (aents: PEntry; afirst, alast: Integer);
+begin
+ mEntries := aents;
+ mFirstEntry := afirst;
+ mLastEntry := alast;
+ cur := mFirstEntry-1;
+end;
+
+function THashBase.TValEnumerator.MoveNext: Boolean;
+begin
+ Inc(cur);
+ while (cur <= mLastEntry) do
+ begin
+ if (mEntries[cur].hash <> 0) then begin result := true; exit; end;
+ end;
+ result := false;
+end;
+
+function THashBase.TValEnumerator.getCurrent (): ValueT;
+begin
+ result := mEntries[cur].value;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TKeyEnumerator.Create (aents: PEntry; afirst, alast: Integer);
+begin
+ mEntries := aents;
+ mFirstEntry := afirst;
+ mLastEntry := alast;
+ cur := mFirstEntry-1;
+end;
+
+function THashBase.TKeyEnumerator.MoveNext: Boolean;
+begin
+ Inc(cur);
+ while (cur <= mLastEntry) do
+ begin
+ if (mEntries[cur].hash <> 0) then begin result := true; exit; end;
+ end;
+ result := false;
+end;
+
+function THashBase.TKeyEnumerator.getCurrent (): KeyT;
+begin
+ result := mEntries[cur].key;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+constructor THashBase.TKeyValEnumerator.Create (aents: PEntry; afirst, alast: Integer);
+begin
+ mEntries := aents;
+ mFirstEntry := afirst;
+ mLastEntry := alast;
+ cur := mFirstEntry-1;
+end;
+
+function THashBase.TKeyValEnumerator.MoveNext: Boolean;
+begin
+ Inc(cur);
+ while (cur <= mLastEntry) do
+ begin
+ if (mEntries[cur].hash <> 0) then begin result := true; exit; end;
+ end;
+ result := false;
+end;
+
+function THashBase.TKeyValEnumerator.getCurrent (): PEntry;
+begin
+ result := mEntries+cur;
+end;
+
+
end.