akaros/user/ndblib/ndbhash.c
<<
>>
Prefs
   1/* 
   2 * This file is part of the UCB release of Plan 9. It is subject to the license
   3 * terms in the LICENSE file found in the top-level directory of this
   4 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
   5 * part of the UCB release of Plan 9, including this file, may be copied,
   6 * modified, propagated, or distributed except according to the terms contained
   7 * in the LICENSE file.
   8 */
   9#include <stdlib.h>
  10
  11#include <stdio.h>
  12#include <parlib/parlib.h>
  13#include <unistd.h>
  14#include <signal.h>
  15#include <fcntl.h>
  16#include <iplib/iplib.h>
  17#include <ndblib/ndb.h>
  18#include <ndblib/ndbhf.h>
  19
  20enum {
  21        Dptr,   /* pointer to database file */
  22        Cptr,   /* pointer to first chain entry */
  23        Cptr1,  /* pointer to second chain entry */
  24};
  25
  26/*
  27 *  generate a hash value for an ascii string (val) given
  28 *  a hash table length (hlen)
  29 */
  30uint32_t
  31ndbhash(char *vp, int hlen)
  32{
  33        uint32_t hash;
  34        uint8_t *val = (uint8_t*)vp;
  35
  36        for(hash = 0; *val; val++)
  37                hash = (hash*13) + *val-'a';
  38        return hash % hlen;
  39}
  40
  41/*
  42 *  read a hash file with buffering
  43 */
  44static uint8_t*
  45hfread(struct ndbhf *hf, long off, int len)
  46{
  47        if(off < hf->off || off + len > hf->off + hf->len){
  48                if(lseek(hf->fd, off, 0) < 0
  49                || (hf->len = read(hf->fd, hf->buf, sizeof(hf->buf))) < len){
  50                        hf->off = -1;
  51                        return 0;
  52                }
  53                hf->off = off;
  54        }
  55        return &hf->buf[off-hf->off];
  56}
  57
  58/*
  59 *  return an opened hash file if one exists for the
  60 *  attribute and if it is current vis-a-vis the data
  61 *  base file
  62 */
  63static struct ndbhf*
  64hfopen(struct ndb *db, char *attr)
  65{
  66        static int beenhere = 0;
  67        struct ndbhf *hf;
  68        char buf[sizeof(hf->attr)+sizeof(db->file)+2];
  69        uint8_t *p;
  70        struct dir *d;
  71
  72        /* try opening the data base if it's closed */
  73        if(db->mtime==0 && ndbreopen(db) < 0)
  74                return 0;
  75
  76        /* if the database has changed, throw out hash files and reopen db */
  77#if 0
  78        if((d = dirfstat(Bfildes(&db->b))) == NULL || db->qid.path != d->qid.path
  79        || db->qid.vers != d->qid.vers){
  80#else
  81        if (! beenhere){
  82#endif
  83                if(ndbreopen(db) < 0){
  84                        free(d);
  85                        return 0;
  86                }
  87                beenhere = 1;
  88                db->mtime = 1;
  89        }
  90        free(d);
  91
  92        if(db->nohash)
  93                return 0;
  94
  95        /* see if a hash file exists for this attribute */
  96        for(hf = db->hf; hf; hf= hf->next){
  97                if(strcmp(hf->attr, attr) == 0)
  98                        return hf;
  99        }
 100
 101        /* create a new one */
 102        hf = (struct ndbhf*)calloc(sizeof(struct ndbhf), 1);
 103        if(hf == 0)
 104                return 0;
 105        memset(hf, 0, sizeof(struct ndbhf));
 106
 107        /* compare it to the database file */
 108        strncpy(hf->attr, attr, sizeof(hf->attr)-1);
 109        sprintf(buf, "%s.%s", db->file, hf->attr);
 110        hf->fd = open(buf, O_RDONLY);
 111        if(hf->fd >= 0){
 112                hf->len = 0;
 113                hf->off = 0;
 114                p = hfread(hf, 0, 2*NDBULLEN);
 115                if(p){
 116                        hf->dbmtime = NDBGETUL(p);
 117                        hf->hlen = NDBGETUL(p+NDBULLEN);
 118                        if(hf->dbmtime == db->mtime){
 119                                hf->next = db->hf;
 120                                db->hf = hf;
 121                                return hf;
 122                        }
 123                }
 124                close(hf->fd);
 125        }
 126
 127        free(hf);
 128        return 0;
 129}
 130
 131/*
 132 *  return the first matching entry
 133 */
 134struct ndbtuple*
 135ndbsearch(struct ndb *db, struct ndbs *s, char *attr, char *val)
 136{
 137        uint8_t *p;
 138        struct ndbtuple *t;
 139        struct ndbhf *hf;
 140        hf = hfopen(db, attr);
 141
 142        memset(s, 0, sizeof(*s));
 143        if(_ndbcachesearch(db, s, attr, val, &t) == 0){
 144                /* found in cache */
 145                if(t != NULL){
 146                        ndbsetmalloctag(t, getcallerpc(&db));
 147                        return t;       /* answer from this file */
 148                }
 149                if(db->next == NULL)
 150                        return NULL;
 151                t = ndbsearch(db->next, s, attr, val);
 152                ndbsetmalloctag(t, getcallerpc(&db));
 153                return t;
 154        }
 155
 156        s->db = db;
 157        s->hf = hf;
 158        if(s->hf){
 159                s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
 160                p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
 161                if(p == 0){
 162                        t = _ndbcacheadd(db, s, attr, val, NULL);
 163                        ndbsetmalloctag(t, getcallerpc(&db));
 164                        return t;
 165                }
 166                s->ptr = NDBGETP(p);
 167                s->type = Cptr1;
 168        } else if(db->length > 128*1024){
 169                printf("Missing or out of date hash file %s.%s.\n", db->file, attr);
 170                //syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr);
 171
 172                /* advance search to next db file */
 173                s->ptr = NDBNAP;
 174                _ndbcacheadd(db, s, attr, val, NULL);
 175                if(db->next == 0)
 176                        return NULL;
 177                t = ndbsearch(db->next, s, attr, val);
 178                ndbsetmalloctag(t, getcallerpc(&db));
 179                return t;
 180        } else {
 181                s->ptr = 0;
 182                s->type = Dptr;
 183        }
 184        t = ndbsnext(s, attr, val);
 185        _ndbcacheadd(db, s, attr, val, (t != NULL && s->db == db)?t:NULL);
 186        ndbsetmalloctag(t, getcallerpc(&db));
 187        return t;
 188}
 189
 190static struct ndbtuple*
 191match(struct ndbtuple *t, char *attr, char *val)
 192{
 193        struct ndbtuple *nt;
 194
 195        for(nt = t; nt; nt = nt->entry)
 196                if(strcmp(attr, nt->attr) == 0
 197                && strcmp(val, nt->val) == 0)
 198                        return nt;
 199        return 0;
 200}
 201
 202/*
 203 *  return the next matching entry in the hash chain
 204 */
 205struct ndbtuple*
 206ndbsnext(struct ndbs *s, char *attr, char *val)
 207{
 208        struct ndbtuple *t;
 209        struct ndb *db;
 210        uint8_t *p;
 211
 212        db = s->db;
 213        if(s->ptr == NDBNAP)
 214                goto nextfile;
 215
 216        for(;;){
 217                if(s->type == Dptr){
 218                        if(fseek(db->b, s->ptr, 0) < 0)
 219                                break;
 220                        t = ndbparse(db);
 221                        s->ptr = ftell(db->b);
 222                        if(t == 0)
 223                                break;
 224                        if(s->t = match(t, attr, val)){
 225                                ndbsetmalloctag(t, getcallerpc(&s));
 226                                return t;
 227                        }
 228                        ndbfree(t);
 229                } else if(s->type == Cptr){
 230                        if(fseek(db->b, s->ptr, 0) < 0)
 231                                break; 
 232                        s->ptr = s->ptr1;
 233                        s->type = Cptr1;
 234                        t = ndbparse(db);
 235                        if(t == 0)
 236                                break;
 237                        if(s->t = match(t, attr, val)){
 238                                ndbsetmalloctag(t, getcallerpc(&s));
 239                                return t;
 240                        }
 241                        ndbfree(t);
 242                } else if(s->type == Cptr1){
 243                        if(s->ptr & NDBCHAIN){  /* hash chain continuation */
 244                                s->ptr &= ~NDBCHAIN;
 245                                p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
 246                                if(p == 0)
 247                                        break;
 248                                s->ptr = NDBGETP(p);
 249                                s->ptr1 = NDBGETP(p+NDBPLEN);
 250                                s->type = Cptr;
 251                        } else {                /* end of hash chain */
 252                                if(fseek(db->b, s->ptr, 0) < 0)
 253                                        break; 
 254                                s->ptr = NDBNAP;
 255                                t = ndbparse(db);
 256                                if(t == 0)
 257                                        break;
 258                                if(s->t = match(t, attr, val)){
 259                                        ndbsetmalloctag(t, getcallerpc(&s));
 260                                        return t;
 261                                }
 262                                ndbfree(t);
 263                                break;
 264                        }
 265                }
 266        }
 267
 268nextfile:
 269
 270        /* nothing left to search? */
 271        s->ptr = NDBNAP;
 272        if(db->next == 0)
 273                return 0;
 274
 275        /* advance search to next db file */
 276        t = ndbsearch(db->next, s, attr, val);
 277        ndbsetmalloctag(t, getcallerpc(&s));
 278        return t;
 279}
 280