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 /*#define HASHSIZE(LEN) ( TYPEALIGN(2, (int)((LEN)*2)) + 1 )*/
  47 #define HASHSIZE(LEN)   ( (LEN)<<1 )
  48 /* end utils */
  49
  50
  51 typedef struct {
  52         union {
  53                 struct {
  54                         u_int16_t offset;
  55                         u_int16_t length;
  56                 } leaf;
  57                 struct {
  58                         u_int32_t link;
  59                 } internal;
  60         } pointer;
  61         union {
  62                 struct {
  63                         u_int16_t       offset;
  64                         u_int16_t       length;
  65                 } varlen;
  66                 struct {
  67                         char key[1];
  68                 } fixed;
  69         } key;
  70 } TBTPointer;
  71
  72 #define TBTPOINTERHRDSZ         (offsetof(TBTPointer, key.fixed.key))
  73 #define TBTPOINTERSIZE(db)      PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
  74 #define ISINFPOINTER(db, page, ptr)  ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) )
  75
  76 #define TBTREEPAGESIZE  8192
  77 #define TBTPAGEHDRSZ    (2*sizeof(u_int32_t))
  78
  79 typedef struct {
  80         u_int32_t       rightlink;
  81         u_int32_t
  82                 freespace:13, /* correlate to BTREEPAGESIZE */
  83                 npointer:10,
  84                 isleaf:1,
  85                 unused: 8;
  86         char    data[TBTREEPAGESIZE-TBTPAGEHDRSZ];
  87 } TBTPage;
  88
  89 typedef struct TBTMemPage {
  90         u_int32_t       pagenumber;
  91         u_int32_t
  92                 issynced:1,
  93                 iscached:1,
  94                 islocked:1,
  95                 unused:29;
  96         struct TBTMemPage *prev;
  97         struct TBTMemPage *next;
  98         struct TBTMemPage *link;
  99         TBTPage page;
 100 } TBTMemPage;
 101
 102 #define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
 103 typedef struct {
 104         u_int16_t       length;
 105         char            *value;
 106 } TBTValue;
 107
 108 #define TBT_STATEGY_HALF        0
 109 #define TBT_STATEGY_LEFTFILL    1
 110 #define TBT_STATEGY_RIGHTFILL   2
 111
 112 typedef struct {
 113         int     fd;     /* file descriptor */
 114
 115         int     (*cmpkey)(const TBTValue *, const TBTValue *);
 116
 117         u_int32_t
 118                 readonly:1,
 119                 keylen:11,
 120                 strategy:2,
 121                 unused:18;
 122
 123         /* cache page subsystem */
 124         u_int32_t       npage;
 125         u_int32_t       curpage;
 126         TBTMemPage      **Cache;
 127         TBTMemPage      *TimeCache;
 128         TBTMemPage      *TimeCacheLast;
 129         u_int32_t       lastpagenumber;
 130
 131         /* stat subsystem */
 132         u_int32_t       cachehits;
 133         u_int32_t       pageread; /* include cachehits */
 134         u_int32_t       pagewrite;
 135 } TBTree;
 136
 137 #define TBT_OK          0
 138 #define TBT_ERROR       1
 139 #define TBT_HUGE        2
 140
 141 #define TBTPAGEROOT     0
 142
 143 int TBTOpen(TBTree *db, char *file) ;
 144 int TBTClose(TBTree *db) ;
 145 int TBTSync(TBTree *db) ;
 146 int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
 147 int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
 148 int TBTDelete(TBTree *db, TBTValue *key);
 149 void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);
 150
 151 typedef struct {
 152         TBTMemPage      *page;
 153         TBTPointer      *ptr;
 154 } TBTIterator;
 155
 156 int TBTInitIterator(TBTree *db, TBTIterator *iterator );
 157 int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
 158 void TBTFreeIterator(TBTree *db, TBTIterator *iterator);
 159
 160
 161 #endif