lkml.org 
[lkml]   [1996]   [Jul]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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


\
 
 \ /
  Last update: 2005-03-22 13:38    [from the cache]
©2003-2011 Jasper Spaans