sys/src/libndb/ndbhash.c

   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                         ndbsetmalloctag(t, getcallerpc(&db));
 128                         return t;       /* answer from this file */
 129                 }
 130                 if(db->next == nil)
 131                         return nil;
 132                 t = ndbsearch(db->next, s, attr, val);
 133                 ndbsetmalloctag(t, getcallerpc(&db));
 134                 return t;
 135         }
 136
 137         s->db = db;
 138         s->hf = hf;
 139         if(s->hf){
 140                 s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
 141                 p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
 142                 if(p == 0){
 143                         t = _ndbcacheadd(db, s, attr, val, nil);
 144                         ndbsetmalloctag(t, getcallerpc(&db));
 145                         return t;
 146                 }
 147                 s->ptr = NDBGETP(p);
 148                 s->type = Cptr1;
 149         } else if(db->length > 128*1024){
 150                 print("Missing or out of date hash file %s.%s.\n", db->file, attr);
 151                 syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr);
 152
 153                 /* advance search to next db file */
 154                 s->ptr = NDBNAP;
 155                 _ndbcacheadd(db, s, attr, val, nil);
 156                 if(db->next == 0)
 157                         return nil;
 158                 t = ndbsearch(db->next, s, attr, val);
 159                 ndbsetmalloctag(t, getcallerpc(&db));
 160                 return t;
 161         } else {
 162                 s->ptr = 0;
 163                 s->type = Dptr;
 164         }
 165         t = ndbsnext(s, attr, val);
 166         _ndbcacheadd(db, s, attr, val, (t != nil && s->db == db)?t:nil);
 167         ndbsetmalloctag(t, getcallerpc(&db));
 168         return t;
 169 }
 170
 171 static Ndbtuple*
 172 match(Ndbtuple *t, char *attr, char *val)
 173 {
 174         Ndbtuple *nt;
 175
 176         for(nt = t; nt; nt = nt->entry)
 177                 if(strcmp(attr, nt->attr) == 0
 178                 && strcmp(val, nt->val) == 0)
 179                         return nt;
 180         return 0;
 181 }
 182
 183 /*
 184  *  return the next matching entry in the hash chain
 185  */
 186 Ndbtuple*
 187 ndbsnext(Ndbs *s, char *attr, char *val)
 188 {
 189         Ndbtuple *t;
 190         Ndb *db;
 191         uchar *p;
 192
 193         db = s->db;
 194         if(s->ptr == NDBNAP)
 195                 goto nextfile;
 196
 197         for(;;){
 198                 if(s->type == Dptr){
 199                         if(Bseek(&db->b, s->ptr, 0) < 0)
 200                                 break;
 201                         t = ndbparse(db);
 202                         s->ptr = Boffset(&db->b);
 203                         if(t == 0)
 204                                 break;
 205                         if(s->t = match(t, attr, val)){
 206                                 ndbsetmalloctag(t, getcallerpc(&s));
 207                                 return t;
 208                         }
 209                         ndbfree(t);
 210                 } else if(s->type == Cptr){
 211                         if(Bseek(&db->b, s->ptr, 0) < 0)
 212                                 break;
 213                         s->ptr = s->ptr1;
 214                         s->type = Cptr1;
 215                         t = ndbparse(db);
 216                         if(t == 0)
 217                                 break;
 218                         if(s->t = match(t, attr, val)){
 219                                 ndbsetmalloctag(t, getcallerpc(&s));
 220                                 return t;
 221                         }
 222                         ndbfree(t);
 223                 } else if(s->type == Cptr1){
 224                         if(s->ptr & NDBCHAIN){  /* hash chain continuation */
 225                                 s->ptr &= ~NDBCHAIN;
 226                                 p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
 227                                 if(p == 0)
 228                                         break;
 229                                 s->ptr = NDBGETP(p);
 230                                 s->ptr1 = NDBGETP(p+NDBPLEN);
 231                                 s->type = Cptr;
 232                         } else {                /* end of hash chain */
 233                                 if(Bseek(&db->b, s->ptr, 0) < 0)
 234                                         break;
 235                                 s->ptr = NDBNAP;
 236                                 t = ndbparse(db);
 237                                 if(t == 0)
 238                                         break;
 239                                 if(s->t = match(t, attr, val)){
 240                                         ndbsetmalloctag(t, getcallerpc(&s));
 241                                         return t;
 242                                 }
 243                                 ndbfree(t);
 244                                 break;
 245                         }
 246                 }
 247         }
 248
 249 nextfile:
 250
 251         /* nothing left to search? */
 252         s->ptr = NDBNAP;
 253         if(db->next == 0)
 254                 return 0;
 255
 256         /* advance search to next db file */
 257         t = ndbsearch(db->next, s, attr, val);
 258         ndbsetmalloctag(t, getcallerpc(&s));
 259         return t;
 260 }