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

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

Move the data structures out of the way and into there own folder and tidy file naming.

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