The dcache uses this to hash directory names. It looks pretty close
to the old Dragon Book rotate-and-xor algorithm.
24 struct qstr {
25 const unsigned char * name;
26 unsigned int len;
27 unsigned int hash;
28 };
29
30 /* Name hashing routines. Initial hash value */
31 #define init_name_hash() 0
32
33 /* partial hash update function. Assume roughly 4 bits per
character */
34 static __inline__ unsigned long partial_name_hash(unsigned long c,
unsigned long prevhash)
35 {
36 prevhash = (prevhash << 4) | (prevhash >>
(8*sizeof(unsigned long)-4));
37 return prevhash ^ c;
38 }
39
40 /* Finally: cut down the number of bits to a int value (and try to
avoid losing bits) */
41 static __inline__ unsigned long end_name_hash(unsigned long hash)
42 {
43 if (sizeof(hash) > sizeof(unsigned int))
44 hash += hash >> 4*sizeof(hash);
45 return (unsigned int) hash;
46 }
47
48 /* Compute the hash for a name string. */
49 static __inline__ unsigned int full_name_hash(const unsigned char
* name, unsigned int len)
50 {
51 unsigned long hash = init_name_hash();
52 while (len--)
53 hash = partial_name_hash(*name++, hash);
54 return end_name_hash(hash);
55 }
56
On Mar 3, 8:32 am, aanchal goyal <[email protected]> wrote:
> Gene:
> I am talking about file names.
>
> On Sat, Mar 3, 2012 at 1:07 AM, Gene <[email protected]> wrote:
> > It's possible you're not getting any clear answers because the
> > question is unclear. Linux does many different kinds of name lookup
> > all over the system. What names are you talking about?
>
> > On Mar 1, 3:50 pm, aanchal goyal <[email protected]> wrote:
> > > anyone knows what hash function is used in the name lookup procedure in
> > > linux?
>
> > > Procedure lookup(name)
> > > 1: h := hash(name)
> > > 2: dentryNode := hashtable(h)
> > > 3: while dentryNode != NULL do
> > > 4: if dentryNode- >name != name then
> > > 5: dentryNode := dentryNode- >next
> > > 6: else
> > > 7: return dentryNode
> > > 8: end if
> > > 9: end while
> > > --
> > > Regards,*
> > > Aanchal Goyal*.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Regards,*
> Aanchal Goyal*.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
