source: lib/data-struct/deque.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.9 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 "deque.h"
27
28#include <assert.h>
29#include <stddef.h>
30#include <stdlib.h>
31#include <string.h>
32
33
34/* Ensure we don't do any reads without locking even if we *know* that
35 * any write will be atomic */
36#ifndef RACE_SAFE
37#define RACE_SAFE 1
38#endif
39
40struct list_node {
41        list_node_t * next;
42        list_node_t * prev;
43        char data[]; // Our item goes here
44};
45
46DLLEXPORT void libtrace_deque_init(libtrace_queue_t * q, size_t element_size)
47{
48        q->head = NULL;
49        q->tail = NULL;
50        q->size = 0;
51        q->element_size = element_size;
52        ASSERT_RET(pthread_mutex_init(&q->lock, NULL), == 0);
53}
54
55DLLEXPORT void libtrace_deque_push_back(libtrace_queue_t *q, void *d)
56{
57        // Do as much work as possible outside the lock
58        list_node_t * new_node = (list_node_t *) malloc(sizeof(list_node_t) + q->element_size);
59        new_node->next = NULL;
60        // Fill it
61        memcpy(&new_node->data, d, q->element_size);
62        // Only ->prev is unknown at this stage to be completed in lock
63        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
64        if (q->head == NULL) {
65                /*assert(q->tail == NULL && q->size == 0);*/
66                if (q->tail != NULL && q->size != 0) {
67                        fprintf(stderr, "Error deque head cannot be NULL with a non NULL tail and size of more than 0 in libtrace_deque_push_back()\n");
68                        return;
69                }
70                new_node->prev = NULL;
71                q->head = q->tail = new_node;
72        } else {
73                /*assert (q->tail != NULL);*/
74                if (q->tail == NULL) {
75                        fprintf(stderr, "Error deque tail cannot be NULL if it contains a head in libtrace_deque_push_back()\n");
76                        return;
77                }
78                q->tail->next = new_node;
79                new_node->prev = q->tail; // Done the double link
80                q->tail = new_node; // Relink tail
81        }
82        q->size++;
83        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
84}
85
86DLLEXPORT void libtrace_deque_push_front(libtrace_queue_t *q, void *d)
87{
88        // Do as much work as possible outside the lock
89        list_node_t * new_node = (list_node_t *) malloc(sizeof(list_node_t) + q->element_size);
90        new_node->prev = NULL;
91        // Fill it
92        memcpy(&new_node->data, d, q->element_size);
93        // Only ->next is unknown at this stage to be completed in lock
94        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
95        if (q->head == NULL) {
96                /*assert(q->tail == NULL && q->size == 0);*/
97                if (q->tail != NULL && q->size != 0) {
98                        fprintf(stderr, "Error deque head cannot be NULL with a non NULL tail and size of more than 0 in libtrace_deque_push_front()\n");
99                        return;
100                }
101                new_node->next = NULL;
102                q->head = q->tail = new_node;
103        } else {
104                /*assert (q->head != NULL);*/
105                if (q->head == NULL) {
106                        fprintf(stderr, "Error deque tail cannot be NULL if it contains a head in libtrace_deque_push_front()\n");
107                        return;
108                }
109                q->head->prev = new_node;
110                new_node->next = q->head; // Done the double link
111                q->head = new_node; // Relink head
112                // Void out the other things
113        }
114        q->size++;
115        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
116}
117
118DLLEXPORT int libtrace_deque_peek_front(libtrace_queue_t *q, void *d)
119{
120        int ret = 1;
121        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
122        if (q->head == NULL)
123                ret = 0;
124        else
125                memcpy(d, &q->head->data, q->element_size);
126        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
127        return ret;
128}
129
130DLLEXPORT int libtrace_deque_peek_tail(libtrace_queue_t *q, void *d)
131{
132        int ret = 1;
133        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
134        if (q->tail == NULL)
135                ret = 0;
136        else
137                memcpy(d, &q->tail->data, q->element_size);
138        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
139        return ret;
140}
141
142DLLEXPORT int libtrace_deque_pop_front(libtrace_queue_t *q, void *d)
143{
144        int ret = 0;
145        list_node_t * n = NULL;
146        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
147        if (q->head != NULL) {
148                n = q->head;
149                ret = 1;
150                q->head = n->next;
151                if (q->head)
152                        q->head->prev = NULL;
153                q->size--;
154                if (q->size <= 1) // Either 1 or 0 items
155                        q->tail = q->head;
156        }
157        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
158        // Unlock once we've removed it :)
159        if (ret) {
160                memcpy(d, &n->data, q->element_size);
161                free(n);
162        }
163        return ret;
164}
165
166DLLEXPORT int libtrace_deque_pop_tail(libtrace_queue_t *q, void *d)
167{
168        int ret = 0;
169        list_node_t * n=NULL;
170        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
171        if (q->tail != NULL) {
172                n = q->tail;
173                ret = 1;
174                q->tail = n->prev;
175                if (q->tail)
176                        q->tail->next = NULL;
177                q->size--;
178                if (q->size <= 1) // Either 1 or 0 items
179                        q->head = q->tail;
180        }
181        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
182        if (ret) {
183                memcpy(d, &n->data, q->element_size);
184                free(n);
185        }
186        return ret;
187}
188
189DLLEXPORT size_t libtrace_deque_get_size(libtrace_queue_t *q)
190{
191#if RACE_SAFE
192        size_t ret;
193        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
194        ret = q->size;
195        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
196        return ret;
197#else
198        return q->size;
199#endif
200}
201
202DLLEXPORT void libtrace_zero_deque(libtrace_queue_t *q)
203{
204        q->head = q->tail = NULL;
205        q->size = q->element_size = 0;
206}
207
208DLLEXPORT void libtrace_deque_apply_function(libtrace_queue_t *q, deque_data_fn fn)
209{
210        list_node_t *n;
211        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
212        n = q->head;
213        for (n = q->head; n != NULL; n = n->next) {
214                (*fn)(&n->data);
215        }
216        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
217}
Note: See TracBrowser for help on using the repository browser.