source: lib/data-struct/linked_list.c @ 88b9798

develop
Last change on this file since 88b9798 was 88b9798, checked in by Jacob Van Walraven <jcv9@…>, 2 years ago

More assertion cleanups

  • Property mode set to 100644
File size: 5.3 KB
Line 
1/*
2 *
3 * Copyright (c) 2007-2016 The University of Waikato, Hamilton, New Zealand.
4 * All rights reserved.
5 *
6 * This file is part of libtrace.
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 *
11 * libtrace is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * libtrace is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 * GNU Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
23 *
24 *
25 */
26#include "linked_list.h"
27
28#include <assert.h>
29#include <stddef.h>
30#include <stdlib.h>
31#include <string.h>
32
33libtrace_list_t *libtrace_list_init(size_t element_size)
34{
35        libtrace_list_t *l = (libtrace_list_t *)malloc(sizeof(libtrace_list_t));
36        if (l == NULL)
37                return NULL;
38
39        memset(l, 0, sizeof(libtrace_list_t));
40        l->element_size = element_size;
41
42        return l;
43}
44
45void libtrace_list_deinit(libtrace_list_t *l)
46{
47        libtrace_list_node_t *tmp, *next;
48        if (l == NULL)
49                return;
50
51        tmp = l->head;
52        while (tmp != NULL) {
53                next = tmp->next;
54
55                if (tmp->data)
56                        free(tmp->data);
57                free(tmp);
58
59                tmp = next;
60        }
61
62        free(l);
63}
64
65void libtrace_list_push_front(libtrace_list_t *l, void *item)
66{
67        libtrace_list_node_t *new;
68
69        if (l == NULL || item == NULL)
70                return;
71
72        /* Create the new node */
73        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
74        /*assert(new != NULL);*/
75        if (!new) {
76                fprintf(stderr, "Unable to allocate memory for node in libtrace_list_push_front()\n");
77                return;
78        }
79        new->data = malloc(l->element_size);
80        /*assert(new->data != NULL);*/
81        if (!new->data) {
82                fprintf(stderr, "Unable to allocate memory for node data in libtrace_list_push_front()\n");
83        }
84
85        new->prev = NULL;
86        memcpy(new->data, item, l->element_size);
87
88        if (l->head == NULL) {
89                /*assert(l->tail == NULL && l->size == 0);*/
90                if (l->tail != NULL && l->size != 0) {
91                        fprintf(stderr, "Error cannot have a NULL head with a non NULL tail and a size of non 0 in libtrace_list_push_front()\n");
92                        return;
93                }
94                new->next = NULL;
95                l->head = l->tail = new;
96        } else {
97                l->head->prev = new;
98                new->next = l->head;
99                l->head = new;
100        }
101        l->size++;
102}
103
104void libtrace_list_push_back(libtrace_list_t *l, void *item)
105{
106        libtrace_list_node_t *new;
107
108        if (l == NULL || item == NULL)
109                return;
110
111        /* Create the new node */
112        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
113        /*assert(new != NULL);*/
114        if (!new) {
115                fprintf(stderr, "Unable to allocate memory for node in libtrace_list_push_back()\n");
116                return;
117        }
118        new->data = malloc(l->element_size);
119        /*assert(new->data != NULL);*/
120        if (!new->data) {
121                fprintf(stderr, "Unable to allocate memory for node data in libtrace_list_push_back()\n");
122                return;
123        }
124        new->next = NULL;
125        memcpy(new->data, item, l->element_size);
126
127        if (l->tail == NULL) {
128                /*assert(l->head == NULL && l->size == 0);*/
129                if (l->head != NULL && l->size != 0) {
130                        fprintf(stderr, "Error cannot have a NULL tail with a non NULL head and a size of non 0 in libtrace_list_push_back()\n");
131                        return;
132                }
133                new->prev = NULL;
134                l->head = l->tail = new;
135        } else {
136                l->tail->next = new;
137                new->prev = l->tail;
138                l->tail = new;
139        }
140        l->size++;
141}
142
143int libtrace_list_pop_front(libtrace_list_t *l, void *item)
144{
145        int ret = 0;
146        libtrace_list_node_t *n;
147
148        if (l == NULL || item == NULL)
149                return -1;
150
151        if (l->head != NULL) {
152                n = l->head;
153                ret = 1;
154
155                /* Relink the list */
156                l->head = l->head->next;
157                if (l->head)
158                        l->head->prev = NULL;
159                l->size--;
160                if (l->size <= 1)
161                        l->tail = l->head;
162        }
163
164        /* If we managed to pull a node out, copy the data and free the
165         * node */
166        if (ret) {
167                memcpy(item, n->data, l->element_size);
168                free(n->data);
169                free(n);
170        }
171
172        return ret;
173}
174
175int libtrace_list_pop_back(libtrace_list_t *l, void *item)
176{
177        int ret = 0;
178        libtrace_list_node_t *n;
179
180        if (l == NULL || item == NULL)
181                return -1;
182
183        if (l->tail != NULL) {
184                n = l->tail;
185                ret = 1;
186
187                /* Relink the list */
188                l->tail = l->tail->prev;
189                if (l->tail)
190                        l->tail->next = NULL;
191                l->size--;
192                if (l->size <= 1)
193                        l->head = l->tail;
194        }
195
196        /* If we managed to pull a node out, copy the data and free the
197         * node */
198        if (ret) {
199                memcpy(item, n->data, l->element_size);
200                free(n->data);
201                free(n);
202        }
203
204        return ret;
205}
206
207libtrace_list_node_t *libtrace_list_get_index(libtrace_list_t *list,
208                                              size_t index) {
209        libtrace_list_node_t *ret = list->head;
210
211        /* Ensure the index is within the list */
212        if (index >= list->size) {
213                printf("List index out of range\n");
214                return NULL;
215        }
216
217        /* Scan the list until we get to the desired index. We could be smart
218         * and scan from the top or the bottom depending on which is closer */
219        while (index--) {
220                ret = ret->next;
221                /*assert(ret != NULL);*/
222                if (!ret) {
223                        fprintf(stderr, "Error encountered NULL index in libtrace_list_get_index()\n");
224                        return NULL;
225                }
226        }
227
228        return ret;
229}
230
231size_t libtrace_list_get_size(libtrace_list_t *l)
232{
233        if (l == NULL)
234                return 0;
235
236        return l->size;
237}
Note: See TracBrowser for help on using the repository browser.