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    [W:0.029 / U:0.800 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site