Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * Doubly Linked List
4 : : * (C) 2013 Jung-Sang Ahn <jungsang.ahn@gmail.com>
5 : : */
6 : :
7 : : #include <stdio.h>
8 : : #include <assert.h>
9 : : #include "list.h"
10 : :
11 : : #ifdef _LIST_LOCK
12 : : #define IFDEF_LOCK(...) __VA_ARGS__
13 : : #else
14 : : #define IFDEF_LOCK(...)
15 : : #endif
16 : :
17 : :
18 : 35216278 : void list_init(struct list *list)
19 : : {
20 : 35216278 : list->head = NULL;
21 : 35216278 : list->tail = NULL;
22 : : IFDEF_LOCK( spin_init(&list->lock); );
23 : 35216278 : }
24 : :
25 : 72038279 : void list_push_front(struct list *list, struct list_elem *e)
26 : : {
27 : : IFDEF_LOCK( spin_lock(&list->lock); );
28 [ + + ]: 72038279 : if (list->head == NULL) {
29 : 37922715 : list->head = e;
30 : 37922715 : list->tail = e;
31 : 37922715 : e->next = e->prev = NULL;
32 : : }else{
33 : 34115564 : list->head->prev = e;
34 : 34115564 : e->prev = NULL;
35 : 34115564 : e->next = list->head;
36 : 34115564 : list->head = e;
37 : : }
38 : : IFDEF_LOCK( spin_unlock(&list->lock); );
39 : 72038279 : }
40 : :
41 : 43056824 : void list_push_back(struct list *list, struct list_elem *e)
42 : : {
43 : : IFDEF_LOCK( spin_lock(&list->lock); );
44 [ + + ]: 43056824 : if (list->tail == NULL) {
45 : 26079656 : list->head = e;
46 : 26079656 : list->tail = e;
47 : 26079656 : e->next = e->prev = NULL;
48 : : }else{
49 : 16977168 : list->tail->next = e;
50 : 16977168 : e->prev = list->tail;
51 : 16977168 : e->next = NULL;
52 : 16977168 : list->tail = e;
53 : : }
54 : : IFDEF_LOCK( spin_unlock(&list->lock); );
55 : 43056824 : }
56 : :
57 : : // insert E just before BEFORE
58 : 44 : void list_insert_before(struct list *list, struct list_elem *before, struct list_elem *e)
59 : : {
60 : : IFDEF_LOCK( spin_lock(&list->lock); );
61 : 44 : e->prev = before->prev;
62 : 44 : e->next = before;
63 [ + - ]: 44 : if (before->prev) before->prev->next = e;
64 : 0 : else list->head = e;
65 : 44 : before->prev = e;
66 : : IFDEF_LOCK( spin_unlock(&list->lock); );
67 : 44 : }
68 : :
69 : : // insert E just after AFTER
70 : 0 : void list_insert_after(struct list *list, struct list_elem *after, struct list_elem *e)
71 : : {
72 : : IFDEF_LOCK( spin_lock(&list->lock); );
73 : 0 : e->next = after->next;
74 : 0 : e->prev = after;
75 [ # # ]: 0 : if (after->next) after->next->prev = e;
76 : 0 : else list->tail = e;
77 : 0 : after->next = e;
78 : : IFDEF_LOCK( spin_unlock(&list->lock); );
79 : 0 : }
80 : :
81 : 96055597 : struct list_elem *list_remove(struct list *list, struct list_elem *e)
82 : : {
83 : : IFDEF_LOCK( spin_lock(&list->lock); );
84 [ + - ]: 96055597 : if (e) {
85 : : // if not NULL
86 [ + + ]: 96055597 : if (e->next) e->next->prev = e->prev;
87 [ + + ]: 96055597 : if (e->prev) e->prev->next = e->next;
88 : :
89 [ + + ]: 96055597 : if (list->head == e) list->head = e->next;
90 [ + + ]: 96055597 : if (list->tail == e) list->tail = e->prev;
91 : :
92 : 96055597 : struct list_elem *next = e->next;
93 : :
94 : : IFDEF_LOCK( spin_unlock(&list->lock); );
95 : 96055597 : return next;
96 : : }
97 : : // NULL .. do nothing
98 : : IFDEF_LOCK( spin_unlock(&list->lock); );
99 : 96055597 : return NULL;
100 : : }
101 : :
102 : 12 : struct list_elem *list_remove_reverse(struct list *list, struct list_elem *e)
103 : : {
104 : : IFDEF_LOCK( spin_lock(&list->lock); );
105 [ + - ]: 12 : if (e) {
106 : : // if not NULL
107 [ + + ]: 12 : if (e->next) e->next->prev = e->prev;
108 [ - + ]: 12 : if (e->prev) e->prev->next = e->next;
109 : :
110 [ + - ]: 12 : if (list->head == e) list->head = e->next;
111 [ + + ]: 12 : if (list->tail == e) list->tail = e->prev;
112 : :
113 : : IFDEF_LOCK( spin_unlock(&list->lock); );
114 : 12 : return e->prev;
115 : : }
116 : : // NULL .. do nothing
117 : : IFDEF_LOCK( spin_unlock(&list->lock); );
118 : 12 : return NULL;
119 : : }
120 : :
121 : 19073357 : struct list_elem *list_pop_front(struct list *list)
122 : : {
123 : : IFDEF_LOCK( spin_lock(&list->lock); );
124 : 19073357 : struct list_elem *e = list->head;
125 [ + + ]: 19073357 : if (e) {
126 : : // if not NULL
127 [ + + ]: 17587922 : if (e->next) e->next->prev = e->prev;
128 [ - + ]: 17587922 : if (e->prev) e->prev->next = e->next;
129 : :
130 [ + + ]: 17587922 : if (list->head == e) list->head = e->next;
131 [ + + ]: 17587922 : if (list->tail == e) list->tail = e->prev;
132 : :
133 : : IFDEF_LOCK( spin_unlock(&list->lock); );
134 : 17587922 : return e;
135 : : }
136 : : // NULL .. do nothing
137 : : IFDEF_LOCK( spin_unlock(&list->lock); );
138 : 19073357 : return NULL;
139 : : }
140 : :
141 : 1679848 : struct list_elem *list_pop_back(struct list *list)
142 : : {
143 : : IFDEF_LOCK( spin_lock(&list->lock); );
144 : 1679848 : struct list_elem *e = list->tail;
145 [ + + ]: 1679848 : if (e) {
146 : : // if not NULL
147 [ - + ]: 1483880 : if (e->next) e->next->prev = e->prev;
148 [ + + ]: 1483880 : if (e->prev) e->prev->next = e->next;
149 : :
150 [ + + ]: 1483880 : if (list->head == e) list->head = e->next;
151 [ + - ]: 1483880 : if (list->tail == e) list->tail = e->prev;
152 : :
153 : : IFDEF_LOCK( spin_unlock(&list->lock); );
154 : 1483880 : return e;
155 : : }
156 : : // NULL .. do nothing
157 : : IFDEF_LOCK( spin_unlock(&list->lock); );
158 : 1679848 : return NULL;
159 : : }
160 : :
161 : 281926497 : struct list_elem *list_begin(struct list *list)
162 : : {
163 : : IFDEF_LOCK( spin_lock(&list->lock); );
164 : 281926497 : struct list_elem *e = list->head;
165 : : IFDEF_LOCK( spin_unlock(&list->lock); );
166 : 281926497 : return e;
167 : : }
168 : :
169 : 35117580 : struct list_elem *list_end(struct list *list)
170 : : {
171 : : IFDEF_LOCK( spin_lock(&list->lock); );
172 : 35117580 : struct list_elem *e = list->tail;
173 : : IFDEF_LOCK( spin_unlock(&list->lock); );
174 : 35117580 : return e;
175 : : }
176 : :
177 : 1263419596 : struct list_elem *list_next(struct list_elem *e)
178 : : {
179 : 1263419596 : return e->next;
180 : : }
181 : :
182 : 21385815 : struct list_elem *list_prev(struct list_elem *e)
183 : : {
184 : 21385815 : return e->prev;
185 : : }
186 : :
|
