/usr/include/python2.7/mx/btr.h is in python-egenix-mx-base-dev 3.2.9-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 | /* Header file extracted from btr.c -- an ANSI C implementation
included in the source code distribution of
SORTING AND SEARCHING ALGORITHMS: A COOKBOOK
by THOMAS NIEMANN Portland, Oregon
email: thomasn@jps.net
home: http://members.xoom.com/thomasn/s_man.htm
From the cookbook:
Permission to reproduce this document, in whole or in part, is
given provided the original web site listed below is referenced,
and no additional restrictions apply. Source code, when part of a
software project, may be used freely without reference to the
author.
Includes modifications by Marc-Andre Lemburg, 1998, mal@lemburg.com:
* removed nearly all globals, namely the global pointer h
* renamed many symbols
* added cursor support
* added bFlush() and bUpdateKey()
* enhanced bFind*() functions to allow scanning the index without copying
any data
* removed some unnecessary stuff like hList
* added EXTRA_BUFFERS
* added bCursorReadData()
* fixed a bug that caused a newly initialized root buffer not to
written to disk (the modified flag was not set)
* added external access to bErrLineNo in btr.h
* fixed a bug in search(): when dealing with duplicates not the first
but the second key was returned (at least sometimes)
* added filemode support to bOpen()
* added a fflush() to flushAll() to make sure the data is really
written to disk and not just to the cache
*/
/*
* this file is divided into sections:
* stuff you'll probably want to place in a .h file...
* implementation dependent
* - you'll probably have to change something here
* implementation independent
* - types and function prototypes that typically go in a .h file
* function prototypes
* - prototypes for user functions
*/
/****************************
* implementation dependent *
****************************/
/* Maximal allowed sectorSize value */
#define MAX_SECTOR_SIZE 4096
typedef unsigned long bRecAddr; /* record address for external record */
typedef unsigned long bIdxAddr; /* record address for btree node */
#define CC_EQ 0
#define CC_GT 1
#define CC_LT -1
/* compare two keys and return:
* CC_LT key1 < key2
* CC_GT key1 > key2
* CC_EQ key1 = key2
*/
typedef int (*bCompFunc)(size_t keysize, const void *key1, const void *key2);
/* Number of buffers to allocate in addition to the implementations
minimum. This will enhance performance if you often read small
sequences from the index or use many cursors. */
#define EXTRA_BUFFERS 10
/******************************
* implementation independent *
******************************/
typedef enum {false, true} bool;
typedef enum {
bErrOk,
bErrKeyNotFound,
bErrDupKeys,
bErrSectorSize,
bErrFileNotOpen,
bErrFileExists,
bErrNotWithDupKeys,
bErrBufferInvalid,
bErrIO,
bErrMemory
} bError;
typedef struct { /* info for bOpen() */
char *iName; /* name of index file */
int filemode; /* Mode in which to open the file:
0 - try to open it in update mode,
revert to creating a new file
if that fails
1 - open the file in read-only mode,
2 - force creation of a new file
*/
int keySize; /* length, in bytes, of key */
bool dupKeys; /* true if duplicate keys allowed */
int sectorSize; /* size of sector on disk */
bCompFunc comp; /* pointer to compare function */
} bDescription;
typedef char bKey; /* keys entries are treated as char arrays */
typedef struct {
unsigned int leaf:1; /* first bit = 1 if leaf */
unsigned int ct:15; /* count of keys present */
bIdxAddr prev; /* prev node in sequence (leaf) */
bIdxAddr next; /* next node in sequence (leaf) */
bIdxAddr childLT; /* child LT first key */
/* ct occurrences of [key,rec,childGE] */
bKey fkey; /* first occurrence */
} bNode;
typedef struct bBufferTag { /* location of node */
struct bBufferTag *next; /* next */
struct bBufferTag *prev; /* previous */
bIdxAddr adr; /* on disk */
bNode *p; /* in memory */
bool valid; /* true if buffer contents valid */
bool modified; /* true if buffer modified */
} bBuffer;
typedef struct bHandle {
FILE *fp; /* idx file */
int keySize; /* key length */
bool dupKeys; /* true if duplicate keys */
int sectorSize; /* block size for idx records */
bCompFunc comp; /* pointer to compare routine */
bBuffer root; /* root of b-tree, room for 3 sets */
bBuffer bufList; /* head of buf list */
void *malloc1; /* malloc'd resources */
void *malloc2; /* malloc'd resources */
bBuffer gbuf; /* gather buffer, room for 3 sets */
unsigned int maxCt; /* minimum # keys in node */
int ks; /* sizeof key entry */
bIdxAddr nextFreeAdr; /* next free b-tree record address */
/* statistics */
int maxHeight; /* maximum height attained */
int nNodesIns; /* number of nodes inserted */
int nNodesDel; /* number of nodes deleted */
int nKeysIns; /* number of keys inserted */
int nKeysDel; /* number of keys deleted */
int nKeysUpd; /* number of key updates */
int nDiskReads; /* number of disk reads */
int nDiskWrites; /* number of disk writes */
} bHandle;
/* Note: Cursors are only valid if their buffer is. */
typedef struct bCursor {
bBuffer *buffer; /* buffer in which the key is stored */
bKey *key; /* pointer to key (in buffer) */
} bCursor;
/* Line number for last IO or memory error */
extern int bErrLineNo;
/***********************
* function prototypes *
***********************/
bError bOpen(bDescription info, bHandle **handle);
/*
* input:
* info info for open
* output:
* handle handle to btree, used in subsequent calls
* returns:
* bErrOk open was successful
* bErrMemory insufficient memory
* bErrSectorSize sector size too small or not 0 mod 4
* bErrFileNotOpen unable to open index file
*/
bError bFlush(bHandle *handle);
/*
* input:
* handle handle returned by bOpen
* returns:
* bErrOk file closed, resources deleted
* notes:
* Flushes all buffers to disk
*/
bError bClose(bHandle *handle);
/*
* input:
* handle handle returned by bOpen
* returns:
* bErrOk file closed, resources deleted
*/
bError bInsertKey(bHandle *handle, void *key, bRecAddr rec);
/*
* input:
* handle handle returned by bOpen
* key key to insert
* rec record address
* returns:
* bErrOk operation successful
* bErrDupKeys duplicate keys (and info.dupKeys = false)
* notes:
* If dupKeys is false, then all records inserted must have a
* unique key. If dupkeys is true, then duplicate keys are
* allowed, but they must all have unique record addresses.
* In this case, record addresses are included in internal
* nodes to generate a "unique" key.
*/
bError bUpdateKey(bHandle *handle, void *key, bRecAddr rec);
/*
* input:
* handle handle returned by bOpen
* key key to update
* rec new record address
* returns:
* bErrOk operation successful
* bErrNotFound key not found
* bErrNotAllowed operation not allowed
* notes:
* This operation is only possible if dupKeys is false due to
* the way duplicate keys are handled by the implementation.
*/
bError bDeleteKey(bHandle *handle, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* key key to delete
* rec record address of key to delete
* output:
* rec record address deleted
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
* notes:
* If dupKeys is false, all keys are unique, and rec is not used
* to determine which key to delete. If dupKeys is true, then
* rec is used to determine which key to delete.
*/
bError bFindKey(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* key key to find
* output:
* cursor cursor pointing to new position
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
*/
bError bFindFirstKey(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* output:
* cursor cursor pointing to new position
* key first key in sequential set (if != NULL)
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
*/
bError bFindLastKey(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* output:
* cursor cursor pointing to new position
* key last key in sequential set (if != NULL)
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
*/
bError bFindNextKey(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* cursor cursor pointing to current position
* output:
* cursor cursor pointing to new position
* key key found (if != NULL)
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
*/
bError bFindPrevKey(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* cursor cursor pointing to current position
* output:
* cursor cursor pointing to new position
* key key found (if != NULL)
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrKeyNotFound key not found
*/
bError bCursorReadData(bHandle *handle, bCursor *c, void *key, bRecAddr *rec);
/*
* input:
* handle handle returned by bOpen
* cursor cursor pointing to current position
* output:
* key key found (if != NULL)
* rec record address (if != NULL)
* returns:
* bErrOk operation successful
* bErrBufferInvalid cursor buffer is invalid
*/
/* Debugging function which validates an open BTree pointed to by
handle and returns 0 for a valid tree structure and a negative
result for an invalid structure. */
int bValidateTree(bHandle *handle);
|