source: lib/data-struct/linked_list.c @ 2193905

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

Apply changes required for pull request #81

  • Property mode set to 100644
File size: 5.0 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 <stddef.h>
29#include <stdlib.h>
30#include <string.h>
31
32libtrace_list_t *libtrace_list_init(size_t element_size)
33{
34        libtrace_list_t *l = (libtrace_list_t *)malloc(sizeof(libtrace_list_t));
35        if (l == NULL)
36                return NULL;
37
38        memset(l, 0, sizeof(libtrace_list_t));
39        l->element_size = element_size;
40
41        return l;
42}
43
44void libtrace_list_deinit(libtrace_list_t *l)
45{
46        libtrace_list_node_t *tmp, *next;
47        if (l == NULL)
48                return;
49
50        tmp = l->head;
51        while (tmp != NULL) {
52                next = tmp->next;
53
54                if (tmp->data)
55                        free(tmp->data);
56                free(tmp);
57
58                tmp = next;
59        }
60
61        free(l);
62}
63
64void libtrace_list_push_front(libtrace_list_t *l, void *item)
65{
66        libtrace_list_node_t *new;
67
68        if (l == NULL || item == NULL)
69                return;
70
71        /* Create the new node */
72        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
73        if (!new) {
74                fprintf(stderr, "Unable to allocate memory for node in libtrace_list_push_front()\n");
75                return;
76        }
77        new->data = malloc(l->element_size);
78        if (!new->data) {
79                fprintf(stderr, "Unable to allocate memory for node data in libtrace_list_push_front()\n");
80        }
81
82        new->prev = NULL;
83        memcpy(new->data, item, l->element_size);
84
85        if (l->head == NULL) {
86                if (l->tail != NULL || l->size != 0) {
87                        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");
88                        return;
89                }
90                new->next = NULL;
91                l->head = l->tail = new;
92        } else {
93                l->head->prev = new;
94                new->next = l->head;
95                l->head = new;
96        }
97        l->size++;
98}
99
100void libtrace_list_push_back(libtrace_list_t *l, void *item)
101{
102        libtrace_list_node_t *new;
103
104        if (l == NULL || item == NULL)
105                return;
106
107        /* Create the new node */
108        new = (libtrace_list_node_t *)malloc(sizeof(libtrace_list_node_t));
109        if (!new) {
110                fprintf(stderr, "Unable to allocate memory for node in libtrace_list_push_back()\n");
111                return;
112        }
113        new->data = malloc(l->element_size);
114        if (!new->data) {
115                fprintf(stderr, "Unable to allocate memory for node data in libtrace_list_push_back()\n");
116                return;
117        }
118        new->next = NULL;
119        memcpy(new->data, item, l->element_size);
120
121        if (l->tail == NULL) {
122                if (l->head != NULL || l->size != 0) {
123                        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");
124                        return;
125                }
126                new->prev = NULL;
127                l->head = l->tail = new;
128        } else {
129                l->tail->next = new;
130                new->prev = l->tail;
131                l->tail = new;
132        }
133        l->size++;
134}
135
136int libtrace_list_pop_front(libtrace_list_t *l, void *item)
137{
138        int ret = 0;
139        libtrace_list_node_t *n;
140
141        if (l == NULL || item == NULL)
142                return -1;
143
144        if (l->head != NULL) {
145                n = l->head;
146                ret = 1;
147
148                /* Relink the list */
149                l->head = l->head->next;
150                if (l->head)
151                        l->head->prev = NULL;
152                l->size--;
153                if (l->size <= 1)
154                        l->tail = l->head;
155        }
156
157        /* If we managed to pull a node out, copy the data and free the
158         * node */
159        if (ret) {
160                memcpy(item, n->data, l->element_size);
161                free(n->data);
162                free(n);
163        }
164
165        return ret;
166}
167
168int libtrace_list_pop_back(libtrace_list_t *l, void *item)
169{
170        int ret = 0;
171        libtrace_list_node_t *n;
172
173        if (l == NULL || item == NULL)
174                return -1;
175
176        if (l->tail != NULL) {
177                n = l->tail;
178                ret = 1;
179
180                /* Relink the list */
181                l->tail = l->tail->prev;
182                if (l->tail)
183                        l->tail->next = NULL;
184                l->size--;
185                if (l->size <= 1)
186                        l->head = l->tail;
187        }
188
189        /* If we managed to pull a node out, copy the data and free the
190         * node */
191        if (ret) {
192                memcpy(item, n->data, l->element_size);
193                free(n->data);
194                free(n);
195        }
196
197        return ret;
198}
199
200libtrace_list_node_t *libtrace_list_get_index(libtrace_list_t *list,
201                                              size_t index) {
202        libtrace_list_node_t *ret = list->head;
203
204        /* Ensure the index is within the list */
205        if (index >= list->size) {
206                printf("List index out of range\n");
207                return NULL;
208        }
209
210        /* Scan the list until we get to the desired index. We could be smart
211         * and scan from the top or the bottom depending on which is closer */
212        while (index--) {
213                ret = ret->next;
214                if (!ret) {
215                        fprintf(stderr, "Error encountered NULL index in libtrace_list_get_index()\n");
216                        return NULL;
217                }
218        }
219
220        return ret;
221}
222
223size_t libtrace_list_get_size(libtrace_list_t *l)
224{
225        if (l == NULL)
226                return 0;
227
228        return l->size;
229}
Note: See TracBrowser for help on using the repository browser.