C++

Forum

  • Forum
  • Lounge
  • Reference Implementation: Linked list...

 
Reference Implementation: Linked list...

closed account (z05DSL3A)
So I started looking at a reference implementation of a linked list.

I chose C so that it leaves room for the reader room to convert it to a C++ class.

This is what I have so far...but I need sleep so will hopefully get back to adding comments and such later.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#ifndef list_h
#define list_h

#include <stdlib.h>


typedef struct ListElement_
{
    void * data;
    struct ListElement_ * next;
}ListElement;

typedef struct List_
{
    int size;
    int (*match)(const void * key1, const void * key2);
    void (*destroy)(void *);
    ListElement *head;
    ListElement *tail;
}List;

void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_insert_next(List *list, ListElement *element, const void *data);
int list_remove_next(List *list, ListElement *element, void **data);

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)

#endif
list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
#include <stdlib.h>
#include <string.h>

#include "list.h"

void list_init(List *list, void (*destroy)(void *data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;

    return;
}

void list_destroy(List *list)
{
    void * data;
    
    while (list_size(list) >0)
    {
        if (list_remove_next(list, NULL, (void **)&data) == 0 &&
            list->destroy != NULL)
        {
            list->destroy(data);
        }
    }
    memset(list, 0, sizeof(List));
}

int list_insert_next(List *list, ListElement *element, const void *data)
{
    ListElement *new_element;
    
    if ((new_element = (ListElement *) malloc(sizeof(ListElement))) == NULL)
        return -1;
    
    new_element->data = (void *) data;
    
    if (element == NULL)
    {
        if(list_size(list) == 0)
            list->tail = new_element;
        
        new_element->next = list->head;
        list->head = new_element;
    }
    else
    {
        if (element->next == NULL)
            list->tail = new_element;
        
        new_element->next = element->next;
        element->next = new_element;
        
    }
    
    list->size++;
    
    return 0;
}

int list_remove_next(List *list, ListElement *element, void **data)
{
    ListElement * old_element;
    
    if (list_size(list) ==0)
        return -1;
    
    if (element == NULL)
    {
        *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;
        
        if (list_size(list) == 1)
            list->tail = NULL;
    }
    else
    {
        if (element->next == NULL)
            return -1;
        
        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;
        
        if (element->next == NULL)
            list->tail = element;
        
    }
    free(old_element);
    
    list->size--;
    return 0;
}
list.c
Last edited on by Canis lupus
naraku9333 (2163)
Why use defines instead of functions?
NoXzema (699)
Well, I suppose you can't inline those functions...
closed account (z05DSL3A)
naraku9333 wrote:
Why use defines instead of functions?
I don't see the need for the extra 'bagage' of making it a function over a simple macro.
Topic archived. No new replies allowed.