1 /* oblist.c:
2 *
3 ****************************************************************
4 * Copyright (C) 2004 Tom Lord
5 *
6 * See the file "COPYING" for further information about
7 * the copyright and warranty status of this work.
8 *
9 */
10
11
12 #include "hackerlab/sort/qsort.h"
13 #include "hackerlab/mem/mem.h"
14 #include "hackerlab/oblists/oblist.h"
15
16
17 struct ol_closure;
18
19
20 /* __STDC__ prototypes for static functions */
21 static int oblist_move_gap (t_oblist * ol,
22 alloc_limits limits,
23 ssize_t elt_size,
24 t_oblist_type * type,
25 void * closure,
26 ssize_t wanted_gap);
27 static void init_ol_closure (struct ol_closure * olc,
28 t_oblist * ol,
29 alloc_limits limits,
30 ssize_t elt_size,
31 t_oblist_type * type,
32 void * closure);
33 static t_obqueue_type * translate_type (struct oblist_type * type);
34 static int forward_init (t_obqueue * oq,
35 alloc_limits limits,
36 ssize_t elt_size,
37 t_obqueue_type * type,
38 void * closure,
39 void * mem,
40 ssize_t n_elts);
41 static void forward_uninit (t_obqueue * oq,
42 alloc_limits limits,
43 ssize_t elt_size,
44 t_obqueue_type * type,
45 void * closure,
46 void * mem,
47 ssize_t n_elts);
48
49
50
51 #define LEFT(OL) (&(OL)->_left)
52 #define RIGHT(OL) (&(OL)->_right)
53
54 struct obqueue_type init_and_uninit = { forward_init, forward_uninit };
55 struct obqueue_type init_only = { forward_init, 0 };
56 struct obqueue_type uninit_only = { 0, forward_uninit };
57
58 struct ol_closure
59 {
60 t_oblist * ol;
61 t_oblist_type * type;
62 void * closure;
63 };
64
65
66
67
68 int
init_oblist(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)69 init_oblist (t_oblist * ol,
70 alloc_limits limits,
71 ssize_t elt_size,
72 t_oblist_type * type,
73 void * closure)
74 {
75 if (!ol)
76 return -1;
77 else
78 {
79 struct ol_closure olc;
80
81 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
82
83 mem_set0 ((t_uchar *)ol, sizeof (*ol));
84 if (0 > init_obqueue (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc))
85 return -1;
86 if (0 > init_obqueue (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc))
87 return -1;
88 return 0;
89 }
90 }
91
92
93 void
uninit_oblist(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)94 uninit_oblist (t_oblist * ol,
95 alloc_limits limits,
96 ssize_t elt_size,
97 t_oblist_type * type,
98 void * closure)
99 {
100 if (ol)
101 {
102 struct ol_closure olc;
103
104 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
105
106 uninit_obqueue (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc);
107 uninit_obqueue (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc);
108 mem_set0 ((t_uchar *)ol, sizeof (*ol));
109 }
110 }
111
112
113
114
115 int
oblist_is_empty(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)116 oblist_is_empty (t_oblist * ol,
117 alloc_limits limits,
118 ssize_t elt_size,
119 t_oblist_type * type,
120 void * closure)
121 {
122 if (!ol)
123 return 1;
124
125 return !oblist_size (ol, limits, elt_size, type, closure);
126 }
127
128
129 ssize_t
oblist_size(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)130 oblist_size (t_oblist * ol,
131 alloc_limits limits,
132 ssize_t elt_size,
133 t_oblist_type * type,
134 void * closure)
135 {
136 struct ol_closure olc;
137
138 if (!ol)
139 return 0;
140
141 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
142
143 return ( obqueue_size (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc)
144 + obqueue_size (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc));
145 }
146
147
148 ssize_t
oblist_room(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)149 oblist_room (t_oblist * ol,
150 alloc_limits limits,
151 ssize_t elt_size,
152 t_oblist_type * type,
153 void * closure)
154 {
155 struct ol_closure olc;
156
157 if (!ol)
158 return 0;
159
160 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
161
162 return ( obqueue__room (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc)
163 + obqueue__room (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc));
164 }
165
166
167
168
169 void *
oblist_burst(ssize_t * len_returned,t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure,ssize_t n,ssize_t len)170 oblist_burst (ssize_t * len_returned,
171 t_oblist * ol,
172 alloc_limits limits,
173 ssize_t elt_size,
174 t_oblist_type * type,
175 void * closure,
176 ssize_t n,
177 ssize_t len)
178 {
179 struct ol_closure olc;
180 ssize_t left_size;
181
182 if (n < 0)
183 return 0;
184
185 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
186
187 left_size = obqueue_size (LEFT (ol), limits, elt_size, translate_type (type), (void *)&olc);
188
189 if (n < left_size)
190 {
191 ssize_t len_avail;
192
193 if ((n + len) <= left_size)
194 len_avail = len;
195 else
196 len_avail = (left_size - n);
197
198 return obqueue_burst (len_returned, LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, n, len_avail);
199 }
200
201 n = (n - obqueue_size (LEFT (ol), limits, elt_size, translate_type (type), (void *)&olc));
202
203 return obqueue_burst (len_returned, RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, n, len);
204 }
205
206
207 void *
oblist_range(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure,ssize_t n,ssize_t len)208 oblist_range (t_oblist * ol,
209 alloc_limits limits,
210 ssize_t elt_size,
211 t_oblist_type * type,
212 void * closure,
213 ssize_t n,
214 ssize_t len)
215 {
216 ssize_t gap;
217 struct ol_closure olc;
218
219 if (n < 0)
220 return 0;
221
222 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
223
224 if ((len < 0) || ((n + len) < 0) || ((n + len) > oblist_size (ol, limits, elt_size, type, closure)))
225 return 0;
226
227 gap = obqueue_size (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc);
228
229 if ((n < gap) && ((n + len) <= gap))
230 {
231 return obqueue_range (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, n, len);
232 }
233
234 if (gap <= n)
235 {
236 return obqueue_range (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, n - gap, len);
237 }
238
239 if ((gap - n) < ((n + len) - gap))
240 {
241 if (0 > oblist_move_gap (ol, limits, elt_size, type, closure, n))
242 return 0;
243 return obqueue_range (RIGHT (ol), limits, elt_size, translate_type (type), (void *)&olc, 0, len);
244 }
245 else
246 {
247 if (0 > oblist_move_gap (ol, limits, elt_size, type, closure, n + len))
248 return 0;
249 return obqueue_range (LEFT (ol), limits, elt_size, translate_type (type), (void *)&olc, n, len);
250 }
251 }
252
253
254 static int
oblist_move_gap(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure,ssize_t wanted_gap)255 oblist_move_gap (t_oblist * ol,
256 alloc_limits limits,
257 ssize_t elt_size,
258 t_oblist_type * type,
259 void * closure,
260 ssize_t wanted_gap)
261 {
262 struct ol_closure olc;
263 ssize_t current_gap;
264 ssize_t size;
265
266 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
267
268 current_gap = obqueue_size (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc);
269 size = oblist_size (ol, limits, elt_size, type, closure);
270
271 if (current_gap == wanted_gap)
272 return 0;
273
274 if (wanted_gap < 0)
275 return -1;
276
277 if (wanted_gap > size)
278 return -1;
279
280 if (wanted_gap < current_gap)
281 {
282 ssize_t amt_to_move;
283 ssize_t amt_moved;
284 ssize_t source_pos;
285 ssize_t dest_pos;
286
287 amt_to_move = current_gap - wanted_gap;
288 amt_moved = 0;
289
290 source_pos = wanted_gap;
291 dest_pos = 0;
292
293 if (0 > obqueue_push_n (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, amt_to_move))
294 return -1;
295
296 while (amt_moved < amt_to_move)
297 {
298 t_uchar * left_burst;
299 ssize_t lb_len;
300 t_uchar * right_burst;
301 ssize_t rb_len;
302 ssize_t useful_len;
303
304 left_burst = obqueue_burst (&lb_len, LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, source_pos, (amt_to_move - amt_moved));
305 right_burst = obqueue_burst (&rb_len, RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, dest_pos, (amt_to_move - amt_moved));
306 if (lb_len < rb_len)
307 useful_len = lb_len;
308 else
309 useful_len = rb_len;
310
311 mem_move (right_burst, left_burst, useful_len * elt_size);
312
313 amt_moved += useful_len;
314 source_pos += useful_len;
315 dest_pos += useful_len;
316 }
317
318 obqueue_pop_last_n (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, amt_to_move);
319 return 0;
320 }
321 else /* (wanted_gap > current_gap) */
322 {
323 ssize_t amt_to_move;
324 ssize_t amt_moved;
325 ssize_t source_pos;
326 ssize_t dest_pos;
327
328 amt_to_move = wanted_gap - current_gap;
329 amt_moved = 0;
330
331 source_pos = 0;
332 dest_pos = current_gap;
333
334 if (0 > obqueue_append_n (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, amt_to_move))
335 return -1;
336
337 while (amt_moved < amt_to_move)
338 {
339 t_uchar * left_burst;
340 ssize_t lb_len;
341 t_uchar * right_burst;
342 ssize_t rb_len;
343 ssize_t useful_len;
344
345 left_burst = obqueue_burst (&lb_len, LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, dest_pos, (amt_to_move - amt_moved));
346 right_burst = obqueue_burst (&rb_len, RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, source_pos, (amt_to_move - amt_moved));
347 if (lb_len < rb_len)
348 useful_len = lb_len;
349 else
350 useful_len = rb_len;
351
352 mem_move (left_burst, right_burst, useful_len * elt_size);
353
354 amt_moved += useful_len;
355 source_pos += useful_len;
356 dest_pos += useful_len;
357 }
358
359 obqueue_pop_n (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, amt_to_move);
360 return 0;
361 }
362 }
363
364
365
366 int
oblist_insert_n(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure,ssize_t before_pos,ssize_t n,void * mem)367 oblist_insert_n (t_oblist * ol,
368 alloc_limits limits,
369 ssize_t elt_size,
370 t_oblist_type * type,
371 void * closure,
372 ssize_t before_pos,
373 ssize_t n,
374 void * mem)
375 {
376 struct ol_closure olc;
377 ssize_t s;
378
379 s = oblist_size (ol, limits, elt_size, type, closure);
380
381 if (before_pos < 0)
382 return -1;
383
384 if (before_pos > s)
385 return -1;
386
387 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
388
389 if (before_pos == 0)
390 {
391 if (0 > obqueue_push_n (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, n))
392 return -1;
393 }
394 else if (before_pos == s)
395 {
396 if (0 > obqueue_append_n (RIGHT(ol), limits, elt_size, translate_type (type), (void *)&olc, n))
397 return -1;
398 }
399 else
400 {
401 if (0 > oblist_move_gap (ol, limits, elt_size, type, closure, before_pos))
402 return -1;
403
404 if (0 > obqueue_append_n (LEFT(ol), limits, elt_size, translate_type (type), (void *)&olc, n))
405 return -1;
406 }
407
408 if (mem)
409 mem_move (oblist_range (ol, limits, elt_size, type, closure, before_pos, n), mem, n * elt_size);
410
411 return 0;
412 }
413
414
415 int
oblist_delete_n(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure,ssize_t pos,ssize_t n)416 oblist_delete_n (t_oblist * ol,
417 alloc_limits limits,
418 ssize_t elt_size,
419 t_oblist_type * type,
420 void * closure,
421 ssize_t pos,
422 ssize_t n)
423 {
424 struct ol_closure olc;
425 ssize_t s;
426 ssize_t gap;
427 ssize_t pos_distance;
428 ssize_t end_distance;
429 ssize_t new_gap;
430
431 s = oblist_size (ol, limits, elt_size, type, closure);
432
433 if (pos < 0)
434 return -1;
435
436 if (pos > s)
437 return -1;
438
439 if (n < 0)
440 return -1;
441
442 if (((pos + n) < 0) || ((pos + n) > s))
443 n = s - pos;
444
445 init_ol_closure (&olc, ol, limits, elt_size, type, closure);
446
447 gap = obqueue_size (LEFT (ol), limits, elt_size, translate_type (type), (void *)&olc);
448
449 if (gap > pos)
450 pos_distance = gap - n;
451 else
452 pos_distance = n - gap;
453
454 if (gap > (pos + n))
455 end_distance = gap - (pos + n);
456 else
457 end_distance = (pos + n) - gap;
458
459 if (pos_distance < end_distance)
460 new_gap = pos;
461 else
462 new_gap = (pos + n);
463
464 if (0 > oblist_move_gap (ol, limits, elt_size, type, closure, new_gap))
465 return -1;
466
467 if (new_gap == pos)
468 {
469 obqueue_pop_n (RIGHT (ol), limits, elt_size, translate_type (type), (void *)&olc, n);
470 return 0;
471 }
472 else
473 {
474 obqueue_pop_last_n (LEFT (ol), limits, elt_size, translate_type (type), (void *)&olc, n);
475 return 0;
476 }
477 }
478
479
480
481
482 int
oblist_sort(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * lclosure,t_oblist_cmp_fn cmp,void * closure)483 oblist_sort (t_oblist * ol,
484 alloc_limits limits,
485 ssize_t elt_size,
486 t_oblist_type * type,
487 void * lclosure,
488 t_oblist_cmp_fn cmp,
489 void * closure)
490 {
491 ssize_t s;
492 void * it;
493
494 s = oblist_size (ol, limits, elt_size, type, lclosure);
495
496 it = oblist_range (ol, limits, elt_size, type, lclosure, 0, s);
497
498 if (!s)
499 return -1;
500
501 quicksort (it, s, elt_size, cmp, closure);
502
503 return 0;
504 }
505
506
507 ssize_t
oblist_find(ssize_t * would_be_before,t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * lclosure,void * key,t_oblist_cmp_fn cmp,void * closure)508 oblist_find (ssize_t * would_be_before,
509 t_oblist * ol,
510 alloc_limits limits,
511 ssize_t elt_size,
512 t_oblist_type * type,
513 void * lclosure,
514 void * key,
515 t_oblist_cmp_fn cmp,
516 void * closure)
517 {
518 ssize_t lo;
519 ssize_t hi;
520 ssize_t leftmost_found;
521
522 lo = 0;
523 hi = oblist_size (ol, limits, elt_size, type, lclosure);
524 leftmost_found = -1;
525
526 while (lo < hi)
527 {
528 ssize_t mid;
529 int c;
530
531 mid = lo + ((hi - lo) >> 1);
532
533 c = cmp (key, oblist_burst (0, ol, limits, elt_size, type, lclosure, mid, 1), closure);
534
535 if (!c)
536 {
537 leftmost_found = mid;
538 hi = mid;
539 }
540 else if (c < 0)
541 {
542 hi = mid;
543 }
544 else
545 {
546 lo = mid + 1;
547 }
548 }
549
550 if (leftmost_found >= 0)
551 return leftmost_found;
552 else
553 {
554 if (would_be_before)
555 {
556 *would_be_before = lo;
557 }
558
559 return -1;
560 }
561 }
562
563
564 ssize_t
oblist_sorted_insert(t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * lclosure,void * key,t_oblist_cmp_fn cmp,void * closure,int copy_from_key,int not_if_present)565 oblist_sorted_insert (t_oblist * ol,
566 alloc_limits limits,
567 ssize_t elt_size,
568 t_oblist_type * type,
569 void * lclosure,
570 void * key,
571 t_oblist_cmp_fn cmp,
572 void * closure,
573 int copy_from_key,
574 int not_if_present)
575 {
576 ssize_t found_at;
577 ssize_t would_be_before;
578 ssize_t insert_at;
579
580 found_at = oblist_find (&would_be_before, ol, limits, elt_size, type, lclosure, key, cmp, closure);
581
582 if (not_if_present && (found_at >= 0))
583 {
584 return found_at;
585 }
586
587 if (found_at >= 0)
588 insert_at = found_at;
589 else
590 insert_at = would_be_before;
591
592 if (0 > oblist_insert_n (ol, limits, elt_size, type, lclosure, insert_at, 1, 0))
593 return -1;
594
595 if (copy_from_key && key)
596 mem_move (oblist_range (ol, limits, elt_size, type, closure, insert_at, 1), key, elt_size);
597
598 return insert_at;
599 }
600
601
602
603
604 static void
init_ol_closure(struct ol_closure * olc,t_oblist * ol,alloc_limits limits,ssize_t elt_size,t_oblist_type * type,void * closure)605 init_ol_closure (struct ol_closure * olc,
606 t_oblist * ol,
607 alloc_limits limits,
608 ssize_t elt_size,
609 t_oblist_type * type,
610 void * closure)
611 {
612 olc->ol = ol;
613 olc->type = type;
614 olc->closure = closure;
615 }
616
617
618 static t_obqueue_type *
translate_type(struct oblist_type * type)619 translate_type (struct oblist_type * type)
620 {
621 if (!type || (!type->init && !type->uninit))
622 return 0;
623 else if (!type->uninit)
624 return &init_only;
625 else if (!type->init)
626 return &uninit_only;
627 else
628 return &init_and_uninit;
629 }
630
631
632 static int
forward_init(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,void * mem,ssize_t n_elts)633 forward_init (t_obqueue * oq,
634 alloc_limits limits,
635 ssize_t elt_size,
636 t_obqueue_type * type,
637 void * closure,
638 void * mem,
639 ssize_t n_elts)
640 {
641 struct ol_closure * olc;
642
643 olc = (struct ol_closure *)closure;
644
645 if (!olc || !olc->type || !olc->type->init)
646 return -1;
647
648 return olc->type->init (olc->ol, limits, elt_size, olc->type, olc->closure, mem, n_elts);
649 }
650
651
652 static void
forward_uninit(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,void * mem,ssize_t n_elts)653 forward_uninit (t_obqueue * oq,
654 alloc_limits limits,
655 ssize_t elt_size,
656 t_obqueue_type * type,
657 void * closure,
658 void * mem,
659 ssize_t n_elts)
660 {
661 struct ol_closure * olc;
662
663 if (!olc || !olc->type || !olc->type->uninit)
664 return;
665
666 olc->type->uninit (olc->ol, limits, elt_size, olc->type, olc->closure, mem, n_elts);
667 }
668
669
670
671 /* tag: Tom Lord Sun Oct 24 08:12:32 2004 (oblist.c)
672 */
673