← Back to branch summary

~ubuntu-branches/ubuntu/maverick/evolution-data-server/maverick-proposed

« back to all changes in this revision

Viewing changes to libdb/dbinc/btree.h

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

Lines of Context:
libdb/dbinc/btree.h
1
 
/*-
2
 
 * See the file LICENSE for redistribution information.
3
 
 *
4
 
 * Copyright (c) 1996-2002
5
 
 *      Sleepycat Software.  All rights reserved.
6
 
 */
7
 
/*
8
 
 * Copyright (c) 1990, 1993, 1994, 1995, 1996
9
 
 *      Keith Bostic.  All rights reserved.
10
 
 */
11
 
/*
12
 
 * Copyright (c) 1990, 1993, 1994, 1995
13
 
 *      The Regents of the University of California.  All rights reserved.
14
 
 *
15
 
 * This code is derived from software contributed to Berkeley by
16
 
 * Mike Olson.
17
 
 *
18
 
 * Redistribution and use in source and binary forms, with or without
19
 
 * modification, are permitted provided that the following conditions
20
 
 * are met:
21
 
 * 1. Redistributions of source code must retain the above copyright
22
 
 *    notice, this list of conditions and the following disclaimer.
23
 
 * 2. Redistributions in binary form must reproduce the above copyright
24
 
 *    notice, this list of conditions and the following disclaimer in the
25
 
 *    documentation and/or other materials provided with the distribution.
26
 
 * 3. Neither the name of the University nor the names of its contributors
27
 
 *    may be used to endorse or promote products derived from this software
28
 
 *    without specific prior written permission.
29
 
 *
30
 
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31
 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32
 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
 
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34
 
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35
 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36
 
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37
 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38
 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39
 
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40
 
 * SUCH DAMAGE.
41
 
 *
42
 
 * $Id$
43
 
 */
44
 
#ifndef _DB_BTREE_H_
45
 
#define _DB_BTREE_H_
46
 
 
47
 
/* Forward structure declarations. */
48
 
struct __btree;         typedef struct __btree BTREE;
49
 
struct __cursor;        typedef struct __cursor BTREE_CURSOR;
50
 
struct __epg;           typedef struct __epg EPG;
51
 
struct __recno;         typedef struct __recno RECNO;
52
 
 
53
 
#define DEFMINKEYPAGE    (2)
54
 
 
55
 
/*
56
 
 * A recno order of 0 indicates that we don't have an order, not that we've
57
 
 * an order less than 1.
58
 
 */
59
 
#define INVALID_ORDER   0
60
 
 
61
 
#define ISINTERNAL(p)   (TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO)
62
 
#define ISLEAF(p)       (TYPE(p) == P_LBTREE ||                         \
63
 
                            TYPE(p) == P_LRECNO || TYPE(p) == P_LDUP)
64
 
 
65
 
/* Flags for __bam_cadjust_log(). */
66
 
#define CAD_UPDATEROOT  0x01            /* Root page count was updated. */
67
 
 
68
 
/* Flags for __bam_split_log(). */
69
 
#define SPL_NRECS       0x01            /* Split tree has record count. */
70
 
 
71
 
/* Flags for __bam_iitem(). */
72
 
#define BI_DELETED      0x01            /* Key/data pair only placeholder. */
73
 
 
74
 
/* Flags for __bam_stkrel(). */
75
 
#define STK_CLRDBC      0x01            /* Clear dbc->page reference. */
76
 
#define STK_NOLOCK      0x02            /* Don't retain locks. */
77
 
 
78
 
/* Flags for __ram_ca(). These get logged, so make the values explicit. */
79
 
typedef enum {
80
 
        CA_DELETE = 0,                  /* Delete the current record. */
81
 
        CA_IAFTER = 1,                  /* Insert before the current record. */
82
 
        CA_IBEFORE = 2,                 /* Insert after the current record. */
83
 
        CA_ICURRENT = 3                 /* Overwrite the current record. */
84
 
} ca_recno_arg;
85
 
 
86
 
/*
87
 
 * Flags for __bam_search() and __bam_rsearch().
88
 
 *
89
 
 * Note, internal page searches must find the largest record less than key in
90
 
 * the tree so that descents work.  Leaf page searches must find the smallest
91
 
 * record greater than key so that the returned index is the record's correct
92
 
 * position for insertion.
93
 
 *
94
 
 * The flags parameter to the search routines describes three aspects of the
95
 
 * search: the type of locking required (including if we're locking a pair of
96
 
 * pages), the item to return in the presence of duplicates and whether or not
97
 
 * to return deleted entries.  To simplify both the mnemonic representation
98
 
 * and the code that checks for various cases, we construct a set of bitmasks.
99
 
 */
100
 
#define S_READ          0x00001         /* Read locks. */
101
 
#define S_WRITE         0x00002         /* Write locks. */
102
 
 
103
 
#define S_APPEND        0x00040         /* Append to the tree. */
104
 
#define S_DELNO         0x00080         /* Don't return deleted items. */
105
 
#define S_DUPFIRST      0x00100         /* Return first duplicate. */
106
 
#define S_DUPLAST       0x00200         /* Return last duplicate. */
107
 
#define S_EXACT         0x00400         /* Exact items only. */
108
 
#define S_PARENT        0x00800         /* Lock page pair. */
109
 
#define S_STACK         0x01000         /* Need a complete stack. */
110
 
#define S_PAST_EOF      0x02000         /* If doing insert search (or keyfirst
111
 
                                         * or keylast operations), or a split
112
 
                                         * on behalf of an insert, it's okay to
113
 
                                         * return an entry one past end-of-page.
114
 
                                         */
115
 
#define S_STK_ONLY      0x04000         /* Just return info in the stack */
116
 
 
117
 
#define S_DELETE        (S_WRITE | S_DUPFIRST | S_DELNO | S_EXACT | S_STACK)
118
 
#define S_FIND          (S_READ | S_DUPFIRST | S_DELNO)
119
 
#define S_FIND_WR       (S_WRITE | S_DUPFIRST | S_DELNO)
120
 
#define S_INSERT        (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
121
 
#define S_KEYFIRST      (S_WRITE | S_DUPFIRST | S_PAST_EOF | S_STACK)
122
 
#define S_KEYLAST       (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
123
 
#define S_WRPAIR        (S_WRITE | S_DUPLAST | S_PAST_EOF | S_PARENT)
124
 
 
125
 
/*
126
 
 * Various routines pass around page references.  A page reference is
127
 
 * a pointer to the page, and the indx indicates an item on the page.
128
 
 * Each page reference may include a lock.
129
 
 */
130
 
struct __epg {
131
 
        PAGE         *page;             /* The page. */
132
 
        db_indx_t     indx;             /* The index on the page. */
133
 
        db_indx_t     entries;          /* The number of entries on page */
134
 
        DB_LOCK       lock;             /* The page's lock. */
135
 
        db_lockmode_t lock_mode;        /* The lock mode. */
136
 
};
137
 
 
138
 
/*
139
 
 * We maintain a stack of the pages that we're locking in the tree.  Grow
140
 
 * the stack as necessary.
141
 
 *
142
 
 * XXX
143
 
 * Temporary fix for #3243 -- clear the page and lock from the stack entry.
144
 
 * The correct fix is to never release a stack that doesn't hold items.
145
 
 */
146
 
#define BT_STK_CLR(c) do {                                              \
147
 
        (c)->csp = (c)->sp;                                             \
148
 
        (c)->csp->page = NULL;                                          \
149
 
        LOCK_INIT((c)->csp->lock);                              \
150
 
} while (0)
151
 
 
152
 
#define BT_STK_ENTER(dbenv, c, pagep, page_indx, l, mode, ret) do {     \
153
 
        if ((ret =                                                      \
154
 
            (c)->csp == (c)->esp ? __bam_stkgrow(dbenv, c) : 0) == 0) { \
155
 
                (c)->csp->page = pagep;                                 \
156
 
                (c)->csp->indx = page_indx;                             \
157
 
                (c)->csp->entries = NUM_ENT(pagep);                     \
158
 
                (c)->csp->lock = l;                                     \
159
 
                (c)->csp->lock_mode = mode;                             \
160
 
        }                                                               \
161
 
} while (0)
162
 
 
163
 
#define BT_STK_PUSH(dbenv, c, pagep, page_indx, lock, mode, ret) do {   \
164
 
        BT_STK_ENTER(dbenv, c, pagep, page_indx, lock, mode, ret);      \
165
 
        ++(c)->csp;                                                     \
166
 
} while (0)
167
 
 
168
 
#define BT_STK_NUM(dbenv, c, pagep, page_indx, ret) do {                \
169
 
        if ((ret =                                                      \
170
 
            (c)->csp == (c)->esp ? __bam_stkgrow(dbenv, c) : 0) == 0) { \
171
 
                (c)->csp->page = NULL;                                  \
172
 
                (c)->csp->indx = page_indx;                             \
173
 
                (c)->csp->entries = NUM_ENT(pagep);                     \
174
 
                LOCK_INIT((c)->csp->lock);                      \
175
 
                (c)->csp->lock_mode = DB_LOCK_NG;                       \
176
 
        }                                                               \
177
 
} while (0)
178
 
 
179
 
#define BT_STK_NUMPUSH(dbenv, c, pagep, page_indx, ret) do {            \
180
 
        BT_STK_NUM(dbenv, cp, pagep, page_indx, ret);                   \
181
 
        ++(c)->csp;                                                     \
182
 
} while (0)
183
 
 
184
 
#define BT_STK_POP(c)                                                   \
185
 
        ((c)->csp == (c)->sp ? NULL : --(c)->csp)
186
 
 
187
 
/* Btree/Recno cursor. */
188
 
struct __cursor {
189
 
        /* struct __dbc_internal */
190
 
        __DBC_INTERNAL
191
 
 
192
 
        /* btree private part */
193
 
        EPG             *sp;            /* Stack pointer. */
194
 
        EPG             *csp;           /* Current stack entry. */
195
 
        EPG             *esp;           /* End stack pointer. */
196
 
        EPG              stack[5];
197
 
 
198
 
        db_indx_t        ovflsize;      /* Maximum key/data on-page size. */
199
 
 
200
 
        db_recno_t       recno;         /* Current record number. */
201
 
        u_int32_t        order;         /* Relative order among deleted curs. */
202
 
 
203
 
        /*
204
 
         * Btree:
205
 
         * We set a flag in the cursor structure if the underlying object has
206
 
         * been deleted.  It's not strictly necessary, we could get the same
207
 
         * information by looking at the page itself, but this method doesn't
208
 
         * require us to retrieve the page on cursor delete.
209
 
         *
210
 
         * Recno:
211
 
         * When renumbering recno databases during deletes, cursors referencing
212
 
         * "deleted" records end up positioned between two records, and so must
213
 
         * be specially adjusted on the next operation.
214
 
         */
215
 
#define C_DELETED       0x0001          /* Record was deleted. */
216
 
        /*
217
 
         * There are three tree types that require maintaining record numbers.
218
 
         * Recno AM trees, Btree AM trees for which the DB_RECNUM flag was set,
219
 
         * and Btree off-page duplicate trees.
220
 
         */
221
 
#define C_RECNUM        0x0002          /* Tree requires record counts. */
222
 
        /*
223
 
         * Recno trees have immutable record numbers by default, but optionally
224
 
         * support mutable record numbers.  Off-page duplicate Recno trees have
225
 
         * mutable record numbers.  All Btrees with record numbers (including
226
 
         * off-page duplicate trees) are mutable by design, no flag is needed.
227
 
         */
228
 
#define C_RENUMBER      0x0004          /* Tree records are mutable. */
229
 
        u_int32_t        flags;
230
 
};
231
 
 
232
 
/*
233
 
 * Threshhold value, as a function of bt_minkey, of the number of
234
 
 * bytes a key/data pair can use before being placed on an overflow
235
 
 * page.  Assume every item requires the maximum alignment for
236
 
 * padding, out of sheer paranoia.
237
 
 */
238
 
#define B_MINKEY_TO_OVFLSIZE(dbp, minkey, pgsize)                       \
239
 
        ((u_int16_t)(((pgsize) - P_OVERHEAD(dbp)) / ((minkey) * P_INDX) -\
240
 
            (BKEYDATA_PSIZE(0) + ALIGN(1, sizeof(int32_t)))))
241
 
 
242
 
/*
243
 
 * The maximum space that a single item can ever take up on one page.
244
 
 * Used by __bam_split to determine whether a split is still necessary.
245
 
 */
246
 
#define B_MAX(a,b)      (((a) > (b)) ? (a) : (b))
247
 
#define B_MAXSIZEONPAGE(ovflsize)                                       \
248
 
        (B_MAX(BOVERFLOW_PSIZE, BKEYDATA_PSIZE(ovflsize)))
249
 
 
250
 
/*
251
 
 * The in-memory, per-tree btree/recno data structure.
252
 
 */
253
 
struct __btree {                        /* Btree access method. */
254
 
        /*
255
 
         * !!!
256
 
         * These fields are write-once (when the structure is created) and
257
 
         * so are ignored as far as multi-threading is concerned.
258
 
         */
259
 
        db_pgno_t bt_meta;              /* Database meta-data page. */
260
 
        db_pgno_t bt_root;              /* Database root page. */
261
 
 
262
 
        u_int32_t bt_maxkey;            /* Maximum keys per page. */
263
 
        u_int32_t bt_minkey;            /* Minimum keys per page. */
264
 
 
265
 
                                        /* Btree comparison function. */
266
 
        int (*bt_compare) __P((DB *, const DBT *, const DBT *));
267
 
                                        /* Btree prefix function. */
268
 
        size_t (*bt_prefix) __P((DB *, const DBT *, const DBT *));
269
 
 
270
 
                                        /* Recno access method. */
271
 
        int       re_pad;               /* Fixed-length padding byte. */
272
 
        int       re_delim;             /* Variable-length delimiting byte. */
273
 
        u_int32_t re_len;               /* Length for fixed-length records. */
274
 
        char     *re_source;            /* Source file name. */
275
 
 
276
 
        /*
277
 
         * !!!
278
 
         * The bt_lpgno field is NOT protected by any mutex, and for this
279
 
         * reason must be advisory only, so, while it is read/written by
280
 
         * multiple threads, DB is completely indifferent to the quality
281
 
         * of its information.
282
 
         */
283
 
        db_pgno_t bt_lpgno;             /* Last insert location. */
284
 
 
285
 
        /*
286
 
         * !!!
287
 
         * The re_modified field is NOT protected by any mutex, and for this
288
 
         * reason cannot be anything more complicated than a zero/non-zero
289
 
         * value.  The actual writing of the backing source file cannot be
290
 
         * threaded, so clearing the flag isn't a problem.
291
 
         */
292
 
        int       re_modified;          /* If the tree was modified. */
293
 
 
294
 
        /*
295
 
         * !!!
296
 
         * These fields are ignored as far as multi-threading is concerned.
297
 
         * There are no transaction semantics associated with backing files,
298
 
         * nor is there any thread protection.
299
 
         */
300
 
        FILE            *re_fp;         /* Source file handle. */
301
 
        int              re_eof;        /* Backing source file EOF reached. */
302
 
        db_recno_t       re_last;       /* Last record number read. */
303
 
};
304
 
 
305
 
/*
306
 
 * Modes for the __bam_curadj recovery records (btree_curadj).
307
 
 * These appear in log records, so we wire the values and
308
 
 * do not leave it up to the compiler.
309
 
 */
310
 
typedef enum {
311
 
        DB_CA_DI        = 1,
312
 
        DB_CA_DUP       = 2,
313
 
        DB_CA_RSPLIT    = 3,
314
 
        DB_CA_SPLIT     = 4
315
 
} db_ca_mode;
316
 
 
317
 
#include "dbinc_auto/btree_auto.h"
318
 
#include "dbinc_auto/btree_ext.h"
319
 
#include "dbinc/db_am.h"
320
 
#endif /* !_DB_BTREE_H_ */