source: lib/deque.c @ 29bbef0

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivelibtrace4ndag_formatpfringrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 29bbef0 was 29bbef0, checked in by Richard Sanger <rsangerarj@…>, 8 years ago

My work from over summer, with a few things tidied up and updated to include recent commits/patches to bring this up to date. Still very much work in progress.
  • Property mode set to 100644
File size: 3.8 KB
Line 
1#include "deque.h"
2#include <assert.h>
3#include <stddef.h>
4#include <malloc.h>
5#include <string.h>
6
7
8/* Ensure we don't do any reads without locking even if we *know* that
9 * any write will be atomic */
10#ifndef RACE_SAFE
11#define RACE_SAFE 1
12#endif
13
14struct list_node {
15        list_node_t * next;
16        list_node_t * prev;
17        char data[]; // Our item goes here
18};
19
20void libtrace_deque_init(libtrace_queue_t * q, int element_size)
21{
22        q->head = NULL;
23        q->tail = NULL;
24        q->size = 0;
25        q->element_size = element_size;
26//      q->max_size;
27        assert(pthread_mutex_init(&q->lock, NULL) == 0);
28}
29
30inline void libtrace_deque_push_back(libtrace_queue_t *q, void *d)
31{
32        // Do as much work as possible outside the lock
33        list_node_t * new_node = (list_node_t *) malloc(sizeof(list_node_t) + q->element_size);
34        new_node->next = NULL;
35        // Fill it
36        memcpy(&new_node->data, d, q->element_size);
37        // Only ->prev is unknown at this stage to be completed in lock
38        assert(pthread_mutex_lock(&q->lock) == 0);
39        if (q->head == NULL) {
40                assert(q->tail == NULL && q->size == 0);
41                new_node->prev = NULL;
42                q->head = q->tail = new_node;
43        } else {
44                assert (q->tail != NULL);
45                q->tail->next = new_node;
46                new_node->prev = q->tail; // Done the double link
47                q->tail = new_node; // Relink tail
48        }
49        q->size++;
50        assert(pthread_mutex_unlock(&q->lock) == 0);
51}
52
53inline void libtrace_deque_push_front(libtrace_queue_t *q, void *d)
54{
55        // Do as much work as possible outside the lock
56        list_node_t * new_node = (list_node_t *) malloc(sizeof(list_node_t) + q->element_size);
57        new_node->prev = NULL;
58        // Fill it
59        memcpy(&new_node->data, d, q->element_size);
60        // Only ->next is unknown at this stage to be completed in lock
61        assert(pthread_mutex_lock(&q->lock) == 0);
62        if (q->head == NULL) {
63                assert(q->tail == NULL && q->size == 0);
64                new_node->next = NULL;
65                q->head = q->tail = new_node;
66        } else {
67                assert (q->head != NULL);
68                q->head->prev = new_node;
69                new_node->next = q->head; // Done the double link
70                q->head = new_node; // Relink head
71                // Void out the other things
72        }
73        q->size++;
74        assert(pthread_mutex_unlock(&q->lock) == 0);
75}
76
77inline int libtrace_deque_peek_front(libtrace_queue_t *q, void *d)
78{
79        int ret = 1;
80        assert(pthread_mutex_lock(&q->lock) == 0);
81        if (q->head == NULL)
82                ret = 0;
83        else
84                memcpy(d, &q->head->data, q->element_size);
85        assert(pthread_mutex_unlock(&q->lock) == 0);
86        return ret;
87}
88
89inline int libtrace_deque_peek_tail(libtrace_queue_t *q, void *d)
90{
91        int ret = 1;
92        assert(pthread_mutex_lock(&q->lock) == 0);
93        if (q->tail == NULL)
94                ret = 0;
95        else
96                memcpy(d, &q->tail->data, q->element_size);
97        assert(pthread_mutex_unlock(&q->lock) == 0);
98        return ret;
99}
100
101inline int libtrace_deque_pop_front(libtrace_queue_t *q, void *d)
102{
103        int ret = 0;
104        list_node_t * n = NULL;
105        assert(pthread_mutex_lock(&q->lock) == 0);
106        if (q->head != NULL) {
107                n = q->head;
108                ret = 1;
109                q->head = n->next;
110                if (q->head)
111                        q->head->prev = NULL;
112                q->size--;
113                if (q->size <= 1) // Either 1 or 0 items
114                        q->tail = q->head;
115        }
116        assert(pthread_mutex_unlock(&q->lock) == 0);
117        // Unlock once we've removed it :)
118        if (ret) {
119                memcpy(d, &n->data, q->element_size);
120                free(n);
121        }
122        return ret;
123}
124
125inline int libtrace_deque_pop_tail(libtrace_queue_t *q, void *d)
126{
127        int ret = 0;
128        list_node_t * n;
129        assert(pthread_mutex_lock(&q->lock) == 0);
130        if (q->tail != NULL) {
131                n = q->tail;
132                ret = 1;
133                q->tail = n->prev;
134                if(q->tail)
135                        q->tail->next = NULL;
136                q->size--;
137                if (q->size <= 1) // Either 1 or 0 items
138                        q->head = q->tail;
139        }
140        assert(pthread_mutex_unlock(&q->lock) == 0);
141        memcpy(d, &q->tail->data, q->element_size);
142        free(n);
143        return ret;
144}
145
146inline int libtrace_deque_get_size(libtrace_queue_t *q)
147{
148#if RACE_SAFE
149        int ret;
150        assert(pthread_mutex_lock(&q->lock) == 0);
151        ret = q->size;
152        assert(pthread_mutex_unlock(&q->lock) == 0);
153        return ret;
154#else
155        return q->size;
156#endif
157}
158
159inline void libtrace_zero_deque(libtrace_queue_t *q)
160{
161        q->head = q->tail = NULL;
162        q->size = q->element_size = 0;
163}
Note: See TracBrowser for help on using the repository browser.