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