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