add .gitignore

[tedtools.git] / tbtree.c

diff --git a/tbtree.c b/tbtree.c
index 949c88e..416cabc 100644 (file)
--- a/tbtree.c
+++ b/tbtree.c
@@ -208,7 +208,7 @@ findInCache(TBTree *db, u_int32_t pagenumber) {
        while(ptr && ptr->pagenumber != pagenumber)
                ptr = ptr->link; 
 
-       return ptr;;
+       return ptr;
 }
 
 static void
@@ -420,8 +420,8 @@ dumpPage(TBTree *db, TBTPage *page, int follow) {
                TBTPointer *ptr= (TBTPointer*)(page->data+db->pointersize*i);
                for(j=0;j<follow+2;j++)
                        putchar(' ');
-               printf("i:%d(%d) kl:%d ko:%d ",
-                       i, (int)ptr, 
+               printf("i:%d(%p) kl:%d ko:%d ",
+                       i, (void*)ptr, 
                        (db->keylen) ? db->keylen : ptr->key.varlen.length,
                        (db->keylen) ? 0 : ptr->key.varlen.offset
                );
@@ -588,8 +588,6 @@ packInternalKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, u_int3
        if ( db->keylen ) {
                if ( key->value )
                        memcpy( ptr->key.fixed.key, key->value, db->keylen );
-               else
-                       memset( ptr->key.fixed.key, 0, db->keylen );
        } else {
                page->freespace -= PTRALIGN(key->length);
                ptr->key.varlen.length = key->length;
@@ -600,13 +598,11 @@ packInternalKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, u_int3
        ptr->pointer.internal.link = pagenumber;
 }
 
-
 static void
 deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) {
-       static char buf[TBTREEPAGESIZE];
-       char  *bufptr = buf;
        TBTPointer *ptr = (TBTPointer*)page->data, *tmp, **ptrptr = ptrs;
-       u_int32_t i, start;
+       u_int32_t i;
+
        /* suppose ptrs are ordered! */
        tmp = ptr;
        while( ptrptr - ptrs < num && (char*)ptr - page->data < db->pointersize*page->npointer ) {
@@ -632,25 +628,30 @@ deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) {
 
        page->npointer-=num;
 
-       tmp = (TBTPointer*)page->data;
-       start = page->npointer * db->pointersize + page->freespace;
-       for(i=0;i<page->npointer;i++) {
-               if ( page->isleaf ) {
-                       memcpy( bufptr, page->data + tmp->pointer.leaf.offset, tmp->pointer.leaf.length );
-                       tmp->pointer.leaf.offset = start + (bufptr-buf);
-                       bufptr+=PTRALIGN(tmp->pointer.leaf.length);
+       if ( page->isleaf || db->keylen == 0 ) {
+               static char buf[TBTREEPAGESIZE];
+               char  *bufptr = buf;
+               u_int32_t start = page->npointer * db->pointersize + page->freespace;
+
+               tmp = (TBTPointer*)page->data;
+               for(i=0;i<page->npointer;i++) {
+                       if ( page->isleaf ) {
+                               memcpy( bufptr, page->data + tmp->pointer.leaf.offset, tmp->pointer.leaf.length );
+                               tmp->pointer.leaf.offset = start + (bufptr-buf);
+                               bufptr+=PTRALIGN(tmp->pointer.leaf.length);
+                       }
+       
+                       if ( db->keylen == 0 ) {
+                               if ( tmp->key.varlen.length )
+                                       memcpy( bufptr, page->data + tmp->key.varlen.offset, tmp->key.varlen.length );
+                               tmp->key.varlen.offset = start + (bufptr-buf);
+                               bufptr+=PTRALIGN(tmp->key.varlen.length);
+                       }
+                       tmp = (TBTPointer*)( (char*)tmp + db->pointersize );
                }
 
-               if ( db->keylen == 0 ) {
-                       if ( tmp->key.varlen.length )
-                               memcpy( bufptr, page->data + tmp->key.varlen.offset, tmp->key.varlen.length );
-                       tmp->key.varlen.offset = start + (bufptr-buf);
-                       bufptr+=PTRALIGN(tmp->key.varlen.length);
-               }
-               tmp = (TBTPointer*)( (char*)tmp + db->pointersize );
+               memcpy( page->data + start, buf, bufptr-buf );
        }
-
-       memcpy( page->data + start, buf, bufptr-buf );
 }
 
 static u_int32_t
@@ -1042,4 +1043,79 @@ TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value ) {
        return TBT_OK;
 }
 
+int 
+TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value) {
+       TBTIterator     iterator;
+       int rc;
+
+       if ( (rc=TBTInitIterator(db, &iterator))!=TBT_OK )
+               return rc;
+
+       rc=TBTIterate(db, &iterator, key, value);
+
+       if ( key->value ) {
+               char * ptr;
+
+               ptr = tmalloc( key->length );
+               memcpy( ptr, key->value, key->length );
+               key->value = ptr;
+ 
+               ptr = tmalloc( value->length );
+               memcpy( ptr, value->value, value->length );
+               value->value = ptr; 
+       }
+
+       TBTFreeIterator(db, &iterator);
+
+       return rc;
+}
+
+static int
+findLast(TBTree *db, TBTValue *key, TBTValue *value, u_int32_t pagenumber) {
+       TBTMemPage      *page;
+       TBTPointer      *ptr;
+       int rc=TBT_OK,i;
+
+       if ( (rc=TBTReadPage(db, pagenumber, &page)) != TBT_OK )
+               return rc;
+
+       if ( page->page.npointer==0 ) {
+               if ( !page->iscached )
+                       tfree(page);
+               return TBT_OK;
+       }
+
+       page->islocked=1;
+       if ( page->page.isleaf ) {
+               ptr = (TBTPointer*)(page->page.data + db->pointersize * (page->page.npointer-1));
+
+               key->length = ( db->keylen ) ? db->keylen : ptr->key.varlen.length;
+               key->value = tmalloc( key->length );
+               memcpy( key->value, ( db->keylen ) ? ptr->key.fixed.key : page->page.data + ptr->key.varlen.offset, key->length ); 
+
+               value->length = ptr->pointer.leaf.length;
+               value->value = tmalloc( value->length );
+               memcpy( value->value, page->page.data + ptr->pointer.leaf.offset, value->length ); 
+       } else {
+               for(i=page->page.npointer-1; i>=0; i--) {
+                       ptr = (TBTPointer*)( page->page.data + db->pointersize * i );
+                       rc = findLast(db, key, value, ptr->pointer.internal.link);
+                       if ( rc!=TBT_OK || key->value )
+                               break;
+               } 
+       }
+
+       page->islocked=0;
+       if ( !page->iscached )
+               tfree(page);
+
+       return rc;
+}
+
+int 
+TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value) {
+       memset(key, 0, sizeof(TBTValue));
+       memset(value, 0, sizeof(TBTValue));
+       return  findLast(db, key, value, TBTPAGEROOT);
+}