From: Nikita Danilov Subject: Re: readdir on hash filesystems Date: Thu, 22 Sep 2005 00:22:48 +0400 Message-ID: <17201.49432.28348.486601@gargle.gargle.HOWL> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Cc: linux-fsdevel@vger.kernel.org Return-path: Received: from moraine.clusterfs.com ([66.96.26.190]:25552 "EHLO moraine.clusterfs.com") by vger.kernel.org with ESMTP id S1751409AbVIUUWe (ORCPT ); Wed, 21 Sep 2005 16:22:34 -0400 To: Bob Copeland In-Reply-To: Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org Bob Copeland writes: > Hi all, > > I am writing a new filesystem driver for the filesystem used by the > Rio Karma (and, as it happens, ReplayTV). See the attached patch and > my webpage here for more info: http://bobcopeland.com/karma/. I have > a > couple of newbie questions: > > 1) The directory structure implements a hash table where each > directory has a fixed number of entries. Each entry is a file that > has a pointer to another file in the hash chain and so there can be an > unlimited number of files in any hash chain. What is the usual way to > implement readdir efficiently in this case? With f_pos alone, I don't All file systems with hash-based directories I know of, treat hash collisions (a hash chain with more than one item) as some sort of exception, because they have large number of hash buckets. For your case where long hash chains are ordinary --because omfs has 201 hash buckets per directory (hard-coded value is bad, by the way)-- there is no "usual way", you have to invent one yourself. > have any idea which node I want along the hash chain without counting > up f_pos nodes in the tree. One possible solution is to use lower 24 bits of f_pos to store an index within given hash chain, and next 8 bits to store index of hash chain: int hchain = file->f_pos >> 24 & 0xff; int hindex = file->f_pos & 0xffffff; Nikita.