X-Git-Url: https://deadsoftware.ru/gitweb?a=blobdiff_plain;ds=sidebyside;f=src%2Fshared%2Fhashtable.pas;h=f3331d816e68d994a3bd234972172c3733184554;hb=223356cbae3197afc861efa6241c4ae91bd92885;hp=15d19f6a15e8d6bd296423412e1580114c9552ff;hpb=21b8c729c535950bb33c3c036f3510331462d00d;p=d2df-sdl.git diff --git a/src/shared/hashtable.pas b/src/shared/hashtable.pas index 15d19f6..f3331d8 100644 --- a/src/shared/hashtable.pas +++ b/src/shared/hashtable.pas @@ -39,16 +39,52 @@ type 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; @@ -77,6 +113,7 @@ type destructor Destroy (); override; procedure clear (); + procedure reset (); // don't shrink buckets procedure rehash (); procedure compact (); // call this instead of `rehash()` after alot of deletions @@ -89,11 +126,16 @@ type //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 @@ -106,7 +148,7 @@ type 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 @@ -121,8 +163,8 @@ function hashNewIntInt (): THashIntInt; 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; @@ -197,7 +239,7 @@ begin end; -procedure TJoaatHasher.put (const buf; len: LongWord); +procedure TJoaatHasher.put (constref buf; len: LongWord); var bytes: PByte; h: LongWord; @@ -227,12 +269,12 @@ end; {$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; @@ -241,7 +283,7 @@ 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 @@ -304,6 +346,7 @@ 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; @@ -311,17 +354,63 @@ begin 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; @@ -329,6 +418,22 @@ function THashBase.allocEntry (): PEntry; 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)'); @@ -365,12 +470,12 @@ begin 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)'); @@ -797,4 +902,105 @@ 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.