1 /*
2 * Copyright (C) 2000-2019 the xine project
3 *
4 * This file is part of xine, a free video player.
5 *
6 * xine is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * xine is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA
19 */
20
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif
24
25 #include <stdlib.h>
26 #include <xine/attributes.h>
27 #include <xine/list.h>
28 #include <xine/xineutils.h> /* dlist_*, dnode_* */
29
30 #define MIN_CHUNK_SIZE 32
31 #define MAX_CHUNK_SIZE 65536
32
33 typedef struct xine_list_elem_s xine_list_elem_t;
34 typedef struct _xine_list_chunk_s _xine_list_chunk_t;
35 /* typedef struct xine_list_s xine_list_t; */
36
37 struct xine_list_elem_s {
38 dnode_t node;
39 /*_xine_list_chunk_t *chunk;*/
40 void *value;
41 };
42
43 struct _xine_list_chunk_s {
44 _xine_list_chunk_t *next;
45 /*_xine_list_t *list;*/
46 uint32_t max_elems;
47 uint32_t first_unused;
48 xine_list_elem_t elems[1];
49 };
50
51 struct xine_list_s {
52 dlist_t used;
53 dlist_t free;
54 _xine_list_chunk_t *chunks;
55 uint32_t size;
56 _xine_list_chunk_t first_chunk;
57 };
58
_xine_list_chunk_new(xine_list_t * list,uint32_t size)59 static _xine_list_chunk_t *XINE_MALLOC _xine_list_chunk_new (xine_list_t *list, uint32_t size) {
60 _xine_list_chunk_t *chunk;
61 chunk = malloc (sizeof (*chunk) + (size - 1) * sizeof (xine_list_elem_t));
62 if (!chunk)
63 return NULL;
64 /*chunk->list = list;*/
65 chunk->max_elems = size;
66 chunk->first_unused = 0;
67 chunk->next = list->chunks;
68 list->chunks = chunk;
69 return chunk;
70 }
71
xine_list_new(void)72 xine_list_t *XINE_MALLOC xine_list_new (void) {
73 xine_list_t *list;
74 list = malloc (sizeof (*list) + (MIN_CHUNK_SIZE - 1) * sizeof (xine_list_elem_t));
75 if (!list)
76 return NULL;
77 DLIST_INIT (&list->used);
78 DLIST_INIT (&list->free);
79 list->size = 0;
80 /*list->first_chunk.list = list;*/
81 list->first_chunk.max_elems = MIN_CHUNK_SIZE;
82 list->first_chunk.first_unused = 0;
83 list->first_chunk.next = NULL;
84 list->chunks = &list->first_chunk;
85 return list;
86 }
87
_xine_list_reset(xine_list_t * list)88 static void _xine_list_reset (xine_list_t *list) {
89 _xine_list_chunk_t *chunk;
90 chunk = list->chunks;
91 while (chunk != &list->first_chunk) {
92 _xine_list_chunk_t *next = chunk->next;
93 free (chunk);
94 chunk = next;
95 }
96 list->size = 0;
97 list->first_chunk.first_unused = 0;
98 DLIST_INIT (&list->used);
99 DLIST_INIT (&list->free);
100 list->chunks = &list->first_chunk;
101 }
102
xine_list_clear(xine_list_t * list)103 void xine_list_clear (xine_list_t *list) {
104 if (list)
105 _xine_list_reset (list);
106 }
107
xine_list_delete(xine_list_t * list)108 void xine_list_delete (xine_list_t *list) {
109 if (list) {
110 _xine_list_reset (list);
111 free (list);
112 }
113 }
114
_xine_list_elem_new(xine_list_t * list)115 static xine_list_elem_t *_xine_list_elem_new (xine_list_t *list) {
116 xine_list_elem_t *elem;
117 _xine_list_chunk_t *chunk;
118 uint32_t n;
119
120 if (!DLIST_IS_EMPTY (&list->free)) {
121 elem = (xine_list_elem_t *)list->free.head;
122 DLIST_REMOVE (&elem->node);
123 return elem;
124 }
125
126 chunk = list->chunks;
127 if (chunk->first_unused < chunk->max_elems) {
128 elem = &chunk->elems[0] + chunk->first_unused;
129 chunk->first_unused++;
130 /*elem->chunk = chunk;*/
131 return elem;
132 }
133
134 n = chunk->max_elems * 2;
135 if (n > MAX_CHUNK_SIZE)
136 n = MAX_CHUNK_SIZE;
137 chunk = _xine_list_chunk_new (list, n);
138 if (!chunk)
139 return NULL;
140 elem = &chunk->elems[0];
141 chunk->first_unused = 1;
142 /* elem->chunk = new_chunk;*/
143 return elem;
144 }
145
xine_list_size(xine_list_t * list)146 unsigned int xine_list_size (xine_list_t *list) {
147 return list ? list->size : 0;
148 }
149
xine_list_empty(xine_list_t * list)150 unsigned int xine_list_empty (xine_list_t *list) {
151 return list ? (list->size == 0) : 1;
152 }
153
xine_list_front(xine_list_t * list)154 xine_list_iterator_t xine_list_front (xine_list_t *list) {
155 return list && list->size ? (xine_list_elem_t *)list->used.head : NULL;
156 }
157
xine_list_back(xine_list_t * list)158 xine_list_iterator_t xine_list_back(xine_list_t *list) {
159 return list && list->size ? (xine_list_elem_t *)list->used.tail : NULL;
160 }
161
xine_list_push_back(xine_list_t * list,void * value)162 void xine_list_push_back(xine_list_t *list, void *value) {
163 xine_list_elem_t *new_elem;
164
165 if (!list)
166 return;
167 new_elem = _xine_list_elem_new (list);
168 if (!new_elem)
169 return;
170
171 new_elem->value = value;
172 DLIST_ADD_TAIL (&new_elem->node, &list->used);
173 list->size++;
174 }
175
xine_list_push_front(xine_list_t * list,void * value)176 void xine_list_push_front(xine_list_t *list, void *value) {
177 xine_list_elem_t *new_elem;
178
179 if (!list)
180 return;
181 new_elem = _xine_list_elem_new (list);
182 if (!new_elem)
183 return;
184
185 new_elem->value = value;
186 DLIST_ADD_HEAD (&new_elem->node, &list->used);
187 list->size++;
188 }
189
xine_list_next(xine_list_t * list,xine_list_iterator_t ite)190 xine_list_iterator_t xine_list_next (xine_list_t *list, xine_list_iterator_t ite) {
191 xine_list_elem_t *elem = ite;
192
193 elem = elem ? (xine_list_elem_t *)elem->node.next : (xine_list_elem_t *)list->used.head;
194 return elem->node.next ? elem : NULL;
195 }
196
xine_list_next_value(xine_list_t * list,xine_list_iterator_t * ite)197 void *xine_list_next_value (xine_list_t *list, xine_list_iterator_t *ite) {
198 xine_list_elem_t *elem = *ite;
199 if (elem) {
200 elem = (xine_list_elem_t *)elem->node.next;
201 } else if (list) {
202 elem = (xine_list_elem_t *)list->used.head;
203 } else {
204 *ite = NULL;
205 return NULL;
206 }
207 if (!elem->node.next) {
208 *ite = NULL;
209 return NULL;
210 }
211 *ite = elem;
212 return elem->value;
213 }
214
xine_list_prev(xine_list_t * list,xine_list_iterator_t ite)215 xine_list_iterator_t xine_list_prev (xine_list_t *list, xine_list_iterator_t ite) {
216 xine_list_elem_t *elem = ite;
217
218 elem = elem ? (xine_list_elem_t *)elem->node.prev : (xine_list_elem_t *)list->used.tail;
219 return elem->node.prev ? elem : NULL;
220 }
221
xine_list_prev_value(xine_list_t * list,xine_list_iterator_t * ite)222 void *xine_list_prev_value (xine_list_t *list, xine_list_iterator_t *ite) {
223 xine_list_elem_t *elem = *ite;
224 if (elem) {
225 elem = (xine_list_elem_t *)elem->node.prev;
226 } else if (list) {
227 elem = (xine_list_elem_t *)list->used.tail;
228 } else {
229 *ite = NULL;
230 return NULL;
231 }
232 if (!elem->node.prev) {
233 *ite = NULL;
234 return NULL;
235 }
236 *ite = elem;
237 return elem->value;
238 }
239
xine_list_get_value(xine_list_t * list,xine_list_iterator_t ite)240 void *xine_list_get_value (xine_list_t *list, xine_list_iterator_t ite) {
241 xine_list_elem_t *elem = ite;
242 (void)list;
243 return elem ? elem->value : NULL;
244 }
245
xine_list_remove(xine_list_t * list,xine_list_iterator_t position)246 void xine_list_remove (xine_list_t *list, xine_list_iterator_t position) {
247 xine_list_elem_t *elem = position;
248
249 if (list && elem) {
250 DLIST_REMOVE (&elem->node);
251 DLIST_ADD_TAIL (&elem->node, &list->free);
252 list->size--;
253 }
254 }
255
xine_list_insert(xine_list_t * list,xine_list_iterator_t position,void * value)256 xine_list_iterator_t xine_list_insert (xine_list_t *list, xine_list_iterator_t position, void *value) {
257 xine_list_elem_t *new_elem, *elem = position;
258
259 if (!list)
260 return NULL;
261 new_elem = _xine_list_elem_new (list);
262 if (!new_elem)
263 return NULL;
264
265 new_elem->value = value;
266 if (!elem) {
267 DLIST_ADD_TAIL (&new_elem->node, &list->used);
268 } else {
269 DLIST_INSERT (&new_elem->node, &elem->node);
270 }
271 list->size++;
272 return new_elem;
273 }
274
xine_list_find(xine_list_t * list,void * value)275 xine_list_iterator_t xine_list_find (xine_list_t *list, void *value) {
276 xine_list_elem_t *elem;
277
278 if (!list)
279 return NULL;
280 for (elem = (xine_list_elem_t *)list->used.head; elem->node.next; elem = (xine_list_elem_t *)elem->node.next) {
281 if (elem->value == value)
282 return elem;
283 }
284 return NULL;
285 }
286
287