1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2021 Tobias Kortkamp <tobik@FreeBSD.org>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #include "config.h"
30
31 #include <sys/types.h>
32 #include <inttypes.h>
33 #include <stdlib.h>
34
35 #include "flow.h"
36 #include "mem.h"
37 #include "queue.h"
38 #include "util.h"
39
40 struct QueueNode {
41 struct QueueNode *next;
42 struct QueueNode *prev;
43 void *value;
44 };
45
46 struct Queue {
47 size_t len;
48 struct QueueNode *head;
49 struct QueueNode *tail;
50 };
51
52 struct QueueIterator {
53 struct QueueNode *current;
54 size_t i;
55 size_t len;
56 };
57
58 struct Queue *
queue_new()59 queue_new()
60 {
61 struct Queue *queue = xmalloc(sizeof(struct Queue));
62 return queue;
63 }
64
65 void
queue_free(struct Queue * queue)66 queue_free(struct Queue *queue)
67 {
68 unless (queue) {
69 return;
70 }
71
72 struct QueueNode *node = queue->head;
73 while (node) {
74 struct QueueNode *next = node->next;
75 free(node);
76 node = next;
77 }
78 free(queue);
79 }
80
81 size_t
queue_len(struct Queue * queue)82 queue_len(struct Queue *queue)
83 {
84 return queue->len;
85 }
86
87 int
queue_contains(struct Queue * queue,const void * value)88 queue_contains(struct Queue *queue, const void *value)
89 {
90 for (struct QueueNode *node = queue->head; node; node = node->next) {
91 if (value == node->value) {
92 return 1;
93 }
94 }
95 return 0;
96 }
97
98 void *
queue_peek(struct Queue * queue)99 queue_peek(struct Queue *queue)
100 {
101 if (queue->head) {
102 return queue->head->value;
103 } else {
104 return NULL;
105 }
106 }
107
108 void *
queue_pop(struct Queue * queue)109 queue_pop(struct Queue *queue)
110 {
111 if (queue->head) {
112 void *value = queue->head->value;
113 struct QueueNode *next = queue->head->next;
114 free(queue->head);
115 queue->head = next;
116 if (queue->head) {
117 queue->head->prev = NULL;
118 unless (queue->head->next) {
119 queue->tail = queue->head;
120 }
121 } else {
122 queue->tail = NULL;
123 }
124 queue->len--;
125 return value;
126 } else {
127 return NULL;
128 }
129 }
130
131 void
queue_push(struct Queue * queue,const void * value)132 queue_push(struct Queue *queue, const void *value)
133 {
134 struct QueueNode *node = xmalloc(sizeof(struct QueueNode));
135 node->value = (void *)value;
136 if (queue->tail) {
137 queue->tail->next = node;
138 node->prev = queue->tail;
139 queue->tail = node;
140 } else {
141 queue->head = queue->tail = node;
142 }
143 queue->len++;
144 }
145
146 void *
queue_dequeue(struct Queue * queue)147 queue_dequeue(struct Queue *queue)
148 {
149 unless (queue->tail) {
150 return NULL;
151 } else {
152 void *value = queue->tail->value;
153 struct QueueNode *newtail = queue->tail->prev;
154 if (newtail) {
155 newtail->next = NULL;
156 }
157 if (queue->tail == queue->head) {
158 queue->head = newtail;
159 }
160 free(queue->tail);
161 queue->tail = newtail;
162 queue->len--;
163 return value;
164 }
165 }
166
167 void
queue_truncate(struct Queue * queue)168 queue_truncate(struct Queue *queue)
169 {
170 struct QueueNode *node = queue->head;
171 while (node) {
172 struct QueueNode *next = node->next;
173 free(node);
174 node = next;
175 }
176 queue->head = NULL;
177 queue->tail = NULL;
178 queue->len = 0;
179 }
180
181 struct QueueIterator *
queue_iterator(struct Queue * queue,ssize_t a,ssize_t b)182 queue_iterator(struct Queue *queue, ssize_t a, ssize_t b)
183 {
184 struct QueueIterator *iter = xmalloc(sizeof(struct QueueIterator));
185 slice_to_range(queue->len, a, b, &iter->i, &iter->len);
186 iter->current = queue->head;
187 for (size_t i = 0; i < iter->i; i++) {
188 iter->current = iter->current->next;
189 }
190 return iter;
191 }
192
193 void
queue_iterator_cleanup(struct QueueIterator ** iter_)194 queue_iterator_cleanup(struct QueueIterator **iter_)
195 {
196 struct QueueIterator *iter = *iter_;
197 if (iter != NULL) {
198 free(iter);
199 *iter_ = NULL;
200 }
201 }
202
203 int
queue_iterator_next(struct QueueIterator ** iter_,size_t * index,void ** key,void ** value)204 queue_iterator_next(struct QueueIterator **iter_, size_t *index, void **key, void **value)
205 {
206 struct QueueIterator *iter = *iter_;
207 if (iter->i < iter->len) {
208 void *v = iter->current->value;
209 iter->current = iter->current->next;
210 *index = iter->i++;
211 *key = v;
212 *value = v;
213 return 1;
214 } else {
215 queue_iterator_cleanup(iter_);
216 *iter_ = NULL;
217 return 0;
218 }
219 }
220