source: lib/data-struct/linked_list.c @ 03aca91

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivelibtrace4ndag_formatpfringrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 03aca91 was 03aca91, checked in by Richard Sanger <rsangerarj@…>, 5 years ago

Fixes an extra level of indirection in a memcopy in the linked list structure

Fixes an issue Dan found, luckly this is in an unused code path.

  • Property mode set to 100644
File size: 3.3 KB
Line 
1#include "linked_list.h"
2
3#include <assert.h>
4#include <stddef.h>
5#include <stdlib.h>
6#include <string.h>
7
8libtrace_list_t *libtrace_list_init(size_t element_size)
9{
10        libtrace_list_t *l = (libtrace_list_t *)malloc(sizeof(libtrace_list_t));
11        if (l == NULL)
12                return NULL;
13
14        memset(l, 0, sizeof(libtrace_list_t));
15        l->element_size = element_size;
16
17        return l;
18}
19
20void libtrace_list_deinit(libtrace_list_t *l)
21{
22        libtrace_list_node_t *tmp, *next;
23        if (l == NULL)
24                return;
25
26        tmp = l->head;
27        while (tmp != NULL) {
28                next = tmp->next;
29
30                if (tmp->data)
31                        free(tmp->data);
32                free(tmp);
33
34                tmp = next;
35        }
36
37        free(l);
38}
39
40void libtrace_list_push_front(libtrace_list_t *l, void *item)
41{
42        libtrace_list_node_t *new;
43
44        if (l == NULL || item == NULL)
45                return;
46
47        /* Create the new node */
48        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
49        assert(new != NULL);
50        new->data = malloc(l->element_size);
51        assert(new->data != NULL);
52
53        new->prev = NULL;
54        memcpy(new->data, item, l->element_size);
55
56        if (l->head == NULL) {
57                assert(l->tail == NULL && l->size == 0);
58                new->next = NULL;
59                l->head = l->tail = new;
60        } else {
61                l->head->prev = new;
62                new->next = l->head;
63                l->head = new;
64        }
65        l->size++;
66}
67
68void libtrace_list_push_back(libtrace_list_t *l, void *item)
69{
70        libtrace_list_node_t *new;
71
72        if (l == NULL || item == NULL)
73                return;
74
75        /* Create the new node */
76        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
77        assert(new != NULL);
78        new->data = malloc(l->element_size);
79        assert(new->data != NULL);
80
81        new->next = NULL;
82        memcpy(new->data, item, l->element_size);
83
84        if (l->tail == NULL) {
85                assert(l->head == NULL && l->size == 0);
86                new->prev = NULL;
87                l->head = l->tail = new;
88        } else {
89                l->tail->next = new;
90                new->prev = l->tail;
91                l->tail = new;
92        }
93        l->size++;
94}
95
96int libtrace_list_pop_front(libtrace_list_t *l, void *item)
97{
98        int ret = 0;
99        libtrace_list_node_t *n;
100
101        if (l == NULL || item == NULL)
102                return -1;
103
104        if (l->head != NULL) {
105                n = l->head;
106                ret = 1;
107
108                /* Relink the list */
109                l->head = l->head->next;
110                if (l->head)
111                        l->head->prev = NULL;
112                l->size--;
113                if (l->size <= 1)
114                        l->tail = l->head;
115        }
116
117        /* If we managed to pull a node out, copy the data and free the
118         * node */
119        if (ret) {
120                memcpy(item, n->data, l->element_size);
121                free(n);
122        }
123
124        return ret;
125}
126
127int libtrace_list_pop_back(libtrace_list_t *l, void *item)
128{
129        int ret = 0;
130        libtrace_list_node_t *n;
131
132        if (l == NULL || item == NULL)
133                return -1;
134
135        if (l->tail != NULL) {
136                n = l->tail;
137                ret = 1;
138
139                /* Relink the list */
140                l->tail = l->tail->prev;
141                if (l->tail)
142                        l->tail->next = NULL;
143                l->size--;
144                if (l->size <= 1)
145                        l->head = l->tail;
146        }
147
148        /* If we managed to pull a node out, copy the data and free the
149         * node */
150        if (ret) {
151                memcpy(item, n->data, l->element_size);
152                free(n);
153        }
154
155        return ret;
156}
157
158libtrace_list_node_t *libtrace_list_get_index(libtrace_list_t *list,
159                                              size_t index) {
160        libtrace_list_node_t *ret = list->head;
161
162        /* Ensure the index is within the list */
163        if (index >= list->size) {
164                printf("List index out of range\n");
165                return NULL;
166        }
167
168        /* Scan the list until we get to the desired index. We could be smart
169         * and scan from the top or the bottom depending on which is closer */
170        while (index--) {
171                ret = ret->next;
172                assert(ret != NULL);
173        }
174
175        return ret;
176}
177
178size_t libtrace_list_get_size(libtrace_list_t *l)
179{
180        if (l == NULL)
181                return 0;
182
183        return l->size;
184}
Note: See TracBrowser for help on using the repository browser.