source: lib/data-struct/deque.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.6 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                if (q->tail != NULL || q->size != 0) {
66                        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");
67                        return;
68                }
69                new_node->prev = NULL;
70                q->head = q->tail = new_node;
71        } else {
72                if (q->tail == NULL) {
73                        fprintf(stderr, "Error deque tail cannot be NULL if it contains a head in libtrace_deque_push_back()\n");
74                        return;
75                }
76                q->tail->next = new_node;
77                new_node->prev = q->tail; // Done the double link
78                q->tail = new_node; // Relink tail
79        }
80        q->size++;
81        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
82}
83
84DLLEXPORT void libtrace_deque_push_front(libtrace_queue_t *q, void *d)
85{
86        // Do as much work as possible outside the lock
87        list_node_t * new_node = (list_node_t *) malloc(sizeof(list_node_t) + q->element_size);
88        new_node->prev = NULL;
89        // Fill it
90        memcpy(&new_node->data, d, q->element_size);
91        // Only ->next is unknown at this stage to be completed in lock
92        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
93        if (q->head == NULL) {
94                if (q->tail != NULL || q->size != 0) {
95                        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");
96                        return;
97                }
98                new_node->next = NULL;
99                q->head = q->tail = new_node;
100        } else {
101                q->head->prev = new_node;
102                new_node->next = q->head; // Done the double link
103                q->head = new_node; // Relink head
104                // Void out the other things
105        }
106        q->size++;
107        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
108}
109
110DLLEXPORT int libtrace_deque_peek_front(libtrace_queue_t *q, void *d)
111{
112        int ret = 1;
113        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
114        if (q->head == NULL)
115                ret = 0;
116        else
117                memcpy(d, &q->head->data, q->element_size);
118        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
119        return ret;
120}
121
122DLLEXPORT int libtrace_deque_peek_tail(libtrace_queue_t *q, void *d)
123{
124        int ret = 1;
125        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
126        if (q->tail == NULL)
127                ret = 0;
128        else
129                memcpy(d, &q->tail->data, q->element_size);
130        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
131        return ret;
132}
133
134DLLEXPORT int libtrace_deque_pop_front(libtrace_queue_t *q, void *d)
135{
136        int ret = 0;
137        list_node_t * n = NULL;
138        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
139        if (q->head != NULL) {
140                n = q->head;
141                ret = 1;
142                q->head = n->next;
143                if (q->head)
144                        q->head->prev = NULL;
145                q->size--;
146                if (q->size <= 1) // Either 1 or 0 items
147                        q->tail = q->head;
148        }
149        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
150        // Unlock once we've removed it :)
151        if (ret) {
152                memcpy(d, &n->data, q->element_size);
153                free(n);
154        }
155        return ret;
156}
157
158DLLEXPORT int libtrace_deque_pop_tail(libtrace_queue_t *q, void *d)
159{
160        int ret = 0;
161        list_node_t * n=NULL;
162        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
163        if (q->tail != NULL) {
164                n = q->tail;
165                ret = 1;
166                q->tail = n->prev;
167                if (q->tail)
168                        q->tail->next = NULL;
169                q->size--;
170                if (q->size <= 1) // Either 1 or 0 items
171                        q->head = q->tail;
172        }
173        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
174        if (ret) {
175                memcpy(d, &n->data, q->element_size);
176                free(n);
177        }
178        return ret;
179}
180
181DLLEXPORT size_t libtrace_deque_get_size(libtrace_queue_t *q)
182{
183#if RACE_SAFE
184        size_t ret;
185        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
186        ret = q->size;
187        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
188        return ret;
189#else
190        return q->size;
191#endif
192}
193
194DLLEXPORT void libtrace_zero_deque(libtrace_queue_t *q)
195{
196        q->head = q->tail = NULL;
197        q->size = q->element_size = 0;
198}
199
200DLLEXPORT void libtrace_deque_apply_function(libtrace_queue_t *q, deque_data_fn fn)
201{
202        list_node_t *n;
203        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
204        n = q->head;
205        for (n = q->head; n != NULL; n = n->next) {
206                (*fn)(&n->data);
207        }
208        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
209}
Note: See TracBrowser for help on using the repository browser.