c - 实现一个具有单个值字段的通用链表

Question

最近在用c写一些linux程序的时候，好像很多地方需要一个可以支持不同类型值的通用链表，所以我尝试实现了一个，但是还有一些问题。

方法:

• 定义一个带指针的结构，然后以 char[] 类型的值字段结束，将其用作通用结构，
• 在链表上定义和实现方法，使用公共(public)结构，
• 定义具有不同类型值字段的新结构类型，
• 调用函数时，将事物转换为普通类型，

---

代码:(草稿)

linked_list.h

#ifndef _LINKED_LIST
#define _LINKED_LIST

// common list for any type,
struct llist_item {
    struct llist_item *next;
    char value[1];
};

// int list
struct llist_int {
    struct llist_int *next;
    int value;
};

/**
 * append item to end of list,
 * 
 * @param headp
 *  pointer to head pointer,
 * @param valuep
 *  pointer set value of deleted item into,
 * @param value_size
 *  size of value,
 * @param struct_size
 *  size of actual struct,
 * 
 * @return
 *  pointer to head,
 */
extern struct llist_item *llist_append(struct llist_item **headp, void *valuep, ssize_t value_size, ssize_t struct_size);

/**
 * delete head,
 * 
 * @param headp
 *  pointer to head pointer,
 * @param valuep
 *  pointer set value of deleted item into,
 * 
 * @return
 *  pointer to new head,
 */
extern struct llist_item *llist_del_head(struct llist_item **headp, char *valuep);

#endif

linked_list.c

// linked_list utility
#include <stdio.h>
#include <string.h>
#include <errno.h>

#include <stdlib.h>

#include "linked_list.h"

/*
   printf("error while linked_list: %s\n", strerror(errno));
   printf("linked_list succeed\n");
 */

struct llist_item *llist_append(struct llist_item **headp, void *valuep, ssize_t value_size, ssize_t struct_size) {
    struct llist_item *head = *headp;

    // create new item
    struct llist_item *new_item = (struct llist_item*) malloc(struct_size);
    new_item->next = NULL;
    memcpy(&(new_item->value), valuep, value_size);

    // append new item
    if(head == NULL) { // empty queue,
        head = new_item;
        *headp = head;
    } else {
        // find last item
        struct llist_item *tail = head;
        while(tail->next != NULL) {
            tail = tail->next;
        }   

        tail->next = new_item;
    }

    return head;
}

struct llist_item *llist_del_head(struct llist_item **headp, char *valuep) {
    struct llist_item *head = *headp;

    if(head == NULL) {
        return NULL;
    } else {
        memcpy(valuep, &(head->value), sizeof(*valuep));
        *headp = head->next;
        free(head);
        return *headp;
    }
}

llist_test.c

// linked_list test
#include <stdio.h>
#include <string.h>
#include <errno.h>

#include <stdlib.h>

#include "linked_list.h"

int linked_list_test() {
    struct llist_int *int_list = NULL; // it's important to initialize this pointer as NULL explicitly,
    int i;

    for(i=1; i<=5; i++) {
        llist_append((struct llist_item **) &int_list, (void *) &i, sizeof(int), sizeof(struct llist_int));
    }

    struct llist_int *int_item;
    int value;
    if(int_list != NULL) {
        do {
            (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
            printf("%d\n", value);
        } while (int_list!= NULL);
    }

    return 0;
}

int main(int argc, char * argv[]) {
    return linked_list_test();
}

---

编译运行

代码列表:

• linked_list.h，标题，
• linked_list.c，实现，
• llist_test.c，做测试，

编译 - 测试:

gcc -Wall linked_list.c llist_test.c -o a.out

执行:

./a.out

---

问题:

• 转换很复杂，有什么方法可以简化它吗？

• 在测试方法linked_list_test()中:

  如果改变:

      do {
          int_item = (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
          printf("%d\n", value);
      } while (int_item != NULL);
  

  到

      do {
          (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
          printf("%d\n", value);
      } while (int_list!= NULL);
  

  然后使用结果，而不是输出:

  1 2 3 4 5

  输出:

  32513 32514 32515 32516 32517

  不同的是指针转换，为什么会导致结果不同？

---

@Update - 关于第二个问题

正如@BLUEPIXY 在评论中描述的那样，确实是 sizeof(*valuep) 导致了这个问题，现在我修改了 llist_del_head()，并在参数列表中提供了大小明确，并修复问题。

函数现在看起来像这样:

extern struct llist_item *llist_del_head(struct llist_item **headp, char *valuep, ssize_t value_size);

Answer 1

这种方法有几个问题:

• 您在结构中预留的空间只有 1 个字节，您不能将大于 1 个字节的类型存储到其中。
• 如果您要为更大的类型腾出空间，您仍然会遇到对齐问题:更大的类型可能需要与编译器为 char 数组在 之后假定的对齐方式不同>结构 llist_item *。因此，即使在结构中使用可变大小的尾随数组也无法提供可行的解决方案。

你可以使用一个void *来分别分配值，但是这样很浪费，或者使用宏来实现不同类型的源代码模板，但是这样很麻烦而且容易出错。

C 没有针对此类概念的正确构造，C++ 以复杂性大得多为代价。