source: lib/data-struct/deque.c @ 6a082f8

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

Move parallel API functions to libtrace_parallel.h

Also started the process of updating the documentation

  • Property mode set to 100644
File size: 4.2 KB
RevLine 
[29bbef0]1#include "deque.h"
[d6a56b6]2
[29bbef0]3#include <assert.h>
4#include <stddef.h>
[8c42377]5#include <stdlib.h>
[29bbef0]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
[ead9478]21DLLEXPORT void libtrace_deque_init(libtrace_queue_t * q, size_t element_size)
[29bbef0]22{
23        q->head = NULL;
24        q->tail = NULL;
25        q->size = 0;
26        q->element_size = element_size;
[a49a9eb]27        ASSERT_RET(pthread_mutex_init(&q->lock, NULL), == 0);
[29bbef0]28}
29
[ead9478]30DLLEXPORT void libtrace_deque_push_back(libtrace_queue_t *q, void *d)
[29bbef0]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
[a49a9eb]38        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]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++;
[a49a9eb]50        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]51}
52
[ead9478]53DLLEXPORT void libtrace_deque_push_front(libtrace_queue_t *q, void *d)
[29bbef0]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
[a49a9eb]61        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]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++;
[a49a9eb]74        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]75}
76
[ead9478]77DLLEXPORT int libtrace_deque_peek_front(libtrace_queue_t *q, void *d)
[29bbef0]78{
79        int ret = 1;
[a49a9eb]80        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]81        if (q->head == NULL)
82                ret = 0;
83        else
84                memcpy(d, &q->head->data, q->element_size);
[a49a9eb]85        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]86        return ret;
87}
88
[ead9478]89DLLEXPORT int libtrace_deque_peek_tail(libtrace_queue_t *q, void *d)
[29bbef0]90{
91        int ret = 1;
[a49a9eb]92        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]93        if (q->tail == NULL)
94                ret = 0;
95        else
96                memcpy(d, &q->tail->data, q->element_size);
[a49a9eb]97        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]98        return ret;
99}
100
[ead9478]101DLLEXPORT int libtrace_deque_pop_front(libtrace_queue_t *q, void *d)
[29bbef0]102{
103        int ret = 0;
104        list_node_t * n = NULL;
[a49a9eb]105        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]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        }
[a49a9eb]116        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]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
[ead9478]125DLLEXPORT int libtrace_deque_pop_tail(libtrace_queue_t *q, void *d)
[29bbef0]126{
127        int ret = 0;
128        list_node_t * n;
[a49a9eb]129        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]130        if (q->tail != NULL) {
131                n = q->tail;
132                ret = 1;
133                q->tail = n->prev;
[ead9478]134                if (q->tail)
[29bbef0]135                        q->tail->next = NULL;
136                q->size--;
137                if (q->size <= 1) // Either 1 or 0 items
138                        q->head = q->tail;
139        }
[a49a9eb]140        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[ead9478]141        if (ret) {
142                memcpy(d, &n->data, q->element_size);
143                free(n);
144        }
[29bbef0]145        return ret;
146}
147
[ead9478]148DLLEXPORT size_t libtrace_deque_get_size(libtrace_queue_t *q)
[29bbef0]149{
150#if RACE_SAFE
[ead9478]151        size_t ret;
[a49a9eb]152        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[29bbef0]153        ret = q->size;
[a49a9eb]154        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
[29bbef0]155        return ret;
156#else
157        return q->size;
158#endif
159}
160
[ead9478]161DLLEXPORT void libtrace_zero_deque(libtrace_queue_t *q)
[29bbef0]162{
163        q->head = q->tail = NULL;
164        q->size = q->element_size = 0;
165}
[fac8c46]166
167DLLEXPORT void libtrace_deque_apply_function(libtrace_queue_t *q, deque_data_fn fn)
168{
169        list_node_t *n;
[a49a9eb]170        ASSERT_RET(pthread_mutex_lock(&q->lock), == 0);
[fac8c46]171        n = q->head;
172        for (n = q->head; n != NULL; n = n->next) {
173                (*fn)(&n->data);
174        }
[a49a9eb]175        ASSERT_RET(pthread_mutex_unlock(&q->lock), == 0);
176}
Note: See TracBrowser for help on using the repository browser.