/*
* Sherlock Library -- Fast Database Management Routines
*
- * (c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
+ * (c) 1999--2001 Martin Mares <mj@ucw.cz>
*/
/*
* o The only pages which can be freed are those of the directory (during
* directory split), so we keep only a simple 32-entry free block list
* and we assume it's sorted.
+ * o All pointers are always given in pages from start of the file.
+ * This gives us page_size*2^32 limit for file size which should be enough.
*/
+#include "lib/lib.h"
+#include "lib/lfs.h"
+#include "lib/pagecache.h"
+#include "lib/db.h"
+#include "lib/db_internal.h"
+
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
-#include "lib.h"
-#include "pagecache.h"
-#include "db.h"
-#include "db_internal.h"
+#define GET_PAGE(d,x) pgc_get((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order)
+#define GET_ZERO_PAGE(d,x) pgc_get_zero((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order)
+#define READ_PAGE(d,x) pgc_read((d)->cache, (d)->fd, ((sh_off_t)(x)) << (d)->page_order)
+#define READ_DIR(d,off) pgc_read((d)->cache, (d)->fd, (((sh_off_t)(d)->root->dir_start) << (d)->page_order) + (off))
struct sdbm *
sdbm_open(struct sdbm_options *o)
struct sdbm_root root, *r;
uns cache_size = o->cache_size ? o->cache_size : 16;
- d = xmalloc(sizeof(struct sdbm));
- bzero(d, sizeof(*d));
+ d = xmalloc_zero(sizeof(struct sdbm));
d->flags = o->flags;
- d->fd = open(o->name, ((d->flags & SDBM_WRITE) ? O_RDWR : O_RDONLY), 0666);
+ d->fd = sh_open(o->name, ((d->flags & SDBM_WRITE) ? O_RDWR : O_RDONLY), 0666);
if (d->fd >= 0) /* Already exists, let's check it */
{
if (read(d->fd, &root, sizeof(root)) != sizeof(root))
goto bad;
if (root.magic != SDBM_MAGIC || root.version != SDBM_VERSION)
goto bad;
- d->file_size = lseek(d->fd, 0, SEEK_END);
+ d->file_size = sh_seek(d->fd, 0, SEEK_END) >> root.page_order;
+ d->page_order = root.page_order;
d->page_size = 1 << root.page_order;
d->cache = pgc_open(d->page_size, cache_size);
d->root_page = pgc_read(d->cache, d->fd, 0);
d->root = (void *) d->root_page->data;
}
- else if ((d->flags & SDBM_CREAT) && (d->fd = open(o->name, O_RDWR | O_CREAT, 0666)) >= 0)
+ else if ((d->flags & SDBM_CREAT) && (d->fd = sh_open(o->name, O_RDWR | O_CREAT, 0666)) >= 0)
{
struct page *q;
uns page_order = o->page_order;
page_order = 10;
d->page_size = 1 << page_order;
d->cache = pgc_open(d->page_size, cache_size);
- d->root_page = pgc_get_zero(d->cache, d->fd, 0);
+ d->root_page = GET_ZERO_PAGE(d, 0);
r = d->root = (void *) d->root_page->data; /* Build root page */
r->magic = SDBM_MAGIC;
r->version = SDBM_VERSION;
- r->page_order = page_order;
+ r->page_order = d->page_order = page_order;
r->key_size = o->key_size;
r->val_size = o->val_size;
- r->dir_start = d->page_size;
+ r->dir_start = 1;
r->dir_order = 0;
- d->file_size = 3*d->page_size;
- q = pgc_get_zero(d->cache, d->fd, d->page_size); /* Build page directory */
- ((u32 *)q->data)[0] = 2*d->page_size;
+ d->file_size = 3;
+ q = GET_ZERO_PAGE(d, 1); /* Build page directory */
+ GET32(q->data, 0) = 2;
pgc_put(d->cache, q);
- q = pgc_get_zero(d->cache, d->fd, 2*d->page_size); /* Build single data page */
+ q = GET_ZERO_PAGE(d, 2); /* Build single data page */
pgc_put(d->cache, q);
}
else
goto bad;
d->dir_size = 1 << d->root->dir_order;
d->dir_shift = 32 - d->root->dir_order;
- d->page_order = d->root->page_order;
d->page_mask = d->page_size - 1;
d->key_size = d->root->key_size;
d->val_size = d->root->val_size;
pgc_close(d->cache);
if (d->fd >= 0)
close(d->fd);
- free(d);
+ xfree(d);
}
static uns
sdbm_alloc_pages(struct sdbm *d, uns number)
{
uns where = d->file_size;
- d->file_size += number << d->page_order;
+ if (where + number < where) /* Wrap around? */
+ die("SDB: Database file too large, giving up");
+ d->file_size += number;
return where;
}
if (!d->root->free_pool[0].count)
return sdbm_alloc_pages(d, 1);
pos = d->root->free_pool[0].first;
- d->root->free_pool[0].first += d->page_size;
+ d->root->free_pool[0].first++;
if (!--d->root->free_pool[0].count)
{
- memmove(d->root->free_pool, d->root->free_pool+1, SDBM_NUM_FREE_PAGE_POOLS * sizeof(d->root->free_pool[0]));
+ memmove(d->root->free_pool, d->root->free_pool+1, (SDBM_NUM_FREE_PAGE_POOLS-1) * sizeof(d->root->free_pool[0]));
d->root->free_pool[SDBM_NUM_FREE_PAGE_POOLS-1].count = 0;
}
pgc_mark_dirty(d->cache, d->root_page);
while (d->root->free_pool[i].count)
i++;
+ ASSERT(i < SDBM_NUM_FREE_PAGE_POOLS);
d->root->free_pool[i].first = start;
d->root->free_pool[i].count = number;
pgc_mark_dirty(d->cache, d->root_page);
}
-static u32
+u32
sdbm_hash(byte *key, uns keylen)
{
/*
- * This is the same hash function as GDBM uses.
- * It seems to work well.
+ * This used to be the same hash function as GDBM uses,
+ * but it turned out that it tends to give the same results
+ * on similar keys. Damn it.
*/
- u32 value;
- uns index;
-
- /* Set the initial value from key. */
- value = 0x238F13AF * keylen;
- for (index = 0; index < keylen; index++)
- value = value + (key[index] << (index*5 % 24));
+ u32 value = 0x238F13AF * keylen;
+ while (keylen--)
+ value = 37*value + *key++;
return (1103515243 * value + 12345);
}
uns l, r;
uns pm = d->page_mask;
- b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~pm));
+ b = READ_DIR(d, dirpos & ~pm);
pg = GET32(b->data, dirpos & pm);
l = dirpos;
while ((l & pm) && GET32(b->data, (l - 4) & pm) == pg)
/* Note that if it spans page boundary, it must contain an integer number of pages */
while (l)
{
- b = pgc_read(d->cache, d->fd, d->root->dir_start + ((l - 4) & ~pm));
+ b = READ_DIR(d, (l - 4) & ~pm);
x = GET32(b->data, 0);
pgc_put(d->cache, b);
if (x != pg)
}
while (r < 4*d->dir_size)
{
- b = pgc_read(d->cache, d->fd, d->root->dir_start + (r & ~pm));
+ b = READ_DIR(d, r & ~pm);
x = GET32(b->data, 0);
pgc_put(d->cache, b);
if (x != pg)
int i, ent;
u32 *dir, *t;
+ if (d->root->dir_order >= 31)
+ die("SDB: Database directory too large, giving up");
+
if (4*d->dir_size < d->page_size)
{
/* It still fits within single page */
- b = pgc_read(d->cache, d->fd, d->root->dir_start);
+ b = READ_DIR(d, 0);
dir = (u32 *) b->data;
for(i=d->dir_size-1; i>=0; i--)
dir[2*i] = dir[2*i+1] = dir[i];
ent = 1 << (d->page_order - 3);
for(page=0; page < old_dir_pages; page++)
{
- b = pgc_read(d->cache, d->fd, old_dir + (page << d->page_order));
+ b = READ_PAGE(d, old_dir + page);
dir = (u32 *) b->data;
- c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1)));
+ c = GET_PAGE(d, new_dir + 2*page);
t = (u32 *) c->data;
for(i=0; i<ent; i++)
t[2*i] = t[2*i+1] = dir[i];
pgc_put(d->cache, c);
- c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1)) + d->page_size);
+ c = GET_PAGE(d, new_dir + 2*page + 1);
t = (u32 *) c->data;
for(i=0; i<ent; i++)
t[2*i] = t[2*i+1] = dir[ent+i];
*/
for(page=0; page < old_dir_pages; page++)
{
- b = pgc_get_zero(d->cache, d->fd, old_dir + (page << d->page_order));
+ b = GET_ZERO_PAGE(d, old_dir + page);
pgc_put(d->cache, b);
}
}
count *= 4;
while (count)
{
- b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~d->page_mask));
+ b = READ_DIR(d, dirpos & ~d->page_mask);
i = d->page_size - (dirpos & d->page_mask);
if (i > count)
i = count;
}
}
+static inline uns
+sdbm_dirpos(struct sdbm *d, uns hash)
+{
+ if (d->dir_shift != 32) /* avoid shifting by 32 bits */
+ return (hash >> d->dir_shift) << 2; /* offset in the directory */
+ else
+ return 0;
+}
+
static struct page *
-sdbm_split_page(struct sdbm *d, struct page *b, u32 hash, uns dirpos)
+sdbm_split_page(struct sdbm *d, struct page *b, u32 hash)
{
struct page *p[2];
- uns i, rank, sigbit, rank_log;
+ uns i, rank, sigbit, rank_log, dirpos, newpg;
+ dirpos = sdbm_dirpos(d, hash);
rank = sdbm_page_rank(d, dirpos); /* rank = # of pointers to this page */
if (rank == 1)
{
rank_log++;
sigbit = d->dir_shift + rank_log - 1; /* sigbit = bit we split on */
p[0] = b;
- p[1] = pgc_get(d->cache, d->fd, sdbm_alloc_page(d));
+ newpg = sdbm_alloc_page(d);
+ p[1] = GET_PAGE(d, newpg);
sdbm_split_data(d, (void *) b->data, (void *) p[0]->data, (void *) p[1]->data, sigbit);
- sdbm_split_dir(d, (dirpos & ~(4*rank - 1))+2*rank, rank/2, pgc_page_pos(d->cache, p[1]));
+ sdbm_split_dir(d, (dirpos & ~(4*rank - 1))+2*rank, rank/2, newpg);
pgc_mark_dirty(d->cache, p[0]);
i = (hash & (1 << sigbit)) ? 1 : 0;
pgc_put(d->cache, p[!i]);
if ((d->key_size >= 0 && keylen != (uns) d->key_size) || keylen > 65535)
return SDBM_ERROR_BAD_KEY_SIZE;
- if (val && ((d->val_size >= 0 && *vallen != (uns) d->val_size) || *vallen >= 65535))
+ if (val && ((d->val_size >= 0 && *vallen != (uns) d->val_size) || *vallen >= 65535) && mode)
return SDBM_ERROR_BAD_VAL_SIZE;
if (!mode && !(d->flags & SDBM_WRITE))
return SDBM_ERROR_READ_ONLY;
hash = sdbm_hash(key, keylen);
- if (d->dir_shift != 32) /* avoid shifting by 32 bits */
- h = (hash >> d->dir_shift) << 2; /* offset in the directory */
- else
- h = 0;
- p = pgc_read(d->cache, d->fd, d->root->dir_start + (h & ~d->page_mask));
+ h = sdbm_dirpos(d, hash);
+ p = READ_DIR(d, h & ~d->page_mask);
pos = GET32(p->data, h & d->page_mask);
pgc_put(d->cache, p);
- q = pgc_read(d->cache, d->fd, pos);
+ q = READ_PAGE(d, pos);
b = (void *) q->data;
c = b->data;
e = c + b->used;
case 0: /* fetch: found */
rc = sdbm_put_user(D, Dl, val, vallen);
pgc_put(d->cache, q);
- return rc ? 1 : SDBM_ERROR_TOO_LARGE;
+ return rc ? SDBM_ERROR_TOO_LARGE : 1;
case 1: /* store: already present */
pgc_put(d->cache, q);
return 0;
while (b->used + size > d->page_size - sizeof(struct sdbm_bucket))
{
/* Page overflow, need to split */
- q = sdbm_split_page(d, q, hash, h);
+ if (size >= d->page_size - sizeof(struct sdbm_bucket))
+ {
+ pgc_put(d->cache, q);
+ return SDBM_ERROR_GIANT;
+ }
+ q = sdbm_split_page(d, q, hash);
b = (void *) q->data;
}
sdbm_store_entry(d, b->data + b->used, key, keylen, val, *vallen);
void
sdbm_rewind(struct sdbm *d)
{
- d->find_pos = d->page_size;
+ d->find_page = 1;
+ d->find_pos = 0;
d->find_free_list = 0;
}
int
sdbm_get_next(struct sdbm *d, byte *key, uns *keylen, byte *val, uns *vallen)
{
+ uns page = d->find_page;
uns pos = d->find_pos;
byte *K, *V;
uns c, Kl, Vl;
for(;;)
{
- c = pos & d->page_mask;
- if (!c)
+ if (!pos)
{
- if (pos >= d->file_size)
+ if (page >= d->file_size)
break;
- if (pos == d->root->dir_start)
- pos += (4*d->dir_size + d->page_size - 1) & ~d->page_mask;
- else if (pos == d->root->free_pool[d->find_free_list].first)
- pos += d->root->free_pool[d->find_free_list++].count << d->page_order;
+ if (page == d->root->dir_start)
+ page += (4*d->dir_size + d->page_size - 1) >> d->page_order;
+ else if (page == d->root->free_pool[d->find_free_list].first)
+ page += d->root->free_pool[d->find_free_list++].count;
else
- pos += 4;
+ pos = 4;
continue;
}
- p = pgc_read(d->cache, d->fd, pos & ~d->page_mask);
+ p = READ_PAGE(d, page);
b = (void *) p->data;
- if (c - 4 >= b->used)
+ if (pos - 4 >= b->used)
{
- pos = (pos & ~d->page_mask) + d->page_size;
+ pos = 0;
+ page++;
pgc_put(d->cache, p);
continue;
}
- c = sdbm_get_entry(d, p->data + c, &K, &Kl, &V, &Vl);
+ c = sdbm_get_entry(d, p->data + pos, &K, &Kl, &V, &Vl);
+ d->find_page = page;
d->find_pos = pos + c;
c = sdbm_put_user(K, Kl, key, keylen) ||
sdbm_put_user(V, Vl, val, vallen);
pgc_put(d->cache, p);
return c ? SDBM_ERROR_TOO_LARGE : 1;
}
+ d->find_page = page;
d->find_pos = pos;
return 0;
}
projects / libucw.git / blobdiff