2 * Sherlock Library -- Fast Database Management Routines
4 * (c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
8 * This library uses the standard algorithm for external hashing (page directory
9 * mapping topmost K bits of hash value to page address, directory splits and
10 * so on). Peculiarities of this implementation (aka design decisions):
12 * o We allow both fixed and variable length keys and values (this includes
13 * zero size values for cases you want to represent only a set of keys).
14 * o We assume that key_size + val_size < page_size.
15 * o We never shrink the directory nor free empty pages. (The reason is that
16 * if the database was once large, it's likely it will again become large soon.)
17 * o The only pages which can be freed are those of the directory (during
18 * directory split), so we keep only a simple 32-entry free block list
19 * and we assume it's sorted.
29 #include "pagecache.h"
31 #include "db_internal.h"
34 sdbm_open(struct sdbm_options *o)
37 struct sdbm_root root, *r;
38 uns cache_size = o->cache_size ? o->cache_size : 16;
40 d = xmalloc(sizeof(struct sdbm));
43 d->fd = open(o->name, ((d->flags & SDBM_WRITE) ? O_RDWR : O_RDONLY), 0666);
44 if (d->fd >= 0) /* Already exists, let's check it */
46 if (read(d->fd, &root, sizeof(root)) != sizeof(root))
48 if (root.magic != SDBM_MAGIC || root.version != SDBM_VERSION)
50 d->file_size = lseek(d->fd, 0, SEEK_END);
51 d->page_size = 1 << root.page_order;
52 d->cache = pgc_open(d->page_size, cache_size);
53 d->root_page = pgc_read(d->cache, d->fd, 0);
54 d->root = (void *) d->root_page->data;
56 else if ((d->flags & SDBM_CREAT) && (d->fd = open(o->name, O_RDWR | O_CREAT, 0666)) >= 0)
59 uns page_order = o->page_order;
62 d->page_size = 1 << page_order;
63 d->cache = pgc_open(d->page_size, cache_size);
64 d->root_page = pgc_get_zero(d->cache, d->fd, 0);
65 r = d->root = (void *) d->root_page->data; /* Build root page */
66 r->magic = SDBM_MAGIC;
67 r->version = SDBM_VERSION;
68 r->page_order = page_order;
69 r->key_size = o->key_size;
70 r->val_size = o->val_size;
71 r->dir_start = d->page_size;
73 d->file_size = 3*d->page_size;
74 q = pgc_get_zero(d->cache, d->fd, d->page_size); /* Build page directory */
75 ((u32 *)q->data)[0] = 2*d->page_size;
77 q = pgc_get_zero(d->cache, d->fd, 2*d->page_size); /* Build single data page */
82 d->dir_size = 1 << d->root->dir_order;
83 d->dir_shift = 32 - d->root->dir_order;
84 d->page_order = d->root->page_order;
85 d->page_mask = d->page_size - 1;
86 d->key_size = d->root->key_size;
87 d->val_size = d->root->val_size;
96 sdbm_close(struct sdbm *d)
99 pgc_put(d->cache, d->root_page);
108 sdbm_alloc_pages(struct sdbm *d, uns number)
110 uns where = d->file_size;
111 d->file_size += number << d->page_order;
116 sdbm_alloc_page(struct sdbm *d)
120 if (!d->root->free_pool[0].count)
121 return sdbm_alloc_pages(d, 1);
122 pos = d->root->free_pool[0].first;
123 d->root->free_pool[0].first += d->page_size;
124 if (!--d->root->free_pool[0].count)
126 memmove(d->root->free_pool, d->root->free_pool+1, SDBM_NUM_FREE_PAGE_POOLS * sizeof(d->root->free_pool[0]));
127 d->root->free_pool[SDBM_NUM_FREE_PAGE_POOLS-1].count = 0;
129 pgc_mark_dirty(d->cache, d->root_page);
134 sdbm_free_pages(struct sdbm *d, uns start, uns number)
138 while (d->root->free_pool[i].count)
140 d->root->free_pool[i].first = start;
141 d->root->free_pool[i].count = number;
142 pgc_mark_dirty(d->cache, d->root_page);
146 sdbm_hash(byte *key, uns keylen)
149 * This used to be the same hash function as GDBM uses,
150 * but it turned out that it tends to give the same results
151 * on similar keys. Damn it.
153 u32 value = 0x238F13AF * keylen;
155 value = 37*value + *key++;
156 return (1103515243 * value + 12345);
160 sdbm_get_entry(struct sdbm *d, byte *pos, byte **key, uns *keylen, byte **val, uns *vallen)
164 if (d->key_size >= 0)
165 *keylen = d->key_size;
168 *keylen = (p[0] << 8) | p[1];
173 if (d->val_size >= 0)
174 *vallen = d->val_size;
177 *vallen = (p[0] << 8) | p[1];
186 sdbm_entry_len(struct sdbm *d, uns keylen, uns vallen)
188 uns len = keylen + vallen;
197 sdbm_store_entry(struct sdbm *d, byte *pos, byte *key, uns keylen, byte *val, uns vallen)
201 *pos++ = keylen >> 8;
204 memmove(pos, key, keylen);
208 *pos++ = vallen >> 8;
211 memmove(pos, val, vallen);
215 sdbm_page_rank(struct sdbm *d, uns dirpos)
220 uns pm = d->page_mask;
222 b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~pm));
223 pg = GET32(b->data, dirpos & pm);
225 while ((l & pm) && GET32(b->data, (l - 4) & pm) == pg)
228 /* We heavily depend on unused directory entries being zero */
229 while ((r & pm) && GET32(b->data, r & pm) == pg)
231 pgc_put(d->cache, b);
233 if (!(l & pm) && !(r & pm))
235 /* Note that if it spans page boundary, it must contain an integer number of pages */
238 b = pgc_read(d->cache, d->fd, d->root->dir_start + ((l - 4) & ~pm));
239 x = GET32(b->data, 0);
240 pgc_put(d->cache, b);
245 while (r < 4*d->dir_size)
247 b = pgc_read(d->cache, d->fd, d->root->dir_start + (r & ~pm));
248 x = GET32(b->data, 0);
249 pgc_put(d->cache, b);
259 sdbm_expand_directory(struct sdbm *d)
265 if (4*d->dir_size < d->page_size)
267 /* It still fits within single page */
268 b = pgc_read(d->cache, d->fd, d->root->dir_start);
269 dir = (u32 *) b->data;
270 for(i=d->dir_size-1; i>=0; i--)
271 dir[2*i] = dir[2*i+1] = dir[i];
272 pgc_mark_dirty(d->cache, b);
273 pgc_put(d->cache, b);
277 uns old_dir = d->root->dir_start;
278 uns old_dir_pages = 1 << (d->root->dir_order + 2 - d->page_order);
280 new_dir = d->root->dir_start = sdbm_alloc_pages(d, 2*old_dir_pages);
281 ent = 1 << (d->page_order - 3);
282 for(page=0; page < old_dir_pages; page++)
284 b = pgc_read(d->cache, d->fd, old_dir + (page << d->page_order));
285 dir = (u32 *) b->data;
286 c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1)));
289 t[2*i] = t[2*i+1] = dir[i];
290 pgc_put(d->cache, c);
291 c = pgc_get(d->cache, d->fd, new_dir + (page << (d->page_order + 1)) + d->page_size);
294 t[2*i] = t[2*i+1] = dir[ent+i];
295 pgc_put(d->cache, c);
296 pgc_put(d->cache, b);
298 if (!(d->flags & SDBM_FAST))
301 * Unless in super-fast mode, fill old directory pages with zeroes.
302 * This slows us down a bit, but allows database reconstruction after
303 * the free list is lost.
305 for(page=0; page < old_dir_pages; page++)
307 b = pgc_get_zero(d->cache, d->fd, old_dir + (page << d->page_order));
308 pgc_put(d->cache, b);
311 sdbm_free_pages(d, old_dir, old_dir_pages);
314 d->root->dir_order++;
315 d->dir_size = 1 << d->root->dir_order;
316 d->dir_shift = 32 - d->root->dir_order;
317 pgc_mark_dirty(d->cache, d->root_page);
318 if (!(d->flags & SDBM_FAST))
323 sdbm_split_data(struct sdbm *d, struct sdbm_bucket *s, struct sdbm_bucket *d0, struct sdbm_bucket *d1, uns sigbit)
326 byte *dp[2] = { d0->data, d1->data };
330 while (sp < s->data + s->used)
332 sz = sdbm_get_entry(d, sp, &K, &Kl, &D, &Dl);
334 i = (sdbm_hash(K, Kl) & (1 << sigbit)) ? 1 : 0;
335 sdbm_store_entry(d, dp[i], K, Kl, D, Dl);
338 d0->used = dp[0] - d0->data;
339 d1->used = dp[1] - d1->data;
343 sdbm_split_dir(struct sdbm *d, uns dirpos, uns count, uns pos)
351 b = pgc_read(d->cache, d->fd, d->root->dir_start + (dirpos & ~d->page_mask));
352 i = d->page_size - (dirpos & d->page_mask);
358 GET32(b->data, dirpos & d->page_mask) = pos;
362 pgc_mark_dirty(d->cache, b);
363 pgc_put(d->cache, b);
368 sdbm_split_page(struct sdbm *d, struct page *b, u32 hash, uns dirpos)
371 uns i, rank, sigbit, rank_log;
373 rank = sdbm_page_rank(d, dirpos); /* rank = # of pointers to this page */
376 sdbm_expand_directory(d);
380 rank_log = 1; /* rank_log = log2(rank) */
381 while ((1U << rank_log) < rank)
383 sigbit = d->dir_shift + rank_log - 1; /* sigbit = bit we split on */
385 p[1] = pgc_get(d->cache, d->fd, sdbm_alloc_page(d));
386 sdbm_split_data(d, (void *) b->data, (void *) p[0]->data, (void *) p[1]->data, sigbit);
387 sdbm_split_dir(d, (dirpos & ~(4*rank - 1))+2*rank, rank/2, p[1]->pos);
388 pgc_mark_dirty(d->cache, p[0]);
389 i = (hash & (1 << sigbit)) ? 1 : 0;
390 pgc_put(d->cache, p[!i]);
395 sdbm_put_user(byte *D, uns Dl, byte *val, uns *vallen)
409 sdbm_access(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen, uns mode) /* 0=read, 1=store, 2=replace */
412 u32 hash, h, pos, size;
413 struct sdbm_bucket *b;
417 if ((d->key_size >= 0 && keylen != (uns) d->key_size) || keylen > 65535)
418 return SDBM_ERROR_BAD_KEY_SIZE;
419 if (val && ((d->val_size >= 0 && *vallen != (uns) d->val_size) || *vallen >= 65535) && mode)
420 return SDBM_ERROR_BAD_VAL_SIZE;
421 if (!mode && !(d->flags & SDBM_WRITE))
422 return SDBM_ERROR_READ_ONLY;
423 hash = sdbm_hash(key, keylen);
424 if (d->dir_shift != 32) /* avoid shifting by 32 bits */
425 h = (hash >> d->dir_shift) << 2; /* offset in the directory */
428 p = pgc_read(d->cache, d->fd, d->root->dir_start + (h & ~d->page_mask));
429 pos = GET32(p->data, h & d->page_mask);
430 pgc_put(d->cache, p);
431 q = pgc_read(d->cache, d->fd, pos);
432 b = (void *) q->data;
439 s = sdbm_get_entry(d, c, &K, &Kl, &D, &Dl);
440 if (Kl == keylen && !memcmp(K, key, Kl))
445 case 0: /* fetch: found */
446 rc = sdbm_put_user(D, Dl, val, vallen);
447 pgc_put(d->cache, q);
448 return rc ? SDBM_ERROR_TOO_LARGE : 1;
449 case 1: /* store: already present */
450 pgc_put(d->cache, q);
452 default: /* replace: delete the old one */
453 memmove(c, c+s, e-(c+s));
460 if (!mode || !val) /* fetch or delete: no success */
462 pgc_put(d->cache, q);
469 size = sdbm_entry_len(d, keylen, *vallen);
470 while (b->used + size > d->page_size - sizeof(struct sdbm_bucket))
472 /* Page overflow, need to split */
473 if (size >= d->page_size - sizeof(struct sdbm_bucket))
475 pgc_put(d->cache, q);
476 return SDBM_ERROR_GIANT;
478 q = sdbm_split_page(d, q, hash, h);
479 b = (void *) q->data;
481 sdbm_store_entry(d, b->data + b->used, key, keylen, val, *vallen);
484 pgc_mark_dirty(d->cache, q);
485 pgc_put(d->cache, q);
486 if (d->flags & SDBM_SYNC)
492 sdbm_store(struct sdbm *d, byte *key, uns keylen, byte *val, uns vallen)
494 return sdbm_access(d, key, keylen, val, &vallen, 1);
498 sdbm_replace(struct sdbm *d, byte *key, uns keylen, byte *val, uns vallen)
500 return sdbm_access(d, key, keylen, val, &vallen, 2);
504 sdbm_delete(struct sdbm *d, byte *key, uns keylen)
506 return sdbm_access(d, key, keylen, NULL, NULL, 2);
510 sdbm_fetch(struct sdbm *d, byte *key, uns keylen, byte *val, uns *vallen)
512 return sdbm_access(d, key, keylen, val, vallen, 0);
516 sdbm_rewind(struct sdbm *d)
518 d->find_pos = d->page_size;
519 d->find_free_list = 0;
523 sdbm_get_next(struct sdbm *d, byte *key, uns *keylen, byte *val, uns *vallen)
525 uns pos = d->find_pos;
529 struct sdbm_bucket *b;
533 c = pos & d->page_mask;
536 if (pos >= d->file_size)
538 if (pos == d->root->dir_start)
539 pos += (4*d->dir_size + d->page_size - 1) & ~d->page_mask;
540 else if (pos == d->root->free_pool[d->find_free_list].first)
541 pos += d->root->free_pool[d->find_free_list++].count << d->page_order;
546 p = pgc_read(d->cache, d->fd, pos & ~d->page_mask);
547 b = (void *) p->data;
548 if (c - 4 >= b->used)
550 pos = (pos & ~d->page_mask) + d->page_size;
551 pgc_put(d->cache, p);
554 c = sdbm_get_entry(d, p->data + c, &K, &Kl, &V, &Vl);
555 d->find_pos = pos + c;
556 c = sdbm_put_user(K, Kl, key, keylen) ||
557 sdbm_put_user(V, Vl, val, vallen);
558 pgc_put(d->cache, p);
559 return c ? SDBM_ERROR_TOO_LARGE : 1;
566 sdbm_sync(struct sdbm *d)
569 if (d->flags & SDBM_FSYNC)