list.c - A linked list by C --- C語言實現的單向鏈表

這是我實現的C語言單向鏈表。單向鏈表很簡單，可以存儲任意類型的數據：整型、字符串或指針類型。但是，不要混存。除整型外，鏈表節點數據由調用者分配和負責釋放，即調用者負責提供一個回調函數，當鏈表釋放時，自動調用你提供的這個函數。記住：鏈表不分配任何用戶的數據，僅分配和管理自己的私有數據，因此，分配和釋放鏈表所存放的數據的工作必須由用戶來完成。讀者可以在測試代碼中看到用例。

鏈表需要的文件為：unistd.h，list.h，list.c。測試文件為test.c。以下是代碼：

/****************************************************************************************
* list.h *
* Generic sequential linked list node structure -- can hold any type data. *
* cheungmine *
* Mar. 22, 2008. All rights reserved. *
****************************************************************************************/
#ifndef LIST_H_INCLUDED__
#define LIST_H_INCLUDED__

#ifdef __cplusplus
extern "C" {
#endif

#include "unistd.h"

typedef struct _listnode_t
{
struct _listnode_t *next;
union{
void *data;
struct _list_t *list;
const char *str;
long key;
};
}listnode_t;

typedef struct _list_t
{
size_t size; /* count of nodes */
listnode_t *head;
listnode_t *tail;
}list_t, *list_p;

/**
* A prototype of callbacked function called by:
* - list_destroy()
* - list_traverse()
* - list_node_free()
* NULL for no use
*/
typedef void(*pfunc_list_callback)(listnode_t* node);

/**
* An prototype example of free node data function implemented by caller:
*/
static void my_listnode_data_free(listnode_t *node)
{
free(node->data);
DBG_TRACE("my_listnode_data_free\n");
}

/**
* A prototype example of traverse implemented by caller:
*/
static void my_listnode_key_traverse(listnode_t *node)
{
printf(" key=%ld\n", node->key);
}

/**
* Traverses a list, applied callback functionn for each node
*/
void
list_traverse(list_t *in_list, pfunc_list_callback pfcb_traversenode);

/**
* Allocates a empty list from heap, this creates a new list
*/
list_t*
list_create();

/**
* Clears a list and free memory, the list cannot be used later
*/
void
list_destroy(list_t *in_list, pfunc_list_callback pfcb_freedata);

/**
* Creates a new node assigned with data, not allocates for data
*/
listnode_t*
list_node_create(void* data);

/**
* Free a list node and it's associated nodes, the freed node cannot be used later
*/
void
list_node_free(listnode_t* node, pfunc_list_callback pfcb_freedata);

/**
* Creates a new node assigned with a key, not allocates for key
*/
listnode_t*
list_key_create(long key);

/**
* Finds prev node of given node
*/
listnode_t*
list_find_prev(const list_t *in_list, const listnode_t *node);

/**
* Appends a node to a list at back
*/
void
list_push_back(list_t *in_list, listnode_t *node);

/**
* Inserts a node in front of head into a list
*/
void
list_push_front(list_t *in_list, listnode_t *in_node);

/**
* Inserts a node after pos node into a list
*/
void
list_insert_after(list_t *in_list, listnode_t *pos_node, listnode_t *in_node);

/**
* Inserts a node before pos node into a list
*/
void
list_insert_before(list_t *in_list, listnode_t *pos_node, listnode_t *in_node);

/**
* Removes the first node from a list and returns it
*/
listnode_t*
list_pop_front(list_t *in_list);

/**
* Removes the last node from a list and returns it
*/
listnode_t*
list_pop_back(list_t *in_list);

/**
* Removes all nodes but for list itself
*/
void
list_clear(list_t *in_list, pfunc_list_callback pfcb);

/**
* Returns a copy of a list_t from heap
*/
list_t*
list_copy(list_t list);

/**
* Concatenates two lists into first list
*/
void
list_concat(list_t *first, list_t *second);

/**
* Gets count of nodes in the list
*/
size_t
list_size(const list_t* in_list);

/**
* Gets node by index: 0-based. 0 is head
*/
listnode_t*
list_node_at(const list_t* in_list, size_t index);

/**
* Slices list off from begin to end, returns begin node
* Caller should free returned list nodes
* begin and end can be same one
*/
listnode_t*
list_slice(list_t* in_list, listnode_t* begin, listnode_t* end);

#ifdef __cplusplus
}
#endif

#endif /* LIST_H_INCLUDED__ */


/****************************************************************************************
* list.c *
* Generic sequential linked list node structure -- can hold any type data. *
* cheungmine *
* Mar. 22, 2008. All rights reserved. *
****************************************************************************************/
#include "list.h"

void
list_traverse(list_t *in_list, pfunc_list_callback pfcb)
{
listnode_t* node;
DBG_TRACE("list_traverse:\n size= %ld\n", in_list->size);
if (pfcb) {
node = in_list->head;
while (node) {
(*pfcb)(node);
node = node->next;
}
}
}

list_t*
list_create()
{
list_t *list = (list_t*)malloc (sizeof(list_t));
list->size = 0;
list->head = list->tail = NULL;

DBG_TRACE("list_create\n");
return list;
}

void
list_destroy(list_t *in_list, pfunc_list_callback pf)
{
DBG_TRACE("list_destroy\n");
list_clear(in_list, pf);
free(in_list);
}

listnode_t*
list_node_create(void* data)
{
listnode_t *node = (listnode_t*)malloc (sizeof(listnode_t));
node->next = NULL;
node->data = data;
DBG_TRACE("list_node_create\n");
return node;
}

void
list_node_free(listnode_t* node, pfunc_list_callback pfcb)
{
listnode_t* next;
DBG_TRACE("list_node_free\n");
while(node){
next = node->next;
if (pfcb)
(*pfcb)(node);
free(node);
node = next;
}
}

listnode_t*
list_key_create(long key)
{
listnode_t *node = (listnode_t*)malloc (sizeof(listnode_t));
node->next = NULL;
node->key = key;
DBG_TRACE("list_key_create: key=%ld\n", key);
return node;
}

listnode_t*
list_find_prev(const list_t *in_list, const listnode_t *node)
{
listnode_t* prev;
assert(node);
prev = in_list->head;
if (prev==node)
return NULL;
while(prev && prev->next!=node) {
prev = prev->next;
}
assert(prev);
return prev;
}

void
list_push_back(list_t *in_list, listnode_t *node)
{
node->next = NULL;

if (in_list->head)
{
in_list->tail->next = node;
in_list->tail = node;
}
else
in_list->head = in_list->tail = node;

in_list->size++;
DBG_TRACE("list_push_back\n");
}

void
list_push_front(list_t *in_list, listnode_t *in_node)
{
in_node->next = in_list->head;
in_list->head = in_node;

if (!in_node->next)
in_list->tail = in_node;

in_list->size++;
DBG_TRACE("list_push_front\n");
}

void
list_insert_after(list_t *in_list, listnode_t *pos_node, listnode_t *in_node)
{
in_node->next = pos_node->next;
pos_node->next = in_node;

if (in_list->tail==pos_node)
in_list->tail = in_node;

in_list->size++;
}

void
list_insert_before(list_t *in_list, listnode_t *pos_node, listnode_t *in_node)
{
listnode_t* prev_node;
prev_node = list_find_prev(in_list, pos_node);
if (prev_node)
list_insert_after(in_list, prev_node, in_node);
else
list_push_front(in_list, in_node);
}

listnode_t*
list_pop_front(list_t *in_list)
{
listnode_t *pop_node = NULL;
if (in_list->head)
{
pop_node = in_list->head;
in_list->head = in_list->head->next;
if (in_list->head == NULL)
in_list->tail = NULL;
pop_node->next = NULL;
in_list->size--;
}
assert(in_list->size >= 0);
DBG_TRACE("list_pop_front\n");
return pop_node;
}

listnode_t*
list_pop_back(list_t *in_list)
{
listnode_t *pop_node = in_list->tail;
if (in_list->head==pop_node) {
in_list->size = 0;
in_list->head = in_list->tail = NULL;
}
else {
assert(pop_node && !pop_node->next);
in_list->tail = list_find_prev(in_list, pop_node);
assert(in_list->tail);
in_list->tail->next = NULL;
in_list->size--;
}
assert(in_list->size >= 0);
DBG_TRACE("list_pop_back\n");
return pop_node;
}

void
list_clear(list_t *in_list, pfunc_list_callback pfcb)
{
listnode_t *node;
if (pfcb) {
while((node = list_pop_front(in_list))){
(*pfcb)(node);
free(node);
}
}
else {
while((node = list_pop_front(in_list))){
free(node);
}
}
assert (in_list->size==0);
DBG_TRACE("list_clear\n");
}

list_t*
list_copy(list_t list)
{
list_t *newlist = (list_t*)malloc (sizeof(list_t));
*newlist = list;
DBG_TRACE("list_copy\n");
return newlist;
}

void
list_concat(list_t *first, list_t *second)
{
if (first->head)
{
if (second->head)
{
first->tail->next = second->head;
first->tail = second->tail;
}
}
else
*first = *second;
second->head = second->tail = NULL;

first->size += second->size;
DBG_TRACE("list_concat\n");
}

size_t
list_size(const list_t* in_list)
{
DBG_TRACE("list_size:%ld\n", in_list->size);
return in_list->size;
}

listnode_t*
list_node_at(const list_t* in_list, size_t index)
{
size_t i=0;
listnode_t *node = in_list->head;
assert(index >=0 && index < in_list->size);
while (i < index) {
node = node->next;
i++;
}
return node;
}

listnode_t*
list_slice(list_t* in_list, listnode_t* begin, listnode_t* end)
{
listnode_t* prev;
assert(end);
prev = list_find_prev(in_list, begin);

if (prev==NULL) {
assert(begin==in_list->head);
in_list->head = end->next;
end->next = NULL;
if (in_list->tail == end)
in_list->tail = in_list->head;
}
else {
prev->next = end->next;
end->next = NULL;
if (in_list->tail == end)
in_list->tail = prev;
}
DBG_TRACE("list_slice\n");

in_list->size = 0;
prev = in_list->head;
while(prev) {
in_list->size++;
prev = prev->next;
}

return begin;
}


/****************************************************************************************
* unistd.h *
* 2008-03-15 Last created by cheungmine. *
* All rights reserved by cheungmine. *
****************************************************************************************/
#ifndef UNISTD_H__
#define UNISTD_H__

/* Standard C header files included */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*============================================================================*/

#ifndef HAVE_INT8
#define HAVE_INT8
typedef signed char int8; /* NB: non-ANSI compilers may not grok */
typedef unsigned char uint8, uchar, byte, BYTE;
#endif

#ifndef HAVE_INT16
#define HAVE_INT16
typedef short int16;
typedef unsigned short uint16, word_t, ushort; /* sizeof (uint16) must == 2 */
#endif

#ifndef HAVE_INT32
#define HAVE_INT32
typedef int int32;
typedef unsigned int uint32, size_t, dword_t; /* sizeof (uint32) must == 4 */
typedef unsigned long ulong;
#endif

typedef long lresult;

typedef __int64 int64, longlong;
typedef unsigned __int64 uint64, qword_t, ulonglong;

#ifndef BOOL
typedef int BOOL;
#define TRUE 1
#define FALSE 0
#endif

#ifndef RESULT
#define RESULT lresult
#define _SUCCESS 0
#define _ERROR -1
#endif

#ifndef IN
#define IN
#endif

#ifndef OUT
#define OUT
#endif

#ifndef INOUT
#define INOUT
#endif

#ifndef OPTIONAL
#define OPTIONAL
#endif

#define SIZE_BYTE 1
#define SIZE_ACHAR 1
#define SIZE_WCHAR 2
#define SIZE_SHORT 2
#define SIZE_INT 4
#define SIZE_LONG 4
#define SIZE_FLT 4
#define SIZE_DBL 8
#define SIZE_WORD 2
#define SIZE_DWORD 4
#define SIZE_QWORD 8
#define SIZE_LINT 8
#define SIZE_INT64 8
#define SIZE_UUID 16

#ifdef _DEBUG
#include <stdarg.h>
static void DBG_TRACE(const char *fmt, ...) {
va_list ap;
va_start(ap, fmt);
vprintf(fmt, ap);
va_end(ap);
}
#else
static void DBG_TRACE(const char *fmt, ...){}
#endif

/*============================================================================*/
#endif /*UNISTD_H__*/

最後是測試工程：

//
// test.c - test topology
// [email protected]
// 2008-3
//
#include <stdio.h>
#include <stdlib.h>

#include "list.h"

void list_use_key()
{
long k;
list_t* lst;
listnode_t* nod;
lst = list_create();
assert(lst);

for(k=1; k<=10; k++){
list_push_back(lst, list_key_create(k));
}

list_size(lst);
list_pop_front(lst);
list_size(lst);
list_pop_back(lst);
list_size(lst);

list_traverse(lst, my_listnode_key_traverse);

nod = list_slice(lst, lst->head->next->next, list_find_prev(lst, lst->tail));
list_node_free(nod, 0);

list_traverse(lst, my_listnode_key_traverse);

list_destroy(lst, 0);
}

typedef struct
{
char * _buff;
size_t _size;
}blob;

blob* blob_create(size_t n)
{
blob* p = (blob*) malloc(sizeof(blob));
p->_buff = (char*) malloc(n);
p->_size = n;
DBG_TRACE("blob_create\n");
return p;
}

void blob_free(blob* p)
{
free(p->_buff);
p->_size = 0;
DBG_TRACE("blob_free\n");
}

void my_listnode_blob_free(listnode_t *node)
{
blob_free((blob*)node->data);
}

void my_listnode_blob_traverse(listnode_t *node)
{
printf(" _size: %d, _buff: %s\n", ((blob*)node->data)->_size, ((blob*)node->data)->_buff);
}

void list_use_data()
{
long k;
list_t* lst;
blob* pb;
listnode_t* nod;
lst = list_create();
assert(lst);

for(k=1; k<=10; k++){
pb = blob_create(50);
sprintf_s(pb->_buff, 50, " this is a blob: %d", k);
list_push_back(lst, list_node_create(pb));
}
list_size(lst);

nod = list_pop_front(lst);
DBG_TRACE("Use blob here...\n");
list_node_free(nod, my_listnode_blob_free);
list_size(lst);

nod = list_pop_back(lst);
list_size(lst);
DBG_TRACE("Use blob here...\n");
list_node_free(nod, my_listnode_blob_free);

list_traverse(lst, my_listnode_blob_traverse);

nod = list_slice(lst, lst->head->next->next, list_find_prev(lst, lst->tail));
list_node_free(nod, my_listnode_blob_free);

list_traverse(lst, my_listnode_blob_traverse);

list_destroy(lst, my_listnode_blob_free);
}

int main()
{
printf("==================list_use_key==================\n");
list_use_key();

printf("==================list_use_data==================\n");
list_use_data();

printf("-----------------\nPress <Enter> for quit! [email protected]\n");
getchar();
return 0;
}