a1483d42d21a017466111d14820a051c7013ee03
[kai/samba.git] / source / tdb / tdb.c
1 /* 
2    Unix SMB/Netbios implementation.
3    Version 3.0
4    Samba database functions
5    Copyright (C) Andrew Tridgell              1999-2000
6    Copyright (C) Luke Kenneth Casson Leighton      2000
7    
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12    
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17    
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22
23 #if STANDALONE
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <fcntl.h>
27 #include <unistd.h>
28 #include <string.h>
29 #include <fcntl.h>
30 #include <errno.h>
31 #include <sys/mman.h>
32 #include <sys/stat.h>
33 #include "tdb.h"
34 #else
35 #include "includes.h"
36 #endif
37
38 #define TDB_VERSION (0x26011967 + 1)
39 #define TDB_MAGIC (0x26011999U)
40 #define TDB_FREE_MAGIC (~TDB_MAGIC)
41 #define TDB_ALIGN 4
42 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN)
43 #define DEFAULT_HASH_SIZE 128
44 #define TDB_PAGE_SIZE 0x2000
45 #define TDB_LEN_MULTIPLIER 10
46 #define FREELIST_TOP (sizeof(struct tdb_header))
47
48 #define LOCK_SET 1
49 #define LOCK_CLEAR 0
50
51 /* lock offsets */
52 #define GLOBAL_LOCK 0
53 #define ACTIVE_LOCK 4
54 #define LIST_LOCK_BASE 1024
55
56 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
57
58 #ifndef MAP_FILE
59 #define MAP_FILE 0
60 #endif
61
62 /* the body of the database is made of one list_struct for the free space
63    plus a separate data list for each hash value */
64 struct list_struct {
65         tdb_len rec_len; /* total byte length of record */
66         tdb_off next; /* offset of the next record in the list */
67         tdb_len key_len; /* byte length of key */
68         tdb_len data_len; /* byte length of data */
69         unsigned full_hash; /* the full 32 bit hash of the key */
70         unsigned magic;   /* try to catch errors */
71         /*
72            the following union is implied 
73            union {
74               char record[rec_len];
75               struct {
76                 char key[key_len];
77                 char data[data_len];
78               }
79            }
80         */
81 };
82
83 /* a null data record - useful for error returns */
84 static TDB_DATA null_data;
85
86 /* a byte range locking function - return 0 on success
87    this functions locks/unlocks 1 byte at the specified offset */
88 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset, 
89                       int set, int rw_type, int lck_type)
90 {
91 #if NOLOCK
92         return 0;
93 #else
94         struct flock fl;
95
96         if (tdb->fd == -1) return 0;   /* for in memory tdb */
97
98         if (tdb->read_only) return -1;
99
100         fl.l_type = set==LOCK_SET?rw_type:F_UNLCK;
101         fl.l_whence = SEEK_SET;
102         fl.l_start = offset;
103         fl.l_len = 1;
104         fl.l_pid = 0;
105
106         if (fcntl(tdb->fd, lck_type, &fl) != 0) {
107 #if TDB_DEBUG
108                 if (lck_type == F_SETLKW) {
109                         printf("lock %d failed at %d (%s)\n", 
110                                set, offset, strerror(errno));
111                 }
112 #endif
113                 tdb->ecode = TDB_ERR_LOCK;
114                 return -1;
115         }
116         return 0;
117 #endif
118 }
119
120 /* lock a list in the database. list -1 is the alloc list */
121 static int tdb_lock(TDB_CONTEXT *tdb, int list)
122 {
123         if (list < -1 || list >= (int)tdb->header.hash_size) {
124 #if TDB_DEBUG
125                 printf("bad list %d\n", list);
126 #endif
127                 return -1;
128         }
129         if (tdb->locked[list+1] == 0) {
130                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_SET, 
131                                F_WRLCK, F_SETLKW) != 0) {
132                         return -1;
133                 }
134         }
135         tdb->locked[list+1]++;
136         return 0;
137 }
138
139 /* unlock the database. */
140 static int tdb_unlock(TDB_CONTEXT *tdb, int list)
141 {
142         if (list < -1 || list >= (int)tdb->header.hash_size) {
143 #if TDB_DEBUG
144                 printf("bad unlock list %d\n", list);
145 #endif
146                 return -1;
147         }
148
149         if (tdb->locked[list+1] == 0) {
150 #if TDB_DEBUG
151                 printf("not locked %d\n", list);
152 #endif
153                 tdb->ecode = TDB_ERR_LOCK;
154                 return -1;
155         }
156         if (tdb->locked[list+1] == 1) {
157                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_CLEAR, 
158                                F_WRLCK, F_SETLKW) != 0) {
159                         return -1;
160                 }
161         }
162         tdb->locked[list+1]--;
163         return 0;
164 }
165
166 /* the hash algorithm - turn a key into an integer
167    This is based on the hash agorithm from gdbm */
168 static unsigned tdb_hash(TDB_DATA *key)
169 {
170         unsigned value; /* Used to compute the hash value.  */
171         unsigned   i;   /* Used to cycle through random values. */
172
173         /* Set the initial value from the key size. */
174         value = 0x238F13AF * key->dsize;
175         for (i=0; i < key->dsize; i++) {
176                 value = (value + (key->dptr[i] << (i*5 % 24)));
177         }
178
179         value = (1103515243 * value + 12345);  
180
181         return value;
182 }
183
184 /* find the top of the hash chain for an open database */
185 static tdb_off tdb_hash_top(TDB_CONTEXT *tdb, unsigned hash)
186 {
187         tdb_off ret;
188         hash = BUCKET(hash);
189         ret = FREELIST_TOP + (hash+1)*sizeof(tdb_off);
190         return ret;
191 }
192
193
194 /* check for an out of bounds access - if it is out of bounds then
195    see if the database has been expanded by someone else and expand
196    if necessary */
197 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off offset)
198 {
199         struct stat st;
200         if ((offset <= tdb->map_size) || (tdb->fd == -1)) return 0;
201
202         fstat(tdb->fd, &st);
203         if (st.st_size <= (size_t)offset) {
204                 tdb->ecode = TDB_ERR_IO;
205                 return -1;
206         }
207
208 #if HAVE_MMAP
209         if (tdb->map_ptr) {
210                 munmap(tdb->map_ptr, tdb->map_size);
211                 tdb->map_ptr = NULL;
212         }
213 #endif
214
215         tdb->map_size = st.st_size;
216 #if HAVE_MMAP
217         tdb->map_ptr = (void *)mmap(NULL, tdb->map_size, 
218                                     tdb->read_only?PROT_READ:PROT_READ|PROT_WRITE,
219                                     MAP_SHARED | MAP_FILE, tdb->fd, 0);
220 #endif  
221         return 0;
222 }
223
224
225 /* write a lump of data at a specified offset */
226 static int tdb_write(TDB_CONTEXT *tdb, tdb_off offset, const char *buf, tdb_len len)
227 {
228         if (tdb_oob(tdb, offset + len) != 0) {
229                 /* oops - trying to write beyond the end of the database! */
230                 return -1;
231         }
232
233         if (tdb->map_ptr) {
234                 memcpy(offset + (char *)tdb->map_ptr, buf, len);
235         } else {
236                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
237                     write(tdb->fd, buf, len) != (ssize_t)len) {
238                         tdb->ecode = TDB_ERR_IO;
239                         return -1;
240                 }
241         }
242         return 0;
243 }
244
245 /* read a lump of data at a specified offset */
246 static int tdb_read(TDB_CONTEXT *tdb, tdb_off offset, char *buf, tdb_len len)
247 {
248         if (tdb_oob(tdb, offset + len) != 0) {
249                 /* oops - trying to read beyond the end of the database! */
250                 return -1;
251         }
252
253         if (tdb->map_ptr) {
254                 memcpy(buf, offset + (char *)tdb->map_ptr, len);
255         } else {
256                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
257                     read(tdb->fd, buf, len) != (ssize_t)len) {
258                         tdb->ecode = TDB_ERR_IO;
259                         return -1;
260                 }
261         }
262         return 0;
263 }
264
265
266 /* read a lump of data, allocating the space for it */
267 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
268 {
269         char *buf;
270
271         buf = (char *)malloc(len);
272
273         if (!buf) {
274                 tdb->ecode = TDB_ERR_OOM;
275                 return NULL;
276         }
277
278         if (tdb_read(tdb, offset, buf, len) == -1) {
279                 free(buf);
280                 return NULL;
281         }
282         
283         return buf;
284 }
285
286 /* convenience routine for writing a record */
287 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
288 {
289         return tdb_write(tdb, offset, (char *)rec, sizeof(*rec));
290 }
291
292 /* convenience routine for writing a tdb_off */
293 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
294 {
295         return tdb_write(tdb, offset, (char *)d, sizeof(*d));
296 }
297
298 /* read a tdb_off from the store */
299 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
300 {
301         return tdb_read(tdb, offset, (char *)d, sizeof(*d));
302 }
303
304 /* read a record and check for simple errors */
305 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
306 {
307         if (tdb_read(tdb, offset, (char *)rec, sizeof(*rec)) == -1) return -1;
308         if (rec->magic != TDB_MAGIC) {
309 #if TDB_DEBUG
310                 printf("bad magic 0x%08x at offset %d\n",
311                        rec->magic, offset);
312 #endif
313                 tdb->ecode = TDB_ERR_CORRUPT;
314                 return -1;
315         }
316         if (tdb_oob(tdb, rec->next) != 0) {
317                 return -1;
318         }
319         return 0;
320 }
321
322 /* expand the database at least length bytes by expanding the
323    underlying file and doing the mmap again if necessary */
324 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off length)
325 {
326         struct list_struct rec;
327         tdb_off offset, ptr;
328         char b = 0;
329
330         tdb_lock(tdb,-1);
331
332         /* make sure we know about any previous expansions by another
333            process */
334         tdb_oob(tdb,tdb->map_size + 1);
335
336         /* always make room for at least 10 more records */
337         length *= TDB_LEN_MULTIPLIER;
338
339         /* and round the database up to a multiple of TDB_PAGE_SIZE */
340         length = ((tdb->map_size + length + TDB_PAGE_SIZE) & ~(TDB_PAGE_SIZE - 1)) - tdb->map_size;
341
342         /* expand the file itself */
343         if (tdb->fd != -1) {
344             lseek(tdb->fd, tdb->map_size + length - 1, SEEK_SET);
345             if (write(tdb->fd, &b, 1) != 1) goto fail;
346         }
347
348         /* form a new freelist record */
349         offset = FREELIST_TOP;
350         rec.rec_len = length - sizeof(rec);
351         rec.magic = TDB_FREE_MAGIC;
352         if (ofs_read(tdb, offset, &rec.next) == -1) {
353                 goto fail;
354         }
355
356 #if HAVE_MMAP
357         if (tdb->fd != -1 && tdb->map_ptr) {
358                 munmap(tdb->map_ptr, tdb->map_size);
359                 tdb->map_ptr = NULL;
360         }
361 #endif
362
363         tdb->map_size += length;
364
365         if (tdb->fd == -1) {
366             tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
367         }
368
369         /* write it out */
370         if (rec_write(tdb, tdb->map_size - length, &rec) == -1) {
371                 goto fail;
372         }
373
374         /* link it into the free list */
375         ptr = tdb->map_size - length;
376         if (ofs_write(tdb, offset, &ptr) == -1) goto fail;
377
378 #if HAVE_MMAP
379         if (tdb->fd != -1) {
380             tdb->map_ptr = (void *)mmap(NULL, tdb->map_size, 
381                                         PROT_READ|PROT_WRITE,
382                                         MAP_SHARED | MAP_FILE, tdb->fd, 0);
383         }
384 #endif
385
386         tdb_unlock(tdb, -1);
387         return 0;
388
389  fail:
390         tdb_unlock(tdb,-1);
391         return -1;
392 }
393
394 /* allocate some space from the free list. The offset returned points
395    to a unconnected list_struct within the database with room for at
396    least length bytes of total data
397
398    0 is returned if the space could not be allocated
399  */
400 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length)
401 {
402         tdb_off offset, rec_ptr, last_ptr;
403         struct list_struct rec, lastrec, newrec;
404
405         tdb_lock(tdb, -1);
406
407  again:
408         last_ptr = 0;
409         offset = FREELIST_TOP;
410
411         /* read in the freelist top */
412         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
413                 goto fail;
414         }
415
416         /* keep looking until we find a freelist record that is big
417            enough */
418         while (rec_ptr) {
419                 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
420                         goto fail;
421                 }
422
423                 if (rec.magic != TDB_FREE_MAGIC) {
424 #if TDB_DEBUG
425                         printf("bad magic 0x%08x in free list\n", rec.magic);
426 #endif
427                         goto fail;
428                 }
429
430                 if (rec.rec_len >= length) {
431                         /* found it - now possibly split it up  */
432                         if (rec.rec_len > length + MIN_REC_SIZE) {
433                                 length = (length + TDB_ALIGN) & ~(TDB_ALIGN-1);
434
435                                 newrec.rec_len = rec.rec_len - (sizeof(rec) + length);
436                                 newrec.next = rec.next;
437                                 newrec.magic = TDB_FREE_MAGIC;
438
439                                 rec.rec_len = length;
440                                 rec.next = rec_ptr + sizeof(rec) + rec.rec_len;
441                                 
442                                 if (rec_write(tdb, rec.next, &newrec) == -1) {
443                                         goto fail;
444                                 }
445
446                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
447                                         goto fail;
448                                 }
449                         }
450
451                         /* remove it from the list */
452                         if (last_ptr == 0) {
453                                 offset = FREELIST_TOP;
454
455                                 if (ofs_write(tdb, offset, &rec.next) == -1) {
456                                         goto fail;
457                                 }                               
458                         } else {
459                                 lastrec.next = rec.next;
460                                 if (rec_write(tdb, last_ptr, &lastrec) == -1) {
461                                         goto fail;
462                                 }
463                         }
464
465                         /* all done - return the new record offset */
466                         tdb_unlock(tdb, -1);
467                         return rec_ptr;
468                 }
469
470                 /* move to the next record */
471                 lastrec = rec;
472                 last_ptr = rec_ptr;
473                 rec_ptr = rec.next;
474         }
475
476         /* we didn't find enough space. See if we can expand the
477            database and if we can then try again */
478         if (tdb_expand(tdb, length + sizeof(rec)) == 0) goto again;
479
480  fail:
481 #if TDB_DEBUG
482         printf("tdb_allocate failed for size %u\n", length);
483 #endif
484         tdb_unlock(tdb, -1);
485         return 0;
486 }
487
488 /* initialise a new database with a specified hash size */
489 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
490 {
491         struct tdb_header header;
492         tdb_off offset;
493         int i, size = 0;
494         tdb_off buf[16];
495
496         /* create the header */
497         memset(&header, 0, sizeof(header));
498         memcpy(header.magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
499         header.version = TDB_VERSION;
500         header.hash_size = hash_size;
501         lseek(tdb->fd, 0, SEEK_SET);
502         if (tdb->fd != -1) ftruncate(tdb->fd, 0);
503         
504         if (tdb->fd != -1 && write(tdb->fd, &header, sizeof(header)) != 
505             sizeof(header)) {
506             tdb->ecode = TDB_ERR_IO;
507             return -1;
508         } else size += sizeof(header);
509         
510         /* the freelist and hash pointers */
511         offset = 0;
512         memset(buf, 0, sizeof(buf));
513
514         for (i=0;(hash_size+1)-i >= 16; i += 16) {
515             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(buf)) != 
516                 sizeof(buf)) {
517                 tdb->ecode = TDB_ERR_IO;
518                 return -1;
519             } else size += sizeof(buf);
520         }
521
522         for (;i<hash_size+1; i++) {
523             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(tdb_off)) != 
524                 sizeof(tdb_off)) {
525                 tdb->ecode = TDB_ERR_IO;
526                 return -1;
527             } else size += sizeof(tdb_off);
528         }
529
530         if (tdb->fd == -1) {
531             tdb->map_ptr = calloc(size, 1);
532             tdb->map_size = size;
533             if (tdb->map_ptr == NULL) {
534                 tdb->ecode = TDB_ERR_IO;
535                 return -1;
536             }
537             memcpy(&tdb->header, &header, sizeof(header));
538         }
539
540 #if TDB_DEBUG
541         printf("initialised database of hash_size %u\n", 
542                hash_size);
543 #endif
544         return 0;
545 }
546
547 /* Returns 0 on fail.  On success, return offset of record, and fills
548    in rec */
549 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, unsigned int hash,
550                         struct list_struct *rec)
551 {
552         tdb_off offset, rec_ptr;
553         
554         /* find the top of the hash chain */
555         offset = tdb_hash_top(tdb, hash);
556
557         /* read in the hash top */
558         if (ofs_read(tdb, offset, &rec_ptr) == -1)
559                 return 0;
560
561         /* keep looking until we find the right record */
562         while (rec_ptr) {
563                 if (rec_read(tdb, rec_ptr, rec) == -1)
564                         return 0;
565
566                 if (hash == rec->full_hash && key.dsize == rec->key_len) {
567                         char *k;
568                         /* a very likely hit - read the key */
569                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*rec), 
570                                            rec->key_len);
571
572                         if (!k)
573                                 return 0;
574
575                         if (memcmp(key.dptr, k, key.dsize) == 0) {
576                                 free(k);
577                                 return rec_ptr;
578                         }
579                         free(k);
580                 }
581
582                 /* move to the next record */
583                 rec_ptr = rec->next;
584         }
585         return 0;
586 }
587
588 /* 
589    return an error string for the last tdb error
590 */
591 char *tdb_error(TDB_CONTEXT *tdb)
592 {
593         int i;
594         static struct {
595                 enum TDB_ERROR ecode;
596                 char *estring;
597         } emap[] = {
598                 {TDB_SUCCESS, "Success"},
599                 {TDB_ERR_CORRUPT, "Corrupt database"},
600                 {TDB_ERR_IO, "IO Error"},
601                 {TDB_ERR_LOCK, "Locking error"},
602                 {TDB_ERR_OOM, "Out of memory"},
603                 {TDB_ERR_EXISTS, "Record exists"},
604                 {TDB_ERR_NOEXIST, "Record does not exist"},
605                 {-1, NULL}};
606         if (tdb != NULL) {
607             for (i=0;emap[i].estring;i++) {
608                 if (tdb->ecode == emap[i].ecode) return emap[i].estring;
609             }
610         } else {
611             return "Invalid tdb context";
612         }
613         return "Invalid error code";
614 }
615
616
617 /* update an entry in place - this only works if the new data size
618    is <= the old data size and the key exists.
619    on failure return -1
620 */
621 int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
622 {
623         unsigned hash;
624         struct list_struct rec;
625         tdb_off rec_ptr;
626         int ret = -1;
627
628         if (tdb == NULL) {
629 #ifdef TDB_DEBUG
630             printf("tdb_update() called with null context\n");
631 #endif
632             return -1;
633         }
634
635         /* initialise error code to ok, first */
636         tdb->ecode = 0;
637
638         /* find which hash bucket it is in */
639         hash = tdb_hash(&key);
640
641         tdb_lock(tdb, BUCKET(hash));
642         rec_ptr = tdb_find(tdb, key, hash, &rec);
643
644         if (!rec_ptr) {
645                 tdb->ecode = TDB_ERR_NOEXIST;
646                 goto out;
647         }
648
649         /* must be long enough */
650         if (rec.rec_len < key.dsize + dbuf.dsize)
651                 goto out;
652
653         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
654                       dbuf.dptr, dbuf.dsize) == -1)
655                 goto out;
656
657         if (dbuf.dsize != rec.data_len) {
658                 /* update size */
659                 rec.data_len = dbuf.dsize;
660                 ret = rec_write(tdb, rec_ptr, &rec);
661         } else
662                 ret = 0;
663
664  out:
665         tdb_unlock(tdb, BUCKET(hash));
666         return ret;
667 }
668
669 /* find an entry in the database given a key */
670 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
671 {
672         unsigned hash;
673         tdb_off rec_ptr;
674         struct list_struct rec;
675         TDB_DATA ret = null_data;
676
677         if (tdb == NULL) {
678 #ifdef TDB_DEBUG
679             printf("tdb_fetch() called with null context\n");
680 #endif
681             return null_data;
682         }
683
684         /* find which hash bucket it is in */
685         hash = tdb_hash(&key);
686
687         tdb_lock(tdb, BUCKET(hash));
688         rec_ptr = tdb_find(tdb, key, hash, &rec);
689
690         if (rec_ptr) {
691                 ret.dptr = tdb_alloc_read(tdb,
692                                           rec_ptr + sizeof(rec) + rec.key_len,
693                                           rec.data_len);
694                 ret.dsize = rec.data_len;
695         }
696         
697         tdb_unlock(tdb, BUCKET(hash));
698         return ret;
699 }
700
701 /* check if an entry in the database exists 
702
703    note that 1 is returned if the key is found and 0 is returned if not found
704    this doesn't match the conventions in the rest of this module, but is
705    compatible with gdbm
706 */
707 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
708 {
709         unsigned hash;
710         tdb_off rec_ptr;
711         struct list_struct rec;
712         
713         if (tdb == NULL) {
714 #ifdef TDB_DEBUG
715             printf("tdb_exists() called with null context\n");
716 #endif
717             return 0;
718         }
719
720         /* find which hash bucket it is in */
721         hash = tdb_hash(&key);
722
723         tdb_lock(tdb, BUCKET(hash));
724         rec_ptr = tdb_find(tdb, key, hash, &rec);
725         tdb_unlock(tdb, BUCKET(hash));
726
727         return rec_ptr != 0;
728 }
729
730 /* traverse the entire database - calling fn(tdb, key, data) on each element.
731    return -1 on error or the record count traversed
732    if fn is NULL then it is not called
733    a non-zero return value from fn() indicates that the traversal should stop
734   */
735 int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, void* state), void* state)
736 {
737         int count = 0;
738         unsigned h;
739         tdb_off offset, rec_ptr;
740         struct list_struct rec;
741         char *data;
742         TDB_DATA key, dbuf;
743
744         if (tdb == NULL) {
745 #ifdef TDB_DEBUG
746             printf("tdb_traverse() called with null context\n");
747 #endif
748             return -1;
749         }
750
751         /* loop over all hash chains */
752         for (h = 0; h < tdb->header.hash_size; h++) {
753                 tdb_lock(tdb, BUCKET(h));
754
755                 /* read in the hash top */
756                 offset = tdb_hash_top(tdb, h);
757                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
758                         goto fail;
759                 }
760
761                 /* traverse all records for this hash */
762                 while (rec_ptr) {
763                         if (rec_read(tdb, rec_ptr, &rec) == -1) {
764                                 goto fail;
765                         }
766
767                         /* now read the full record */
768                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), 
769                                              rec.key_len + rec.data_len);
770                         if (!data) {
771                                 goto fail;
772                         }
773
774                         key.dptr = data;
775                         key.dsize = rec.key_len;
776                         dbuf.dptr = data + rec.key_len;
777                         dbuf.dsize = rec.data_len;
778                         count++;
779
780                         if (fn && fn(tdb, key, dbuf, state) != 0) {
781                                 /* they want us to stop traversing */
782                                 free(data);
783                                 tdb_unlock(tdb, BUCKET(h));
784                                 return count;
785                         }
786
787                         /* a miss - drat */
788                         free(data);
789
790                         /* move to the next record */
791                         rec_ptr = rec.next;
792                 }
793                 tdb_unlock(tdb, BUCKET(h));
794         }
795
796         /* return the number traversed */
797         return count;
798
799  fail:
800         tdb_unlock(tdb, BUCKET(h));
801         return -1;
802 }
803
804
805 /* find the first entry in the database and return its key */
806 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
807 {
808         tdb_off offset, rec_ptr;
809         struct list_struct rec;
810         unsigned hash;
811         TDB_DATA ret;
812
813         if (tdb == NULL) {
814 #ifdef TDB_DEBUG
815             printf("tdb_firstkey() called with null context\n");
816 #endif
817             return null_data;
818         }
819
820         /* look for a non-empty hash chain */
821         for (hash = 0, rec_ptr = 0; 
822              hash < tdb->header.hash_size;
823              hash++) {
824                 /* find the top of the hash chain */
825                 offset = tdb_hash_top(tdb, hash);
826
827                 tdb_lock(tdb, BUCKET(hash));
828
829                 /* read in the hash top */
830                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
831                         goto fail;
832                 }
833
834                 if (rec_ptr) break;
835
836                 tdb_unlock(tdb, BUCKET(hash));
837         }
838
839         if (rec_ptr == 0) return null_data;
840
841         /* we've found a non-empty chain, now read the record */
842         if (rec_read(tdb, rec_ptr, &rec) == -1) {
843                 goto fail;
844         }
845
846         /* allocate and read the key space */
847         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
848         ret.dsize = rec.key_len;
849         tdb_unlock(tdb, BUCKET(hash));
850         return ret;
851
852  fail:
853         tdb_unlock(tdb, BUCKET(hash));
854         return null_data;
855 }
856
857 /* find the next entry in the database, returning its key */
858 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key)
859 {
860         unsigned hash, hbucket;
861         tdb_off rec_ptr, offset;
862         struct list_struct rec;
863         TDB_DATA ret;
864
865         if (tdb == NULL) {
866 #ifdef TDB_DEBUG
867             printf("tdb_nextkey() called with null context\n");
868 #endif
869             return null_data;
870         }
871
872         /* find which hash bucket it is in */
873         hash = tdb_hash(&key);
874         hbucket = BUCKET(hash);
875         
876         tdb_lock(tdb, hbucket);
877         rec_ptr = tdb_find(tdb, key, hash, &rec);
878         if (rec_ptr) {
879                 /* we want the next record after this one */
880                 rec_ptr = rec.next;
881         }
882
883         /* not found or last in hash: look for next non-empty hash chain */
884         while (rec_ptr == 0) {
885                 tdb_unlock(tdb, hbucket);
886
887                 if (++hbucket >= tdb->header.hash_size - 1)
888                         return null_data;
889
890                 offset = tdb_hash_top(tdb, hbucket);
891                 tdb_lock(tdb, hbucket);
892                 /* read in the hash top */
893                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
894                         tdb_unlock(tdb, hbucket);
895                         return null_data;
896                 }
897         }
898
899         /* Read the record. */
900         if (rec_read(tdb, rec_ptr, &rec) == -1) {
901                 tdb_unlock(tdb, hbucket);
902                 return null_data;
903         }
904         /* allocate and read the key */
905         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
906         ret.dsize = rec.key_len;
907         tdb_unlock(tdb, hbucket);
908
909         return ret;
910 }
911
912 /* delete an entry in the database given a key */
913 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
914 {
915         unsigned hash;
916         tdb_off offset, rec_ptr, last_ptr;
917         struct list_struct rec, lastrec;
918         char *data = NULL;
919
920         if (tdb == NULL) {
921 #ifdef TDB_DEBUG
922             printf("tdb_delete() called with null context\n");
923 #endif
924             return -1;
925         }
926
927         /* find which hash bucket it is in */
928         hash = tdb_hash(&key);
929
930         tdb_lock(tdb, BUCKET(hash));
931
932         /* find the top of the hash chain */
933         offset = tdb_hash_top(tdb, hash);
934
935         /* read in the hash top */
936         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
937                 goto fail;
938         }
939
940         last_ptr = 0;
941
942         /* keep looking until we find the right record */
943         while (rec_ptr) {
944                 if (rec_read(tdb, rec_ptr, &rec) == -1) {
945                         goto fail;
946                 }
947
948                 if (hash == rec.full_hash && key.dsize == rec.key_len) {
949                         /* a very likely hit - read the record and full key */
950                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), 
951                                              rec.key_len);
952                         if (!data) {
953                                 goto fail;
954                         }
955
956                         if (memcmp(key.dptr, data, key.dsize) == 0) {
957                                 /* a definite match - delete it */
958                                 if (last_ptr == 0) {
959                                         offset = tdb_hash_top(tdb, hash);
960                                         if (ofs_write(tdb, offset, &rec.next) == -1) {
961                                                 goto fail;
962                                         }
963                                 } else {
964                                         lastrec.next = rec.next;
965                                         if (rec_write(tdb, last_ptr, &lastrec) == -1) {
966                                                 goto fail;
967                                         }                                       
968                                 }
969                                 tdb_unlock(tdb, BUCKET(hash));
970                                 tdb_lock(tdb, -1);
971                                 /* and recover the space */
972                                 offset = FREELIST_TOP;
973                                 if (ofs_read(tdb, offset, &rec.next) == -1) {
974                                         goto fail2;
975                                 }
976                                 rec.magic = TDB_FREE_MAGIC;
977                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
978                                         goto fail2;
979                                 }
980                                 if (ofs_write(tdb, offset, &rec_ptr) == -1) {
981                                         goto fail2;
982                                 }
983
984                                 /* yipee - all done */
985                                 free(data);
986                                 tdb_unlock(tdb, -1);
987                                 return 0;
988                         }
989
990                         /* a miss - drat */
991                         free(data);
992                         data = NULL;
993                 }
994
995                 /* move to the next record */
996                 last_ptr = rec_ptr;
997                 lastrec = rec;
998                 rec_ptr = rec.next;
999         }
1000
1001  fail:
1002         if (data) free(data);
1003         tdb_unlock(tdb, BUCKET(hash));
1004         return -1;
1005
1006  fail2:
1007         if (data) free(data);
1008         tdb_unlock(tdb, -1);
1009         return -1;
1010 }
1011
1012
1013 /* store an element in the database, replacing any existing element
1014    with the same key 
1015
1016    return 0 on success, -1 on failure
1017 */
1018 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1019 {
1020         struct list_struct rec;
1021         unsigned hash;
1022         tdb_off rec_ptr, offset;
1023         char *p = NULL;
1024
1025         if (tdb == NULL) {
1026 #ifdef TDB_DEBUG
1027             printf("tdb_store() called with null context\n");
1028 #endif
1029             return -1;
1030         }
1031
1032         /* find which hash bucket it is in */
1033         hash = tdb_hash(&key);
1034
1035         /* check for it existing, on insert. */
1036         if (flag == TDB_INSERT && tdb_exists(tdb, key)) {
1037                 tdb->ecode = TDB_ERR_EXISTS;
1038                 return -1;
1039         }
1040
1041         /* first try in-place update, on modify or replace. */
1042         if (flag != TDB_INSERT && tdb_update(tdb, key, dbuf) == 0) {
1043                 return 0;
1044         }
1045
1046         /* check for it _not_ existing, from error code of the update. */
1047         if (flag == TDB_MODIFY && tdb->ecode == TDB_ERR_NOEXIST) {
1048                 return -1;
1049         }
1050
1051         /* reset the error code potentially set by the tdb_update() */
1052         tdb->ecode = 0;
1053
1054         /*
1055          * now we're into insert / modify / replace of a record
1056          * which we know could not be optimised by an in-place
1057          * store (for various reasons).
1058          */
1059
1060         rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize);
1061         if (rec_ptr == 0) {
1062                 return -1;
1063         }
1064
1065         tdb_lock(tdb, BUCKET(hash));
1066
1067         /* delete any existing record - if it doesn't exist we don't care */
1068         if (flag != TDB_INSERT) {
1069                 tdb_delete(tdb, key);
1070         }
1071
1072         /* read the newly created record */
1073         if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
1074                 goto fail;
1075         }
1076
1077         if (rec.magic != TDB_FREE_MAGIC) goto fail;
1078
1079         /* find the top of the hash chain */
1080         offset = tdb_hash_top(tdb, hash);
1081
1082         /* read in the hash top diretcly into our next pointer */
1083         if (ofs_read(tdb, offset, &rec.next) == -1) {
1084                 goto fail;
1085         }
1086
1087         rec.key_len = key.dsize;
1088         rec.data_len = dbuf.dsize;
1089         rec.full_hash = hash;
1090         rec.magic = TDB_MAGIC;
1091
1092         p = (char *)malloc(sizeof(rec) + key.dsize + dbuf.dsize);
1093         if (!p) {
1094                 tdb->ecode = TDB_ERR_OOM;
1095                 goto fail;
1096         }
1097
1098         memcpy(p, &rec, sizeof(rec));
1099         memcpy(p+sizeof(rec), key.dptr, key.dsize);
1100         memcpy(p+sizeof(rec)+key.dsize, dbuf.dptr, dbuf.dsize);
1101
1102         if (tdb_write(tdb, rec_ptr, p, sizeof(rec)+key.dsize+dbuf.dsize) == -1)
1103                 goto fail;
1104
1105         free(p); 
1106         p = NULL;
1107
1108         /* and point the top of the hash chain at it */
1109         if (ofs_write(tdb, offset, &rec_ptr) == -1) goto fail;
1110
1111         tdb_unlock(tdb, BUCKET(hash));
1112         return 0;
1113
1114  fail:
1115 #if TDB_DEBUG
1116         printf("store failed for hash 0x%08x in bucket %u\n", hash, BUCKET(hash));
1117 #endif
1118         if (p) free(p);
1119         tdb_unlock(tdb, BUCKET(hash));
1120         return -1;
1121 }
1122
1123
1124 /* open the database, creating it if necessary 
1125
1126    The open_flags and mode are passed straight to the open call on the database
1127    file. A flags value of O_WRONLY is invalid
1128
1129    The hash size is advisory, use zero for a default value. 
1130
1131    return is NULL on error
1132 */
1133 TDB_CONTEXT *tdb_open(char *name, int hash_size, int tdb_flags,
1134                       int open_flags, mode_t mode)
1135 {
1136         TDB_CONTEXT tdb, *ret;
1137         struct stat st;
1138
1139         memset(&tdb, 0, sizeof(tdb));
1140
1141         tdb.fd = -1;
1142         tdb.name = NULL;
1143         tdb.map_ptr = NULL;
1144
1145         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1146                 goto fail;
1147         }
1148
1149         if (hash_size == 0) hash_size = DEFAULT_HASH_SIZE;
1150
1151         tdb.read_only = ((open_flags & O_ACCMODE) == O_RDONLY);
1152
1153         if (name == NULL) goto in_memory;
1154
1155         tdb.fd = open(name, open_flags, mode);
1156         if (tdb.fd == -1) {
1157                 goto fail;
1158         }
1159
1160         /* ensure there is only one process initialising at once */
1161         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_SET, F_WRLCK, F_SETLKW);
1162         
1163         if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1164                 /* we need to zero the database if we are the only
1165                    one with it open */
1166                 if (tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_WRLCK, F_SETLK) == 0) {
1167                         ftruncate(tdb.fd, 0);
1168                         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLK);
1169                 }
1170         }
1171
1172         /* leave this lock in place */
1173         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_RDLCK, F_SETLKW);
1174
1175         if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header) ||
1176             strcmp(tdb.header.magic_food, TDB_MAGIC_FOOD) != 0 ||
1177             tdb.header.version != TDB_VERSION) {
1178                 /* its not a valid database - possibly initialise it */
1179                 if (!(open_flags & O_CREAT)) {
1180                         goto fail;
1181                 }
1182                 if (tdb_new_database(&tdb, hash_size) == -1) goto fail;
1183
1184                 lseek(tdb.fd, 0, SEEK_SET);
1185                 if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header)) 
1186                     goto fail;
1187         }
1188
1189         fstat(tdb.fd, &st);
1190
1191         /* map the database and fill in the return structure */
1192         tdb.name = (char *)strdup(name);
1193         tdb.map_size = st.st_size;
1194
1195         tdb.locked = (int *)calloc(tdb.header.hash_size+1, 
1196                                    sizeof(tdb.locked[0]));
1197         if (!tdb.locked) {
1198             goto fail;
1199         }
1200
1201 #if HAVE_MMAP
1202         tdb.map_ptr = (void *)mmap(NULL, st.st_size, 
1203                                    tdb.read_only? PROT_READ : PROT_READ|PROT_WRITE,
1204                                    MAP_SHARED | MAP_FILE, tdb.fd, 0);
1205 #endif
1206
1207  in_memory:
1208         ret = (TDB_CONTEXT *)malloc(sizeof(tdb));
1209         if (!ret) goto fail;
1210
1211         *ret = tdb;
1212
1213 #if TDB_DEBUG
1214         printf("mapped database of hash_size %u map_size=%u\n", 
1215                hash_size, tdb.map_size);
1216 #endif
1217
1218         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLKW);
1219         return ret;
1220
1221  fail:
1222         if (tdb.name) free(tdb.name);
1223         if (tdb.fd != -1) close(tdb.fd);
1224         if (tdb.map_ptr) munmap(tdb.map_ptr, tdb.map_size);
1225
1226         return NULL;
1227 }
1228
1229 /* close a database */
1230 int tdb_close(TDB_CONTEXT *tdb)
1231 {
1232         if (!tdb) return -1;
1233
1234         if (tdb->name) free(tdb->name);
1235         if (tdb->fd != -1) close(tdb->fd);
1236         if (tdb->locked) free(tdb->locked);
1237
1238         if (tdb->map_ptr) {
1239             if (tdb->fd != -1) {
1240                 munmap(tdb->map_ptr, tdb->map_size);
1241             } else {
1242                 free(tdb->map_ptr);
1243             }
1244         }
1245
1246         memset(tdb, 0, sizeof(*tdb));
1247         free(tdb);
1248
1249         return 0;
1250 }
1251
1252 /* lock the database. If we already have it locked then don't do anything */
1253 int tdb_writelock(TDB_CONTEXT *tdb)
1254 {
1255         if (tdb == NULL) {
1256 #ifdef TDB_DEBUG
1257             printf("tdb_writelock() called with null context\n");
1258 #endif
1259             return -1;
1260         }
1261
1262         return tdb_lock(tdb, -1);
1263 }
1264
1265 /* unlock the database. */
1266 int tdb_writeunlock(TDB_CONTEXT *tdb)
1267 {
1268         if (tdb == NULL) {
1269 #ifdef TDB_DEBUG
1270             printf("tdb_writeunlock() called with null context\n");
1271 #endif
1272             return -1;
1273         }
1274
1275         return tdb_unlock(tdb, -1);
1276 }
1277
1278 /* lock one hash chain. This is meant to be used to reduce locking
1279    contention - it cannot guarantee how many records will be locked */
1280 int tdb_lockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1281 {
1282         if (tdb == NULL) {
1283 #ifdef TDB_DEBUG
1284             printf("tdb_lockchain() called with null context\n");
1285 #endif
1286             return -1;
1287         }
1288
1289         return tdb_lock(tdb, BUCKET(tdb_hash(&key)));
1290 }
1291
1292
1293 /* unlock one hash chain */
1294 int tdb_unlockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1295 {
1296         if (tdb == NULL) {
1297 #ifdef TDB_DEBUG
1298             printf("tdb_unlockchain() called with null context\n");
1299 #endif
1300             return -1;
1301         }
1302
1303         return tdb_unlock(tdb, BUCKET(tdb_hash(&key)));
1304 }
1305
1306