1implement Attrhash, Attrindex; 2 3include "sys.m"; 4 sys: Sys; 5 6include "bufio.m"; 7 bufio: Bufio; 8 9include "attrdb.m"; 10 11init(): string 12{ 13 sys = load Sys Sys->PATH; 14 bufio = load Bufio Bufio->PATH; 15 if(bufio == nil) 16 return sys->sprint("can't load %s: %r", Bufio->PATH); 17 return nil; 18} 19 20attrindex(): Attrindex 21{ 22 return load Attrindex "$self"; 23} 24 25Index.open(dbf: Attrdb->Dbf, attr: string, fd: ref Sys->FD): ref Index 26{ 27 (ok, d) := sys->fstat(fd); 28 if(ok < 0 || dbf.dir == nil || dbf.dir.mtime > d.mtime) 29 return nil; 30 length := int d.length; 31 if(length < NDBHLEN) 32 return nil; 33 buf := array[length] of byte; 34 if(sys->read(fd, buf, len buf) != len buf) 35 return nil; 36 mtime := get4(buf); 37 if(mtime != dbf.dir.mtime) 38 return nil; 39 size := get3(buf[4:]); 40 return ref Index(fd, attr, d.mtime, size, buf[8:]); 41} 42 43#Index.firstoff(ind: self ref Index, val: string): ref Attrdb->Dbptr 44#{ 45# o := hash(val, ind.size)*NDBPLEN; 46# p := get3(tab[o:]); 47# if(p == NDBNAP) 48# return nil; 49# if((p & NDBCHAIN) == 0) 50# return ref Attrdb.Direct(p); 51# p &= ~NDBCHAIN; 52# return ref Attrdb.Hash(get3(tab[p:]), get3(tab[p+NDBPLEN:])); 53#} 54 55#Index.nextoff(ind: self ref Index, val: string, ptr: ref Attrdb->Dbptr): (int, ref Attrdb->Dbptr) 56#{ 57# pick p := ptr { 58# Hash => 59# o := get3(tab[p.current:]); 60# if((o & NDBCHAIN) == 0) 61# return (o, ref Attrdb.Direct(p.next)); 62# o &= ~NDBCHAIN; 63# o1 := get3(tab[o:]); 64# o2 := get3(tab[o+NDBPLEN:]); 65# 66 67# o := hash(val, ind.size)*NDBPLEN; 68# p := get3(tab[o:]); 69# if(p == NDBNAP) 70# return nil; 71# for(; (p := get3(tab[o:])) != NDBNAP; o = p & ~NDBCHAIN) 72# if((p & NDBCHAIN) == 0){ 73# put3(tab[o:], chain | NDBCHAIN); 74# put3(tab[chain:], p); 75# put3(tab[chain+NDBPLEN:], offset); 76# return chain+2*NDBPLEN; 77# } 78# return nil; 79#} 80 81# 82# this must be the same hash function used by Plan 9's ndb 83# 84hash(s: string, hlen: int): int 85{ 86 h := 0; 87 for(i := 0; i < len s; i++) 88 if(s[i] >= 16r80){ 89 # could optimise by calculating utf ourselves 90 a := array of byte s; 91 for(i=0; i<len a; i++) 92 h = (h*13) + int a[i] - 'a'; 93 break; 94 }else 95 h = (h*13) + s[i]-'a'; 96 if(h < 0) 97 return int((big h & big 16rFFFFFFFF)%big hlen); 98 return h%hlen; 99} 100 101get3(a: array of byte): int 102{ 103 return (int a[2]<<16) | (int a[1]<<8) | int a[0]; 104} 105 106get4(a: array of byte): int 107{ 108 return (int a[3]<<24) | (int a[2]<<16) | (int a[1]<<8) | int a[0]; 109} 110