Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

B+ Tree C Implementation

linked list b+ tree

  • Please log in to reply
3 replies to this topic

#1 makkx9

makkx9

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 15 May 2008 - 04:10 PM

Hi,
I have to implement a B+ Tree, I found this code online.
This code allows to insert and lookup.

First you will be prompted to enter number of keys to insert, number of lookups to perform, and whether duplicates keys are allowed or not.

e.g. 5 2 0 (# keys to insert, # keys to search, no duplicate keys).

The main program is easy to understand, but the functions are not that straight forward.
The insert works just fine, but the lookup (second loop in main) goes into an infinite loop in the function Lookup(int Index, long Key).

I just want to get the lookup working.
Any ideas or suggestions is appreciated. I am a Pathobiology student, I do not have much experience in programming.

I have the link for the source code and sample input if you are interested.
The function call that is casing the problem is highlighted in RED.
C Code:

/************** Bplustree.c *****************/
/* To Compile gcc -o Bplustree Bplustree.c */
/* To Run Bplustree <input */
/*******************************************************/

#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <string.h>

#ifndef _BTREE_

#ifdef __cplusplus
extern "C" {
#endif

int OpenIndex(char *Name, int DupKeys);
/* open or create index file, find free entry in index table,
fill in entry, DupKeys is 1 if duplicate keys are allowed, 0 if not,
return number of entry in table */

void CloseIndex(int Index);
/* close Index file, free entry in index info table */

int Insert(int Index, long Key, long Ptr);
/* insert Key & Ptr in index file, return 0 for success, nonzero for error */

long Lookup(int Index, long Key);
/* return pointer for entry in Index file <= Key, return -1 if none */


#ifdef __cplusplus
}
#endif

#endif

#define ORDER 64
#define BLKSIZE (ORDER*8)
#define BKTPTRS (ORDER*2 - 1)
#define NLEN 40
#define NIDX 20
#define SEEK_SET 0

typedef struct {
short LeafNode;
short KeyCount;
long Keys[ORDER - 1];
long Ptrs[ORDER];
} NodeType;

typedef struct {
long RootBlock;
long AllocBlock;
char Junk[BLKSIZE - 2*sizeof(long)];
} HeadType;

typedef struct {
long Pointers[BKTPTRS];
long NextBucket;
} BucketType;

typedef struct {
int Used;
int File;
char Name[NLEN];
int DupKeys;
long RootBlk;
long AllocBlk;
long CurBlk;
short CurKey;
short CurPtr;
} IdxInfo;
#define File(Idx) (IdxTab[Idx].File)
#define Root(Idx) (IdxTab[Idx].RootBlk)
#define Used(Idx) (IdxTab[Idx].Used)
#define Dups(Idx) (IdxTab[Idx].DupKeys)
#define Alloc(Idx) (IdxTab[Idx].AllocBlk)
#define CBlk(Idx) (IdxTab[Idx].CurBlk)
#define CKey(Idx) (IdxTab[Idx].CurKey)
#define CPtr(Idx) (IdxTab[Idx].CurPtr)

BucketType Bucket;

static IdxInfo IdxTab[NIDX];

static void ReadBlock(int File, long Block, int Size, void *Addr) {
/*
printf("ReadBlock(File %d, Block %ld, Size %d, Addr %x)\n",
File, Block, Size, Addr);
*/

if(lseek(File, Block * Size, SEEK_SET) == -1 ||
read(File, Addr, Size) == -1)
printf("ReadBlock Error, File %d, Block %d, Size %d\n",
File, Block, Size);
}

static void WriteBlock(int File, long Block, int Size, void *Addr) {
/*
printf("WriteBlock(File %d, Block %ld, Size %d, Addr %x)\n",
File, Block, Size, Addr);
*/
if(lseek(File, Block * Size, SEEK_SET) == -1 ||
write(File, Addr, Size) == -1)
printf("WriteBlock Error, File %d, Block %d, Size %d\n",
File, Block, Size);
}

static void ReadHead(int Index) {
HeadType HeadBlock;
ReadBlock(File(Index), 0, BLKSIZE, &HeadBlock);
Root(Index) = HeadBlock.RootBlock;
Alloc(Index) = HeadBlock.AllocBlock;
}

static void WriteHead(int Index) {
HeadType HeadBlock;
int i;
HeadBlock.RootBlock = Root(Index);
HeadBlock.AllocBlock = Alloc(Index);
WriteBlock(File(Index), 0, BLKSIZE, &HeadBlock);
}

int OpenIndex(char *Name, int DupKeys) {
int i;
int j;
for(i = 0; i < NIDX; i++)
if(!Used(i)) break;
Used(i) = 1;
strcpy(IdxTab[i].Name, Name);
Dups(i) = DupKeys;
CBlk(i) = -1;
if((File(i) = open(Name, O_RDWR)) >= 0) {
ReadHead(i);
} else
/* if((File(i) = creat(Name, S_IREAD|S_IWRITE)) >= 0) { */
if((File(i) = open(Name, O_RDWR|O_CREAT, 0644)) >= 0) {
NodeType Node;
Root(i) = 1;
Alloc(i) = 2;
WriteHead(i);
Node.LeafNode = 1;
Node.KeyCount = 0;
for(j = 0; j < ORDER-1; j++)
{
Node.Ptrs[j] = -1;
Node.Keys[j] = 0;
}
Node.Ptrs[ORDER - 1] = -1;
WriteBlock(File(i), 1, BLKSIZE, &Node);
} else {
perror("OpenIndex");
Used(i) = 0;
i = -1;
}
return i;
}

void CloseIndex(int Index) {
WriteHead(Index);
close(File(Index));
Used(Index) = 0;
}

static int FindKey(NodeType *Node, long Key) {
int k;
for(k = 0; k < Node->KeyCount; k++)
if(Node->Keys[k] > Key) break;
return k;
}

static void CheckBucket(int Index, NodeType *Node, long *Key, long *Ptr) {
*Ptr = -1;
if(CBlk(Index) >= 0) {
long NextPtr;
*Key = Node->Keys[CKey(Index)-1];
*Ptr = Node->Ptrs[CKey(Index)];
if(Dups(Index)) {
/* BucketType Bucket; */
ReadBlock(File(Index), *Ptr, BLKSIZE, &Bucket);
*Ptr = Bucket.Pointers[CPtr(Index)];
CPtr(Index)++;
NextPtr = Bucket.Pointers[CPtr(Index)];
}
if(!Dups(Index) || NextPtr < 0) {
CPtr(Index) = 0;
CKey(Index)++;
if(CKey(Index) > Node->KeyCount) {
CBlk(Index) = Node->Ptrs[0];
CKey(Index) = 1;
}
}
/*
printf("I%d K%ld P%ld\n", Index, *Key, *Ptr);
*/
}
}

long Lookup(int Index, long Key) {
NodeType Node;
long Ptr;
CBlk(Index) = Root(Index);
for(; ;) {
ReadBlock(File(Index), CBlk(Index), BLKSIZE, &Node);
CKey(Index) = FindKey(&Node, Key);
if(Node.LeafNode) break;
CBlk(Index) = Node.Ptrs[CKey(Index)];
}
CPtr(Index) = 0;
if(CKey(Index) == 0) CBlk(Index) = -1;
CheckBucket(Index, &Node, &Key, &Ptr);
return Ptr;
}



static int InsertKey(int Index, NodeType *Node, int KIdx, long *Key, long *Ptr) {
long Keys[ORDER], Ptrs[ORDER+1];
int Count, Count1, Count2, k;
Count = Node->KeyCount + 1;
Count1 = Count < ORDER ? Count : ORDER/2;
Count2 = Count - Count1;
for(k = ORDER/2; k < KIdx; k++) {
Keys[k] = Node->Keys[k];
Ptrs[k+1] = Node->Ptrs[k+1];
}
Keys[KIdx] = *Key;
Ptrs[KIdx+1] = *Ptr;
for(k = KIdx; k < Node->KeyCount; k++) {
Keys[k+1] = Node->Keys[k];
Ptrs[k+2] = Node->Ptrs[k+1];
}
for(k = KIdx; k < Count1; k++) {
Node->Keys[k] = Keys[k];
Node->Ptrs[k+1] = Ptrs[k+1];
}
Node->KeyCount = Count1;
if(Count2) {
int s, d;
NodeType NNode;
NNode.LeafNode = Node->LeafNode;
Count2 -= !Node->LeafNode;
for(s = ORDER/2 + !Node->LeafNode, d = 0; d < Count2; s++, d++) {
NNode.Keys[d] = Keys[s];
NNode.Ptrs[d] = Ptrs[s];
}
NNode.Ptrs[d] = Ptrs[s];
NNode.KeyCount = Count2;
*Key = Keys[ORDER/2];
*Ptr = Alloc(Index)++;
if(Node->LeafNode) { /* insert in sequential linked list */
NNode.Ptrs[0] = Node->Ptrs[0];
Node->Ptrs[0] = *Ptr;
}
WriteBlock(File(Index), *Ptr, BLKSIZE, &NNode);
WriteHead(Index);
}
return Count2;
}

static long NewBucket(int Index, long Ptr, long Next) {
long BBlk;
int j;
BucketType Bucket;
Bucket.Pointers[0] = Ptr;
Bucket.Pointers[1] = -1;
Bucket.NextBucket = Next;
BBlk = Alloc(Index)++;
WriteBlock(File(Index), BBlk, BLKSIZE, &Bucket);
WriteHead(Index);
return BBlk;
}

static int Error;

static int RecInsert(int Index, long Block, long *Key, long *Ptr) {
NodeType Node;
int KIdx, Split = 0;
int EqualKey;
ReadBlock(File(Index), Block, BLKSIZE, &Node);
KIdx = FindKey(&Node, *Key);
EqualKey = KIdx && Node.Keys[KIdx-1] == *Key;
if(!Node.LeafNode)
Split = RecInsert(Index, Node.Ptrs[KIdx], Key, Ptr);
if(Split || Node.LeafNode && !EqualKey) {
if(Node.LeafNode && Dups(Index))
*Ptr = NewBucket(Index, *Ptr, -1);
Split = InsertKey(Index, &Node, KIdx, Key, Ptr);
WriteBlock(File(Index), Block, BLKSIZE, &Node);
} else if(Node.LeafNode && Dups(Index)) { /* put in existing bucket */
BucketType Bucket;
int i;
ReadBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);
for(i = 0; i < BKTPTRS && Bucket.Pointers[i] >= 0; i++);
if(i < BKTPTRS) {
Bucket.Pointers[i] = *Ptr;
if(i < BKTPTRS-1) Bucket.Pointers[i+1] = -1;
WriteBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);
} else {
printf("ERROR: Bucket Overflow\n");
}
} else if(Node.LeafNode) {
Error = -1;
}
return Split;
}

int Insert(int Index, long Key, long Ptr) {
int Split;
Error = 0;
Split = RecInsert(Index, Root(Index), &Key, &Ptr);
if(Split) {
NodeType Node;
Node.LeafNode = 0;
Node.KeyCount = 1;
Node.Keys[0] = Key;
Node.Ptrs[1] = Ptr;
Node.Ptrs[0] = Root(Index);
Root(Index) = Alloc(Index)++;
WriteBlock(File(Index), Root(Index), BLKSIZE, &Node);
WriteHead(Index);
}
CBlk(Index) = -1;
return Error;
}

main() {

/********************************************************************/
/* The main section of code should be replaced. */
/* It just illustrates how keys and addresses can be inserted */
/* into a B+ tree and then retrieved */
/********************************************************************/

char Xname[8];
int Xdupkeys;
int XEntryNum;
long XKey, XPtr;
int RetnCode;
int i,j;

int NumInsert, NumLookup;

printf("start main\n");

Xdupkeys = 0;
Xname[0] = 'm';
Xname[1] = 'y';
Xname[2] = 'f';
Xname[3] = 'i';
Xname[4] = 'l';
Xname[5] = 'e';


/********************************************************************/
/* read number of keys to insert, the number of keys to search for */
/* and whether duplicates are allowed in the index */
/********************************************************************/

scanf("%d %d %d",&NumInsert, &NumLookup, &Xdupkeys);

XEntryNum = OpenIndex(Xname, Xdupkeys);

for(i = 0; i < NumInsert; i++){
printf("Insert KEY, PTR:");
/* read key and address to insert into the B+ tree */

scanf("%d %d",&XKey, &XPtr);
printf("%d %d",XKey, XPtr);
printf("\n");

RetnCode = Insert(XEntryNum, XKey, XPtr);
if (RetnCode != 0)
printf("Error During Key Insertion\n");
}


for(i = 0; i < NumLookup; i++)
{

/* read key to lookup in the B+ tree */
printf("Search KEY:");
scanf("%d",&XKey);
printf("%d",XKey);
printf("\n");
[B][COLOR="Red"]XPtr = Lookup(XEntryNum, XKey); [/COLOR][/B]
if (Xdupkeys == 0) {
printf("Key value is %d and Ptr value is %d\n", XKey, XPtr);
}
else
printf("Key value is %d\n", XKey);

if (Xdupkeys == 1) {
j = 0;
while (Bucket.Pointers[j] != -1) {
printf("Ptr value is %d\n", Bucket.Pointers[j]);
j++;
}
}
}


CloseIndex(XEntryNum);

printf("finish main\n");


}

Any suggestions or ideas is appreciated.

Thank you,

Edited by Roger, 20 September 2013 - 01:47 PM.
tags

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 17 May 2008 - 02:12 PM

In your ForLookup function, if Node.LeafNode is never true for some reason, that would cause the infinite loop condition.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 HackerxSasi

HackerxSasi

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 20 September 2013 - 08:45 AM

XPtr = Lookup(XEntryNum, XKey);

 

the above line is giving me error please help ..!!!

 

it throws expression syntax .... please help ...


Edited by dargueta, 21 September 2013 - 09:03 AM.

  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 20 September 2013 - 12:31 PM

What is the exact error message? Nothing is obviously incorrect.


  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: linked list, b+ tree

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download