]> pd.if.org Git - btree/blob - btree2s.c
Fix a few bugs.
[btree] / btree2s.c
1 // btree version 2s
2 //      with reworked bt_deletekey code
3 // 25 FEB 2014
4
5 // author: karl malbrain, malbrain@cal.berkeley.edu
6
7 /*
8 This work, including the source code, documentation
9 and related data, is placed into the public domain.
10
11 The orginal author is Karl Malbrain.
12
13 THIS SOFTWARE IS PROVIDED AS-IS WITHOUT WARRANTY
14 OF ANY KIND, NOT EVEN THE IMPLIED WARRANTY OF
15 MERCHANTABILITY. THE AUTHOR OF THIS SOFTWARE,
16 ASSUMES _NO_ RESPONSIBILITY FOR ANY CONSEQUENCE
17 RESULTING FROM THE USE, MODIFICATION, OR
18 REDISTRIBUTION OF THIS SOFTWARE.
19 */
20
21 // Please see the project home page for documentation
22 // code.google.com/p/high-concurrency-btree
23
24 #define _FILE_OFFSET_BITS 64
25 #define _LARGEFILE64_SOURCE
26
27 #ifdef linux
28 #define _GNU_SOURCE
29 #endif
30
31 #ifdef unix
32 #include <unistd.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <time.h>
36 #include <fcntl.h>
37 #include <sys/mman.h>
38 #include <errno.h>
39 #else
40 #define WIN32_LEAN_AND_MEAN
41 #include <windows.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <time.h>
45 #include <fcntl.h>
46 #endif
47
48 #include <memory.h>
49 #include <string.h>
50
51 typedef unsigned long long      uid;
52
53 #ifndef unix
54 typedef unsigned long long      off64_t;
55 typedef unsigned short          ushort;
56 typedef unsigned int            uint;
57 #endif
58
59 #define BT_ro 0x6f72    // ro
60 #define BT_rw 0x7772    // rw
61 #define BT_fl 0x6c66    // fl
62
63 #define BT_maxbits              24                                      // maximum page size in bits
64 #define BT_minbits              9                                       // minimum page size in bits
65 #define BT_minpage              (1 << BT_minbits)       // minimum page size
66
67 /*
68 There are five lock types for each node in three independent sets: 
69 1. (set 1) AccessIntent: Sharable. Going to Read the node. Incompatible with NodeDelete. 
70 2. (set 1) NodeDelete: Exclusive. About to release the node. Incompatible with AccessIntent. 
71 3. (set 2) ReadLock: Sharable. Read the node. Incompatible with WriteLock. 
72 4. (set 2) WriteLock: Exclusive. Modify the node. Incompatible with ReadLock and other WriteLocks. 
73 5. (set 3) ParentModification: Exclusive. Change the node's parent keys. Incompatible with another ParentModification. 
74 */
75
76 typedef enum{
77         BtLockAccess,
78         BtLockDelete,
79         BtLockRead,
80         BtLockWrite,
81         BtLockParent
82 }BtLock;
83
84 //      Define the length of the page and key pointers
85
86 #define BtId 6
87
88 //      Page key slot definition.
89
90 //      If BT_maxbits is 15 or less, you can save 2 bytes
91 //      for each key stored by making the first two uints
92 //      into ushorts.  You can also save 4 bytes by removing
93 //      the tod field from the key.
94
95 //      Keys are marked dead, but remain on the page until
96 //      cleanup is called. The fence key (highest key) for
97 //      the page is always present, even if dead.
98
99 typedef struct {
100         uint off:BT_maxbits;            // page offset for key start
101         uint dead:1;                            // set for deleted key
102         uint tod;                                       // time-stamp for key
103         unsigned char id[BtId];         // id associated with key
104 } BtSlot;
105
106 //      The key structure occupies space at the upper end of
107 //      each page.  It's a length byte followed by the value
108 //      bytes.
109
110 typedef struct {
111         unsigned char len;
112         unsigned char key[0];
113 } *BtKey;
114
115 //      The first part of an index page.
116 //      It is immediately followed
117 //      by the BtSlot array of keys.
118
119 typedef struct {
120         uint cnt;                                       // count of keys in page
121         uint act;                                       // count of active keys
122         uint min;                                       // next key offset
123         unsigned char bits:7;           // page size in bits
124         unsigned char free:1;           // page is on free list
125         unsigned char lvl:6;            // level of page
126         unsigned char kill:1;           // page is being deleted
127         unsigned char dirty:1;          // page is dirty
128         unsigned char right[BtId];      // page number to right
129 } *BtPage;
130
131 //      The memory mapping hash table entry
132
133 typedef struct {
134         BtPage page;            // mapped page pointer
135         uid  page_no;           // mapped page number
136         void *lruprev;          // least recently used previous cache block
137         void *lrunext;          // lru next cache block
138         void *hashprev;         // previous cache block for the same hash idx
139         void *hashnext;         // next cache block for the same hash idx
140 #ifndef unix
141         HANDLE hmap;
142 #endif
143 }BtHash;
144
145 //      The object structure for Btree access
146
147 typedef struct _BtDb {
148         uint page_size;         // each page size       
149         uint page_bits;         // each page size in bits       
150         uint seg_bits;          // segment size in pages in bits
151         uid page_no;            // current page number  
152         uid cursor_page;        // current cursor page number   
153         int  err;
154         uint mode;                      // read-write mode
155         uint mapped_io;         // use memory mapping
156         BtPage temp;            // temporary frame buffer (memory mapped/file IO)
157         BtPage alloc;           // frame buffer for alloc page ( page 0 )
158         BtPage cursor;          // cached frame for start/next (never mapped)
159         BtPage frame;           // spare frame for the page split (never mapped)
160         BtPage zero;            // zeroes frame buffer (never mapped)
161         BtPage page;            // current page
162 #ifdef unix
163         int idx;
164 #else
165         HANDLE idx;
166 #endif
167         unsigned char *mem;     // frame, cursor, page memory buffer
168         int nodecnt;            // highest page cache segment in use
169         int nodemax;            // highest page cache segment allocated
170         int hashmask;           // number of pages in segments - 1
171         int hashsize;           // size of hash table
172         int found;                      // last deletekey found key
173         BtHash *lrufirst;       // lru list head
174         BtHash *lrulast;        // lru list tail
175         ushort *cache;          // hash table for cached segments
176         BtHash nodes[1];        // segment cache follows
177 } BtDb;
178
179 typedef enum {
180 BTERR_ok = 0,
181 BTERR_struct,
182 BTERR_ovflw,
183 BTERR_lock,
184 BTERR_map,
185 BTERR_wrt,
186 BTERR_hash
187 } BTERR;
188
189 // B-Tree functions
190 extern void bt_close (BtDb *bt);
191 extern BtDb *bt_open (char *name, uint mode, uint bits, uint cacheblk, uint pgblk);
192 extern BTERR  bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod);
193 extern BTERR  bt_deletekey (BtDb *bt, unsigned char *key, uint len, uint lvl);
194 extern uid bt_findkey    (BtDb *bt, unsigned char *key, uint len);
195 extern uint bt_startkey  (BtDb *bt, unsigned char *key, uint len);
196 extern uint bt_nextkey   (BtDb *bt, uint slot);
197
198 //  Helper functions to return slot values
199
200 extern BtKey bt_key (BtDb *bt, uint slot);
201 extern uid bt_uid (BtDb *bt, uint slot);
202 extern uint bt_tod (BtDb *bt, uint slot);
203
204 //  BTree page number constants
205 #define ALLOC_page              0
206 #define ROOT_page               1
207 #define LEAF_page               2
208
209 //      Number of levels to create in a new BTree
210
211 #define MIN_lvl                 2
212
213 //  The page is allocated from low and hi ends.
214 //  The key offsets and row-id's are allocated
215 //  from the bottom, while the text of the key
216 //  is allocated from the top.  When the two
217 //  areas meet, the page is split into two.
218
219 //  A key consists of a length byte, two bytes of
220 //  index number (0 - 65534), and up to 253 bytes
221 //  of key value.  Duplicate keys are discarded.
222 //  Associated with each key is a 48 bit row-id.
223
224 //  The b-tree root is always located at page 1.
225 //      The first leaf page of level zero is always
226 //      located on page 2.
227
228 //      The b-tree pages are linked with right
229 //      pointers to facilitate enumerators,
230 //      and provide for concurrency.
231
232 //      When to root page fills, it is split in two and
233 //      the tree height is raised by a new root at page
234 //      one with two keys.
235
236 //      Deleted keys are marked with a dead bit until
237 //      page cleanup The fence key for a node is always
238 //      present, even after deletion and cleanup.
239
240 //  Deleted leaf pages are reclaimed  on a free list.
241 //      The upper levels of the btree are fixed on creation.
242
243 //  Groups of pages from the btree are optionally
244 //  cached with memory mapping. A hash table is used to keep
245 //  track of the cached pages.  This behaviour is controlled
246 //  by the number of cache blocks parameter and pages per block
247 //      given to bt_open.
248
249 //  To achieve maximum concurrency one page is locked at a time
250 //  as the tree is traversed to find leaf key in question. The right
251 //  page numbers are used in cases where the page is being split,
252 //      or consolidated.
253
254 //  Page 0 (ALLOC page) is dedicated to lock for new page extensions,
255 //      and chains empty leaf pages together for reuse.
256
257 //      Parent locks are obtained to prevent resplitting or deleting a node
258 //      before its fence is posted into its upper level.
259
260 //      A special open mode of BT_fl is provided to safely access files on
261 //      WIN32 networks. WIN32 network operations should not use memory mapping.
262 //      This WIN32 mode sets FILE_FLAG_NOBUFFERING and FILE_FLAG_WRITETHROUGH
263 //      to prevent local caching of network file contents.
264
265 //      Access macros to address slot and key values from the page.
266 //      Page slots use 1 based indexing.
267
268 #define slotptr(page, slot) (((BtSlot *)(page+1)) + (slot-1))
269 #define keyptr(page, slot) ((BtKey)((unsigned char*)(page) + slotptr(page, slot)->off))
270
271 void bt_putid(unsigned char *dest, uid id)
272 {
273 int i = BtId;
274
275         while( i-- )
276                 dest[i] = (unsigned char)id, id >>= 8;
277 }
278
279 uid bt_getid(unsigned char *src)
280 {
281 uid id = 0;
282 int i;
283
284         for( i = 0; i < BtId; i++ )
285                 id <<= 8, id |= *src++; 
286
287         return id;
288 }
289
290 // place write, read, or parent lock on requested page_no.
291
292 BTERR bt_lockpage(BtDb *bt, uid page_no, BtLock mode)
293 {
294 off64_t off = page_no << bt->page_bits;
295 #ifdef unix
296 int flag = PROT_READ | ( bt->mode == BT_ro ? 0 : PROT_WRITE );
297 struct flock lock[1];
298 #else
299 uint flags = 0, len;
300 OVERLAPPED ovl[1];
301 #endif
302
303         if( mode == BtLockRead || mode == BtLockWrite )
304                 off +=  sizeof(*bt->page);      // use second segment
305
306         if( mode == BtLockParent )
307                 off +=  2 * sizeof(*bt->page);  // use third segment
308
309 #ifdef unix
310         memset (lock, 0, sizeof(lock));
311
312         lock->l_start = off;
313         lock->l_type = (mode == BtLockDelete || mode == BtLockWrite || mode == BtLockParent) ? F_WRLCK : F_RDLCK;
314         lock->l_len = sizeof(*bt->page);
315         lock->l_whence = 0;
316
317         if( fcntl (bt->idx, F_SETLKW, lock) < 0 )
318                 return bt->err = BTERR_lock;
319
320         return 0;
321 #else
322         memset (ovl, 0, sizeof(ovl));
323         ovl->OffsetHigh = (uint)(off >> 32);
324         ovl->Offset = (uint)off;
325         len = sizeof(*bt->page);
326
327         //      use large offsets to
328         //      simulate advisory locking
329
330         ovl->OffsetHigh |= 0x80000000;
331
332         if( mode == BtLockDelete || mode == BtLockWrite || mode == BtLockParent )
333                 flags |= LOCKFILE_EXCLUSIVE_LOCK;
334
335         if( LockFileEx (bt->idx, flags, 0, len, 0L, ovl) )
336                 return bt->err = 0;
337
338         return bt->err = BTERR_lock;
339 #endif 
340 }
341
342 // remove write, read, or parent lock on requested page_no.
343
344 BTERR bt_unlockpage(BtDb *bt, uid page_no, BtLock mode)
345 {
346 off64_t off = page_no << bt->page_bits;
347 #ifdef unix
348 struct flock lock[1];
349 #else
350 OVERLAPPED ovl[1];
351 uint len;
352 #endif
353
354         if( mode == BtLockRead || mode == BtLockWrite )
355                 off +=  sizeof(*bt->page);      // use second segment
356
357         if( mode == BtLockParent )
358                 off +=  2 * sizeof(*bt->page);  // use third segment
359
360 #ifdef unix
361         memset (lock, 0, sizeof(lock));
362
363         lock->l_start = off;
364         lock->l_type = F_UNLCK;
365         lock->l_len = sizeof(*bt->page);
366         lock->l_whence = 0;
367
368         if( fcntl (bt->idx, F_SETLK, lock) < 0 )
369                 return bt->err = BTERR_lock;
370 #else
371         memset (ovl, 0, sizeof(ovl));
372         ovl->OffsetHigh = (uint)(off >> 32);
373         ovl->Offset = (uint)off;
374         len = sizeof(*bt->page);
375
376         //      use large offsets to
377         //      simulate advisory locking
378
379         ovl->OffsetHigh |= 0x80000000;
380
381         if( !UnlockFileEx (bt->idx, 0, len, 0, ovl) )
382                 return GetLastError(), bt->err = BTERR_lock;
383 #endif
384
385         return bt->err = 0;
386 }
387
388 //      close and release memory
389
390 void bt_close (BtDb *bt)
391 {
392 BtHash *hash;
393 #ifdef unix
394         // release mapped pages
395
396         if( hash = bt->lrufirst )
397                 do munmap (hash->page, (bt->hashmask+1) << bt->page_bits);
398                 while(hash = hash->lrunext);
399
400         if( bt->mem )
401                 free (bt->mem);
402         close (bt->idx);
403         free (bt->cache);
404         free (bt);
405 #else
406         if( hash = bt->lrufirst )
407           do
408           {
409                 FlushViewOfFile(hash->page, 0);
410                 UnmapViewOfFile(hash->page);
411                 CloseHandle(hash->hmap);
412           } while(hash = hash->lrunext);
413
414         if( bt->mem)
415                 VirtualFree (bt->mem, 0, MEM_RELEASE);
416         FlushFileBuffers(bt->idx);
417         CloseHandle(bt->idx);
418         GlobalFree (bt->cache);
419         GlobalFree (bt);
420 #endif
421 }
422
423 //  open/create new btree
424 //      call with file_name, BT_openmode, bits in page size (e.g. 16),
425 //              size of mapped page cache (e.g. 8192) or zero for no mapping.
426
427 BtDb *bt_open (char *name, uint mode, uint bits, uint nodemax, uint pgblk)
428 {
429 uint lvl, attr, cacheblk, last;
430 BtLock lockmode = BtLockWrite;
431 BtPage alloc;
432 off64_t size;
433 uint amt[1];
434 BtKey key;
435 BtDb* bt;
436
437 #ifndef unix
438 SYSTEM_INFO sysinfo[1];
439 #endif
440
441 #ifdef unix
442         bt = malloc (sizeof(BtDb) + nodemax * sizeof(BtHash));
443         memset (bt, 0, sizeof(BtDb));
444
445         switch (mode & 0x7fff)
446         {
447         case BT_fl:
448         case BT_rw:
449                 bt->idx = open ((char*)name, O_RDWR | O_CREAT, 0666);
450                 break;
451
452         case BT_ro:
453         default:
454                 bt->idx = open ((char*)name, O_RDONLY);
455                 lockmode = BtLockRead;
456                 break;
457         }
458         if( bt->idx == -1 )
459                 return free(bt), NULL;
460         
461         if( nodemax )
462                 cacheblk = 4096;        // page size for unix
463         else
464                 cacheblk = 0;
465
466 #else
467         bt = GlobalAlloc (GMEM_FIXED|GMEM_ZEROINIT, sizeof(BtDb) + nodemax * sizeof(BtHash));
468         attr = FILE_ATTRIBUTE_NORMAL;
469         switch (mode & 0x7fff)
470         {
471         case BT_fl:
472                 attr |= FILE_FLAG_WRITE_THROUGH | FILE_FLAG_NO_BUFFERING;
473
474         case BT_rw:
475                 bt->idx = CreateFile(name, GENERIC_READ| GENERIC_WRITE, FILE_SHARE_READ|FILE_SHARE_WRITE, NULL, OPEN_ALWAYS, attr, NULL);
476                 break;
477
478         case BT_ro:
479         default:
480                 bt->idx = CreateFile(name, GENERIC_READ, FILE_SHARE_READ|FILE_SHARE_WRITE, NULL, OPEN_EXISTING, attr, NULL);
481                 lockmode = BtLockRead;
482                 break;
483         }
484         if( bt->idx == INVALID_HANDLE_VALUE )
485                 return GlobalFree(bt), NULL;
486
487         // normalize cacheblk to multiple of sysinfo->dwAllocationGranularity
488         GetSystemInfo(sysinfo);
489
490         if( nodemax )
491                 cacheblk = sysinfo->dwAllocationGranularity;
492         else
493                 cacheblk = 0;
494 #endif
495
496         // determine sanity of page size
497
498         if( bits > BT_maxbits )
499                 bits = BT_maxbits;
500         else if( bits < BT_minbits )
501                 bits = BT_minbits;
502
503         if( bt_lockpage(bt, ALLOC_page, lockmode) )
504                 return bt_close (bt), NULL;
505
506 #ifdef unix
507         *amt = 0;
508
509         // read minimum page size to get root info
510
511         if( size = lseek (bt->idx, 0L, 2) ) {
512                 alloc = malloc (BT_minpage);
513                 pread(bt->idx, alloc, BT_minpage, 0);
514                 bits = alloc->bits;
515                 free (alloc);
516         } else if( mode == BT_ro )
517                 return bt_close (bt), NULL;
518 #else
519         size = GetFileSize(bt->idx, amt);
520
521         if( size || *amt ) {
522                 alloc = VirtualAlloc(NULL, BT_minpage, MEM_COMMIT, PAGE_READWRITE);
523                 if( !ReadFile(bt->idx, (char *)alloc, BT_minpage, amt, NULL) )
524                         return bt_close (bt), NULL;
525                 bits = alloc->bits;
526                 VirtualFree (alloc, 0, MEM_RELEASE);
527         } else if( mode == BT_ro )
528                 return bt_close (bt), NULL;
529 #endif
530
531         bt->page_size = 1 << bits;
532         bt->page_bits = bits;
533
534         bt->nodemax = nodemax;
535         bt->mode = mode;
536
537         // setup cache mapping
538
539         if( cacheblk ) {
540                 if( cacheblk < bt->page_size )
541                         cacheblk = bt->page_size;
542
543                 bt->hashsize = nodemax / 8;
544                 bt->hashmask = (cacheblk >> bits) - 1;
545                 bt->mapped_io = 1;
546         }
547
548         //      requested number of pages per memmap segment
549
550         if( cacheblk )
551           if( (1 << pgblk) > bt->hashmask )
552                 bt->hashmask = (1 << pgblk) - 1;
553
554         bt->seg_bits = 0;
555
556         while( (1 << bt->seg_bits) <= bt->hashmask )
557                 bt->seg_bits++;
558
559 #ifdef unix
560         bt->mem = malloc (6 *bt->page_size);
561         bt->cache = calloc (bt->hashsize, sizeof(ushort));
562 #else
563         bt->mem = VirtualAlloc(NULL, 6 * bt->page_size, MEM_COMMIT, PAGE_READWRITE);
564         bt->cache = GlobalAlloc (GMEM_FIXED|GMEM_ZEROINIT, bt->hashsize * sizeof(ushort));
565 #endif
566         bt->frame = (BtPage)bt->mem;
567         bt->cursor = (BtPage)(bt->mem + bt->page_size);
568         bt->page = (BtPage)(bt->mem + 2 * bt->page_size);
569         bt->alloc = (BtPage)(bt->mem + 3 * bt->page_size);
570         bt->temp = (BtPage)(bt->mem + 4 * bt->page_size);
571         bt->zero = (BtPage)(bt->mem + 5 * bt->page_size);
572
573         if( size || *amt ) {
574                 if( bt_unlockpage(bt, ALLOC_page, lockmode) )
575                         return bt_close (bt), NULL;
576
577                 return bt;
578         }
579
580         // initializes an empty b-tree with root page and page of leaves
581
582         memset (bt->alloc, 0, bt->page_size);
583         bt_putid(bt->alloc->right, MIN_lvl+1);
584         bt->alloc->bits = bt->page_bits;
585
586 #ifdef unix
587         if( write (bt->idx, bt->alloc, bt->page_size) < bt->page_size )
588                 return bt_close (bt), NULL;
589 #else
590         if( !WriteFile (bt->idx, (char *)bt->alloc, bt->page_size, amt, NULL) )
591                 return bt_close (bt), NULL;
592
593         if( *amt < bt->page_size )
594                 return bt_close (bt), NULL;
595 #endif
596
597         memset (bt->frame, 0, bt->page_size);
598         bt->frame->bits = bt->page_bits;
599
600         for( lvl=MIN_lvl; lvl--; ) {
601                 slotptr(bt->frame, 1)->off = bt->page_size - 3;
602                 bt_putid(slotptr(bt->frame, 1)->id, lvl ? MIN_lvl - lvl + 1 : 0);               // next(lower) page number
603                 key = keyptr(bt->frame, 1);
604                 key->len = 2;                   // create stopper key
605                 key->key[0] = 0xff;
606                 key->key[1] = 0xff;
607                 bt->frame->min = bt->page_size - 3;
608                 bt->frame->lvl = lvl;
609                 bt->frame->cnt = 1;
610                 bt->frame->act = 1;
611 #ifdef unix
612                 if( write (bt->idx, bt->frame, bt->page_size) < bt->page_size )
613                         return bt_close (bt), NULL;
614 #else
615                 if( !WriteFile (bt->idx, (char *)bt->frame, bt->page_size, amt, NULL) )
616                         return bt_close (bt), NULL;
617
618                 if( *amt < bt->page_size )
619                         return bt_close (bt), NULL;
620 #endif
621         }
622
623         // create empty page area by writing last page of first
624         // cache area (other pages are zeroed by O/S)
625
626         if( bt->mapped_io && bt->hashmask ) {
627                 memset(bt->frame, 0, bt->page_size);
628                 last = bt->hashmask;
629
630                 while( last < MIN_lvl + 1 )
631                         last += bt->hashmask + 1;
632 #ifdef unix
633                 pwrite(bt->idx, bt->frame, bt->page_size, last << bt->page_bits);
634 #else
635                 SetFilePointer (bt->idx, last << bt->page_bits, NULL, FILE_BEGIN);
636                 if( !WriteFile (bt->idx, (char *)bt->frame, bt->page_size, amt, NULL) )
637                         return bt_close (bt), NULL;
638                 if( *amt < bt->page_size )
639                         return bt_close (bt), NULL;
640 #endif
641         }
642
643         if( bt_unlockpage(bt, ALLOC_page, lockmode) )
644                 return bt_close (bt), NULL;
645
646         return bt;
647 }
648
649 //  compare two keys, returning > 0, = 0, or < 0
650 //  as the comparison value
651
652 int keycmp (BtKey key1, unsigned char *key2, uint len2)
653 {
654 uint len1 = key1->len;
655 int ans;
656
657         if( ans = memcmp (key1->key, key2, len1 > len2 ? len2 : len1) )
658                 return ans;
659
660         if( len1 > len2 )
661                 return 1;
662         if( len1 < len2 )
663                 return -1;
664
665         return 0;
666 }
667
668 //  Update current page of btree by writing file contents
669 //      or flushing mapped area to disk.
670
671 BTERR bt_update (BtDb *bt, BtPage page, uid page_no)
672 {
673 off64_t off = page_no << bt->page_bits;
674
675 #ifdef unix
676     if( !bt->mapped_io )
677          if( pwrite(bt->idx, page, bt->page_size, off) != bt->page_size )
678                  return bt->err = BTERR_wrt;
679 #else
680 uint amt[1];
681         if( !bt->mapped_io )
682         {
683                 SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN);
684                 if( !WriteFile (bt->idx, (char *)page, bt->page_size, amt, NULL) )
685                         return GetLastError(), bt->err = BTERR_wrt;
686
687                 if( *amt < bt->page_size )
688                         return GetLastError(), bt->err = BTERR_wrt;
689         } 
690         else if( bt->mode == BT_fl ) {
691                         FlushViewOfFile(page, bt->page_size);
692                         FlushFileBuffers(bt->idx);
693         }
694 #endif
695         return 0;
696 }
697
698 // find page in cache 
699
700 BtHash *bt_findhash(BtDb *bt, uid page_no)
701 {
702 BtHash *hash;
703 uint idx;
704
705         // compute cache block first page and hash idx 
706
707         page_no &= ~bt->hashmask;
708         idx = (uint)(page_no >> bt->seg_bits) % bt->hashsize;
709
710         if( bt->cache[idx] ) 
711                 hash = bt->nodes + bt->cache[idx];
712         else
713                 return NULL;
714
715         do if( hash->page_no == page_no )
716                  break;
717         while(hash = hash->hashnext );
718
719         return hash;
720 }
721
722 // add page cache entry to hash index
723
724 void bt_linkhash(BtDb *bt, BtHash *node, uid page_no)
725 {
726 uint idx = (uint)(page_no >> bt->seg_bits) % bt->hashsize;
727 BtHash *hash;
728
729         if( bt->cache[idx] ) {
730                 node->hashnext = hash = bt->nodes + bt->cache[idx];
731                 hash->hashprev = node;
732         }
733
734         node->hashprev = NULL;
735         bt->cache[idx] = (ushort)(node - bt->nodes);
736 }
737
738 // remove cache entry from hash table
739
740 void bt_unlinkhash(BtDb *bt, BtHash *node)
741 {
742 uint idx = (uint)(node->page_no >> bt->seg_bits) % bt->hashsize;
743 BtHash *hash;
744
745         // unlink node
746         if( hash = node->hashprev )
747                 hash->hashnext = node->hashnext;
748         else if( hash = node->hashnext )
749                 bt->cache[idx] = (ushort)(hash - bt->nodes);
750         else
751                 bt->cache[idx] = 0;
752
753         if( hash = node->hashnext )
754                 hash->hashprev = node->hashprev;
755 }
756
757 // add cache page to lru chain and map pages
758
759 BtPage bt_linklru(BtDb *bt, BtHash *hash, uid page_no)
760 {
761 int flag;
762 off64_t off = (page_no & ~bt->hashmask) << bt->page_bits;
763 off64_t limit = off + ((bt->hashmask+1) << bt->page_bits);
764 BtHash *node;
765
766         memset(hash, 0, sizeof(BtHash));
767         hash->page_no = (page_no & ~bt->hashmask);
768         bt_linkhash(bt, hash, page_no);
769
770         if( node = hash->lrunext = bt->lrufirst )
771                 node->lruprev = hash;
772         else
773                 bt->lrulast = hash;
774
775         bt->lrufirst = hash;
776
777 #ifdef unix
778         flag = PROT_READ | ( bt->mode == BT_ro ? 0 : PROT_WRITE );
779         hash->page = (BtPage)mmap (0, (bt->hashmask+1) << bt->page_bits, flag, MAP_SHARED, bt->idx, off);
780         if( hash->page == MAP_FAILED )
781                 return bt->err = BTERR_map, (BtPage)NULL;
782
783 #else
784         flag = ( bt->mode == BT_ro ? PAGE_READONLY : PAGE_READWRITE );
785         hash->hmap = CreateFileMapping(bt->idx, NULL, flag,     (DWORD)(limit >> 32), (DWORD)limit, NULL);
786         if( !hash->hmap )
787                 return bt->err = BTERR_map, NULL;
788
789         flag = ( bt->mode == BT_ro ? FILE_MAP_READ : FILE_MAP_WRITE );
790         hash->page = MapViewOfFile(hash->hmap, flag, (DWORD)(off >> 32), (DWORD)off, (bt->hashmask+1) << bt->page_bits);
791         if( !hash->page )
792                 return bt->err = BTERR_map, NULL;
793 #endif
794
795         return (BtPage)((char*)hash->page + ((uint)(page_no & bt->hashmask) << bt->page_bits));
796 }
797
798 //      find or place requested page in page-cache
799 //      return memory address where page is located.
800
801 BtPage bt_hashpage(BtDb *bt, uid page_no)
802 {
803 BtHash *hash, *node, *next;
804 BtPage page;
805
806         // find page in cache and move to top of lru list  
807
808         if( hash = bt_findhash(bt, page_no) ) {
809                 page = (BtPage)((char*)hash->page + ((uint)(page_no & bt->hashmask) << bt->page_bits));
810                 // swap node in lru list
811                 if( node = hash->lruprev ) {
812                         if( next = node->lrunext = hash->lrunext )
813                                 next->lruprev = node;
814                         else
815                                 bt->lrulast = node;
816
817                         if( next = hash->lrunext = bt->lrufirst )
818                                 next->lruprev = hash;
819                         else
820                                 return bt->err = BTERR_hash, (BtPage)NULL;
821
822                         hash->lruprev = NULL;
823                         bt->lrufirst = hash;
824                 }
825                 return page;
826         }
827
828         // map pages and add to cache entry
829
830         if( bt->nodecnt < bt->nodemax ) {
831                 hash = bt->nodes + ++bt->nodecnt;
832                 return bt_linklru(bt, hash, page_no);
833         }
834
835         // hash table is already full, replace last lru entry from the cache
836
837         if( hash = bt->lrulast ) {
838                 // unlink from lru list
839                 if( node = bt->lrulast = hash->lruprev )
840                         node->lrunext = NULL;
841                 else
842                         return bt->err = BTERR_hash, (BtPage)NULL;
843
844 #ifdef unix
845                 munmap (hash->page, (bt->hashmask+1) << bt->page_bits);
846 #else
847                 FlushViewOfFile(hash->page, 0);
848                 UnmapViewOfFile(hash->page);
849                 CloseHandle(hash->hmap);
850 #endif
851                 // unlink from hash table
852
853                 bt_unlinkhash(bt, hash);
854
855                 // map and add to cache
856
857                 return bt_linklru(bt, hash, page_no);
858         }
859
860         return bt->err = BTERR_hash, (BtPage)NULL;
861 }
862
863 //  map a btree page onto current page
864
865 BTERR bt_mappage (BtDb *bt, BtPage *page, uid page_no)
866 {
867 off64_t off = page_no << bt->page_bits;
868 #ifndef unix
869 int amt[1];
870 #endif
871         
872         if( bt->mapped_io ) {
873                 bt->err = 0;
874                 *page = bt_hashpage(bt, page_no);
875                 return bt->err;
876         }
877 #ifdef unix
878         if( pread(bt->idx, *page, bt->page_size, off) < bt->page_size )
879                 return bt->err = BTERR_map;
880 #else
881         SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN);
882
883         if( !ReadFile(bt->idx, *page, bt->page_size, amt, NULL) )
884                 return bt->err = BTERR_map;
885
886         if( *amt <  bt->page_size )
887                 return bt->err = BTERR_map;
888 #endif
889         return 0;
890 }
891
892 //      deallocate a deleted page 
893 //      place on free chain out of allocator page
894
895 BTERR bt_freepage(BtDb *bt, uid page_no)
896 {
897         if( bt_mappage (bt, &bt->temp, page_no) )
898                 return bt->err;
899
900         //      lock allocation page
901
902         if( bt_lockpage(bt, ALLOC_page, BtLockWrite) )
903                 return bt->err;
904
905         if( bt_mappage (bt, &bt->alloc, ALLOC_page) )
906                 return bt->err;
907
908         //      store chain in second right
909         bt_putid(bt->temp->right, bt_getid(bt->alloc[1].right));
910         bt_putid(bt->alloc[1].right, page_no);
911         bt->temp->free = 1;
912
913         if( bt_update(bt, bt->alloc, ALLOC_page) )
914                 return bt->err;
915         if( bt_update(bt, bt->temp, page_no) )
916                 return bt->err;
917
918         // unlock page zero 
919
920         if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
921                 return bt->err;
922
923         //  remove write lock on deleted node
924
925         if( bt_unlockpage(bt, page_no, BtLockWrite) )
926                 return bt->err;
927
928         //  remove delete lock on deleted node
929
930         if( bt_unlockpage(bt, page_no, BtLockDelete) )
931                 return bt->err;
932
933         return 0;
934 }
935
936 //      allocate a new page and write page into it
937
938 uid bt_newpage(BtDb *bt, BtPage page)
939 {
940 uid new_page;
941 char *pmap;
942 int reuse;
943
944         // lock page zero
945
946         if( bt_lockpage(bt, ALLOC_page, BtLockWrite) )
947                 return 0;
948
949         if( bt_mappage (bt, &bt->alloc, ALLOC_page) )
950                 return 0;
951
952         // use empty chain first
953         // else allocate empty page
954
955         if( new_page = bt_getid(bt->alloc[1].right) ) {
956                 if( bt_mappage (bt, &bt->temp, new_page) )
957                         return 0;       // don't unlock on error
958                 bt_putid(bt->alloc[1].right, bt_getid(bt->temp->right));
959                 reuse = 1;
960         } else {
961                 new_page = bt_getid(bt->alloc->right);
962                 bt_putid(bt->alloc->right, new_page+1);
963                 reuse = 0;
964         }
965
966         if( bt_update(bt, bt->alloc, ALLOC_page) )
967                 return 0;       // don't unlock on error
968
969         if( !bt->mapped_io ) {
970                 if( bt_update(bt, page, new_page) )
971                         return 0;       //don't unlock on error
972
973                 // unlock page zero 
974
975                 if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
976                         return 0;
977
978                 return new_page;
979         }
980
981 #ifdef unix
982         if( pwrite(bt->idx, page, bt->page_size, new_page << bt->page_bits) < bt->page_size )
983                 return bt->err = BTERR_wrt, 0;
984
985         // if writing first page of hash block, zero last page in the block
986
987         if( !reuse && bt->hashmask > 0 && (new_page & bt->hashmask) == 0 )
988         {
989                 // use temp buffer to write zeros
990                 memset(bt->zero, 0, bt->page_size);
991                 if( pwrite(bt->idx,bt->zero, bt->page_size, (new_page | bt->hashmask) << bt->page_bits) < bt->page_size )
992                         return bt->err = BTERR_wrt, 0;
993         }
994 #else
995         //      bring new page into page-cache and copy page.
996         //      this will extend the file into the new pages.
997
998         if( !(pmap = (char*)bt_hashpage(bt, new_page & ~bt->hashmask)) )
999                 return 0;
1000
1001         memcpy(pmap+((new_page & bt->hashmask) << bt->page_bits), page, bt->page_size);
1002 #endif
1003
1004         // unlock page zero 
1005
1006         if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) )
1007                 return 0;
1008
1009         return new_page;
1010 }
1011
1012 //  find slot in page for given key at a given level
1013
1014 int bt_findslot (BtDb *bt, unsigned char *key, uint len)
1015 {
1016 uint diff, higher = bt->page->cnt, low = 1, slot;
1017 uint good = 0;
1018
1019         //      make stopper key an infinite fence value
1020
1021         if( bt_getid (bt->page->right) )
1022                 higher++;
1023         else
1024                 good++;
1025
1026         //      low is the lowest candidate, higher is already
1027         //      tested as .ge. the given key, loop ends when they meet
1028
1029         while( diff = higher - low ) {
1030                 slot = low + ( diff >> 1 );
1031                 if( keycmp (keyptr(bt->page, slot), key, len) < 0 )
1032                         low = slot + 1;
1033                 else
1034                         higher = slot, good++;
1035         }
1036
1037         //      return zero if key is on right link page
1038
1039         return good ? higher : 0;
1040 }
1041
1042 //  find and load page at given level for given key
1043 //      leave page rd or wr locked as requested
1044
1045 int bt_loadpage (BtDb *bt, unsigned char *key, uint len, uint lvl, uint lock)
1046 {
1047 uid page_no = ROOT_page, prevpage = 0;
1048 uint drill = 0xff, slot;
1049 uint mode, prevmode;
1050
1051   //  start at root of btree and drill down
1052
1053   do {
1054         // determine lock mode of drill level
1055         mode = (lock == BtLockWrite) && (drill == lvl) ? BtLockWrite : BtLockRead; 
1056
1057         bt->page_no = page_no;
1058
1059         // obtain access lock using lock chaining
1060
1061         if( page_no > ROOT_page )
1062           if( bt_lockpage(bt, bt->page_no, BtLockAccess) )
1063                 return 0;                                                                       
1064
1065         if( prevpage )
1066           if( bt_unlockpage(bt, prevpage, prevmode) )
1067                 return 0;
1068
1069         // obtain read lock using lock chaining
1070
1071         if( bt_lockpage(bt, bt->page_no, mode) )
1072                 return 0;                                                                       
1073
1074         if( page_no > ROOT_page )
1075           if( bt_unlockpage(bt, bt->page_no, BtLockAccess) )
1076                 return 0;                                                                       
1077
1078         //      map/obtain page contents
1079
1080         if( bt_mappage (bt, &bt->page, page_no) )
1081                 return 0;
1082
1083         // re-read and re-lock root after determining actual level of root
1084
1085         if( bt->page->lvl != drill) {
1086                 if( bt->page_no != ROOT_page )
1087                         return bt->err = BTERR_struct, 0;
1088                         
1089                 drill = bt->page->lvl;
1090
1091                 if( lock != BtLockRead && drill == lvl )
1092                   if( bt_unlockpage(bt, page_no, mode) )
1093                         return 0;
1094                   else
1095                         continue;
1096         }
1097
1098         prevpage = bt->page_no;
1099         prevmode = mode;
1100
1101         //  find key on page at this level
1102         //  and descend to requested level
1103
1104         if( !bt->page->kill )
1105          if( slot = bt_findslot (bt, key, len) ) {
1106           if( drill == lvl )
1107                 return slot;
1108
1109           while( slotptr(bt->page, slot)->dead )
1110                 if( slot++ < bt->page->cnt )
1111                         continue;
1112                 else
1113                         goto slideright;
1114
1115           page_no = bt_getid(slotptr(bt->page, slot)->id);
1116           drill--;
1117           continue;
1118          }
1119
1120         //  or slide right into next page
1121
1122 slideright:
1123         page_no = bt_getid(bt->page->right);
1124
1125   } while( page_no );
1126
1127   // return error on end of right chain
1128
1129   bt->err = BTERR_struct;
1130   return 0;     // return error
1131 }
1132
1133 //      a fence key was deleted from a page
1134 //      push new fence value upwards
1135
1136 BTERR bt_fixfence (BtDb *bt, uid page_no, uint lvl)
1137 {
1138 unsigned char leftkey[256], rightkey[256];
1139 BtKey ptr;
1140
1141         // remove deleted key, the old fence value
1142
1143         ptr = keyptr(bt->page, bt->page->cnt);
1144         memcpy(rightkey, ptr, ptr->len + 1);
1145
1146         memset (slotptr(bt->page, bt->page->cnt--), 0, sizeof(BtSlot));
1147         bt->page->dirty = 1;
1148
1149         ptr = keyptr(bt->page, bt->page->cnt);
1150         memcpy(leftkey, ptr, ptr->len + 1);
1151
1152         if( bt_update (bt, bt->page, page_no) )
1153                 return bt->err;
1154
1155         if( bt_lockpage (bt, page_no, BtLockParent) )
1156                 return bt->err;
1157
1158         if( bt_unlockpage (bt, page_no, BtLockWrite) )
1159                 return bt->err;
1160
1161         //  insert new (now smaller) fence key
1162
1163         if( bt_insertkey (bt, leftkey+1, *leftkey, lvl + 1, page_no, time(NULL)) )
1164                 return bt->err;
1165
1166         //  remove old (larger) fence key
1167
1168         if( bt_deletekey (bt, rightkey+1, *rightkey, lvl + 1) )
1169                 return bt->err;
1170
1171         return bt_unlockpage (bt, page_no, BtLockParent);
1172 }
1173
1174 //      root has a single child
1175 //      collapse a level from the btree
1176 //      call with root locked in bt->page
1177
1178 BTERR bt_collapseroot (BtDb *bt, BtPage root)
1179 {
1180 uid child;
1181 uint idx;
1182
1183         // find the child entry
1184         //      and promote to new root
1185
1186   do {
1187         for( idx = 0; idx++ < root->cnt; )
1188           if( !slotptr(root, idx)->dead )
1189                 break;
1190
1191         child = bt_getid (slotptr(root, idx)->id);
1192
1193         if( bt_lockpage (bt, child, BtLockDelete) )
1194                 return bt->err;
1195
1196         if( bt_lockpage (bt, child, BtLockWrite) )
1197                 return bt->err;
1198
1199         if( bt_mappage (bt, &bt->temp, child) )
1200                 return bt->err;
1201
1202         memcpy (root, bt->temp, bt->page_size);
1203
1204         if( bt_update (bt, root, ROOT_page) )
1205                 return bt->err;
1206
1207         if( bt_freepage (bt, child) )
1208                 return bt->err;
1209
1210   } while( root->lvl > 1 && root->act == 1 );
1211
1212   return bt_unlockpage (bt, ROOT_page, BtLockWrite);
1213 }
1214
1215 //  find and delete key on page by marking delete flag bit
1216 //  when page becomes empty, delete it
1217
1218 BTERR bt_deletekey (BtDb *bt, unsigned char *key, uint len, uint lvl)
1219 {
1220 unsigned char lowerkey[256], higherkey[256];
1221 uint slot, dirty = 0, idx, fence, found;
1222 uid page_no, right;
1223 BtKey ptr;
1224
1225         if( slot = bt_loadpage (bt, key, len, lvl, BtLockWrite) )
1226                 ptr = keyptr(bt->page, slot);
1227         else
1228                 return bt->err;
1229
1230         // are we deleting a fence slot?
1231
1232         fence = slot == bt->page->cnt;
1233
1234         // if key is found delete it, otherwise ignore request
1235
1236         if( found = !keycmp (ptr, key, len) )
1237           if( found = slotptr(bt->page, slot)->dead == 0 ) {
1238                 dirty = slotptr(bt->page,slot)->dead = 1;
1239                 bt->page->dirty = 1;
1240                 bt->page->act--;
1241
1242                 // collapse empty slots
1243
1244                 while( idx = bt->page->cnt - 1 )
1245                   if( slotptr(bt->page, idx)->dead ) {
1246                         *slotptr(bt->page, idx) = *slotptr(bt->page, idx + 1);
1247                         memset (slotptr(bt->page, bt->page->cnt--), 0, sizeof(BtSlot));
1248                   } else
1249                         break;
1250           }
1251
1252         right = bt_getid(bt->page->right);
1253         page_no = bt->page_no;
1254
1255         //      did we delete a fence key in an upper level?
1256
1257         if( dirty && lvl && bt->page->act && fence )
1258           if( bt_fixfence (bt, page_no, lvl) )
1259                 return bt->err;
1260           else
1261                 return bt->found = found, 0;
1262
1263         //      is this a collapsed root?
1264
1265         if( lvl > 1 && page_no == ROOT_page && bt->page->act == 1 )
1266           if( bt_collapseroot (bt, bt->page) )
1267                 return bt->err;
1268           else
1269                 return bt->found = found, 0;
1270
1271         // return if page is not empty
1272
1273         if( bt->page->act ) {
1274           if( dirty && bt_update(bt, bt->page, page_no) )
1275                 return bt->err;
1276           if( bt_unlockpage(bt, page_no, BtLockWrite) )
1277                 return bt->err;
1278           return bt->found = found, 0;
1279         }
1280
1281         // cache copy of fence key
1282         //      in order to find parent
1283
1284         ptr = keyptr(bt->page, bt->page->cnt);
1285         memcpy(lowerkey, ptr, ptr->len + 1);
1286
1287         // obtain lock on right page
1288
1289         if( bt_lockpage(bt, right, BtLockWrite) )
1290                 return bt->err;
1291
1292         if( bt_mappage (bt, &bt->temp, right) )
1293                 return bt->err;
1294
1295         if( bt->temp->kill )
1296                 return bt->err = BTERR_struct;
1297
1298         // pull contents of next page into current empty page 
1299
1300         memcpy (bt->page, bt->temp, bt->page_size);
1301
1302         //      cache copy of key to update
1303
1304         ptr = keyptr(bt->temp, bt->temp->cnt);
1305         memcpy(higherkey, ptr, ptr->len + 1);
1306
1307         //  Mark right page as deleted and point it to left page
1308         //      until we can post updates at higher level.
1309
1310         bt_putid(bt->temp->right, page_no);
1311         bt->temp->kill = 1;
1312
1313         if( bt_update(bt, bt->page, page_no) )
1314                 return bt->err;
1315
1316         if( bt_update(bt, bt->temp, right) )
1317                 return bt->err;
1318
1319         if( bt_lockpage(bt, page_no, BtLockParent) )
1320                 return bt->err;
1321
1322         if( bt_unlockpage(bt, page_no, BtLockWrite) )
1323                 return bt->err;
1324
1325         if( bt_lockpage(bt, right, BtLockParent) )
1326                 return bt->err;
1327
1328         if( bt_unlockpage(bt, right, BtLockWrite) )
1329                 return bt->err;
1330
1331         //  redirect higher key directly to consolidated node
1332
1333         if( bt_insertkey (bt, higherkey+1, *higherkey, lvl+1, page_no, time(NULL)) )
1334                 return bt->err;
1335
1336         //  delete old lower key to consolidated node
1337
1338         if( bt_deletekey (bt, lowerkey + 1, *lowerkey, lvl + 1) )
1339                 return bt->err;
1340
1341         //  obtain write & delete lock on deleted node
1342         //      add right block to free chain
1343
1344         if( bt_lockpage(bt, right, BtLockDelete) )
1345                 return bt->err;
1346
1347         if( bt_lockpage(bt, right, BtLockWrite) )
1348                 return bt->err;
1349
1350         if( bt_freepage (bt, right) )
1351                 return bt->err;
1352
1353         //      remove ParentModify locks
1354
1355         if( bt_unlockpage(bt, right, BtLockParent) )
1356                 return bt->err;
1357
1358         return bt_unlockpage(bt, page_no, BtLockParent);
1359 }
1360
1361 //      find key in leaf level and return row-id
1362
1363 uid bt_findkey (BtDb *bt, unsigned char *key, uint len)
1364 {
1365 uint  slot;
1366 BtKey ptr;
1367 uid id;
1368
1369         if( slot = bt_loadpage (bt, key, len, 0, BtLockRead) )
1370                 ptr = keyptr(bt->page, slot);
1371         else
1372                 return 0;
1373
1374         // if key exists, return row-id
1375         //      otherwise return 0
1376
1377         if( ptr->len == len && !memcmp (ptr->key, key, len) )
1378                 id = bt_getid(slotptr(bt->page,slot)->id);
1379         else
1380                 id = 0;
1381
1382         if( bt_unlockpage(bt, bt->page_no, BtLockRead) )
1383                 return 0;
1384
1385         return id;
1386 }
1387
1388 //      check page for space available,
1389 //      clean if necessary and return
1390 //      0 - page needs splitting
1391 //      >0 - go ahead with new slot
1392  
1393 uint bt_cleanpage(BtDb *bt, uint amt, uint slot)
1394 {
1395 uint nxt = bt->page_size;
1396 BtPage page = bt->page;
1397 uint cnt = 0, idx = 0;
1398 uint max = page->cnt;
1399 uint newslot = slot;
1400 BtKey key;
1401 int ret;
1402
1403         if( page->min >= (max+1) * sizeof(BtSlot) + sizeof(*page) + amt + 1 )
1404                 return slot;
1405
1406         //      skip cleanup if nothing to reclaim
1407
1408         if( !page->dirty )
1409                 return 0;
1410
1411         memcpy (bt->frame, page, bt->page_size);
1412
1413         // skip page info and set rest of page to zero
1414
1415         memset (page+1, 0, bt->page_size - sizeof(*page));
1416         page->act = 0;
1417
1418         while( cnt++ < max ) {
1419                 if( cnt == slot )
1420                         newslot = idx + 1;
1421                 // always leave fence key in list
1422                 if( cnt < max && slotptr(bt->frame,cnt)->dead )
1423                         continue;
1424
1425                 // copy key
1426                 key = keyptr(bt->frame, cnt);
1427                 nxt -= key->len + 1;
1428                 memcpy ((unsigned char *)page + nxt, key, key->len + 1);
1429
1430                 // copy slot
1431                 memcpy(slotptr(page, ++idx)->id, slotptr(bt->frame, cnt)->id, BtId);
1432                 if( !(slotptr(page, idx)->dead = slotptr(bt->frame, cnt)->dead) )
1433                         page->act++;
1434                 slotptr(page, idx)->tod = slotptr(bt->frame, cnt)->tod;
1435                 slotptr(page, idx)->off = nxt;
1436         }
1437
1438         page->min = nxt;
1439         page->cnt = idx;
1440
1441         if( page->min >= (max+1) * sizeof(BtSlot) + sizeof(*page) + amt + 1 )
1442                 return newslot;
1443
1444         return 0;
1445 }
1446
1447 // split the root and raise the height of the btree
1448
1449 BTERR bt_splitroot(BtDb *bt, unsigned char *leftkey, uid page_no2)
1450 {
1451 uint nxt = bt->page_size;
1452 BtPage root = bt->page;
1453 uid right;
1454
1455         //  Obtain an empty page to use, and copy the current
1456         //  root contents into it
1457
1458         if( !(right = bt_newpage(bt, root)) )
1459                 return bt->err;
1460
1461         // preserve the page info at the bottom
1462         // and set rest to zero
1463
1464         memset(root+1, 0, bt->page_size - sizeof(*root));
1465
1466         // insert first key on newroot page
1467
1468         nxt -= *leftkey + 1;
1469         memcpy ((unsigned char *)root + nxt, leftkey, *leftkey + 1);
1470         bt_putid(slotptr(root, 1)->id, right);
1471         slotptr(root, 1)->off = nxt;
1472         
1473         // insert second key on newroot page
1474         // and increase the root height
1475
1476         nxt -= 3;
1477         ((unsigned char *)root)[nxt] = 2;
1478         ((unsigned char *)root)[nxt+1] = 0xff;
1479         ((unsigned char *)root)[nxt+2] = 0xff;
1480         bt_putid(slotptr(root, 2)->id, page_no2);
1481         slotptr(root, 2)->off = nxt;
1482
1483         bt_putid(root->right, 0);
1484         root->min = nxt;                // reset lowest used offset and key count
1485         root->cnt = 2;
1486         root->act = 2;
1487         root->lvl++;
1488
1489         // update and release root (bt->page)
1490
1491         if( bt_update(bt, root, bt->page_no) )
1492                 return bt->err;
1493
1494         return bt_unlockpage(bt, bt->page_no, BtLockWrite);
1495 }
1496
1497 //  split already locked full node
1498 //      return unlocked.
1499
1500 BTERR bt_splitpage (BtDb *bt)
1501 {
1502 uint cnt = 0, idx = 0, max, nxt = bt->page_size;
1503 unsigned char fencekey[256], rightkey[256];
1504 uid page_no = bt->page_no, right;
1505 BtPage page = bt->page;
1506 uint lvl = page->lvl;
1507 BtKey key;
1508
1509         //  split higher half of keys to bt->frame
1510         //      the last key (fence key) might be dead
1511
1512         memset (bt->frame, 0, bt->page_size);
1513         max = page->cnt;
1514         cnt = max / 2;
1515         idx = 0;
1516
1517         while( cnt++ < max ) {
1518                 key = keyptr(page, cnt);
1519                 nxt -= key->len + 1;
1520                 memcpy ((unsigned char *)bt->frame + nxt, key, key->len + 1);
1521                 memcpy(slotptr(bt->frame,++idx)->id, slotptr(page,cnt)->id, BtId);
1522                 if( !(slotptr(bt->frame, idx)->dead = slotptr(page, cnt)->dead) )
1523                         bt->frame->act++;
1524                 slotptr(bt->frame, idx)->tod = slotptr(page, cnt)->tod;
1525                 slotptr(bt->frame, idx)->off = nxt;
1526         }
1527
1528         //      remember fence key for new right page
1529
1530         memcpy (rightkey, key, key->len + 1);
1531
1532         bt->frame->bits = bt->page_bits;
1533         bt->frame->min = nxt;
1534         bt->frame->cnt = idx;
1535         bt->frame->lvl = lvl;
1536
1537         // link right node
1538
1539         if( page_no > ROOT_page )
1540                 memcpy (bt->frame->right, page->right, BtId);
1541
1542         //      get new free page and write frame to it.
1543
1544         if( !(right = bt_newpage(bt, bt->frame)) )
1545                 return bt->err;
1546
1547         //      update lower keys to continue in old page
1548
1549         memcpy (bt->frame, page, bt->page_size);
1550         memset (page+1, 0, bt->page_size - sizeof(*page));
1551         nxt = bt->page_size;
1552         page->dirty = 0;
1553         page->act = 0;
1554         cnt = 0;
1555         idx = 0;
1556
1557         //  assemble page of smaller keys
1558         //      (they're all active keys)
1559
1560         while( cnt++ < max / 2 ) {
1561                 key = keyptr(bt->frame, cnt);
1562                 nxt -= key->len + 1;
1563                 memcpy ((unsigned char *)page + nxt, key, key->len + 1);
1564                 memcpy(slotptr(page,++idx)->id, slotptr(bt->frame,cnt)->id, BtId);
1565                 slotptr(page, idx)->tod = slotptr(bt->frame, cnt)->tod;
1566                 slotptr(page, idx)->off = nxt;
1567                 page->act++;
1568         }
1569
1570         // remember fence key for smaller page
1571
1572         memcpy (fencekey, key, key->len + 1);
1573
1574         bt_putid(page->right, right);
1575         page->min = nxt;
1576         page->cnt = idx;
1577
1578         // if current page is the root page, split it
1579
1580         if( page_no == ROOT_page )
1581                 return bt_splitroot (bt, fencekey, right);
1582
1583         //      lock right page
1584
1585         if( bt_lockpage (bt, right, BtLockParent) )
1586                 return bt->err;
1587
1588         // update left (containing) node
1589
1590         if( bt_update(bt, page, page_no) )
1591                 return bt->err;
1592
1593         if( bt_lockpage (bt, page_no, BtLockParent) )
1594                 return bt->err;
1595
1596         if( bt_unlockpage (bt, page_no, BtLockWrite) )
1597                 return bt->err;
1598
1599         // insert new fence for reformulated left block
1600
1601         if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, page_no, time(NULL)) )
1602                 return bt->err;
1603
1604         //      switch fence for right block of larger keys to new right page
1605
1606         if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right, time(NULL)) )
1607                 return bt->err;
1608
1609         if( bt_unlockpage (bt, page_no, BtLockParent) )
1610                 return bt->err;
1611
1612         return bt_unlockpage (bt, right, BtLockParent);
1613 }
1614
1615 //  Insert new key into the btree at requested level.
1616 //  Level zero pages are leaf pages and are unlocked at exit.
1617 //      Interior nodes remain locked.
1618
1619 BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)
1620 {
1621 uint slot, idx;
1622 BtPage page;
1623 BtKey ptr;
1624
1625   while( 1 ) {
1626         if( slot = bt_loadpage (bt, key, len, lvl, BtLockWrite) )
1627                 ptr = keyptr(bt->page, slot);
1628         else
1629         {
1630                 if( !bt->err )
1631                         bt->err = BTERR_ovflw;
1632                 return bt->err;
1633         }
1634
1635         // if key already exists, update id and return
1636
1637         page = bt->page;
1638
1639         if( !keycmp (ptr, key, len) ) {
1640           if( slotptr(page, slot)->dead )
1641                 page->act++;
1642           slotptr(page, slot)->dead = 0;
1643           slotptr(page, slot)->tod = tod;
1644           bt_putid(slotptr(page,slot)->id, id);
1645           if( bt_update(bt, bt->page, bt->page_no) )
1646                 return bt->err;
1647           return bt_unlockpage(bt, bt->page_no, BtLockWrite);
1648         }
1649
1650         // check if page has enough space
1651
1652         if( slot = bt_cleanpage (bt, len, slot) )
1653                 break;
1654
1655         if( bt_splitpage (bt) )
1656                 return bt->err;
1657   }
1658
1659   // calculate next available slot and copy key into page
1660
1661   page->min -= len + 1; // reset lowest used offset
1662   ((unsigned char *)page)[page->min] = len;
1663   memcpy ((unsigned char *)page + page->min +1, key, len );
1664
1665   for( idx = slot; idx < page->cnt; idx++ )
1666         if( slotptr(page, idx)->dead )
1667                 break;
1668
1669   // now insert key into array before slot
1670   // preserving the fence slot
1671
1672   if( idx == page->cnt )
1673         idx++, page->cnt++;
1674
1675   page->act++;
1676
1677   while( idx > slot )
1678         *slotptr(page, idx) = *slotptr(page, idx -1), idx--;
1679
1680   bt_putid(slotptr(page,slot)->id, id);
1681   slotptr(page, slot)->off = page->min;
1682   slotptr(page, slot)->tod = tod;
1683   slotptr(page, slot)->dead = 0;
1684
1685   if( bt_update(bt, bt->page, bt->page_no) )
1686           return bt->err;
1687
1688   return bt_unlockpage(bt, bt->page_no, BtLockWrite);
1689 }
1690
1691 //  cache page of keys into cursor and return starting slot for given key
1692
1693 uint bt_startkey (BtDb *bt, unsigned char *key, uint len)
1694 {
1695 uint slot;
1696
1697         // cache page for retrieval
1698
1699         if( slot = bt_loadpage (bt, key, len, 0, BtLockRead) )
1700           memcpy (bt->cursor, bt->page, bt->page_size);
1701         else
1702           return 0;
1703
1704         bt->cursor_page = bt->page_no;
1705
1706         if( bt_unlockpage(bt, bt->page_no, BtLockRead) )
1707           return 0;
1708
1709         return slot;
1710 }
1711
1712 //  return next slot for cursor page
1713 //  or slide cursor right into next page
1714
1715 uint bt_nextkey (BtDb *bt, uint slot)
1716 {
1717 off64_t right;
1718
1719   do {
1720         right = bt_getid(bt->cursor->right);
1721
1722         while( slot++ < bt->cursor->cnt )
1723           if( slotptr(bt->cursor,slot)->dead )
1724                 continue;
1725           else if( right || (slot < bt->cursor->cnt))
1726                 return slot;
1727           else
1728                 break;
1729
1730         if( !right )
1731                 break;
1732
1733         bt->cursor_page = right;
1734
1735     if( bt_lockpage(bt, right, BtLockRead) )
1736                 return 0;
1737
1738         if( bt_mappage (bt, &bt->page, right) )
1739                 return 0;
1740
1741         memcpy (bt->cursor, bt->page, bt->page_size);
1742
1743         if( bt_unlockpage(bt, right, BtLockRead) )
1744                 return 0;
1745
1746         slot = 0;
1747
1748   } while( 1 );
1749
1750   return bt->err = 0;
1751 }
1752
1753 BtKey bt_key(BtDb *bt, uint slot)
1754 {
1755         return keyptr(bt->cursor, slot);
1756 }
1757
1758 uid bt_uid(BtDb *bt, uint slot)
1759 {
1760         return bt_getid(slotptr(bt->cursor,slot)->id);
1761 }
1762
1763 uint bt_tod(BtDb *bt, uint slot)
1764 {
1765         return slotptr(bt->cursor,slot)->tod;
1766 }
1767
1768
1769 #ifdef STANDALONE
1770
1771 #ifndef unix
1772 double getCpuTime(int type)
1773 {
1774 FILETIME crtime[1];
1775 FILETIME xittime[1];
1776 FILETIME systime[1];
1777 FILETIME usrtime[1];
1778 SYSTEMTIME timeconv[1];
1779 double ans = 0;
1780
1781         memset (timeconv, 0, sizeof(SYSTEMTIME));
1782
1783         switch( type ) {
1784         case 0:
1785                 GetSystemTimeAsFileTime (xittime);
1786                 FileTimeToSystemTime (xittime, timeconv);
1787                 ans = (double)timeconv->wDayOfWeek * 3600 * 24;
1788                 break;
1789         case 1:
1790                 GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime);
1791                 FileTimeToSystemTime (usrtime, timeconv);
1792                 break;
1793         case 2:
1794                 GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime);
1795                 FileTimeToSystemTime (systime, timeconv);
1796                 break;
1797         }
1798
1799         ans += (double)timeconv->wHour * 3600;
1800         ans += (double)timeconv->wMinute * 60;
1801         ans += (double)timeconv->wSecond;
1802         ans += (double)timeconv->wMilliseconds / 1000;
1803         return ans;
1804 }
1805 #else
1806 #include <time.h>
1807 #include <sys/resource.h>
1808
1809 double getCpuTime(int type)
1810 {
1811 struct rusage used[1];
1812 struct timeval tv[1];
1813
1814         switch( type ) {
1815         case 0:
1816                 gettimeofday(tv, NULL);
1817                 return (double)tv->tv_sec + (double)tv->tv_usec / 1000000;
1818
1819         case 1:
1820                 getrusage(RUSAGE_SELF, used);
1821                 return (double)used->ru_utime.tv_sec + (double)used->ru_utime.tv_usec / 1000000;
1822
1823         case 2:
1824                 getrusage(RUSAGE_SELF, used);
1825                 return (double)used->ru_stime.tv_sec + (double)used->ru_stime.tv_usec / 1000000;
1826         }
1827
1828         return 0;
1829 }
1830 #endif
1831
1832 //  standalone program to index file of keys
1833 //  then list them onto std-out
1834
1835 int main (int argc, char **argv)
1836 {
1837 uint slot, line = 0, off = 0, found = 0;
1838 int dead, ch, cnt = 0, bits = 12;
1839 unsigned char key[256];
1840 double done, start;
1841 uint pgblk = 0;
1842 float elapsed;
1843 time_t tod[1];
1844 uint scan = 0;
1845 uint len = 0;
1846 uint map = 0;
1847 uid page_no;
1848 BtKey ptr;
1849 BtDb *bt;
1850 FILE *in;
1851
1852         if( argc < 4 ) {
1853                 fprintf (stderr, "Usage: %s idx_file src_file Read/Write/Scan/Delete/Find [page_bits mapped_pool_segments pages_per_segment start_line_number]\n", argv[0]);
1854                 fprintf (stderr, "  page_bits: size of btree page in bits\n");
1855                 fprintf (stderr, "  mapped_pool_segments: size of buffer pool in segments\n");
1856                 fprintf (stderr, "  pages_per_segment: size of buffer pool segment in pages in bits\n");
1857                 exit(0);
1858         }
1859
1860         start = getCpuTime(0);
1861         time(tod);
1862
1863         if( argc > 4 )
1864                 bits = atoi(argv[4]);
1865
1866         if( argc > 5 )
1867                 map = atoi(argv[5]);
1868
1869         if( map > 65536 )
1870                 fprintf (stderr, "Warning: buffer_pool > 65536 segments\n");
1871
1872         if( map && map < 8 )
1873                 fprintf (stderr, "Buffer_pool too small\n");
1874
1875         if( argc > 6 )
1876                 pgblk = atoi(argv[6]);
1877
1878         if( bits + pgblk > 30 )
1879                 fprintf (stderr, "Warning: very large buffer pool segment size\n");
1880
1881         if( argc > 7 )
1882                 off = atoi(argv[7]);
1883
1884         bt = bt_open ((argv[1]), BT_rw, bits, map, pgblk);
1885
1886         if( !bt ) {
1887                 fprintf(stderr, "Index Open Error %s\n", argv[1]);
1888                 exit (1);
1889         }
1890
1891         switch(argv[3][0]| 0x20)
1892         {
1893         case 'w':
1894                 fprintf(stderr, "started indexing for %s\n", argv[2]);
1895                 if( argc > 2 && (in = fopen (argv[2], "rb")) )
1896                   while( ch = getc(in), ch != EOF )
1897                         if( ch == '\n' )
1898                         {
1899                           if( off )
1900                                 sprintf((char *)key+len, "%.9d", line + off), len += 9;
1901
1902                           if( bt_insertkey (bt, key, len, 0, ++line, *tod) )
1903                                 fprintf(stderr, "Error %d Line: %d\n", bt->err, line), exit(0);
1904                           len = 0;
1905                         }
1906                         else if( len < 245 )
1907                                 key[len++] = ch;
1908                 fprintf(stderr, "finished adding keys for %s, %d \n", argv[2], line);
1909                 break;
1910
1911         case 'd':
1912                 fprintf(stderr, "started deleting keys for %s\n", argv[2]);
1913                 if( argc > 2 && (in = fopen (argv[2], "rb")) )
1914                   while( ch = getc(in), ch != EOF )
1915                         if( ch == '\n' )
1916                         {
1917                           if( off )
1918                                 sprintf((char *)key+len, "%.9d", line + off), len += 9;
1919                           line++;
1920                           if( bt_deletekey (bt, key, len, 0) )
1921                                 fprintf(stderr, "Error %d Line: %d\n", bt->err, line), exit(0);
1922                           len = 0;
1923                         }
1924                         else if( len < 245 )
1925                                 key[len++] = ch;
1926                 fprintf(stderr, "finished deleting keys for %s, %d \n", argv[2], line);
1927                 break;
1928
1929         case 'f':
1930                 fprintf(stderr, "started finding keys for %s\n", argv[2]);
1931                 if( argc > 2 && (in = fopen (argv[2], "rb")) )
1932                   while( ch = getc(in), ch != EOF )
1933                         if( ch == '\n' )
1934                         {
1935                           if( off )
1936                                 sprintf((char *)key+len, "%.9d", line + off), len += 9;
1937                           line++;
1938                           if( bt_findkey (bt, key, len) )
1939                                 found++;
1940                           else if( bt->err )
1941                                 fprintf(stderr, "Error %d Syserr %d Line: %d\n", bt->err, errno, line), exit(0);
1942                           len = 0;
1943                         }
1944                         else if( len < 245 )
1945                                 key[len++] = ch;
1946                 fprintf(stderr, "finished search of %d keys for %s, found %d\n", line, argv[2], found);
1947                 break;
1948
1949         case 's':
1950                 cnt = len = key[0] = 0;
1951
1952                 if( slot = bt_startkey (bt, key, len) )
1953                   slot--;
1954                 else
1955                   fprintf(stderr, "Error %d in StartKey. Syserror: %d\n", bt->err, errno), exit(0);
1956
1957                 while( slot = bt_nextkey (bt, slot) ) {
1958                         ptr = bt_key(bt, slot);
1959                         fwrite (ptr->key, ptr->len, 1, stdout);
1960                         fputc ('\n', stdout);
1961                         cnt++;
1962                 }
1963
1964           fprintf(stderr, " Total keys read %d\n", cnt - 1);
1965           break;
1966
1967         case 'c':
1968           fprintf(stderr, "started counting\n");
1969           cnt = 0;
1970
1971           page_no = LEAF_page;
1972           cnt = 0;
1973
1974           while( 1 ) {
1975           uid off = page_no << bt->page_bits;
1976 #ifdef unix
1977                 if( !pread (bt->idx, bt->frame, bt->page_size, off) )
1978                         break;
1979 #else
1980                 DWORD amt[1];
1981
1982                 SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN);
1983
1984                 if( !ReadFile(bt->idx, bt->frame, bt->page_size, amt, NULL))
1985                         break;
1986
1987                 if( *amt <  bt->page_size )
1988                         fprintf (stderr, "unable to read page %.8x", page_no);
1989 #endif
1990                 if( !bt->frame->free && !bt->frame->lvl )
1991                         cnt += bt->frame->act;
1992
1993                 page_no++;
1994           }
1995                 
1996           cnt--;        // remove stopper key
1997           fprintf(stderr, " Total keys read %d\n", cnt);
1998           break;
1999         }
2000
2001         done = getCpuTime(0);
2002         elapsed = (float)(done - start);
2003         fprintf(stderr, " real %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60);
2004         elapsed = getCpuTime(1);
2005         fprintf(stderr, " user %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60);
2006         elapsed = getCpuTime(2);
2007         fprintf(stderr, " sys  %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60);
2008
2009         return 0;
2010 }
2011
2012 #endif  //STANDALONE