ndbhash.c (4975B)
1 #include <u.h> 2 #include <libc.h> 3 #include <bio.h> 4 #include "ndb.h" 5 #include "ndbhf.h" 6 7 enum { 8 Dptr, /* pointer to database file */ 9 Cptr, /* pointer to first chain entry */ 10 Cptr1 /* pointer to second chain entry */ 11 }; 12 13 /* 14 * generate a hash value for an ascii string (val) given 15 * a hash table length (hlen) 16 */ 17 ulong 18 ndbhash(char *vp, int hlen) 19 { 20 ulong hash; 21 uchar *val = (uchar*)vp; 22 23 for(hash = 0; *val; val++) 24 hash = (hash*13) + *val-'a'; 25 return hash % hlen; 26 } 27 28 /* 29 * read a hash file with buffering 30 */ 31 static uchar* 32 hfread(Ndbhf *hf, long off, int len) 33 { 34 if(off < hf->off || off + len > hf->off + hf->len){ 35 if(seek(hf->fd, off, 0) < 0 36 || (hf->len = read(hf->fd, hf->buf, sizeof(hf->buf))) < len){ 37 hf->off = -1; 38 return 0; 39 } 40 hf->off = off; 41 } 42 return &hf->buf[off-hf->off]; 43 } 44 45 /* 46 * return an opened hash file if one exists for the 47 * attribute and if it is current vis-a-vis the data 48 * base file 49 */ 50 static Ndbhf* 51 hfopen(Ndb *db, char *attr) 52 { 53 Ndbhf *hf; 54 char buf[sizeof(hf->attr)+sizeof(db->file)+2]; 55 uchar *p; 56 Dir *d; 57 58 /* try opening the data base if it's closed */ 59 if(db->mtime==0 && ndbreopen(db) < 0) 60 return 0; 61 62 /* if the database has changed, throw out hash files and reopen db */ 63 if((d = dirfstat(Bfildes(&db->b))) == nil || db->qid.path != d->qid.path 64 || db->qid.vers != d->qid.vers){ 65 if(ndbreopen(db) < 0){ 66 free(d); 67 return 0; 68 } 69 } 70 free(d); 71 72 if(db->nohash) 73 return 0; 74 75 /* see if a hash file exists for this attribute */ 76 for(hf = db->hf; hf; hf= hf->next){ 77 if(strcmp(hf->attr, attr) == 0) 78 return hf; 79 } 80 81 /* create a new one */ 82 hf = (Ndbhf*)malloc(sizeof(Ndbhf)); 83 if(hf == 0) 84 return 0; 85 memset(hf, 0, sizeof(Ndbhf)); 86 87 /* compare it to the database file */ 88 strncpy(hf->attr, attr, sizeof(hf->attr)-1); 89 sprint(buf, "%s.%s", db->file, hf->attr); 90 hf->fd = open(buf, OREAD); 91 if(hf->fd >= 0){ 92 hf->len = 0; 93 hf->off = 0; 94 p = hfread(hf, 0, 2*NDBULLEN); 95 if(p){ 96 hf->dbmtime = NDBGETUL(p); 97 hf->hlen = NDBGETUL(p+NDBULLEN); 98 if(hf->dbmtime == db->mtime){ 99 hf->next = db->hf; 100 db->hf = hf; 101 return hf; 102 } 103 } 104 close(hf->fd); 105 } 106 107 free(hf); 108 return 0; 109 } 110 111 /* 112 * return the first matching entry 113 */ 114 Ndbtuple* 115 ndbsearch(Ndb *db, Ndbs *s, char *attr, char *val) 116 { 117 uchar *p; 118 Ndbtuple *t; 119 Ndbhf *hf; 120 121 hf = hfopen(db, attr); 122 123 memset(s, 0, sizeof(*s)); 124 if(_ndbcachesearch(db, s, attr, val, &t) == 0){ 125 /* found in cache */ 126 if(t != nil) 127 return t; /* answer from this file */ 128 if(db->next == nil) 129 return nil; 130 return ndbsearch(db->next, s, attr, val); 131 } 132 133 s->db = db; 134 s->hf = hf; 135 if(s->hf){ 136 s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN; 137 p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN); 138 if(p == 0) 139 return _ndbcacheadd(db, s, attr, val, nil); 140 s->ptr = NDBGETP(p); 141 s->type = Cptr1; 142 } else if(db->length > 128*1024){ 143 print("Missing or out of date hash file %s.%s.\n", db->file, attr); 144 /* syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr); */ 145 146 /* advance search to next db file */ 147 s->ptr = NDBNAP; 148 _ndbcacheadd(db, s, attr, val, nil); 149 if(db->next == 0) 150 return nil; 151 return ndbsearch(db->next, s, attr, val); 152 } else { 153 s->ptr = 0; 154 s->type = Dptr; 155 } 156 t = ndbsnext(s, attr, val); 157 _ndbcacheadd(db, s, attr, val, (t != nil && s->db == db)?t:nil); 158 setmalloctag(t, getcallerpc(&db)); 159 return t; 160 } 161 162 static Ndbtuple* 163 match(Ndbtuple *t, char *attr, char *val) 164 { 165 Ndbtuple *nt; 166 167 for(nt = t; nt; nt = nt->entry) 168 if(strcmp(attr, nt->attr) == 0 169 && strcmp(val, nt->val) == 0) 170 return nt; 171 return 0; 172 } 173 174 /* 175 * return the next matching entry in the hash chain 176 */ 177 Ndbtuple* 178 ndbsnext(Ndbs *s, char *attr, char *val) 179 { 180 Ndbtuple *t; 181 Ndb *db; 182 uchar *p; 183 184 db = s->db; 185 if(s->ptr == NDBNAP) 186 goto nextfile; 187 188 for(;;){ 189 if(s->type == Dptr){ 190 if(Bseek(&db->b, s->ptr, 0) < 0) 191 break; 192 t = ndbparse(db); 193 s->ptr = Boffset(&db->b); 194 if(t == 0) 195 break; 196 if(s->t = match(t, attr, val)) 197 return t; 198 ndbfree(t); 199 } else if(s->type == Cptr){ 200 if(Bseek(&db->b, s->ptr, 0) < 0) 201 break; 202 s->ptr = s->ptr1; 203 s->type = Cptr1; 204 t = ndbparse(db); 205 if(t == 0) 206 break; 207 if(s->t = match(t, attr, val)) 208 return t; 209 ndbfree(t); 210 } else if(s->type == Cptr1){ 211 if(s->ptr & NDBCHAIN){ /* hash chain continuation */ 212 s->ptr &= ~NDBCHAIN; 213 p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN); 214 if(p == 0) 215 break; 216 s->ptr = NDBGETP(p); 217 s->ptr1 = NDBGETP(p+NDBPLEN); 218 s->type = Cptr; 219 } else { /* end of hash chain */ 220 if(Bseek(&db->b, s->ptr, 0) < 0) 221 break; 222 s->ptr = NDBNAP; 223 t = ndbparse(db); 224 if(t == 0) 225 break; 226 if(s->t = match(t, attr, val)){ 227 setmalloctag(t, getcallerpc(&s)); 228 return t; 229 } 230 ndbfree(t); 231 break; 232 } 233 } 234 } 235 236 nextfile: 237 238 /* nothing left to search? */ 239 s->ptr = NDBNAP; 240 if(db->next == 0) 241 return 0; 242 243 /* advance search to next db file */ 244 t = ndbsearch(db->next, s, attr, val); 245 setmalloctag(t, getcallerpc(&s)); 246 return t; 247 }