index 15d19f6a15e8d6bd296423412e1580114c9552ff..8e6158fcefbff31d5d6bcff14d499d5d621a5b77 100644 (file)
--- a/src/shared/hashtable.pas
+++ b/src/shared/hashtable.pas
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
hashfn: THashFn;
equfn: TEquFn;
destructor Destroy (); override;
procedure clear ();
+ procedure reset (); // don't shrink buckets
procedure rehash ();
procedure compact (); // call this instead of `rehash()` after alot of deletions
//WARNING! don't modify table in iterator (queries are ok, though)
function forEach (it: TIteratorFn): Boolean;
+ function GetEnumerator (): TValEnumerator;
+
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
for idx := 0 to High(mBuckets) do mBuckets[idx] := nil;
SetLength(mEntries, Length(mBuckets));
+ {
for idx := 0 to High(mEntries)-1 do
begin
mEntries[idx].hash := 0;
end;
mEntries[High(mEntries)].hash := 0;
mEntries[High(mEntries)].nextFree := nil;
+ }
+ {
+ for idx := 0 to High(mEntries) do
+ begin
+ mEntries[idx].hash := 0;
+ mEntries[idx].nextFree := nil;
+ end;
+ }
mBucketsUsed := 0;
{$IFDEF RBHASH_SANITY_CHECKS}
mEntriesUsed := 0;
{$ENDIF}
- mFreeEntryHead := @mEntries[0];
+ mFreeEntryHead := nil; //@mEntries[0];
mFirstEntry := -1;
mLastEntry := -1;
end;
+procedure THashBase.reset ();
+var
+ idx: Integer;
+begin
+ if (mBucketsUsed > 0) then
+ begin
+ for idx := 0 to High(mBuckets) do mBuckets[idx] := nil;
+ {
+ for idx := 0 to High(mEntries)-1 do
+ begin
+ mEntries[idx].hash := 0;
+ mEntries[idx].nextFree := @mEntries[idx+1]; //idx+1;
+ end;
+ mEntries[High(mEntries)].hash := 0;
+ mEntries[High(mEntries)].nextFree := nil;
+ }
+ {
+ if (mFirstEntry >= 0) then
+ begin
+ for idx := mFirstEntry to mLastEntry do
+ begin
+ mEntries[idx].hash := 0;
+ mEntries[idx].nextFree := nil;
+ end;
+ end;
+ }
+
+ mBucketsUsed := 0;
+ {$IFDEF RBHASH_SANITY_CHECKS}
+ mEntriesUsed := 0;
+ {$ENDIF}
+ mFreeEntryHead := nil; //@mEntries[0];
+ mFirstEntry := -1;
+ mLastEntry := -1;
+ end;
+end;
+
+
function THashBase.getCapacity (): Integer; inline; begin result := Length(mBuckets); end;
var
idx: Integer;
begin
+ if (mFreeEntryHead = nil) then
+ begin
+ if (mLastEntry = High(mEntries)) then raise Exception.Create('internal error in hash entry allocator (0.0)');
+ Inc(mLastEntry);
+ if (mFirstEntry = -1) then
+ begin
+ if (mLastEntry <> 0) then raise Exception.Create('internal error in hash entry allocator (0.1)');
+ mFirstEntry := 0;
+ end;
+ result := @mEntries[mLastEntry];
+ result.nextFree := nil; // just in case
+ {$IFDEF RBHASH_SANITY_CHECKS}
+ Inc(mEntriesUsed);
+ {$ENDIF}
+ exit;
+ end;
{$IFDEF RBHASH_SANITY_CHECKS}
if (mFreeEntryHead = nil) then raise Exception.Create('internal error in hash entry allocator (0)');
if (mFreeEntryHead.hash <> 0) then raise Exception.Create('internal error in hash entry allocator (1)');
if (idx < 0) or (idx > High(mEntries)) then raise Exception.Create('internal error in hash entry allocator (invalid entry address)');
if (e <> @mEntries[idx]) then raise Exception.Create('internal error in hash entry allocator (wtf?!)');
{$ENDIF}
- e.hash := 0;
- e.nextFree := mFreeEntryHead;
- mFreeEntryHead := e; //idx;
{$IFDEF RBHASH_SANITY_CHECKS}
Dec(mEntriesUsed);
{$ENDIF}
+ e.hash := 0;
+ e.nextFree := mFreeEntryHead;
+ mFreeEntryHead := e; //idx;
// fix mFirstEntry and mLastEntry
{$IFDEF RBHASH_SANITY_CHECKS}
if (mFirstEntry < 0) or (mLastEntry < 0) then raise Exception.Create('internal error in hash entry allocator (invalid first/last range; 0)');
end;
+function THashBase.GetEnumerator (): TValEnumerator;
+begin
+ if (Length(mEntries) > 0) then
+ begin
+ result := TValEnumerator.Create(@mEntries[0], mFirstEntry, mLastEntry);
+ end
+ else
+ begin
+ result := TValEnumerator.Create(nil, -1, -1);
+ end;
+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;
+
+
end.