Swap Position of the Node in C

Question

Okay so I want to swap POSITION (not values) of two nodes.
My Program is running with any errors or warnings, but I am not sure if I am swapping position or values.
Here is my sort function:

void sort(struct node **recordsHead,int (*compare_fcn)(struct node*, struct node*)) 
{   
 void swap(struct node**, struct node**);   
 struct node *tmp,*lastPtr = NULL;  
 int swapped;
  do {
      swapped = 0;
      tmp = *recordsHead;

      while (tmp->next_ != lastPtr)
      {
          if (compare_fcn(tmp, tmp->next_))
          {
              swap(&tmp, &(tmp->next_));
              swapped = 1;
          }
          tmp = tmp->next_;
      }
            lastPtr = tmp;
      } while (swapped);

}

Here is my Swap Function

void swap(struct node** node1, struct node** node2)
{
  student_record *tmp;

  tmp = (*node1)->record_;
  (*node1)->record_ = (*node2)->record_;
  (*node2)->record_ = tmp;
}

Thank you.

Answer 1

Rachel, continuing from the comments, since you appear to be attempting to 'swap-pointers' in a linked-list, you cannot simply swap adjacent pointers in a list without destroying the linkage between the nodes (e.g. the node->next pointers will no longer point to the next node in the list). Consider the following:

+------+      +------+      +------+     
|  a   |  +-->|  b   |  +-->|  c   |  +--> ...
+------+  |   +------+  |   +------+  |
| next |--+   | next |--+   | next |--+   
+------+      +------+      +------+      

Where

a->next = b;
b->next = c;
c->next ...

If you simply swap the a and b pointers, where do a->next and b-next point?, e.g.

+------+      +------+      +------+     
|  b   |  +-->|  a   |  +-->|  c   |  +--> ...
+------+  |   +------+  |   +------+  |
| next |--+   | next |--+   | next |--+   
+------+      +------+      +------+      

Since you haven't swapped (or re-wired) the next pointers, they still hold (point to) the original memory locations, e.g. a->next = b; and b->next = c; (that's not right, you will skip 'a' completely, and if you did hit a, a->next would backup to b and then b->next skips to c ...)

So if you want to sort by some member value and not swap values, but instead swap pointers, you must "re-wire" each next pointer to point to the node with the next ascending (or descending) member value in correct sort order that is different from simply swapping the a, b, c pointer values.

Next, you have to consider two distinct cases. A rewiring of the first node, and thus changing the address of the list itself (e.g. the head pointer), and then the general case for all other nodes (for a singly-linked-list, circular lists and doubly-linked list will required additional attention to the prev and last->first linkages). The two cases you need to visualize and consider are swaps involving the first node:

         head                  next                next->next
        (iter)              (iter->next)       (iter->next->next)
     +------------+        +------------+        +------------+
     |   Payload  |        |   Payload  |        |   Payload  |
     +------------+        +------------+        +------------+
     |   Next     |------->|   Next     |------->|   Next     |--->+
     +------------+        +------------+        +------------+

and your general case:

         prev                 current                next
        (last)                 iter               (iter->next)
     +------------+        +------------+        +------------+
     |   Payload  |        |   Payload  |        |   Payload  |
     +------------+        +------------+        +------------+
     |   Next     |------->|   Next     |------->|   Next     |--->+
     +------------+        +------------+        +------------+

For cases involving the head node (and using struct node *iter = *head; and choosing tmp = iter->next; for the replacement, you would do something like the following:

            if (iter == *head) {
                struct node *tmp = iter->next;
                iter->next = tmp->next;
                tmp->next = iter;
                *head = tmp;
                iter = *head;
            }

To handle the general case (in the following else clause, you would do something like the following:

            else {
                struct node *tmp = iter->next;
                iter->next = tmp->next;
                tmp->next = last->next;
                last->next = tmp;
                iter = tmp;
            }
            swapped = 1;

You would use no swap function in your code at all (you could, but you would need to pass the list address so a comparison for head could take place.

Putting all the pieces together in a short example and sorting in ascending order on an integer value within each node, you can do something like the following:

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

#define MAXN 10

typedef struct node {
    int val;
    struct node *next;
} node;

int cmp (struct node *a, struct node *b) {
    /* (a > b) - (a < b) */
    return (a->val > b->val) - (a->val < b->val);
}

void sort (struct node **recordsHead, 
            int (*compare_fcn)(struct node*, struct node*));

int main (void) {

    srand (time (NULL));

    node *head = NULL;

    for (int i = 0; i < MAXN; i++) 
    {
        node *newnode = malloc (sizeof *newnode);
        if (!newnode) { /* allocate node and validate memory */
            fprintf (stderr, "error: memory exhausted node '%d'.\n", i);
            break;
        }

        newnode->val = rand() % 100;    /* initialize pointers */
        newnode->next = NULL;

        if (!head)          /* new list, assign to head */
            head = newnode;
        else {              /* otherwise iterate and add to end */
            node *iter = head;
            for (; iter->next; iter = iter->next) {}
            iter->next = newnode;
        }
    }

    int j = 0;  /* output list (including pointer addresses) */
    printf ("\noriginal pointer and value order:\n\n");
    for (node *iter = head; iter; iter = iter->next)
        printf ("node[%3d] : %3d,       addr: %p, next: %p\n",
                j++, iter->val, (void*)iter, (void*)iter->next);

    sort (&head, cmp);  /* sort by swapping pointers */

    j = 0;      /* output sorted list (with addresses */
    printf ("\nsorted pointer and value order:\n\n");
    for (node *iter = head; iter; iter = iter->next)
        printf ("node[%3d] : %3d,       addr: %p, next: %p\n",
                j++, iter->val, (void*)iter, (void*)iter->next);

    /* free list memory */
    node *victim = NULL;    /* node to delete */
    for (node *iter = head; iter; iter = iter->next) {
        if (victim)     /* cannot delete until after loop increment */
            free (victim);
        victim = iter;  /* so save node as victim, delete next iteration */
    }
    if (victim)         /* free last node */
        free (victim);

    return 0;
}

/* sort (ascending) by rewiring nodes */
void sort (struct node **head, int (*compare_fcn)(struct node*, struct node*)) 
{   
    struct node *iter, *last = NULL;  
    int swapped;

    do {    /* while a swap occurs during iterating list */
        swapped = 0;
        iter = *head;

        while (iter->next != NULL)  /* traverse each node in list */
        {
            if (compare_fcn (iter, iter->next) > 0) /* sort ascending */
            {
                if (iter == *head) {    /* swap head pointers (rewire) */
                    struct node *tmp = iter->next;
                    iter->next = tmp->next;
                    tmp->next = iter;
                    *head = tmp;
                    iter = *head;
                }
                else {  /* swap of remaining nondes (rewire pointers) */
                    struct node *tmp = iter->next;
                    iter->next = tmp->next;
                    tmp->next = last->next;
                    last->next = tmp;
                    iter = tmp;
                }
                swapped = 1;    /* swap flag */
            }
            last = iter;        /* update last */
            iter = iter->next;  /* advance ptr */
        }
    } while (swapped);
}

Example Use/Output

$ ./bin/llminsort

original pointer and value order:

node[  0] :  63,       addr: 0x9fb010, next: 0x9fb030
node[  1] :  76,       addr: 0x9fb030, next: 0x9fb050
node[  2] :   4,       addr: 0x9fb050, next: 0x9fb070
node[  3] :  95,       addr: 0x9fb070, next: 0x9fb090
node[  4] :  76,       addr: 0x9fb090, next: 0x9fb0b0
node[  5] :  64,       addr: 0x9fb0b0, next: 0x9fb0d0
node[  6] :  81,       addr: 0x9fb0d0, next: 0x9fb0f0
node[  7] :  43,       addr: 0x9fb0f0, next: 0x9fb110
node[  8] :  51,       addr: 0x9fb110, next: 0x9fb130
node[  9] :  68,       addr: 0x9fb130, next: (nil)

sorted pointer and value order:

node[  0] :   4,       addr: 0x9fb050, next: 0x9fb0f0
node[  1] :  43,       addr: 0x9fb0f0, next: 0x9fb110
node[  2] :  51,       addr: 0x9fb110, next: 0x9fb010
node[  3] :  63,       addr: 0x9fb010, next: 0x9fb0b0
node[  4] :  64,       addr: 0x9fb0b0, next: 0x9fb130
node[  5] :  68,       addr: 0x9fb130, next: 0x9fb030
node[  6] :  76,       addr: 0x9fb030, next: 0x9fb090
node[  7] :  76,       addr: 0x9fb090, next: 0x9fb0d0
node[  8] :  81,       addr: 0x9fb0d0, next: 0x9fb070
node[  9] :  95,       addr: 0x9fb070, next: (nil)

Memory Leak/Error Check

It is imperative that you use a memory error checking program to insure you do not attempt to write beyond/outside the bounds of your allocated block of memory, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/llminsort
==1844== Memcheck, a memory error detector
==1844== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==1844== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==1844== Command: ./bin/llminsort
==1844==

original pointer and value order:

node[  0] :  27,       addr: 0x51d8040, next: 0x51d8090
node[  1] :  68,       addr: 0x51d8090, next: 0x51d80e0
node[  2] :  55,       addr: 0x51d80e0, next: 0x51d8130
node[  3] :  44,       addr: 0x51d8130, next: 0x51d8180
node[  4] :  47,       addr: 0x51d8180, next: 0x51d81d0
node[  5] :  10,       addr: 0x51d81d0, next: 0x51d8220
node[  6] :   8,       addr: 0x51d8220, next: 0x51d8270
node[  7] :  13,       addr: 0x51d8270, next: 0x51d82c0
node[  8] :  73,       addr: 0x51d82c0, next: 0x51d8310
node[  9] :  11,       addr: 0x51d8310, next: (nil)

sorted pointer and value order:

node[  0] :   8,       addr: 0x51d8220, next: 0x51d81d0
node[  1] :  10,       addr: 0x51d81d0, next: 0x51d8310
node[  2] :  11,       addr: 0x51d8310, next: 0x51d8270
node[  3] :  13,       addr: 0x51d8270, next: 0x51d8040
node[  4] :  27,       addr: 0x51d8040, next: 0x51d8130
node[  5] :  44,       addr: 0x51d8130, next: 0x51d8180
node[  6] :  47,       addr: 0x51d8180, next: 0x51d80e0
node[  7] :  55,       addr: 0x51d80e0, next: 0x51d8090
node[  8] :  68,       addr: 0x51d8090, next: 0x51d82c0
node[  9] :  73,       addr: 0x51d82c0, next: (nil)
==1844==
==1844== HEAP SUMMARY:
==1844==     in use at exit: 0 bytes in 0 blocks
==1844==   total heap usage: 10 allocs, 10 frees, 160 bytes allocated
==1844==
==1844== All heap blocks were freed -- no leaks are possible
==1844==
==1844== For counts of detected and suppressed errors, rerun with: -v
==1844== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Look things over and let me know if you have any further questions.