Infinite Loop with Pointers - Why?

Question

I am relatively new to C & pointers. I am trying to sort and then print a linked list of structs. Either I am missing a logical error or I am not fully understanding pointers. Can someone please explain to me what I am missing in this code? Thank you kindly in advance!

// *** Sort Linked List ( Merge Sort ) ***

struct address_node *newRoot;

// ptr, rearPtr, and tempRoot are also struct Pointers
newRoot = root;
root = root->next;

while (root != NULL)
{
    tempRoot = root;
    ptr = newRoot;
    rearPtr = newRoot;

    while (ptr != NULL)
    {
        printf("here");
        if ((root->frequency) == (ptr->frequency))
        {                       // SPECIAL CASE: To determine read hierarchy for repeated
                                // Entries
            if ((root->read_order) < (ptr->read_order))
            {
                if (ptr == newRoot)
                {
                    root = root->next;
                    tempRoot->next = newRoot;
                    newRoot = tempRoot;
                    ptr = NULL;
                }
                else
                {
                    root = root->next;
                    tempRoot->next = ptr;
                    rearPtr->next = tempRoot;
                    ptr = NULL;
                }
            }
        }
        else if ((root->frequency) > ptr->frequency)
        {                       // To ADD BEFORE an ENTRY
            if (ptr == newRoot)
            {
                root = root->next;
                tempRoot->next = newRoot;
                newRoot = tempRoot;
                ptr = NULL;
            }
            else
            {
                root = root->next;
                tempRoot->next = ptr;
                rearPtr->next = tempRoot;
                ptr = NULL;
            }
        }
        else if (ptr->next == NULL)
        {                       // if END OF LIST
            root = root->next;
            ptr->next = tempRoot;
            ptr = NULL;
        }
        else
        {                       // SPOT NOT FOUND YET< MOVE FORWARD THROUGH LIST
            rearPtr = ptr;
            ptr = ptr->next;
        }
    }
}

// *** PRINT ***
ptr = newRoot;
if (numOut == 0)
{
    while (ptr != NULL)
    {
        printf("0x%zx :%d\n", ptr->address, ptr->frequency);
        ptr = ptr->next;
    }
}
else
{
    while (ptr != NULL && numOut > 0)
    {
        printf("0x%zx :%d\n", ptr->address, ptr->frequency);
        numOut--;
        ptr = ptr->next;
    }
}

Answer 1

You are not ensuring that root is updated on every iteration of the inner loop. For example, given this instrumented variation on your code:

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

struct address_node
{
    struct address_node *next;
    int frequency;
    int read_order;
};
static void sort_list(struct address_node * *root);
static void print_list(char const *tag, struct address_node const *root);

int main(void)
{
    struct address_node data[] =
    {
        { &data[1], 43, 0 },
        { &data[2], 23, 1 },
        { &data[3], 13, 2 },
        { &data[4], 27, 3 },
        { &data[5], 57, 4 },
        { &data[6], 17, 5 },
        { &data[7], 27, 6 },
        { &data[8], 20, 7 },
        { &data[9], 30, 8 },
        {     NULL, 50, 9 },
    };
    struct address_node *root = &data[0];

    print_list("Before", root);
    sort_list(&root);
    print_list("After", root);
}

static void sort_list(struct address_node **proot)
{
    struct address_node *root = *proot;
    struct address_node *newRoot;
    struct address_node *ptr;
    struct address_node *rearPtr;
    struct address_node *tempRoot;

    printf("-->> %s: root 0x%.12" PRIXPTR "\n", __func__, (uintptr_t)root);
    newRoot = root;
    root = root->next;


    while (root != NULL)
    {
        tempRoot = root;
        ptr = newRoot;
        rearPtr = newRoot;

        while (ptr != NULL)
        {
            printf("here  1: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
            if (root->frequency == ptr->frequency)
            {
                printf("here  2: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                if (root->read_order < ptr->read_order)
                {
                    if (ptr == newRoot)
                    {
                        root = root->next;
                        tempRoot->next = newRoot;
                        newRoot = tempRoot;
                        ptr = NULL;
                        printf("here 2A: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                    }
                    else
                    {
                        root = root->next;
                        tempRoot->next = ptr;
                        rearPtr->next = tempRoot;
                        ptr = NULL;
                        printf("here 2B: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                    }
                }
                else
                    printf("here 2C: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
            }
            else if (root->frequency > ptr->frequency)
            {
                printf("here  3: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                if (ptr == newRoot)
                {
                    root = root->next;
                    tempRoot->next = newRoot;
                    newRoot = tempRoot;
                    ptr = NULL;
                    printf("here 3A: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                }
                else
                {
                    root = root->next;
                    tempRoot->next = ptr;
                    rearPtr->next = tempRoot;
                    ptr = NULL;
                printf("here 3B: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                }
            }
            else if (ptr->next == NULL)
            {
                printf("here  4: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                root = root->next;
                ptr->next = tempRoot;
                ptr = NULL;
            }
            else
            {
                printf("here  5: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                rearPtr = ptr;
                ptr = ptr->next;
            }
        }
    }
    *proot = root;
    printf("<<-- %s: root 0x%.12" PRIXPTR "\n", __func__, (uintptr_t)root);
}

static void print_list(char const *tag, struct address_node const *root)
{
    printf("%s: 0x%.12" PRIXPTR "\n", tag, (uintptr_t)root);
    while (root != NULL)
    {
        printf("0x%.12" PRIXPTR " : %2d %2d\n",
              (uintptr_t)root, root->frequency, root->read_order);
        root = root->next;
    }
}

The output I get starts:

Before: 0x7FFF5382D440
0x7FFF5382D440 : 43  0
0x7FFF5382D450 : 23  1
0x7FFF5382D460 : 13  2
0x7FFF5382D470 : 27  3
0x7FFF5382D480 : 57  4
0x7FFF5382D490 : 17  5
0x7FFF5382D4A0 : 27  6
0x7FFF5382D4B0 : 20  7
0x7FFF5382D4C0 : 30  8
0x7FFF5382D4D0 : 50  9
-->> sort_list: root 0x7FFF5382D440
here  1: root 0x7FFF5382D450
here  5: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450

It doesn't get any more exciting after this. You need the inner loop to progress forward on every iteration, I believe, so you need to ensure that root is updated each time around. The else clause (5) does not alter root at all; neither does the (2C) clause. So, you need to go back and ensure that root is updated appropriately on every iteration. If the change is always root = root->next;, you should investigate whether a for loop with root = root->next as the reinitialization condition is appropriate.

Answer 2

All your pointers seem to be pointing to the same thing, root. So in one instance root gets moved forward, but then you point root->next points to whats behind root. so imagine that root points to bob and root->next points to bill, assume your first nest of ifs all turn up true, root = bill but root->next = bob. No forward movement is being made.