Buddy Algorithm Implementation using Linked Lists in C

fahad.anwar · 07-17-2012, 12:57 AM

Hi all

I tried implementing a buddy algorithm. But I keep on getting segmentation faults. I am a novice so I would appreciate any help with the code.

thanks in advance

Here is the full code :
Its compiling fine but gives a segfault while execution
The input is of the form
U L
P S
Where the maximum memory size is 2 to the power of U, and the minimum block size is 2 to the power of L.
P is the name of the block to be allocated and is only of the range A to Z and S is the size of the memory to be allocated. If S is 0 then that letter should be deallocated.

Quote:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define LETTER_A 65
#define LETTER_Z 90
#define BASE 2

int minSize;

struct tree_str
{
int used; /* size taken in allocated size */
int size; /* size of size */
char alloc; /* name of allocated size */
struct tree_str * right; /* pointer to right child */
struct tree_str * left; /* pointer to left child */
};

typedef struct tree_str node;

int isLeaf(node * tree)
{
if(!tree->right && !tree->left)
return 1;
return 0;
}

void allocateRec(node * tree, int used, node * small)
{
if(!isLeaf(tree)){
if((tree->left->used != 0))
allocateRec(tree->left, used, small);
if((tree->right->used != 0))
allocateRec(tree->right, used, small);
}
if(isLeaf(tree) && (tree->size > used) && (tree->size < small->size))
{
printf("%d %d %d %d %d\n",isLeaf(tree),used, tree->size, small->size, tree->used);
printf("Found smaller\n");
small = tree;
}
}
void allocate(node * tree, char P, int used)
{
node * small = tree;
allocateRec(tree, used, small);
while(used * 2 <= small->size && small->size >= minSize)
{
// printf("%d %d\n",used, small->size);
small->left = (node *)malloc(sizeof(node));
small->left->size = (small->size / 2);
small->right = (node *)malloc(sizeof(node));
small->right->size = (small->size / 2);
small = small->left;
}
small->used = used;
small->alloc = P;
print(tree);
}

void glue(node * tree)
{
if(!isLeaf(tree))
{
glue(tree->left);
glue(tree->right);
}
if(!isLeaf(tree) && tree->right->used == 0 && tree->left->used == 0){
tree->left = NULL;
tree->right = NULL;
}
}

void deallocRec(node * tree, char P)
{
if(tree->alloc == P)
{
tree->used = 0;
tree->alloc = '\0';
}
if(!isLeaf(tree)){
deallocRec(tree->right, P);
deallocRec(tree->left, P);
}

}
void deallocate(node * tree, char P)
{
deallocRec(tree, P);
glue(tree);
print(tree);
}

void print(node * tree)
{
if(!isLeaf(tree))
print(tree->left);
if(isLeaf(tree)){
if(tree->used == 0)
printf("free:%d\n", tree->size);
else
printf("%c:%d\n",tree->alloc,tree->size);
}
if(!isLeaf(tree))
print(tree->right);

}

int power(int base, int index)
{
int i, pow = 1;
for(i = 0; i < index; i++)
pow *= base;
return pow;
}

int main()
{
int U, L, S;
char P, *in, *pEnd;
node * root = (node *)malloc(sizeof(node));
fgets(in, 20, stdin);
U = strtol (in,&pEnd,10);
L = strtol (pEnd,NULL,10);
minSize = power(BASE, L);
root->size = power(BASE, U);
root->used = 0;
while(1)
{
fgets(in, 20, stdin);
if(P == '\0')
break;
P = *in;
if((int)P >= LETTER_A && (int)P <= LETTER_Z){
S = strtol (in+1,NULL,10);
if(S == 0)
deallocate(root, P);
else
allocate(root, P, S);
}else break;
}
print(root);
return 0;
}

pan64 · 07-17-2012, 02:42 AM

please use [code][/code] to keep formatting. Also please provide a small instruction, how to use (invoke) this tool and how to reproduce the error. Also copy the full error message:

Quote:

Program received signal SIGSEGV, Segmentation fault.
0xff24f9e8 in memccpy () from /lib/libc.so.1
(gdb) where
#0 0xff24f9e8 in memccpy () from /lib/libc.so.1
#1 0xff2cce8c in fgets () from /lib/libc.so.1
#2 0x10c7c in main () at t.c:126

and you will see the variable in has not been initialized, so that causes the segfault.

johnsfine · 07-17-2012, 06:27 AM

Quote:

Originally Posted by fahad.anwar

I tried implementing a buddy algorithm.

I think you have misunderstood the point of the buddy algorithm, so your whole approach is wrong.

I haven't seen the assignment or other materials your instructor gave you, so I can't give you more specific guidance on the algorithm. But on the C programming ...

Code:

void allocateRec(node * tree, int used, node * small)
{
   if(!isLeaf(tree)){
      if((tree->left->used != 0))
         allocateRec(tree->left, used, small);
      if((tree->right->used != 0))
         allocateRec(tree->right, used, small);
      }
   if(isLeaf(tree) && (tree->size > used) && (tree->size < small->size))
   {
      printf("%d %d %d %d %d\n",isLeaf(tree),used, tree->size, small->size, tree->used);
      printf("Found smaller\n");
      small = tree;
   }
}

You seem to misunderstand the nature of parameter passing in C. Parameters are passed by value, not by reference. You seem to expect that modifying a parameters (small) inside a function will modify the caller's copy of that variable outside the function. It doesn't work that way.

fahad.anwar · 07-19-2012, 05:33 AM

Hi all

I made the necessary corrections in my code pointed out by you guys. Thanks a tonne for the help. However I keep getting segfaults when I try to deallocate. Kindly help with that.

Thanks in advance.

PS:
The program takes as input the upper limit and the lower limit of the memory space in terms of power of 2. Therefore,

INPUT
10 4
20

10 is the upper limit -> 2^10=1024 is the biggest memory block
4 is the lower limit -> 2^4=16 is the smallest block size.
20 is the bytes to be allocated.
if I enter 0 for deallocation, i get segfaults and that is what I need help in fixing.

fahad.anwar · 07-22-2012, 11:35 PM

Code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int minSize;
int count;

struct tree_str
{
        int used;                       /* size taken in allocated size */
        int size;                       /* size of size */
        int count;
        char alloc;                     /* name of allocated size */
        struct tree_str * right;        /* pointer to right child */
        struct tree_str * left;         /* pointer to left child */
        struct tree_str * parent;
};

typedef struct tree_str node;

int isLeaf(node * tree)
{
        return (!(tree->right) && !(tree->left));
}

void print(node * tree)
{
    if(!isLeaf(tree))
        print(tree->left);
    if(isLeaf(tree)){
            if(tree->used == 0)
                printf("free:%d\n", tree->size);
            else
                printf("%c:%d\n",tree->alloc,tree->used);
    }
    if(!isLeaf(tree))
        print(tree->right);

}

int isFree(node * tree)
{
        return (tree && isLeaf(tree) && !tree->used);
}

void glue(node* tree)
{
        if(!isLeaf(tree) && isFree(tree->left) && isFree(tree->right))
        {
                free(tree->left);
                free(tree->right);
                tree->left = NULL;
                tree->right = NULL;
                tree->count = ++count;
        }
        if(tree->parent)
                glue(tree->parent);
}

node* dallocRec(node *tree,char P)
{
        printf("\n1\n");
    node *temp;
    if(tree->alloc == P)
    {
        printf("\n1\n");
        tree->used = 0;
        tree->alloc = '\0';
        tree->count = ++count;
        printf("\n1\n");
        return tree;
    }
        printf("\n1\n");
    if(isLeaf(tree))
        return NULL;
    else
    {
        printf("\n1\n");
        if((temp = dallocRec(tree->left, P)))
                return temp;
        printf("\n1\n");
        return dallocRec(tree->right, P);
    }
}

void deallocate(node * tree, char P)
{
        glue(dallocRec(tree, P));
}

node * allocRec(node *tree, int used)
{
    node * left;
    node * right;
    if(tree->used != 0 || tree->size < used)
        return NULL;
    if( (!tree->parent || tree->size >= used) && isLeaf(tree))
        return tree;
    if(!isLeaf(tree) && tree->size >= used)
    {
        if(!(left = allocRec(tree->left, used)))
                return allocRec(tree->right, used);
        if(!(right = allocRec(tree->right, used)))
                return left;
    }
    if(left->size > right->size)
        return right;
    if(left->size < right->size)
        return left;
    if(left->count < right->count)
        return right;
    return left;
}

node * split(node * small, int used)
{
        while(used * 2 <= small->size && small->size > minSize)
        {
                small->left = (node *)calloc(1,sizeof(node));
                small->left->size = (small->size / 2);
                small->left->parent = small;
                small->left->count = ++count;
                small->right = (node *)calloc(1,sizeof(node));
                small->right->size = (small->size / 2);
                small->right->parent = small;
                small->right->count = ++count;
                small = small->left;
        }
        return small;
}
void allocate(node * tree, char P, int used)
{
        node * small = allocRec(tree, used);
        small = split(small, used);
        small->used = used;
        small->alloc = P;
}

int main()
{
        int U, L, S;
        char in[20], *pEnd;
        node * root = (node *)calloc(1,sizeof(node));
        fgets(in, 20, stdin);
        U = strtol (in,&pEnd,10);
        L = strtol (pEnd,NULL,10);
        minSize = 1<<L;
        root->size = 1<<U;
        //fgets() return s on success, and NULL on error or when end of file occurs while no characters have been read.
        while(fgets(in, 20, stdin))
        {
                S = strtol (in,NULL,10);
                if(S == 0)
                        deallocate(root, *in);
                else
                        allocate(root, *in, S);
        }
        print(root);
        return 0;
}