From 6c6dc08503773de6746ecbd5f6e6eadeb99759a5 Mon Sep 17 00:00:00 2001 From: teodor Date: Wed, 9 Feb 2005 16:49:41 +0000 Subject: [PATCH] Small optimization --- tbtree.c | 85 ++++++++++++++++++++++++++++---------------------------- tbtree.h | 3 +- 2 files changed, 45 insertions(+), 43 deletions(-) diff --git a/tbtree.c b/tbtree.c index f9eae19..949c88e 100644 --- a/tbtree.c +++ b/tbtree.c @@ -114,6 +114,7 @@ TBTOpen(TBTree *db, char *file) { } } + db->pointersize = TBTPOINTERSIZE(db); db->lastpagenumber=0; return TBT_OK; } @@ -416,7 +417,7 @@ dumpPage(TBTree *db, TBTPage *page, int follow) { page->npointer ); for(i=0;inpointer;i++) { - TBTPointer *ptr= (TBTPointer*)(page->data+TBTPOINTERSIZE(db)*i); + TBTPointer *ptr= (TBTPointer*)(page->data+db->pointersize*i); for(j=0;jdata); - TBTPointer *StopHigh = (TBTPointer*)(page->data + TBTPOINTERSIZE(db)*page->npointer); + TBTPointer *StopHigh = (TBTPointer*)(page->data + db->pointersize*page->npointer); TBTPointer *StopMiddle; int diff ; TBTValue A; + A.length = db->keylen; /* Loop invariant: StopLow <= StopMiddle < StopHigh */ while (StopLow < StopHigh) { - StopMiddle = (TBTPointer*)(((char*)StopLow) + TBTPOINTERSIZE(db)*((((char*)StopHigh - (char*)StopLow)/TBTPOINTERSIZE(db)) >> 1)); + StopMiddle = (TBTPointer*)(((char*)StopLow) + db->pointersize*((((char*)StopHigh - (char*)StopLow)/db->pointersize) >> 1)); if ( db->keylen == 0 ) { A.length = StopMiddle->key.varlen.length; A.value = page->data + StopMiddle->key.varlen.offset; - } else { - A.length = db->keylen; + } else A.value = StopMiddle->key.fixed.key; - } + if ( ISINFPOINTER(db, page, StopMiddle) ) diff = 1; @@ -486,7 +487,7 @@ findInPage(TBTree *db, TBTPage *page, TBTValue *key, TBTPointer **res) { *res = StopMiddle; return FOUND; } else if ( diff < 0 ) - StopLow = (TBTPointer*)((char*)StopMiddle + TBTPOINTERSIZE(db)); + StopLow = (TBTPointer*)((char*)StopMiddle + db->pointersize); else StopHigh = StopMiddle; } @@ -552,22 +553,22 @@ TBTFind(TBTree *db, TBTValue *key, TBTValue *value) { static void packLeafKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, TBTValue *value) { if ( ptr ) { - if ( (char*)ptr - page->data != page->npointer * TBTPOINTERSIZE(db) ) - memmove((char*)ptr+TBTPOINTERSIZE(db), ptr, page->npointer * TBTPOINTERSIZE(db) - ( (char*)ptr - page->data )); + if ( (char*)ptr - page->data != page->npointer * db->pointersize ) + memmove((char*)ptr+db->pointersize, ptr, page->npointer * db->pointersize - ( (char*)ptr - page->data )); } else - ptr = (TBTPointer*)(page->data + page->npointer * TBTPOINTERSIZE(db)); + ptr = (TBTPointer*)(page->data + page->npointer * db->pointersize); page->npointer++; - page->freespace -= TBTPOINTERSIZE(db) + PTRALIGN(value->length); + page->freespace -= db->pointersize + PTRALIGN(value->length); if ( db->keylen ) { memcpy( ptr->key.fixed.key, key->value, db->keylen ); - ptr->pointer.leaf.offset = page->npointer * TBTPOINTERSIZE(db) + page->freespace; + ptr->pointer.leaf.offset = page->npointer * db->pointersize + page->freespace; } else { page->freespace -= PTRALIGN(key->length); ptr->key.varlen.length = key->length; - ptr->key.varlen.offset = page->npointer * TBTPOINTERSIZE(db) + page->freespace; + ptr->key.varlen.offset = page->npointer * db->pointersize + page->freespace; memcpy( page->data + ptr->key.varlen.offset, key->value, key->length); - ptr->pointer.leaf.offset = page->npointer * TBTPOINTERSIZE(db) + page->freespace + PTRALIGN(key->length); + ptr->pointer.leaf.offset = page->npointer * db->pointersize + page->freespace + PTRALIGN(key->length); } ptr->pointer.leaf.length = value->length; memcpy( page->data + ptr->pointer.leaf.offset, value->value, value->length ); @@ -576,13 +577,13 @@ packLeafKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, TBTValue * static void packInternalKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, u_int32_t pagenumber) { if ( ptr ) { - if ( (char*)ptr - page->data != page->npointer * TBTPOINTERSIZE(db) ) - memmove((char*)ptr+TBTPOINTERSIZE(db), ptr, page->npointer * TBTPOINTERSIZE(db) - ( (char*)ptr - page->data )); + if ( (char*)ptr - page->data != page->npointer * db->pointersize ) + memmove((char*)ptr+db->pointersize, ptr, page->npointer * db->pointersize - ( (char*)ptr - page->data )); } else - ptr = (TBTPointer*)(page->data + page->npointer * TBTPOINTERSIZE(db)); + ptr = (TBTPointer*)(page->data + page->npointer * db->pointersize); page->npointer++; - page->freespace -= TBTPOINTERSIZE(db); + page->freespace -= db->pointersize; if ( db->keylen ) { if ( key->value ) @@ -592,7 +593,7 @@ packInternalKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, u_int3 } else { page->freespace -= PTRALIGN(key->length); ptr->key.varlen.length = key->length; - ptr->key.varlen.offset = page->npointer * TBTPOINTERSIZE(db) + page->freespace; + ptr->key.varlen.offset = page->npointer * db->pointersize + page->freespace; if ( key->length ) memcpy( page->data + ptr->key.varlen.offset, key->value, key->length); } @@ -608,31 +609,31 @@ deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) { u_int32_t i, start; /* suppose ptrs are ordered! */ tmp = ptr; - while( ptrptr - ptrs < num && (char*)ptr - page->data < TBTPOINTERSIZE(db)*page->npointer ) { + while( ptrptr - ptrs < num && (char*)ptr - page->data < db->pointersize*page->npointer ) { if ( *ptrptr < ptr ) { tlog(TL_CRIT,"deleteKV: Something wrong: unexistent *ptrs"); ptrptr++; } else if ( *ptrptr > ptr ) { if ( tmp != ptr ) - memcpy(tmp, ptr, TBTPOINTERSIZE(db)); - ptr = (TBTPointer*)( (char*)ptr + TBTPOINTERSIZE(db) ); - tmp = (TBTPointer*)( (char*)tmp + TBTPOINTERSIZE(db) ); + memcpy(tmp, ptr, db->pointersize); + ptr = (TBTPointer*)( (char*)ptr + db->pointersize ); + tmp = (TBTPointer*)( (char*)tmp + db->pointersize ); } else { - page->freespace += TBTPOINTERSIZE(db) + + page->freespace += db->pointersize + ( ( page->isleaf ) ? PTRALIGN(ptr->pointer.leaf.length) : 0 ) + ( ( db->keylen ) ? 0 : PTRALIGN(ptr->key.varlen.length) ); ptrptr++; - ptr = (TBTPointer*)( (char*)ptr + TBTPOINTERSIZE(db) ); + ptr = (TBTPointer*)( (char*)ptr + db->pointersize ); } } - if ( (char*)ptr - page->data < TBTPOINTERSIZE(db)*page->npointer && tmp!=ptr ) - memmove( tmp, ptr, page->npointer * TBTPOINTERSIZE(db) - ((char*)ptr - page->data) ); + if ( (char*)ptr - page->data < db->pointersize*page->npointer && tmp!=ptr ) + memmove( tmp, ptr, page->npointer * db->pointersize - ((char*)ptr - page->data) ); page->npointer-=num; tmp = (TBTPointer*)page->data; - start = page->npointer * TBTPOINTERSIZE(db) + page->freespace; + start = page->npointer * db->pointersize + page->freespace; for(i=0;inpointer;i++) { if ( page->isleaf ) { memcpy( bufptr, page->data + tmp->pointer.leaf.offset, tmp->pointer.leaf.length ); @@ -646,7 +647,7 @@ deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) { tmp->key.varlen.offset = start + (bufptr-buf); bufptr+=PTRALIGN(tmp->key.varlen.length); } - tmp = (TBTPointer*)( (char*)tmp + TBTPOINTERSIZE(db) ); + tmp = (TBTPointer*)( (char*)tmp + db->pointersize ); } memcpy( page->data + start, buf, bufptr-buf ); @@ -658,16 +659,16 @@ findDelimiter(TBTree *db, TBTPage *page, TBTPointer *ptr, int size, u_int32_t st int i; TBTPointer *tomove; int lfree=TBTREEPAGESIZE-TBTPAGEHDRSZ, rfree=TBTREEPAGESIZE-TBTPAGEHDRSZ; - int nptr = ( (char*)ptr - page->data ) / TBTPOINTERSIZE(db); + int nptr = ( (char*)ptr - page->data ) / db->pointersize; int was=0; for(i=0; inpointer;i++) { - tomove = (TBTPointer*)(page->data + i*TBTPOINTERSIZE(db)); + tomove = (TBTPointer*)(page->data + i*db->pointersize); if ( was==0 && i==nptr ) { sizes[i] = size; was=1; } - sizes[i+was] = TBTPOINTERSIZE(db) + + sizes[i+was] = db->pointersize + ( (page->isleaf) ? PTRALIGN(tomove->pointer.leaf.length) : 0 ) + ( ( db->keylen ) ? 0 : PTRALIGN(tomove->key.varlen.length) ); @@ -712,7 +713,7 @@ populatePages(TBTree *db, TBTPage *srcpage, TBTPage* newpage, u_int32_t start) { TBTValue k, v; for(i=start;inpointer;i++) { - tomove = (TBTPointer*)(srcpage->data + i*TBTPOINTERSIZE(db)); + tomove = (TBTPointer*)(srcpage->data + i*db->pointersize); todelete[numtodelete] = tomove; numtodelete++; @@ -740,7 +741,7 @@ static int splitPage(TBTree *db, TBTMemPage *srcpage, TBTMemPage** newpage, TBTPointer **ptr, int size, TBTValue *key, TBTValue *value, u_int32_t pagenumber) { TBTMemPage *tmp; int start=0, where=0; - int nptr = ( (char*)(*ptr) - srcpage->page.data ) / TBTPOINTERSIZE(db); + int nptr = ( (char*)(*ptr) - srcpage->page.data ) / db->pointersize; if ( TBTNewPage(db, newpage) ) return TBT_ERROR; @@ -772,7 +773,7 @@ splitPage(TBTree *db, TBTMemPage *srcpage, TBTMemPage** newpage, TBTPointer **pt tmp=srcpage; else nptr-=start; - *ptr = (TBTPointer*)(tmp->page.data + nptr*TBTPOINTERSIZE(db)); + *ptr = (TBTPointer*)(tmp->page.data + nptr*db->pointersize); if ( tmp->page.isleaf ) packLeafKV(db, &(tmp->page), *ptr, key, value); @@ -809,7 +810,7 @@ layerInsert(TBTree *db, u_int32_t pagenumber, TBTMemPage **left, TBTMemPage **ri *left=*right=NULL; if ( page->page.isleaf ) { - u_int32_t size = TBTPOINTERSIZE(db) + + u_int32_t size = db->pointersize + PTRALIGN(value->length) + ( ( db->keylen ) ? 0 : PTRALIGN(key->length) ); @@ -843,7 +844,7 @@ layerInsert(TBTree *db, u_int32_t pagenumber, TBTMemPage **left, TBTMemPage **ri if ( *left ) { /* child page was splited */ u_int32_t size; - TBTPointer *rightptr = (TBTPointer*)( (*left)->page.data + ((*left)->page.npointer-1) * TBTPOINTERSIZE(db) ); + TBTPointer *rightptr = (TBTPointer*)( (*left)->page.data + ((*left)->page.npointer-1) * db->pointersize ); TBTValue K; if ( ISINFPOINTER(db, &(page->page), ptr) ) { @@ -856,7 +857,7 @@ layerInsert(TBTree *db, u_int32_t pagenumber, TBTMemPage **left, TBTMemPage **ri K.length = ( db->keylen ) ? db->keylen : rightptr->key.varlen.length; K.value = ( db->keylen ) ? rightptr->key.fixed.key : (*left)->page.data + rightptr->key.varlen.offset; - size = TBTPOINTERSIZE(db) + ( ( db->keylen ) ? 0 : PTRALIGN(K.length) ); + size = db->pointersize + ( ( db->keylen ) ? 0 : PTRALIGN(K.length) ); if ( size <= page->page.freespace ) { packInternalKV(db, &(page->page), ptr, &K, (*left)->pagenumber); @@ -891,12 +892,12 @@ layerInsert(TBTree *db, u_int32_t pagenumber, TBTMemPage **left, TBTMemPage **ri memset( &(page->page), 0, TBTREEPAGESIZE); page->page.freespace=TBTREEPAGESIZE-TBTPAGEHDRSZ; - ptr = (TBTPointer*)( newleft->page.data + (newleft->page.npointer-1) * TBTPOINTERSIZE(db) ); + ptr = (TBTPointer*)( newleft->page.data + (newleft->page.npointer-1) * db->pointersize ); K.length = ( db->keylen ) ? db->keylen : ptr->key.varlen.length; K.value = ( db->keylen ) ? ptr->key.fixed.key : newleft->page.data + ptr->key.varlen.offset; packInternalKV(db, &(page->page), NULL, &K, newleft->pagenumber); - ptr = (TBTPointer*)( newright->page.data + (newright->page.npointer-1) * TBTPOINTERSIZE(db) ); + ptr = (TBTPointer*)( newright->page.data + (newright->page.npointer-1) * db->pointersize ); K.length = 0; K.value = NULL; packInternalKV(db, &(page->page), NULL, &K, newright->pagenumber); @@ -1004,7 +1005,7 @@ TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value ) { return TBT_OK; } - if ( (char*)(iterator->ptr) - iterator->page->page.data >= TBTPOINTERSIZE(db) * iterator->page->page.npointer ) { + if ( (char*)(iterator->ptr) - iterator->page->page.data >= db->pointersize * iterator->page->page.npointer ) { do { u_int32_t pagenumber = iterator->page->page.rightlink; iterator->page->islocked=0; @@ -1036,7 +1037,7 @@ TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value ) { value->length = iterator->ptr->pointer.leaf.length; value->value = iterator->page->page.data + iterator->ptr->pointer.leaf.offset; - iterator->ptr = ( TBTPointer* ) ( (char*)(iterator->ptr) + TBTPOINTERSIZE(db) ); + iterator->ptr = ( TBTPointer* ) ( (char*)(iterator->ptr) + db->pointersize ); return TBT_OK; } diff --git a/tbtree.h b/tbtree.h index e6169a6..9e75231 100644 --- a/tbtree.h +++ b/tbtree.h @@ -118,7 +118,8 @@ typedef struct { readonly:1, keylen:11, strategy:2, - unused:18; + unused:2, + pointersize:16; /* cache page subsystem */ u_int32_t npage; -- 2.37.3