lkml.org 
[lkml]   [1999]   [Jun]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectQuota file format
Hello

Finally here's the format of quota file I'll try to implement:
It will be a hash table (I don't want to bother with b-trees ;-)). Its size would
be dynamic (I mean you can choose it at the beginning and there will be some tool
for resizing...). I would suggest default size ~ 16384 entries -> 64 KB. All entries
will be pointing to one block at the beginning (the file would be divided into blocks
sized 1KB so we can take advantage of buffer cache). When we are adding entry we compute
hash value and try to add entry to block hashtable is pointing to. If block is full we'll
try to split it - we'll get hashvalues of all entries in the block and divide them into
two (or more?) groups. For each group we'll set up new block rewrite the pointer in the
hashtable. By this we hopefully prevent existence of hashchains split among more blocks
and we won't waste much space. As it can happen that many structures will have same hashval
and so we won't be able to split them we have to admit chains of blocks but I hope
it won't happen often so it won't impact our performance.
When deleting we simply rewrite the structure by the last structure in the chain. If
block becomes empty or almost empty we'll try to merge it with some almost empty block
too. IMHO deleting isn't much used operation and so we can spend some time
by serching almost empty block :-) (maybe there will be some list of them or we won't
do any merging by default and there will be some tool for shrinking of file).
Lookup will look like following: compute hashval, read the pointer, read the block,
find structure in the block (simple linear search). If not found take next block in
chain (hopefully there won't be any). If it was last block, return 'not found'.

Any comments, suggestions?

Honza.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:52    [W:2.223 / U:0.012 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site