X-Git-Url: https://deadsoftware.ru/gitweb?a=blobdiff_plain;f=src%2Fshared%2Fhashtable.pas;h=8aaa522a45bae64530243a8fa031f42b4b035b4f;hb=3d8489bb2d74d08d3a9ccad06eea7e8fb7d4038d;hp=b847720ba90a3ed86977b6adbc2531a4c4ce4b9c;hpb=ed2957d16cd248859884dc5ce8be287616f5e546;p=d2df-sdl.git diff --git a/src/shared/hashtable.pas b/src/shared/hashtable.pas index b847720..8aaa522 100644 --- a/src/shared/hashtable.pas +++ b/src/shared/hashtable.pas @@ -39,22 +39,60 @@ 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 + 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} @@ -90,11 +128,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 @@ -107,7 +150,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 @@ -117,17 +160,28 @@ type type THashIntInt = specialize THashBase; + THashStrInt = specialize THashBase; + THashStrStr = specialize THashBase; function hashNewIntInt (): THashIntInt; +function hashNewStrInt (): THashStrInt; +function hashNewStrStr (): THashStrStr; 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; +// 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 @@ -153,12 +207,13 @@ end; // ////////////////////////////////////////////////////////////////////////// // 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); @@ -167,6 +222,11 @@ begin 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} @@ -176,6 +236,18 @@ begin end; +function hashNewStrInt (): THashStrInt; +begin + result := THashStrInt.Create(hsihash, hsiequ); +end; + + +function hashNewStrStr (): THashStrStr; +begin + result := THashStrStr.Create(hsihash, hsiequ); +end; + + // ////////////////////////////////////////////////////////////////////////// // {$PUSH} {$RANGECHECKS OFF} @@ -198,7 +270,7 @@ begin end; -procedure TJoaatHasher.put (const buf; len: LongWord); +procedure TJoaatHasher.put (constref buf; len: LongWord); var bytes: PByte; h: LongWord; @@ -228,12 +300,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; @@ -242,7 +314,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 @@ -861,4 +933,105 @@ begin end; +// enumerators +function THashBase.GetEnumerator (): TValEnumerator; +begin + 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 + 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 + if (mEntries[cur].hash <> 0) then begin result := true; exit; end; + end; + result := false; +end; + +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; + mLastEntry := alast; + cur := mFirstEntry-1; +end; + +function THashBase.TKeyValEnumerator.MoveNext (): Boolean; inline; +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; inline; +begin + result := @mEntries[cur]; +end; + + end.