Correct use of function pointers

Question

The doubly-linked list upon which I have based a fair amount of code appears to have a bug in it related to the way that I go about deleting nodes from the list, but I am unable to spot it. Consider the following code:

typedef struct DL_LIST
{
    uint16 tag;
    struct DL_LIST *previous;
    struct DL_LIST *next;
    void *object;
    uint32 size;
} DL_LIST;

The function used to delete nodes is as follows:

void dl_delete(DL_LIST *node, void (*destructor)(void*))
{
    assert(destructor != NULL);

    if (node != NULL)
    {
        dl_extract(node);

        if (node->object != NULL)
        {
            destructor(node->object);
        }

        free(node);
    }
}

where:

DL_LIST *dl_extract(DL_LIST *node)
{
    if (node != NULL)
    {
        if (node->previous != NULL)
        {
            node->previous->next = node->next;
        }

        if (node->next != NULL)
        {
            node->next->previous = node->previous;
        }

        node->previous = NULL;
        node->next = NULL;
    }

    return node;
}

Is anyone able to spot the problem with the way I am deleting nodes? The reason I believe that there is a problem is that I have used DL_LIST as the basis for a queue structure, and the function used to delete items from the queue corrupts it, except when I comment out the call to dl_delete.

EDIT 1. As requested in the comments, the queue code follows:

typedef struct QU_LIST
{
    DL_LIST *list;
    uint32 count;
} QU_LIST;

uint8 qu_remove(QU_LIST *queue, void *object, void (*destructor)(void*))
{
    uint8 result = QU_SUCCESS;
    uint32 size;
    DL_LIST *first_node;
    DL_LIST *next_node;
    void *marker;

    assert(queue != NULL && destructor != NULL);

    if (queue->count > 0)
    {
        first_node = dl_get_first(queue->list);
        next_node = dl_get_next(first_node);

        marker = dl_get_object(first_node, NULL, &size);

        if (marker != NULL)
        {
            if (object != NULL)
            {
                memcpy(object, marker, size);
            }
        }
        else
        {
            result = QU_NO_MEMORY;
        }

        queue->list = next_node;

        dl_delete(first_node, destructor); // this is the problem

        --queue->count;
    }
    else
    {
        result = QU_EMPTY;
    }

    return result;
}

where:

DL_LIST *dl_get_first(DL_LIST *list)
{
    if (list != NULL)
    {
        while (list->previous != NULL)
        {
            list = list->previous;
        }
    }

    return list;
}

DL_LIST *dl_get_next(DL_LIST *node)
{
    if (node != NULL)
    {
        node = node->next;
    }

    return node;
}

void *dl_get_object(DL_LIST *node, uint16 *tag, uint32 *size)
{
    void *marker = NULL;

    if (node != NULL)
    {
        if (tag != NULL)
        {
            *tag = node->tag;
        }

        if (size != NULL)
        {
            *size = node->size;
        }

        marker = node->object;
    }

    return marker;
}

EDIT 2. Thanks to a sterling answer on the part of Wumpus Q. Wumbley, the source of the problem has been narrowed down to the following code, which is part of a navigation button library for an embedded system.

void bu_test(void)
{
    QU_LIST button_list = {0};
    BU_OBJECT *object = NULL;

    object = bu_create("O");
    // object->identifier is "O" at this point.

    bu_add(&button_list, "N");
    bu_add(&button_list, "S");
    bu_add(&button_list, "E");
    bu_add(&button_list, "W");

    qu_remove(&button_list, object, (void(*)(void*)) &_destructor);
    // object->identifier should be "N" at this point, but is not.
}

where:

typedef struct BU_OBJECT
{
    char *identifier;
} BU_OBJECT;

uint8 bu_add(QU_LIST *queue, char *identifier)
{
    uint8 result = BU_SUCCESS;
    BU_OBJECT* object;

    assert(queue != NULL && identifier != NULL);

    object = bu_create(identifier);

    if (object != NULL)
    {
        result = qu_add(queue, _TAG, object, sizeof(*object));

        if (result == QU_NO_MEMORY)
        {
            _destructor(object);

            result = BU_NO_MEMORY;
        }
    }
    else
    {
        result = BU_NO_MEMORY;
    }

    return result;
}

and:

BU_OBJECT *bu_create(char *identifier)
{
    BU_OBJECT *object = NULL;
    char *p;

    assert(identifier != NULL);

    object = malloc(sizeof(*object));

    if (object != NULL)
    {
        p = malloc(sizeof(*identifier));

        if (p != NULL)
        {
            strcpy(p, identifier);
            object->identifier = p;
        }
        else
        {
            free(object);
            object = NULL;
        }
    }

    return object;
}

and finally:

void _destructor(BU_OBJECT *object)
{  
    free(object->identifier);
    free(object);
}

Objects are added to the button_list without error, but it appears that _destructor is destroying the object parameter that is passed to the function qu_remove, which seems extremely strange to me, as it should be the object of the first_node that is destroyed, not that of the parameter.

RBE · Accepted Answer

I have found the problem. It lies not with the code, but with my understanding of it. To illustrate, consider the following line from the function qu_remove:

memcpy(object, marker, &size);

Prior to the call to memcpy, the content of object and marker in qu_remove are as follows:

Location      Content       Location Description
--------      -------       --------------------
0x1FFF8658    0x1FFF8668    Pointer to object (object)
0x1FFF8668    "O"           Pointer to identifier

0x1FFF86B0    0x1FFF8688    Pointer to object (marker)
0x1FFF8688    "N"           Pointer to identifier

After the call to memcpy, the content of object is as follows:

Location      Content       Location Description
--------      -------       --------------------
0x1FFF8658    0x1FFF8688    Pointer to object (marker)
0x1FFF8688    "N"           Pointer to identifier

For some reason I thought that memcpy would of copied the character "N" from location 0x1FFF8688 (the location of the identifier in marker) to 0x1FFF8668 (the location of the identifier in object). I now see that this is nonsense. The character "N" is not part of marker, and is therefore not copied - only the pointer to "N" is copied.

Knowing this explains the failure of the bu_test function. The tricky bit will be figuring out a way to solve the problem. What I will need is to write a replacement for memcpy that follows any pointer chains right down to the object that is being pointed-to, and copies that as well.

Correct use of function pointers

Answers (2)

Related Questions