source: lib/data-struct/deque.c @ ee6e802

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivendag_formatrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since ee6e802 was ee6e802, checked in by Shane Alcock <salcock@…>, 4 years ago

Updated copyright blurb on all source files

In some cases, this meant adding copyright blurbs to files that
had never had them before.

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