Insertion sort debug help

Question

The following C code doesn't work (it just clears the list):

/* Takes linkedlist of strings */
static int insertSort (linkedlist *list) {
  linkedlist sorted;
  void *data;
  node *one, *two, *newnode;
  unsigned int comp, x;

  removeHeadLL (list, &data);
  initLL (&sorted);
  addHeadLL (&sorted, data);

  while (list->count) {
    removeHeadLL (list, &data);
    two = sorted.head;

    x = 0;
    for (comp = strcomp (data, two->data) ; comp > 1 && x < sorted.count ; x++) {
      one = two;
      two = two->next;
    }

    if (x) {
      newnode = malloc (sizeof(node));
      newnode->next = two;
      newnode->data = data;
      one->next = newnode;
    }
    else {
      addHeadLL(&sorted, data);
    }

    (sorted.count)++;
  }

  destroythis (list);
  list = &sorted;
  return 0;
}

Full context: http://buu700.res.cmu.edu/CMU/15123/6/

Answer 1

Danger, Will Robinson: untested code.

struct list { char *datum; struct list *next; };
typedef struct list *listptr;

listptr insert(char *x, listptr xs) {  

  listptr result = xs;
  listptr *from = &result;
  listptr new = (listptr) malloc(sizeof(struct list));

  while (xs != null && strcmp(xs.datum, x) < 0) {
    from = &xs;
    xs = xs->next;
  }

  new.datum = x;
  new.next = xs;
  *from = new;

  return result;
}

listptr isort(listptr xs) {
  listptr result = null;
  for(; xs != null; xs = xs->next) {
    insert(xs.datum, result);
  }
  return result;
}

Answer 2

If your intent is really to modify the input pointer list to point to the memory allocated inside this function, then you need to declare the function as

static int insertSort (linkedlist **list)

and then return the newly-built list from sorted like so:

*list = &sorted;

As it stands, the call to destroylist frees up what is in list on entry, but the assignment only modifies a local copy of the input pointer.

In other words, in your original code this line:

list = &sorted;

has exactly zero effect outside the function, but this line:

  destroythis (list);

does indeed free up the memory that was owned by list on entry. So after return, your input pointer now accesses an empty list.