Path: utzoo!attcan!uunet!husc6!mailrus!iuvax!bsu-cs!dhesi
From: dhesi@bsu-cs.UUCP (Rahul Dhesi)
Newsgroups: comp.unix.wizards
Subject: Re: libraries
Message-ID: <5266@bsu-cs.UUCP>
Date: 22 Dec 88 16:16:55 GMT
References: <14946@mimsy.UUCP> <1269@nusdhub.UUCP> <15080@mimsy.UUCP> <10211@rpp386.Dallas.TX.US> <15106@mimsy.UUCP>
Reply-To: dhesi@bsu-cs.UUCP (Rahul Dhesi)
Organization: CS Dept, Ball St U, Muncie, Indiana
Lines: 12

In article <15106@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes:
     Directory scanning tended to be O(n^2).  That is why 4.3BSD,
     current SunOSes, and perhaps even SVR3 have name caches.  It
     reduces the behaviour to O(n) in most cases.  Granted, O(n) is
     still considerably higher than O(1)....

In the long run (4.5BSD?) perhaps a bit could be found to mark a
directory as hashed.  To preserve compatibility with current utilities,
you would need a shadow directory with the hashed structure that
mimicked the current sequential list.
-- 
Rahul Dhesi         UUCP:  <backbones>!{iuvax,pur-ee}!bsu-cs!dhesi