X-Git-Url: https://pd.if.org/git/?p=btree;a=blobdiff_plain;f=btree2s.c;h=19ad3beb64436ce60d78a7e03327f2c2c06895cc;hp=af39f90f0db14db8dadf49b1bee29a9612246786;hb=HEAD;hpb=07891352e2c84646ffe3071b4ebf708a97cf5c3e diff --git a/btree2s.c b/btree2s.c index af39f90..19ad3be 100644 --- a/btree2s.c +++ b/btree2s.c @@ -1,5 +1,6 @@ // btree version 2s -// 13 FEB 2014 +// with reworked bt_deletekey code +// 25 FEB 2014 // author: karl malbrain, malbrain@cal.berkeley.edu @@ -121,10 +122,9 @@ typedef struct { uint min; // next key offset unsigned char bits:7; // page size in bits unsigned char free:1; // page is on free list - unsigned char lvl:5; // level of page + unsigned char lvl:6; // level of page unsigned char kill:1; // page is being deleted unsigned char dirty:1; // page is dirty - unsigned char posted:1; // page is posted in parent unsigned char right[BtId]; // page number to right } *BtPage; @@ -397,7 +397,7 @@ BtHash *hash; do munmap (hash->page, (bt->hashmask+1) << bt->page_bits); while(hash = hash->lrunext); - if ( bt->mem ) + if( bt->mem ) free (bt->mem); close (bt->idx); free (bt->cache); @@ -411,7 +411,7 @@ BtHash *hash; CloseHandle(hash->hmap); } while(hash = hash->lrunext); - if ( bt->mem) + if( bt->mem) VirtualFree (bt->mem, 0, MEM_RELEASE); FlushFileBuffers(bt->idx); CloseHandle(bt->idx); @@ -500,7 +500,7 @@ SYSTEM_INFO sysinfo[1]; else if( bits < BT_minbits ) bits = BT_minbits; - if ( bt_lockpage(bt, ALLOC_page, lockmode) ) + if( bt_lockpage(bt, ALLOC_page, lockmode) ) return bt_close (bt), NULL; #ifdef unix @@ -571,7 +571,7 @@ SYSTEM_INFO sysinfo[1]; bt->zero = (BtPage)(bt->mem + 5 * bt->page_size); if( size || *amt ) { - if ( bt_unlockpage(bt, ALLOC_page, lockmode) ) + if( bt_unlockpage(bt, ALLOC_page, lockmode) ) return bt_close (bt), NULL; return bt; @@ -673,12 +673,12 @@ BTERR bt_update (BtDb *bt, BtPage page, uid page_no) off64_t off = page_no << bt->page_bits; #ifdef unix - if ( !bt->mapped_io ) - if ( pwrite(bt->idx, page, bt->page_size, off) != bt->page_size ) + if( !bt->mapped_io ) + if( pwrite(bt->idx, page, bt->page_size, off) != bt->page_size ) return bt->err = BTERR_wrt; #else uint amt[1]; - if ( !bt->mapped_io ) + if( !bt->mapped_io ) { SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN); if( !WriteFile (bt->idx, (char *)page, bt->page_size, amt, NULL) ) @@ -687,7 +687,7 @@ uint amt[1]; if( *amt < bt->page_size ) return GetLastError(), bt->err = BTERR_wrt; } - else if ( bt->mode == BT_fl ) { + else if( bt->mode == BT_fl ) { FlushViewOfFile(page, bt->page_size); FlushFileBuffers(bt->idx); } @@ -875,7 +875,7 @@ int amt[1]; return bt->err; } #ifdef unix - if ( pread(bt->idx, *page, bt->page_size, off) < bt->page_size ) + if( pread(bt->idx, *page, bt->page_size, off) < bt->page_size ) return bt->err = BTERR_map; #else SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN); @@ -899,7 +899,7 @@ BTERR bt_freepage(BtDb *bt, uid page_no) // lock allocation page - if ( bt_lockpage(bt, ALLOC_page, BtLockWrite) ) + if( bt_lockpage(bt, ALLOC_page, BtLockWrite) ) return bt->err; if( bt_mappage (bt, &bt->alloc, ALLOC_page) ) @@ -943,7 +943,7 @@ int reuse; // lock page zero - if ( bt_lockpage(bt, ALLOC_page, BtLockWrite) ) + if( bt_lockpage(bt, ALLOC_page, BtLockWrite) ) return 0; if( bt_mappage (bt, &bt->alloc, ALLOC_page) ) @@ -972,23 +972,23 @@ int reuse; // unlock page zero - if ( bt_unlockpage(bt, ALLOC_page, BtLockWrite) ) + if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) ) return 0; return new_page; } #ifdef unix - if ( pwrite(bt->idx, page, bt->page_size, new_page << bt->page_bits) < bt->page_size ) + if( pwrite(bt->idx, page, bt->page_size, new_page << bt->page_bits) < bt->page_size ) return bt->err = BTERR_wrt, 0; // if writing first page of hash block, zero last page in the block - if ( !reuse && bt->hashmask > 0 && (new_page & bt->hashmask) == 0 ) + if( !reuse && bt->hashmask > 0 && (new_page & bt->hashmask) == 0 ) { // use temp buffer to write zeros memset(bt->zero, 0, bt->page_size); - if ( pwrite(bt->idx,bt->zero, bt->page_size, (new_page | bt->hashmask) << bt->page_bits) < bt->page_size ) + if( pwrite(bt->idx,bt->zero, bt->page_size, (new_page | bt->hashmask) << bt->page_bits) < bt->page_size ) return bt->err = BTERR_wrt, 0; } #else @@ -1003,7 +1003,7 @@ int reuse; // unlock page zero - if ( bt_unlockpage(bt, ALLOC_page, BtLockWrite) ) + if( bt_unlockpage(bt, ALLOC_page, BtLockWrite) ) return 0; return new_page; @@ -1023,7 +1023,7 @@ uint good = 0; else good++; - // low is the next candidate, higher is already + // low is the lowest candidate, higher is already // tested as .ge. the given key, loop ends when they meet while( diff = higher - low ) { @@ -1083,12 +1083,12 @@ uint mode, prevmode; // re-read and re-lock root after determining actual level of root if( bt->page->lvl != drill) { - if ( bt->page_no != ROOT_page ) + if( bt->page_no != ROOT_page ) return bt->err = BTERR_struct, 0; drill = bt->page->lvl; - if( lock == BtLockWrite && drill == lvl ) + if( lock != BtLockRead && drill == lvl ) if( bt_unlockpage(bt, page_no, mode) ) return 0; else @@ -1110,20 +1110,16 @@ uint mode, prevmode; if( slot++ < bt->page->cnt ) continue; else - break; + goto slideright; - // if the page has no active slots, - // move right otherwise drill down - - if( slot <= bt->page->cnt ) { - page_no = bt_getid(slotptr(bt->page, slot)->id); - drill--; - continue; - } + page_no = bt_getid(slotptr(bt->page, slot)->id); + drill--; + continue; } // or slide right into next page +slideright: page_no = bt_getid(bt->page->right); } while( page_no ); @@ -1135,30 +1131,31 @@ uint mode, prevmode; } // a fence key was deleted from a page -// push new fence value up to the root +// push new fence value upwards BTERR bt_fixfence (BtDb *bt, uid page_no, uint lvl) { unsigned char leftkey[256], rightkey[256]; BtKey ptr; -uid left; // remove deleted key, the old fence value - ptr = keyptr(bt->page, bt->page->cnt--); + ptr = keyptr(bt->page, bt->page->cnt); memcpy(rightkey, ptr, ptr->len + 1); - left = bt_getid (slotptr(bt->page, bt->page->cnt)->id); + memset (slotptr(bt->page, bt->page->cnt--), 0, sizeof(BtSlot)); + bt->page->dirty = 1; + ptr = keyptr(bt->page, bt->page->cnt); memcpy(leftkey, ptr, ptr->len + 1); if( bt_update (bt, bt->page, page_no) ) return bt->err; - if( bt_unlockpage (bt, page_no, BtLockWrite) ) + if( bt_lockpage (bt, page_no, BtLockParent) ) return bt->err; - if( bt_lockpage (bt, left, BtLockParent) ) + if( bt_unlockpage (bt, page_no, BtLockWrite) ) return bt->err; // insert new (now smaller) fence key @@ -1166,12 +1163,12 @@ uid left; if( bt_insertkey (bt, leftkey+1, *leftkey, lvl + 1, page_no, time(NULL)) ) return bt->err; - if( bt_unlockpage (bt, left, BtLockParent) ) - return bt->err; - // remove old (larger) fence key - return bt_deletekey (bt, rightkey+1, *rightkey, lvl + 1); + if( bt_deletekey (bt, rightkey+1, *rightkey, lvl + 1) ) + return bt->err; + + return bt_unlockpage (bt, page_no, BtLockParent); } // root has a single child @@ -1221,11 +1218,10 @@ uint idx; BTERR bt_deletekey (BtDb *bt, unsigned char *key, uint len, uint lvl) { unsigned char lowerkey[256], higherkey[256]; -uint slot, dirty = 0, idx, fence; +uint slot, dirty = 0, idx, fence, found; uid page_no, right; BtKey ptr; -retry: if( slot = bt_loadpage (bt, key, len, lvl, BtLockWrite) ) ptr = keyptr(bt->page, slot); else @@ -1237,11 +1233,10 @@ retry: // if key is found delete it, otherwise ignore request - if( !keycmp (ptr, key, len) ) - if( slotptr(bt->page, slot)->dead == 0 ) { + if( found = !keycmp (ptr, key, len) ) + if( found = slotptr(bt->page, slot)->dead == 0 ) { dirty = slotptr(bt->page,slot)->dead = 1; - if( slot < bt->page->cnt ) - bt->page->dirty = 1; + bt->page->dirty = 1; bt->page->act--; // collapse empty slots @@ -1257,27 +1252,31 @@ retry: right = bt_getid(bt->page->right); page_no = bt->page_no; - // did we delete our fence key in an upper level? + // did we delete a fence key in an upper level? if( dirty && lvl && bt->page->act && fence ) - return bt_fixfence (bt, page_no, lvl); + if( bt_fixfence (bt, page_no, lvl) ) + return bt->err; + else + return bt->found = found, 0; // is this a collapsed root? if( lvl > 1 && page_no == ROOT_page && bt->page->act == 1 ) - return bt_collapseroot (bt, bt->page); - - // return if page is not empty - - if( bt->page->act ) - if ( dirty && bt_update(bt, bt->page, page_no) ) + if( bt_collapseroot (bt, bt->page) ) return bt->err; else - return bt_unlockpage(bt, page_no, BtLockWrite); + return bt->found = found, 0; - // mark page being deleted + // return if page is not empty - bt->page->kill = 1; + if( bt->page->act ) { + if( dirty && bt_update(bt, bt->page, page_no) ) + return bt->err; + if( bt_unlockpage(bt, page_no, BtLockWrite) ) + return bt->err; + return bt->found = found, 0; + } // cache copy of fence key // in order to find parent @@ -1285,46 +1284,16 @@ retry: ptr = keyptr(bt->page, bt->page->cnt); memcpy(lowerkey, ptr, ptr->len + 1); - if( bt_update(bt, bt->page, page_no) ) - return bt->err; - - if( bt_unlockpage(bt, page_no, BtLockWrite) ) - return bt->err; - - // obtain Parent lock - - if( bt_lockpage(bt, page_no, BtLockParent) ) - return bt->err; - - // lock and map right page + // obtain lock on right page - if ( bt_lockpage(bt, right, BtLockWrite) ) + if( bt_lockpage(bt, right, BtLockWrite) ) return bt->err; if( bt_mappage (bt, &bt->temp, right) ) return bt->err; - // is our right sibling being deleted? - - if( bt->temp->kill ) { - if ( bt_unlockpage(bt, right, BtLockWrite) ) - return bt->err; - - if( bt_unlockpage(bt, page_no, BtLockParent) ) - return bt->err; -#ifdef linux - sched_yield (); -#else - SwitchToThread(); -#endif - goto retry; - } - - if( bt_lockpage(bt, page_no, BtLockWrite) ) - return bt->err; - - if( bt_mappage (bt, &bt->page, page_no) ) - return bt->err; + if( bt->temp->kill ) + return bt->err = BTERR_struct; // pull contents of next page into current empty page @@ -1347,15 +1316,21 @@ retry: if( bt_update(bt, bt->temp, right) ) return bt->err; - if( bt_unlockpage(bt, right, BtLockWrite) ) + if( bt_lockpage(bt, page_no, BtLockParent) ) return bt->err; if( bt_unlockpage(bt, page_no, BtLockWrite) ) return bt->err; + if( bt_lockpage(bt, right, BtLockParent) ) + return bt->err; + + if( bt_unlockpage(bt, right, BtLockWrite) ) + return bt->err; + // redirect higher key directly to consolidated node - if( bt_insertkey (bt, higherkey+1, *higherkey, lvl + 1, page_no, time(NULL)) ) + if( bt_insertkey (bt, higherkey+1, *higherkey, lvl+1, page_no, time(NULL)) ) return bt->err; // delete old lower key to consolidated node @@ -1363,21 +1338,22 @@ retry: if( bt_deletekey (bt, lowerkey + 1, *lowerkey, lvl + 1) ) return bt->err; - // obtain delete lock on deleted node + // obtain write & delete lock on deleted node // add right block to free chain if( bt_lockpage(bt, right, BtLockDelete) ) return bt->err; - // obtain write lock on deleted node - if( bt_lockpage(bt, right, BtLockWrite) ) return bt->err; if( bt_freepage (bt, right) ) return bt->err; - // remove ParentModify lock + // remove ParentModify locks + + if( bt_unlockpage(bt, right, BtLockParent) ) + return bt->err; return bt_unlockpage(bt, page_no, BtLockParent); } @@ -1403,7 +1379,7 @@ uid id; else id = 0; - if ( bt_unlockpage(bt, bt->page_no, BtLockRead) ) + if( bt_unlockpage(bt, bt->page_no, BtLockRead) ) return 0; return id; @@ -1524,8 +1500,8 @@ uid right; BTERR bt_splitpage (BtDb *bt) { uint cnt = 0, idx = 0, max, nxt = bt->page_size; +unsigned char fencekey[256], rightkey[256]; uid page_no = bt->page_no, right; -unsigned char fencekey[256]; BtPage page = bt->page; uint lvl = page->lvl; BtKey key; @@ -1534,7 +1510,7 @@ BtKey key; // the last key (fence key) might be dead memset (bt->frame, 0, bt->page_size); - max = (int)page->cnt; + max = page->cnt; cnt = max / 2; idx = 0; @@ -1549,6 +1525,10 @@ BtKey key; slotptr(bt->frame, idx)->off = nxt; } + // remember fence key for new right page + + memcpy (rightkey, key, key->len + 1); + bt->frame->bits = bt->page_bits; bt->frame->min = nxt; bt->frame->cnt = idx; @@ -1569,7 +1549,6 @@ BtKey key; memcpy (bt->frame, page, bt->page_size); memset (page+1, 0, bt->page_size - sizeof(*page)); nxt = bt->page_size; - page->posted = 0; page->dirty = 0; page->act = 0; cnt = 0; @@ -1588,9 +1567,10 @@ BtKey key; page->act++; } - // remember fence key for old page + // remember fence key for smaller page memcpy (fencekey, key, key->len + 1); + bt_putid(page->right, right); page->min = nxt; page->cnt = idx; @@ -1600,54 +1580,36 @@ BtKey key; if( page_no == ROOT_page ) return bt_splitroot (bt, fencekey, right); - // update left (containing) node - - if( bt_update(bt, page, page_no) ) - return bt->err; + // lock right page - if( bt_unlockpage (bt, page_no, BtLockWrite) ) + if( bt_lockpage (bt, right, BtLockParent) ) return bt->err; - // insert new fences in parent pages + // update left (containing) node - do { - if( bt_lockpage (bt, page_no, BtLockParent) ) + if( bt_update(bt, page, page_no) ) return bt->err; - if( bt_lockpage (bt, page_no, BtLockWrite) ) + if( bt_lockpage (bt, page_no, BtLockParent) ) return bt->err; - if( bt_mappage (bt, &bt->page, page_no) ) + if( bt_unlockpage (bt, page_no, BtLockWrite) ) return bt->err; - key = keyptr(bt->page, bt->page->cnt); - memcpy (fencekey, key, key->len + 1); - - if( bt->page->posted ) { - if( bt_unlockpage (bt, page_no, BtLockParent) ) - return bt->err; - return bt_unlockpage (bt, page_no, BtLockWrite); - } - - right = bt_getid (bt->page->right); - bt->page->posted = 1; - - if( bt_update (bt, bt->page, page_no) ) - return bt->err; + // insert new fence for reformulated left block - if( bt_unlockpage (bt, page_no, BtLockWrite) ) + if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, page_no, time(NULL)) ) return bt->err; - // insert new fence for reformulated left block + // switch fence for right block of larger keys to new right page - if( bt_insertkey (bt, fencekey+1, *fencekey, lvl + 1, page_no, time(NULL)) ) + if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right, time(NULL)) ) return bt->err; - if( bt_unlockpage (bt, page_no, BtLockParent) ) + if( bt_unlockpage (bt, page_no, BtLockParent) ) return bt->err; - } while( page_no = right ); - return 0; + return bt_unlockpage (bt, right, BtLockParent); } // Insert new key into the btree at requested level. @@ -1665,7 +1627,7 @@ BtKey ptr; ptr = keyptr(bt->page, slot); else { - if ( !bt->err ) + if( !bt->err ) bt->err = BTERR_ovflw; return bt->err; } @@ -1675,12 +1637,14 @@ BtKey ptr; page = bt->page; if( !keycmp (ptr, key, len) ) { - slotptr(page, slot)->dead = 0; - slotptr(page, slot)->tod = tod; - bt_putid(slotptr(page,slot)->id, id); - if ( bt_update(bt, bt->page, bt->page_no) ) - return bt->err; - return bt_unlockpage(bt, bt->page_no, BtLockWrite); + if( slotptr(page, slot)->dead ) + page->act++; + slotptr(page, slot)->dead = 0; + slotptr(page, slot)->tod = tod; + bt_putid(slotptr(page,slot)->id, id); + if( bt_update(bt, bt->page, bt->page_no) ) + return bt->err; + return bt_unlockpage(bt, bt->page_no, BtLockWrite); } // check if page has enough space @@ -1718,7 +1682,7 @@ BtKey ptr; slotptr(page, slot)->tod = tod; slotptr(page, slot)->dead = 0; - if ( bt_update(bt, bt->page, bt->page_no) ) + if( bt_update(bt, bt->page, bt->page_no) ) return bt->err; return bt_unlockpage(bt, bt->page_no, BtLockWrite); @@ -1731,11 +1695,16 @@ uint bt_startkey (BtDb *bt, unsigned char *key, uint len) uint slot; // cache page for retrieval + if( slot = bt_loadpage (bt, key, len, 0, BtLockRead) ) - memcpy (bt->cursor, bt->page, bt->page_size); + memcpy (bt->cursor, bt->page, bt->page_size); + else + return 0; + bt->cursor_page = bt->page_no; - if ( bt_unlockpage(bt, bt->page_no, BtLockRead) ) - return 0; + + if( bt_unlockpage(bt, bt->page_no, BtLockRead) ) + return 0; return slot; } @@ -1749,6 +1718,7 @@ off64_t right; do { right = bt_getid(bt->cursor->right); + while( slot++ < bt->cursor->cnt ) if( slotptr(bt->cursor,slot)->dead ) continue; @@ -1762,17 +1732,19 @@ off64_t right; bt->cursor_page = right; - if( bt_lockpage(bt, right,BtLockRead) ) + if( bt_lockpage(bt, right, BtLockRead) ) return 0; if( bt_mappage (bt, &bt->page, right) ) - break; + return 0; memcpy (bt->cursor, bt->page, bt->page_size); - if ( bt_unlockpage(bt, right, BtLockRead) ) + + if( bt_unlockpage(bt, right, BtLockRead) ) return 0; slot = 0; + } while( 1 ); return bt->err = 0; @@ -1795,6 +1767,68 @@ uint bt_tod(BtDb *bt, uint slot) #ifdef STANDALONE + +#ifndef unix +double getCpuTime(int type) +{ +FILETIME crtime[1]; +FILETIME xittime[1]; +FILETIME systime[1]; +FILETIME usrtime[1]; +SYSTEMTIME timeconv[1]; +double ans = 0; + + memset (timeconv, 0, sizeof(SYSTEMTIME)); + + switch( type ) { + case 0: + GetSystemTimeAsFileTime (xittime); + FileTimeToSystemTime (xittime, timeconv); + ans = (double)timeconv->wDayOfWeek * 3600 * 24; + break; + case 1: + GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime); + FileTimeToSystemTime (usrtime, timeconv); + break; + case 2: + GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime); + FileTimeToSystemTime (systime, timeconv); + break; + } + + ans += (double)timeconv->wHour * 3600; + ans += (double)timeconv->wMinute * 60; + ans += (double)timeconv->wSecond; + ans += (double)timeconv->wMilliseconds / 1000; + return ans; +} +#else +#include +#include + +double getCpuTime(int type) +{ +struct rusage used[1]; +struct timeval tv[1]; + + switch( type ) { + case 0: + gettimeofday(tv, NULL); + return (double)tv->tv_sec + (double)tv->tv_usec / 1000000; + + case 1: + getrusage(RUSAGE_SELF, used); + return (double)used->ru_utime.tv_sec + (double)used->ru_utime.tv_usec / 1000000; + + case 2: + getrusage(RUSAGE_SELF, used); + return (double)used->ru_stime.tv_sec + (double)used->ru_stime.tv_usec / 1000000; + } + + return 0; +} +#endif + // standalone program to index file of keys // then list them onto std-out @@ -1803,12 +1837,14 @@ int main (int argc, char **argv) uint slot, line = 0, off = 0, found = 0; int dead, ch, cnt = 0, bits = 12; unsigned char key[256]; -clock_t done, start; +double done, start; uint pgblk = 0; +float elapsed; time_t tod[1]; uint scan = 0; uint len = 0; uint map = 0; +uid page_no; BtKey ptr; BtDb *bt; FILE *in; @@ -1821,7 +1857,7 @@ FILE *in; exit(0); } - start = clock(); + start = getCpuTime(0); time(tod); if( argc > 4 ) @@ -1869,7 +1905,7 @@ FILE *in; } else if( len < 245 ) key[len++] = ch; - fprintf(stderr, "finished adding keys, %d \n", line); + fprintf(stderr, "finished adding keys for %s, %d \n", argv[2], line); break; case 'd': @@ -1887,7 +1923,7 @@ FILE *in; } else if( len < 245 ) key[len++] = ch; - fprintf(stderr, "finished deleting keys, %d \n", line); + fprintf(stderr, "finished deleting keys for %s, %d \n", argv[2], line); break; case 'f': @@ -1907,36 +1943,69 @@ FILE *in; } else if( len < 245 ) key[len++] = ch; - fprintf(stderr, "finished search of %d keys, found %d\n", line, found); + fprintf(stderr, "finished search of %d keys for %s, found %d\n", line, argv[2], found); break; case 's': - scan++; - break; + cnt = len = key[0] = 0; - } + if( slot = bt_startkey (bt, key, len) ) + slot--; + else + fprintf(stderr, "Error %d in StartKey. Syserror: %d\n", bt->err, errno), exit(0); + + while( slot = bt_nextkey (bt, slot) ) { + ptr = bt_key(bt, slot); + fwrite (ptr->key, ptr->len, 1, stdout); + fputc ('\n', stdout); + cnt++; + } - done = clock(); - fprintf(stderr, " Time to complete: %.2f seconds\n", (float)(done - start) / CLOCKS_PER_SEC); + fprintf(stderr, " Total keys read %d\n", cnt - 1); + break; - dead = cnt = 0; - len = key[0] = 0; + case 'c': + fprintf(stderr, "started counting\n"); + cnt = 0; - fprintf(stderr, "started reading\n"); + page_no = LEAF_page; + cnt = 0; - if( slot = bt_startkey (bt, key, len) ) - slot--; - else - fprintf(stderr, "Error %d in StartKey. Syserror: %d\n", bt->err, errno), exit(0); + while( 1 ) { + uid off = page_no << bt->page_bits; +#ifdef unix + if( !pread (bt->idx, bt->frame, bt->page_size, off) ) + break; +#else + DWORD amt[1]; - while( slot = bt_nextkey (bt, slot) ) - if( cnt++, scan ) { - ptr = bt_key(bt, slot); - fwrite (ptr->key, ptr->len, 1, stdout); - fputc ('\n', stdout); + SetFilePointer (bt->idx, (long)off, (long*)(&off)+1, FILE_BEGIN); + + if( !ReadFile(bt->idx, bt->frame, bt->page_size, amt, NULL)) + break; + + if( *amt < bt->page_size ) + fprintf (stderr, "unable to read page %.8x", page_no); +#endif + if( !bt->frame->free && !bt->frame->lvl ) + cnt += bt->frame->act; + + page_no++; } + + cnt--; // remove stopper key + fprintf(stderr, " Total keys read %d\n", cnt); + break; + } + + done = getCpuTime(0); + elapsed = (float)(done - start); + fprintf(stderr, " real %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); + elapsed = getCpuTime(1); + fprintf(stderr, " user %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); + elapsed = getCpuTime(2); + fprintf(stderr, " sys %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); - fprintf(stderr, " Total keys read %d\n", cnt); return 0; }