函数指针的正确使用

Question

我大量代码基于的双向链表似乎有一个错误，与我从列表中删除节点的方式有关，但我无法发现它。考虑以下代码:

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

用于删除节点的函数如下:

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);
    }
}

哪里:

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;
}

是否有人能够发现我删除节点的方式存在问题？我认为存在问题的原因是我使用 DL_LIST 作为队列结构的基础，而用于从队列中删除项目的函数破坏了它，除了 当我注释掉对 dl_delete 的调用时。

编辑 1. 根据评论中的要求，队列代码如下:

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;
}

哪里:

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;
}

编辑 2。感谢 Wumpus Q. Wumbley 的出色回答，问题的根源已缩小到以下代码，它是嵌入式系统导航按钮库的一部分。

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.
}

哪里:

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;
}

和:

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;
}

最后:

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

对象添加到 button_list 没有错误，但似乎 _destructor 正在破坏传递给函数 qu_remove 的对象参数，这对我来说似乎非常奇怪，因为它应该是被销毁的 first_node 的对象，而不是参数的对象。

Answer 1

这是一个完整的程序，它完全按原样使用您的函数(您目前发布的所有函数)。有用。该错误在您未显示的部分。

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

typedef uint8_t uint8;
typedef uint16_t uint16;
typedef uint32_t uint32;
enum { QU_SUCCESS, QU_NO_MEMORY, QU_EMPTY };

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

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;
}

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);
    }
}

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;
}

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;
}

DL_LIST *dl_get_last(DL_LIST *list)
{
    if (list != NULL)
    {
        while (list->next != NULL)
        {
            list = list->next;
        }
    }

    return list;
}

DL_LIST **qu_get_tail(QU_LIST *queue)
{
    DL_LIST *node = dl_get_last(queue->list);
    if(node)
        return &node->next;
    return &queue->list;
}

uint8 qu_add(QU_LIST *queue, uint16 tag, void *object, uint32 size)
{
  DL_LIST *node = malloc(sizeof *node), *prev;
  if(!node)
    return QU_NO_MEMORY;
  node->next = NULL;
  node->tag = tag;
  node->object = object;
  node->size = size;
  if(queue->list) {
      prev = dl_get_last(queue->list);
      prev->next = node;
      node->previous = prev;
  } else {
      queue->list = node;
      node->previous = NULL;
  }
  ++queue->count;
  return QU_SUCCESS;
}

void qu_init(QU_LIST *queue)
{
    queue->list = NULL;
    queue->count = 0;
}

void destroydata(void *data)
{
    memset(data, 'X', 3);
}

int main(void)
{
    char testdata[] = "ABC DEF GHI JKL!";
    char removed[4] = "";
    int i;
    QU_LIST q;

    qu_init(&q);
    if(qu_add(&q, 0, &testdata[0], 3) != QU_SUCCESS) abort();
    if(qu_add(&q, 1, &testdata[4], 3) != QU_SUCCESS) abort();
    if(qu_add(&q, 2, &testdata[8], 3) != QU_SUCCESS) abort();
    if(qu_add(&q, 3, &testdata[12], 3) != QU_SUCCESS) abort();
    puts("Done adding");
    for(i=0;i<4;++i) {
      if(qu_remove(&q, removed, destroydata) !=QU_SUCCESS) abort();
      printf("Removed: %s\n", removed);
      printf("testdata now contains: %s\n", testdata);
    }
    return 0;
}