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