Messages in this thread | | | Date | 27 Jul 1996 10:04:00 +0200 | From | (Kai Henningsen) | Subject | Re: Is any file system on Linux appropriate for very large directories |
| |
smurf@smurf.noris.de (Matthias Urlichs) wrote on 26.07.96 in <96Jul26.191212+0100met_dst.2218-301+71@work.smurf.noris.de>:
> In linux.dev.kernel, article <1.5.4.32.19960726100547.008d9cbc@picard.c > sihq.com>, > Mike Black <mblack@csihq.com> writes:
> > P.S. What was the new mailing list for this subject??? I lost the ma > il... > > Obviously, I don't know it either. :-/
I think there is none. The new list was for a new _networked_ fs.
Anyway, here is my current "perfect hashing" db source. As I explained before, it's currently used to keep track of message ids, not file names; and it's performing quite well with an amount of data I didn't expect to handle when I coded it.
The beauty of this scheme is that the only reason it gets slower is disk cache size. The access path to an item is always constant in length, no matter how many items. (I actually had trouble believing it when I first heard about this.)
It can handle as many entries with the exact same hash as there are elements in the tBucket.E array. I do not consider this a problem.
unit MsgDB;
interface
type tHash = Longint; tTime = Longint; tMsgRec = record FilePos : Longint; IdHash : tHash; TimeGot, TimeExpire : tTime; MsgId : string; end;
procedure InitMsgDB(inDir: string); procedure ExitMsgDB;
function GetMsgById(const Id: string; var Msg: tMsgRec): Boolean; var WasHashDupe : Boolean; { valid after GetMsgById } procedure UpdateMsg(var Msg: tMsgRec); procedure NewMsg(var Msg: tMsgRec); { Needs MsgId already set. No Dupe check! } procedure DelMsg(const Id: string);
implementation
type tBucket = record { exactly 4096 bytes } BNo : Word; N : Word; BucketMod : Word; Filler : Word; E : array [1 .. 511] of record Hash : tHash; FilePos : Longint end; end; tDir = array [0 .. MaxInt - 1] of Word; pDir = ^ tDir; var Recs : file; Buckets : file of tBucket; Dir : file; Directory : pDir; DirectoryMod : Word; ActBucket : tBucket;
procedure GetBucket(N: Word); begin if ActBucket.BNo = N then Exit; Seek(Buckets, N); Read(Buckets, ActBucket); end;
procedure PutBucket; begin Seek(Buckets, ActBucket.BNo); Write(Buckets, ActBucket); end;
procedure NewBucket(Depth: Word); begin FillChar(ActBucket, SizeOf(ActBucket), 0); ActBucket.BNo := FileSize(Buckets); ActBucket.BucketMod := Depth; end;
procedure InitMsgDB(inDir: string); begin Assign(Recs, inDir + '/MsgDB.Rec'); {$i-} Reset(Recs, 1); {$i+} if IOResult <> 0 then Rewrite(Recs, 1); Assign(Buckets, inDir + '/MsgDB.Bkt'); {$i-} Reset(Buckets); {$i+} if IOResult <> 0 then Rewrite(Buckets); NewBucket(1); Assign(Dir, inDir + '/MsgDB.Dir'); {$i-} Reset(Dir, 1); {$i+} if IOResult = 0 then begin BlockRead(Dir, DirectoryMod, SizeOf(DirectoryMod)); GetMem(Directory, DirectoryMod * SizeOf(Directory^[0])); BlockRead(Dir, Directory^, DirectoryMod * SizeOf(Directory^[0])); Close(Dir); end else begin DirectoryMod := 1; GetMem(Directory, SizeOf(Directory^[0])); Directory^[0] := 0; PutBucket; end { if IOResult=0 else}; end { InitMsgDB};
procedure ExitMsgDB; begin Close(Recs); Close(Buckets); Rewrite(Dir, 1); BlockWrite(Dir, DirectoryMod, SizeOf(DirectoryMod)); BlockWrite(Dir, Directory^, DirectoryMod * SizeOf(Directory^[0])); Close(Dir); FreeMem(Directory, DirectoryMod * SizeOf(Directory^[0])); end;
function Hash(const Id: string): tHash; var H : tHash; i : Byte; begin H := 0; for i := 1 to Length(Id) do {$q-} H := 131 * H + Ord(Id[i]); {$q+} Hash := H and MaxLongint; end { Hash};
procedure GetMsg(FilePos: Longint; var Msg: tMsgRec); var r : Word; begin Seek(Recs, FilePos); FillChar(Msg, SizeOf(Msg), 0); BlockRead(Recs, Msg, SizeOf(Msg), r); end;
function GetMsgById(const Id: string; var Msg: tMsgRec): Boolean; var H : tHash; i : Word; begin WasHashDupe := False; H := Hash(Id); GetBucket(Directory^[H mod DirectoryMod]); with ActBucket do for i := 1 to N do with E[i] do if Hash = H then begin GetMsg(FilePos, Msg); if Msg.MsgId = Id then begin GetMsgById := True; Exit; end; WasHashDupe := True; end; GetMsgById := False; Msg.FilePos := - 1; end { GetMsgById};
procedure UpdateMsg(var Msg: tMsgRec); begin with Msg do begin Seek(Recs, FilePos); BlockWrite(Recs, Msg, SizeOf(Msg) - High(MsgId) + Length(MsgId)); end; end;
procedure NewMsg(var Msg: tMsgRec); var Old : tBucket; i, j : Word; D2 : pDir; begin with Msg do begin FilePos := FileSize(Recs); IdHash := Hash(MsgId); UpdateMsg(Msg); with ActBucket do begin repeat GetBucket(Directory^[IdHash mod DirectoryMod]); if N >= High(E) then begin { split } BucketMod := BucketMod * 2; Old := ActBucket; if BucketMod > DirectoryMod then begin { Directory split } GetMem(D2, DirectoryMod * 2 * SizeOf(Directory^[0])); Move(Directory^, D2^[0], DirectoryMod * SizeOf(Directory^[0])); Move(Directory^, D2^[DirectoryMod], DirectoryMod * SizeOf( Directory^[0])); FreeMem(Directory, DirectoryMod * SizeOf(Directory^[0])); Directory := D2; DirectoryMod := DirectoryMod * 2; end; NewBucket(BucketMod); for i := 0 to DirectoryMod - 1 do if Directory^[i] = Old.BNo then if i mod BucketMod = IdHash mod BucketMod then Directory^[i] := BNo; j := 0; for i := 1 to Old.N do if Old.E[i].Hash mod BucketMod = IdHash mod BucketMod then begin Inc(N); E[N] := Old.E[i]; end else begin Inc(j); if i <> j then Old.E[j] := Old.E[i]; end; Old.N := j; PutBucket; ActBucket := Old; PutBucket; end { if N>=High(E)} else Break; until False; Inc(N); with E[N] do begin FilePos := Msg.FilePos; Hash := IdHash; end; PutBucket; end { with ActBucket}; end { with Msg}; end { NewMsg};
procedure DelMsg(const Id: string); var Msg : tMsgRec; found : Boolean; i : Word; begin if GetMsgById(Id, Msg) then with Msg, ActBucket do begin found := False; for i := 1 to N do begin if E[i].FilePos = FilePos then found := True; if found and (i < N) then E[i] := E[i + 1]; end; Dec(N); PutBucket; end; end { DelMsg};
end { MsgDB}.
MfG Kai
| |