Messages in this thread | | | Date | Sun, 6 Jun 1999 18:00:19 +0200 | From | Jan Kara <> | Subject | Quota 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/
| |