tbtree.h

   1 /*
   2  * Copyright (c) 2005 Teodor Sigaev <teodor@sigaev.ru>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *      notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *      notice, this list of conditions and the following disclaimer in the
  12  *      documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the author nor the names of any co-contributors
  14  *      may be used to endorse or promote products derived from this software
  15  *      without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
  18  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef __TBTREE_H__
  31 #define __TBTREE_H__
  32
  33
  34 #include <sys/types.h>
  35
  36 /* C-utils */
  37 #ifndef offsetof
  38 #define offsetof(type, field)   ((int) &((type *)0)->field)
  39 #endif   /* offsetof */
  40
  41 #define TYPEALIGN(ALIGNVAL,LEN)  \
  42         (((long) (LEN) + (ALIGNVAL-1)) & ~((long) (ALIGNVAL-1)))
  43
  44 #define PTRALIGN(LEN)     TYPEALIGN(sizeof(void*), (LEN))
  45
  46 /* end utils */
  47
  48
  49 typedef struct {
  50         union {
  51                 struct {
  52                         u_int16_t offset;
  53                         u_int16_t length;
  54                 } leaf;
  55                 struct {
  56                         u_int32_t link;
  57                 } internal;
  58         } pointer;
  59         union {
  60                 struct {
  61                         u_int16_t       offset;
  62                         u_int16_t       length;
  63                 } varlen;
  64                 struct {
  65                         char key[1];
  66                 } fixed;
  67         } key;
  68 } TBTPointer;
  69
  70 #define TBTPOINTERHRDSZ         (offsetof(TBTPointer, key.fixed.key))
  71 #define TBTPOINTERSIZE(db)      PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
  72 #define ISINFPOINTER(db, page, ptr)  ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) )
  73
  74 #define TBTREEPAGESIZE  8192
  75 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
  76
  77 typedef struct {
  78         u_int32_t       rightlink;
  79         u_int32_t
  80                 freespace:13, /* correlate to BTREEPAGESIZE */
  81                 npointer:10,
  82                 isleaf:1,
  83                 unused: 8;
  84         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];
  85 } TBTPage;
  86
  87 typedef struct TBTMemPage {
  88         u_int32_t       pagenumber;
  89         u_int32_t
  90                 issynced:1,
  91                 iscached:1,
  92                 islocked:1,
  93                 unused:29;
  94         struct TBTMemPage *prev;
  95         struct TBTMemPage *next;
  96         TBTPage page;
  97 } TBTMemPage;
  98
  99 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*2 + TBTPAGEHDRSZ)
 100 typedef struct {
 101         u_int16_t       length;
 102         char            *value;
 103 } TBTValue;
 104
 105 #define TBT_STATEGY_HALF        0
 106 #define TBT_STATEGY_LEFTFILL    1
 107 #define TBT_STATEGY_RIGHTFILL   2
 108
 109 typedef struct {
 110         int     fd;     /* file descriptor */
 111
 112         int     (*cmpkey)(const TBTValue *, const TBTValue *);
 113
 114         u_int32_t
 115                 readonly:1,
 116                 keylen:11,
 117                 strategy:2,
 118                 unused:18;
 119
 120         /* cache page subsystem */
 121         u_int32_t       npage;
 122         u_int32_t       curpage;
 123         TBTMemPage      **Cache;
 124         TBTMemPage      *TimeCache;
 125         TBTMemPage      *TimeCacheLast;
 126         u_int32_t       lastpagenumber;
 127
 128         /* stat subsystem */
 129         u_int32_t       cachehits;
 130         u_int32_t       pageread; /* include cachehits */
 131         u_int32_t       pagewrite;
 132 } TBTree;
 133
 134 #define TBT_OK          0
 135 #define TBT_ERROR       1
 136 #define TBT_HUGE        2
 137
 138 #define TBTPAGEROOT     0
 139
 140 int TBTOpen(TBTree *db, char *file) ;
 141 int TBTClose(TBTree *db) ;
 142 int TBTSync(TBTree *db) ;
 143 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
 144 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
 145 int TBTDelete(TBTree *db, TBTValue *key);
 146 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
 147
 148 typedef struct {
 149         TBTMemPage      *page;
 150         TBTPointer      *ptr;
 151 } TBTIterator;
 152
 153 int TBTInitIterator(TBTree *db, TBTIterator *iterator );
 154 int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
 155 void TBTFreeIterator(TBTree *db, TBTIterator *iterator);
 156
 157
 158 #endif