File: | src/usr.sbin/npppd/npppd/../common/slist.c |
Warning: | line 151, column 18 Result of 'realloc' is converted to a pointer of type 'void *', which is incompatible with sizeof operand type 'intptr_t' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: slist.c,v 1.8 2021/03/29 03:54:39 yasuoka Exp $ */ |
2 | /*- |
3 | * Copyright (c) 2009 Internet Initiative Japan Inc. |
4 | * All rights reserved. |
5 | * |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions |
8 | * are met: |
9 | * 1. Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * 2. Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
14 | * |
15 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
16 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
17 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
18 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
19 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
20 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
21 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
22 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
23 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
24 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
25 | * SUCH DAMAGE. |
26 | */ |
27 | /**@file |
28 | * provide list accesses against any pointer |
29 | */ |
30 | /* |
31 | * void **list; |
32 | * list_size; // allocated size for the list |
33 | * last_idx; // The last index |
34 | * first_idx; // The first index |
35 | * |
36 | * - first_idx == last_idx means empty. |
37 | * - 0 <= (fist_idx and last_idx) <= (list_size - 1) |
38 | * - Allocated size is (last_idx - first_idx) % list_size. |
39 | * To make the code for checking empty and full simple, we use only |
40 | * list_size-1 items instead of using the full size. |
41 | * - XXX Wnen itr_curr is removed... |
42 | */ |
43 | #include <sys/types.h> |
44 | |
45 | #include <stdint.h> |
46 | #include <stdlib.h> |
47 | #include <string.h> |
48 | |
49 | #include "slist.h" |
50 | |
51 | #define GROW_SIZE256 256 |
52 | #define PTR_SIZE(sizeof(intptr_t)) (sizeof(intptr_t)) |
53 | |
54 | #ifdef SLIST_DEBUG |
55 | #include <stdio.h> |
56 | #define SLIST_ASSERT(cond) \ |
57 | if (!(cond)) { \ |
58 | fprintf(stderr, \ |
59 | "\nAssertion failure("#cond") at (%s):%s:%d\n", \ |
60 | __func__, __FILE__"/usr/src/usr.sbin/npppd/npppd/../common/slist.c", __LINE__60); \ |
61 | } |
62 | #else |
63 | #define SLIST_ASSERT(cond) |
64 | #endif |
65 | |
66 | /** |
67 | * Returns 1 if a index is in the valid range, otherwise returns 0. |
68 | */ |
69 | #define VALID_IDX(_list, _idx)(((_list)->first_idx <= (_list)->last_idx) ? (((_list )->first_idx <= (_idx) && (_idx) < (_list)-> last_idx)? 1 : 0) : (((_list)->first_idx <= (_idx) || ( _idx) < (_list)->last_idx)? 1 : 0)) \ |
70 | (((_list)->first_idx <= (_list)->last_idx) \ |
71 | ? (((_list)->first_idx <= (_idx) && (_idx) < (_list)->last_idx)? 1 : 0)\ |
72 | : (((_list)->first_idx <= (_idx) || (_idx) < (_list)->last_idx)? 1 : 0)) |
73 | |
74 | /** Convert an index into the internal index */ |
75 | #define REAL_IDX(_list, _idx)(((_list)->first_idx + (_idx)) % (_list)->list_size) \ |
76 | (((_list)->first_idx + (_idx)) % (_list)->list_size) |
77 | |
78 | /** Convert a virtual index into the index */ |
79 | #define VIRT_IDX(_list, _idx)(((_list)->first_idx <= (_idx)) ? (_idx) - (_list)-> first_idx : (_list)->list_size - (_list)->first_idx + ( _idx)) (((_list)->first_idx <= (_idx)) \ |
80 | ? (_idx) - (_list)->first_idx \ |
81 | : (_list)->list_size - (_list)->first_idx + (_idx)) |
82 | |
83 | /** Decrement an index */ |
84 | #define DECR_IDX(_list, _memb)(_list)->_memb = ((_list)->list_size + --((_list)->_memb )) % (_list)->list_size \ |
85 | (_list)->_memb = ((_list)->list_size + --((_list)->_memb)) \ |
86 | % (_list)->list_size |
87 | /** Increment an index */ |
88 | #define INCR_IDX(_list, _memb)(_list)->_memb = (++((_list)->_memb)) % (_list)->list_size \ |
89 | (_list)->_memb = (++((_list)->_memb)) % (_list)->list_size |
90 | |
91 | static int slist_grow (slist *); |
92 | static int slist_grow0 (slist *, int); |
93 | static __inline void slist_swap0 (slist *, int, int); |
94 | static __inline void slist_qsort0(slist *, int (*)(const void *, const void *), int, int); |
95 | |
96 | #define itr_is_valid(list)((list)->itr_next >= 0) ((list)->itr_next >= 0) |
97 | #define itr_invalidate(list)((list)->itr_next = -1) ((list)->itr_next = -1) |
98 | |
99 | /** Initialize a slist */ |
100 | void |
101 | slist_init(slist *list) |
102 | { |
103 | memset(list, 0, sizeof(slist)); |
104 | itr_invalidate(list)((list)->itr_next = -1); |
105 | } |
106 | |
107 | /** |
108 | * Specify the size of a list. The size must be specified with the size you |
109 | * want to use +1. Extra 1 entry is for internal use. The size doesn't shrink. |
110 | */ |
111 | int |
112 | slist_set_size(slist *list, int size) |
113 | { |
114 | if (size > list->list_size) |
115 | return slist_grow0(list, size - list->list_size); |
116 | |
117 | return 0; |
118 | } |
119 | |
120 | /** Finish using. Free the buffers and reinit. */ |
121 | void |
122 | slist_fini(slist *list) |
123 | { |
124 | free(list->list); |
125 | slist_init(list); |
126 | } |
127 | |
128 | /** The length of the list */ |
129 | int |
130 | slist_length(slist *list) |
131 | { |
132 | return |
133 | (list->first_idx <= list->last_idx) |
134 | ? (list->last_idx - list->first_idx) |
135 | : (list->list_size - list->first_idx + list->last_idx); |
136 | } |
137 | |
138 | /** Extend the size. Used if the list is full. */ |
139 | static int |
140 | slist_grow0(slist *list, int grow_sz) |
141 | { |
142 | int size_new; |
143 | void **list_new = NULL((void *)0); |
144 | |
145 | /* just return if it is possible to add one item */ |
146 | if (slist_length(list) + 1 < list->list_size) |
147 | /* "+ 1" to avoid the situation list_size == slist_length() */ |
148 | return 0; |
149 | |
150 | size_new = list->list_size + grow_sz; |
151 | if ((list_new = realloc(list->list, PTR_SIZE(sizeof(intptr_t)) * size_new)) |
Result of 'realloc' is converted to a pointer of type 'void *', which is incompatible with sizeof operand type 'intptr_t' | |
152 | == NULL((void *)0)) |
153 | return -1; |
154 | |
155 | memset(&list_new[list->list_size], 0, |
156 | PTR_SIZE(sizeof(intptr_t)) * (size_new - list->list_size)); |
157 | |
158 | list->list = list_new; |
159 | if (list->last_idx < list->first_idx && list->last_idx >= 0) { |
160 | |
161 | /* |
162 | * space is created at the right side when center has space, |
163 | * so move left side to right side |
164 | */ |
165 | if (list->last_idx <= grow_sz) { |
166 | /* |
167 | * The right side has enough space, so move the left |
168 | * side to right side. |
169 | */ |
170 | memmove(&list->list[list->list_size], |
171 | &list->list[0], PTR_SIZE(sizeof(intptr_t)) * list->last_idx); |
172 | list->last_idx = list->list_size + list->last_idx; |
173 | } else { |
174 | /* |
175 | * Copy the left side to right side as long as we |
176 | * can |
177 | */ |
178 | memmove(&list->list[list->list_size], |
179 | &list->list[0], PTR_SIZE(sizeof(intptr_t)) * grow_sz); |
180 | /* Shift the remain to left */ |
181 | memmove(&list->list[0], &list->list[grow_sz], |
182 | PTR_SIZE(sizeof(intptr_t)) *(list->last_idx - grow_sz)); |
183 | |
184 | list->last_idx -= grow_sz; |
185 | } |
186 | } |
187 | list->list_size = size_new; |
188 | |
189 | return 0; |
190 | } |
191 | |
192 | static int |
193 | slist_grow(slist *list) |
194 | { |
195 | return slist_grow0(list, GROW_SIZE256); |
196 | } |
197 | |
198 | /** Add an item to a list */ |
199 | void * |
200 | slist_add(slist *list, void *item) |
201 | { |
202 | if (slist_grow(list) != 0) |
203 | return NULL((void *)0); |
204 | |
205 | list->list[list->last_idx] = item; |
206 | |
207 | if (list->itr_next == -2) { |
208 | /* the iterator points the last, update it. */ |
209 | list->itr_next = list->last_idx; |
210 | } |
211 | |
212 | INCR_IDX(list, last_idx)(list)->last_idx = (++((list)->last_idx)) % (list)-> list_size; |
213 | |
214 | return item; |
215 | } |
216 | |
217 | #define slist_get0(list_, idx)((list_)->list[((((list_))->first_idx + ((idx))) % ((list_ ))->list_size)]) ((list_)->list[REAL_IDX((list_), (idx))((((list_))->first_idx + ((idx))) % ((list_))->list_size )]) |
218 | |
219 | /** Add all items in add_items to a list. */ |
220 | int |
221 | slist_add_all(slist *list, slist *add_items) |
222 | { |
223 | int i, n; |
224 | |
225 | n = slist_length(add_items); |
226 | for (i = 0; i < n; i++) { |
227 | if (slist_add(list, slist_get0(add_items, i)((add_items)->list[((((add_items))->first_idx + ((i))) % ((add_items))->list_size)])) == NULL((void *)0)) |
228 | return 1; |
229 | } |
230 | |
231 | return 0; |
232 | } |
233 | |
234 | /** Return "idx"th item. */ |
235 | void * |
236 | slist_get(slist *list, int idx) |
237 | { |
238 | SLIST_ASSERT(idx >= 0); |
239 | SLIST_ASSERT(slist_length(list) > idx); |
240 | |
241 | if (idx < 0 || slist_length(list) <= idx) |
242 | return NULL((void *)0); |
243 | |
244 | return slist_get0(list, idx)((list)->list[((((list))->first_idx + ((idx))) % ((list ))->list_size)]); |
245 | } |
246 | |
247 | /** Store a value in "idx"th item */ |
248 | int |
249 | slist_set(slist *list, int idx, void *item) |
250 | { |
251 | SLIST_ASSERT(idx >= 0); |
252 | SLIST_ASSERT(slist_length(list) > idx); |
253 | |
254 | if (idx < 0 || slist_length(list) <= idx) |
255 | return -1; |
256 | |
257 | list->list[REAL_IDX(list, idx)(((list)->first_idx + (idx)) % (list)->list_size)] = item; |
258 | |
259 | return 0; |
260 | } |
261 | |
262 | /** Remove the 1st entry and return it. */ |
263 | void * |
264 | slist_remove_first(slist *list) |
265 | { |
266 | void *oldVal; |
267 | |
268 | if (slist_length(list) <= 0) |
269 | return NULL((void *)0); |
270 | |
271 | oldVal = list->list[list->first_idx]; |
272 | |
273 | if (itr_is_valid(list)((list)->itr_next >= 0) && list->itr_next == list->first_idx) |
274 | INCR_IDX(list, itr_next)(list)->itr_next = (++((list)->itr_next)) % (list)-> list_size; |
275 | |
276 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
277 | itr_invalidate(list)((list)->itr_next = -1); |
278 | |
279 | INCR_IDX(list, first_idx)(list)->first_idx = (++((list)->first_idx)) % (list)-> list_size; |
280 | |
281 | return oldVal; |
282 | } |
283 | |
284 | /** Remove the last entry and return it */ |
285 | void * |
286 | slist_remove_last(slist *list) |
287 | { |
288 | if (slist_length(list) <= 0) |
289 | return NULL((void *)0); |
290 | |
291 | DECR_IDX(list, last_idx)(list)->last_idx = ((list)->list_size + --((list)->last_idx )) % (list)->list_size; |
292 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
293 | itr_invalidate(list)((list)->itr_next = -1); |
294 | |
295 | return list->list[list->last_idx]; |
296 | } |
297 | |
298 | /** Remove all entries */ |
299 | void |
300 | slist_remove_all(slist *list) |
301 | { |
302 | void **list0 = list->list; |
303 | |
304 | slist_init(list); |
305 | |
306 | list->list = list0; |
307 | } |
308 | |
309 | /* Swap items. This doesn't check boundary. */ |
310 | static __inline void |
311 | slist_swap0(slist *list, int m, int n) |
312 | { |
313 | void *m0; |
314 | |
315 | itr_invalidate(list)((list)->itr_next = -1); /* Invalidate iterator */ |
316 | |
317 | m0 = list->list[REAL_IDX(list, m)(((list)->first_idx + (m)) % (list)->list_size)]; |
318 | list->list[REAL_IDX(list, m)(((list)->first_idx + (m)) % (list)->list_size)] = list->list[REAL_IDX(list, n)(((list)->first_idx + (n)) % (list)->list_size)]; |
319 | list->list[REAL_IDX(list, n)(((list)->first_idx + (n)) % (list)->list_size)] = m0; |
320 | } |
321 | |
322 | /** Swap between mth and nth */ |
323 | void |
324 | slist_swap(slist *list, int m, int n) |
325 | { |
326 | int len; |
327 | |
328 | len = slist_length(list); |
329 | SLIST_ASSERT(m >= 0); |
330 | SLIST_ASSERT(n >= 0); |
331 | SLIST_ASSERT(len > m); |
332 | SLIST_ASSERT(len > n); |
333 | |
334 | if (m < 0 || n < 0) |
335 | return; |
336 | if (m >= len || n >= len) |
337 | return; |
338 | |
339 | slist_swap0(list, m, n); |
340 | } |
341 | |
342 | /** Remove "idx"th item */ |
343 | void * |
344 | slist_remove(slist *list, int idx) |
345 | { |
346 | int first, last, idx0, reset_itr; |
347 | void *oldVal; |
348 | |
349 | SLIST_ASSERT(idx >= 0); |
350 | SLIST_ASSERT(slist_length(list) > idx); |
351 | |
352 | if (idx < 0 || slist_length(list) <= idx) |
353 | return NULL((void *)0); |
354 | |
355 | idx0 = REAL_IDX(list, idx)(((list)->first_idx + (idx)) % (list)->list_size); |
356 | oldVal = list->list[idx0]; |
357 | reset_itr = 0; |
358 | |
359 | first = -1; |
360 | last = -1; |
361 | |
362 | if (list->itr_next == idx0) { |
363 | INCR_IDX(list, itr_next)(list)->itr_next = (++((list)->itr_next)) % (list)-> list_size; |
364 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
365 | list->itr_next = -2; /* on the last item */ |
366 | } |
367 | |
368 | /* should we reduce the last side or the first side? */ |
369 | if (list->first_idx < list->last_idx) { |
370 | /* take the smaller side */ |
371 | if (idx0 - list->first_idx < list->last_idx - idx0) { |
372 | first = list->first_idx; |
373 | INCR_IDX(list, first_idx)(list)->first_idx = (++((list)->first_idx)) % (list)-> list_size; |
374 | } else { |
375 | last = list->last_idx; |
376 | DECR_IDX(list, last_idx)(list)->last_idx = ((list)->list_size + --((list)->last_idx )) % (list)->list_size; |
377 | } |
378 | } else { |
379 | /* |
380 | * 0 < last (unused) first < idx < size, so let's reduce the |
381 | * first. |
382 | */ |
383 | if (list->first_idx <= idx0) { |
384 | first = list->first_idx; |
385 | INCR_IDX(list, first_idx)(list)->first_idx = (++((list)->first_idx)) % (list)-> list_size; |
386 | } else { |
387 | last = list->last_idx; |
388 | DECR_IDX(list, last_idx)(list)->last_idx = ((list)->list_size + --((list)->last_idx )) % (list)->list_size; |
389 | } |
390 | } |
391 | |
392 | /* the last side */ |
393 | if (last != -1 && last != 0 && last != idx0) { |
394 | |
395 | /* move left the items that is from idx0 to the last */ |
396 | if (itr_is_valid(list)((list)->itr_next >= 0) && |
397 | idx0 <= list->itr_next && list->itr_next <= last) { |
398 | DECR_IDX(list, itr_next)(list)->itr_next = ((list)->list_size + --((list)->itr_next )) % (list)->list_size; |
399 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
400 | itr_invalidate(list)((list)->itr_next = -1); |
401 | } |
402 | |
403 | memmove(&list->list[idx0], &list->list[idx0 + 1], |
404 | (PTR_SIZE(sizeof(intptr_t))) * (last - idx0)); |
405 | } |
406 | /* the first side */ |
407 | if (first != -1 && first != idx0) { |
408 | |
409 | /* move right the items that is from first to the idx0 */ |
410 | if (itr_is_valid(list)((list)->itr_next >= 0) && |
411 | first <= list->itr_next && list->itr_next <= idx0) { |
412 | INCR_IDX(list, itr_next)(list)->itr_next = (++((list)->itr_next)) % (list)-> list_size; |
413 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
414 | itr_invalidate(list)((list)->itr_next = -1); |
415 | } |
416 | |
417 | memmove(&list->list[first + 1], &list->list[first], |
418 | (PTR_SIZE(sizeof(intptr_t))) * (idx0 - first)); |
419 | } |
420 | if (list->first_idx == list->last_idx) { |
421 | list->first_idx = 0; |
422 | list->last_idx = 0; |
423 | } |
424 | |
425 | return oldVal; |
426 | } |
427 | |
428 | /** |
429 | * Shuffle items. |
430 | */ |
431 | void |
432 | slist_shuffle(slist *list) |
433 | { |
434 | int i, len; |
435 | |
436 | len = slist_length(list); |
437 | for (i = len; i > 1; i--) |
438 | slist_swap0(list, i - 1, (int)arc4random_uniform(i)); |
439 | } |
440 | |
441 | /** Init an iterator. Only one iterator exists. */ |
442 | void |
443 | slist_itr_first(slist *list) |
444 | { |
445 | list->itr_next = list->first_idx; |
446 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
447 | itr_invalidate(list)((list)->itr_next = -1); |
448 | } |
449 | |
450 | /** |
451 | * Return whether a iterator can go to the next item. |
452 | * @return Return 1 if the iterator can return the next item. |
453 | * Return 0 it reaches the end of the list or the list is modified |
454 | * destructively. |
455 | */ |
456 | int |
457 | slist_itr_has_next(slist *list) |
458 | { |
459 | if (list->itr_next < 0) |
460 | return 0; |
461 | return VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0)); |
462 | } |
463 | |
464 | /** Return the next item and iterate to the next */ |
465 | void * |
466 | slist_itr_next(slist *list) |
467 | { |
468 | void *rval; |
469 | |
470 | if (!itr_is_valid(list)((list)->itr_next >= 0)) |
471 | return NULL((void *)0); |
472 | SLIST_ASSERT(VALID_IDX(list, list->itr_next)); |
473 | |
474 | if (list->list == NULL((void *)0)) |
475 | return NULL((void *)0); |
476 | |
477 | rval = list->list[list->itr_next]; |
478 | list->itr_curr = list->itr_next; |
479 | INCR_IDX(list, itr_next)(list)->itr_next = (++((list)->itr_next)) % (list)-> list_size; |
480 | |
481 | if (!VALID_IDX(list, list->itr_next)(((list)->first_idx <= (list)->last_idx) ? (((list)-> first_idx <= (list->itr_next) && (list->itr_next ) < (list)->last_idx)? 1 : 0) : (((list)->first_idx <= (list->itr_next) || (list->itr_next) < (list)->last_idx )? 1 : 0))) |
482 | list->itr_next = -2; /* on the last item */ |
483 | |
484 | return rval; |
485 | } |
486 | |
487 | /** Delete the current iterated item */ |
488 | void * |
489 | slist_itr_remove(slist *list) |
490 | { |
491 | SLIST_ASSERT(list != NULL); |
492 | |
493 | return slist_remove(list, VIRT_IDX(list, list->itr_curr)(((list)->first_idx <= (list->itr_curr)) ? (list-> itr_curr) - (list)->first_idx : (list)->list_size - (list )->first_idx + (list->itr_curr))); |
494 | } |
495 | |
496 | /** Sort the list items by quick sort algorithm using given compar */ |
497 | void |
498 | slist_qsort(slist *list, int (*compar)(const void *, const void *)) |
499 | { |
500 | if (list->first_idx != list->last_idx) /* is not empty */ |
501 | slist_qsort0(list, compar, 0, slist_length(list) - 1); |
502 | } |
503 | |
504 | static __inline void |
505 | slist_qsort0(slist *list, int (*compar)(const void *, const void *), int l, |
506 | int r) |
507 | { |
508 | int i, j; |
509 | void *p; |
510 | |
511 | i = l; |
512 | j = r; |
513 | p = slist_get0(list, (j + i) / 2)((list)->list[((((list))->first_idx + (((j + i) / 2))) % ((list))->list_size)]); |
514 | while (i <= j) { |
515 | while (compar(slist_get0(list, i)((list)->list[((((list))->first_idx + ((i))) % ((list)) ->list_size)]), p) < 0) |
516 | i++; |
517 | while (compar(slist_get0(list, j)((list)->list[((((list))->first_idx + ((j))) % ((list)) ->list_size)]), p) > 0) |
518 | j--; |
519 | if (i <= j) |
520 | slist_swap0(list, i++, j--); |
521 | } |
522 | if (l < j) |
523 | slist_qsort0(list, compar, l, j); |
524 | if (i < r) |
525 | slist_qsort0(list, compar, i, r); |
526 | } |