1

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

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被破坏的对象，而不是参数的对象。

4

2 回答 2

3

这是一个完整的程序，它完全按原样使用您的功能（到目前为止您发布的所有功能）。有用。该错误在您未显示的部分中。

#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;
}
于 2013-06-18T22:57:52.027 回答
1

我发现了问题。它不在于代码，而在于我对它的理解。为了说明，请考虑函数中的以下行qu_remove：

memcpy(object, marker, &size);

在调用 to 之前，和inmemcpy的内容如下：objectmarkerqu_remove

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

调用后memcpy的内容object如下：

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

出于某种原因，我认为memcpy会将字符“N”从位置 0x1FFF8688（标识符的位置marker）复制到 0x1FFF8668（标识符的位置object）。我现在明白这是胡说八道。字符“N”不是 的一部分marker，因此不会被复制 - 只有指向“N”的指针被复制。

知道这一点解释了bu_test功能的失败。棘手的一点将是找出解决问题的方法。我需要的是写一个替换，memcpy它跟随任何指针链一直到被指向的对象，并复制它。

于 2013-06-20T00:22:53.850 回答