linked list insertion

[Dewey1040]

so I haven't used pointers to this extent for a few years so I'm a little rusty.

I'll give a quick explanation on what the code is supposed to do, but from looking at my output I am messing up pointer arithmetic somewhere along the lines. I'm pretty sure it's a syntax error with pointers somewhere along the lines, so try to spot the error and if you need more explanation on what the code is doing or if you need more code from my program just let me know.

Here is the linked list struct I'm using:

typedef struct free_list{
  struct free_list *next;
  struct free_list *previous;
  int block_size;
  int block_adr;
  int adjacent_adr;
}list_node;

Here is the code in the main file that is applicable to the error(I think but if you think you need to see more just let me know)

  list_node header_node;

  list_node current_node;

    //This is the for the first node created

    header_node.next = (list_node*) malloc(sizeof(list_node));
    header_node.previous = 0;
    header_node.block_size = size;
    header_node.adjacent_adr = memory - 1;

    current_node = header_node;

    //this is for all subsequent nodes

    current_node.next = NULL;
    current_node.previous = 0;
    current_node.block_size = size;
    current_node.block_adr = -1;
    current_node.adjacent_adr = -1;

    insert_first(&header_node, &current_node);

Finally here is the insert function I'm using(its not a normal insert function, once again the problem is the syntax not the algorithm, but if you need a little insight on what is going on just ask)

void insert_first(list_node *current, list_node *new){

  list_node *tmp;

  if( (current->adjacent_adr - (current->block_adr + current->block_size)) <
      new->block_size )
    insert_first( current->next, new );
  else{

    if(current->next == NULL){
      current->next = new;
    }else{
      tmp = current->next;
      current->next = new;
      new->next = tmp;
    }
    new->previous = current;
    new->block_adr = current->block_size + current->block_adr;

    new->adjacent_adr = current->adjacent_adr;
    current->adjacent_adr = new->block_adr;

    total_free_space = total_free_space - new->block_size;
    free_list_length++;

  }

}

This last piece of code is looking to return the size of the biggest space of memory available in the linked list(The list starts automatically with 1024000 made up bytes of memory) The purpose of the code is to add and remove pieces of the linked list with arbitrary amounts of memory, then put the newest node into the first spot it would fit.

int largest_chunk( list_node *current, int largest, int memory ){

  if( current->adjacent_adr != memory-1 ){
    if( (current->adjacent_adr - (current->block_size + current->block_adr))
        > largest )
      return( largest_chunk( current->next, (current->adjacent_adr -
                                             (current->block_size +
                                              current->block_adr)), memory));
  }else{
    printf("got here\n");
    return(largest);
  }
}

Once again any help will be appreciated, I know you may not fully understand what it is I'm trying to do, but the problem comes from playing with the pointers. Any questions just ask.

[deceptikon]

Could you be a little more specific as to what exactly the error is? All I see is code and vague references to "something's wrong".

[rubberman]

Remember that memory allocations are ALWAYS on word boundaries, and aligning structures that are stored in an opaque buffer requires that you ALWAYS align the structure on a word boundary. This is likely why your math is not working as you expect.

[Dewey1040]

Sorry about the delayed response I went away for the weekend.

The issue I'm currently having, is the largest_chunk algorithm. I've slightly altered my code as follows, but whats happening right now is the largest_chunk algorithm is returning 0. I'll give a quick explanation as to what I'm attempting to do; each node has a fake address listed as list_node.block_adr, and the largest chunk algorithm is finding the biggest chunk of free space after some is freed up. So here are a few lines my program will read in:

 1          alloc               99744
 2          alloc              111776
 3          alloc               64864
 4          alloc               91552
 5          free                                2

To start there will be 1MB(1048576) of free space, the first four of these input lines will create four nodes in my linked list as long as there is available space(which there will be). Then line 5 will free the second allocation, so in the linked list there will be 3 nodes, and there will be free space of 111776 in between node 1 and node 2. After more allocations and frees largest_chunk will compare the free spaces and return the largest chunk. To begin the largest chunk will always be at the end of the linked list because the last nodes adjacent_adr will be equal to 1048575.

My code works fine with the first output 1048575 - 99743 = 948832, but after that it is just returning 0 and I'm stumped as to where I'm going wrong. Here is my updated code that is relevent. (If i didn't include something from above it didnt change)

initializtion of the header_node(first node in the list which shouldn't change) and the current_node(the node that the program is currently reading/ updating)

  list_node header_node;

  list_node *current_node;

This is initializing the header_node for the first line of input. which shouldn't change throughout the program.

    header_node.next = (list_node*) malloc(sizeof(list_node));
    header_node.previous = 0;
    header_node.block_size = size;
    header_node.adjacent_adr = memory - 1;

    current_node = header_node.next;

This is what is used for the second and all subsequent run throughs of my program.

      current_node->next = (list_node *) malloc(sizeof(list_node));

      current_node->next = NULL;

      current_node->previous = 0;
      current_node->block_size = size;
      current_node->block_adr = -1;
      current_node->adjacent_adr = -1;

      printf("got here\n");

      insert_first(&header_node, current_node);

This is the algorithm to insert new nodes into the first spot of the linked list they would fit, so if there are freed blocks then starting from the list header and going through the list the node is inserted into the first spot it will fit(at the beginning it will just be the end).

void insert_first(list_node *current, list_node *new){

  list_node *tmp;

  printf(" %d \n", current->block_size );

  if( (current->adjacent_adr - (current->block_adr + current->block_size)) <
      new->block_size )
    insert_first( current->next, new );
  else{

    if(current->next == NULL){
      current->next = new;
    }else{

      tmp = (list_node*) malloc(sizeof(list_node));

      tmp = current->next;
      current->next = new;
      new->next = tmp;
    }

    new->previous = current;
    new->block_adr = current->block_size + current->block_adr;

    new->adjacent_adr = current->adjacent_adr;
    current->adjacent_adr = new->block_adr;

    total_free_space = total_free_space - new->block_size;
    free_list_length++;

  }

}

Finally here is the largest_chunk algorithm I have

void insert_first(list_node *current, list_node *new){

  list_node *tmp;

  printf(" %d \n", current->block_size );

  if( (current->adjacent_adr - (current->block_adr + current->block_size)) <
      new->block_size )
    insert_first( current->next, new );
  else{

    if(current->next == NULL){
      current->next = new;
    }else{

      tmp = (list_node*) malloc(sizeof(list_node));

      tmp = current->next;
      current->next = new;
      new->next = tmp;
    }

    new->previous = current;
    new->block_adr = current->block_size + current->block_adr;

    new->adjacent_adr = current->adjacent_adr;
    current->adjacent_adr = new->block_adr;

    total_free_space = total_free_space - new->block_size;
    free_list_length++;

  }

}

[Dewey1040]

So I got farther and that isn't my error anymore, now I'm getting a segmentation fault 23 items down the list after multiple allocations and frees have been completed. I'm almost positive it has to do with my updated insertion or free functions. Here are my updated functions, and I'm not sure if it's helpful or not, but somewhere down the line the adjacent_adr of one or more nodes(not sure how many but definitely not all of them) got messed up and the function is inserting a node to the middle when it should be going to the end.

void insert_first(list_node *current, list_node *new){

  list_node *tmp;

  if( current->previous == NULL && current->block_adr > new->block_size){
    new->previous = NULL;
    new->next = current;
    new->adjacent_adr = current->block_adr;
    new->block_adr = 0;
  }else{
    if( (current->adjacent_adr - (current->block_adr + current->block_size))
    < new->block_size ){

      insert_first( current->next, new );

    }else{

      printf("size+adr: %d\n", current->block_adr + current->block_size );
      printf("adjacent: %d\n", current->adjacent_adr );

      tmp = current->next;
      current->next = new;
      new->next = tmp;
      new->adjacent_adr = current->adjacent_adr;

      new->previous = current;
      new->block_adr = current->block_size + current->block_adr;

      current->adjacent_adr = new->block_adr;

      total_free_space = total_free_space - new->block_size;

    }

  }

}



void insert_first(list_node *current, list_node *new){

  list_node *tmp;

  if( current->previous == NULL && current->block_adr > new->block_size){
    new->previous = NULL;
    new->next = current;
    new->adjacent_adr = current->block_adr;
    new->block_adr = 0;
  }else{
    if( (current->adjacent_adr - (current->block_adr + current->block_size))
    < new->block_size ){

      insert_first( current->next, new );

    }else{

      printf("size+adr: %d\n", current->block_adr + current->block_size );
      printf("adjacent: %d\n", current->adjacent_adr );

      tmp = current->next;
      current->next = new;
      new->next = tmp;
      new->adjacent_adr = current->adjacent_adr;

      new->previous = current;
      new->block_adr = current->block_size + current->block_adr;

      current->adjacent_adr = new->block_adr;

      total_free_space = total_free_space - new->block_size;

    }

  }

}