linked_list.c

#include "linked_list.h"

void Init(int M, int B){
  total_size = M;
  working_size = total_size;
  block_size = B;
  head = NULL;
  free_ptr =(char*) malloc (total_size);
}

int Insert(int x, char* value_ptr, int value_len){
  // checking if space remaining and decrementing if there is
  // same effect as m/b and checking if space remaining in node is great enough for payload
  if ((working_size<block_size) || (value_len>block_size-(8+sizeof(head)))){
    printf("\n*** Failure on insertion with key %d, incorrect values or not enough space ***\n", x);
    return 1;
  } else {working_size -= block_size;}

  if (head!=NULL){
    struct node* holder;
    holder = free_ptr - block_size;

    free_ptr->next = NULL;
    holder->next = free_ptr;
    free_ptr->key = x;
    free_ptr->val_len = value_len;
    free_ptr->val_ptr = free_ptr+8+sizeof(head);
    memcpy((void *)free_ptr->val_ptr, (void *)value_ptr, value_len);

    free_ptr += block_size;
  } else {
    head = free_ptr;
    free_ptr += block_size;

    head->next = NULL;
    head->key = x;
    head->val_len = value_len;
    head->val_ptr = head+8+sizeof(head);
    memcpy((void *)head->val_ptr, (void *)value_ptr, value_len);
  }
  return 0;
}

void Delete(int x){
  struct node *holder;
  holder = head;
  struct node *temp;
  temp = NULL;    // for the first node

  while ((holder->key!=x) && (holder->next!=NULL)){
    // for assigning previous to next
    temp = holder;
    holder = holder->next;
  }
  if (holder->key==x) {
    if (temp!=NULL) {
      temp->next = holder->next;
    } else {
      head = holder->next;
    }
  } else {
    printf("\n*** Key %d is not in the linked_list ***\n", x);
  }
  working_size += block_size;
}

void Destroy(){
  free_ptr = NULL;
  head = NULL;
  free(free_ptr);
}

struct node* Lookup(int x){
  struct node *holder;
  holder = head;

  while ((holder->key!=x) && (holder->next!=NULL)){
    holder = holder->next;
  }
  if (holder->key==x) {
    printf("\nlets try this shit again\n");
    return holder;
  } else {
    printf("\n*** %d is not in the linked_list ***\n", x);
    return NULL;
  }
}

void PrintList(){
  struct node *holder;
  holder = head;
  printf("\nList:\n");
  while (holder!=NULL){
    printf("Key: %d Value: %s\n", holder->key, holder->val_ptr);
    holder = holder->next;
  }
}

linked_list.h

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

struct node{
  // header
  struct node *next;

  // payload
  int key;
  char* val_ptr;
  int val_len;
};

void 	Init (int M, int b);
int Insert(int x, char* value_ptr, int value_len);
void Delete(int x);
void Destroy();
struct node* Lookup (int x);
void PrintList();

int working_size, total_size, block_size;
struct node* free_ptr;
void* front_ptr;
struct node* head;

main.c

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

int main(int argc, char ** argv)
{
	int b = 128;
	int M = b * 11;  // so we have space for 11 items

	char buf [1024];
	memset (buf, 1, 1024);		// set each byte to 1

	char * msg = "a sample message";
	Init (M,b); // initialize
	// test operations
	int testnums [] = {100, 5, 200, 7, 39, 25, 400, 50, 200, 300};
	int i = 0;
	// some sample insertions
	for (i=0; i< 10; i ++)
	{
		Insert (testnums [i], buf, 50);   // insert 50 bytes from the buffer as value for each of the insertions
	}
	Insert (150, buf, 200); // this Insert should fail
	PrintList ();
	Delete (7);
	Insert (13, msg, strlen(msg)+1);		// insertion of strings, copies the null byte at the end
	PrintList();
	Delete (55);
	Insert (15, "test msg", 8);
	Delete (3);
	PrintList ();
	//
	// // a sample lookup operations that should return null, because it is looking up a non-existent number
	struct node* kv = Lookup (3);
	if (kv)
		printf ("Key = %d, Value Len = %d\n", *(int *) kv, *(int *) (kv+4));


	// this look up  should succeed and print the string "a sample message"
	kv = Lookup (13);
	
// THE FOLLOWING CAUSES AN ERROR:
// For some reason the access of kv causes a seg fault
	if (kv)
		printf ("%s\n", kv->val_ptr);


	// // end test operations
	Destroy ();

}