1 /* obqueue.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 #include "hackerlab/mem/mem.h"
12 #include "hackerlab/arrays/ar.h"
13 #include "hackerlab/obqueues/obqueue.h"
14
15
16 /* __STDC__ prototypes for static functions */
17 static ssize_t obqueue__head (t_obqueue * oq,
18 alloc_limits limits,
19 ssize_t elt_size,
20 t_obqueue_type * type,
21 void * closure);
22 static ssize_t obqueue__tail (t_obqueue * oq,
23 alloc_limits limits,
24 ssize_t elt_size,
25 t_obqueue_type * type,
26 void * closure);
27 static ssize_t ideal_room_for_size (ssize_t s);
28 static int ensure_room (t_obqueue * oq,
29 alloc_limits limits,
30 ssize_t elt_size,
31 t_obqueue_type * type,
32 void * closure,
33 ssize_t n_more);
34 static void uninit_elements (t_obqueue * oq,
35 alloc_limits limits,
36 ssize_t elt_size,
37 t_obqueue_type * type,
38 void * closure,
39 ssize_t from,
40 ssize_t to);
41 static int init_elements (t_obqueue * oq,
42 alloc_limits limits,
43 ssize_t elt_size,
44 t_obqueue_type * type,
45 void * closure,
46 ssize_t from,
47 ssize_t to);
48
49
50 int
init_obqueue(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)51 init_obqueue (t_obqueue * oq,
52 alloc_limits limits,
53 ssize_t elt_size,
54 t_obqueue_type * type,
55 void * closure)
56 {
57 if (!oq)
58 return -1;
59
60 mem_set0 ((t_uchar *)oq, sizeof (*oq));
61 return 0;
62 }
63
64
65 void
uninit_obqueue(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)66 uninit_obqueue (t_obqueue * oq,
67 alloc_limits limits,
68 ssize_t elt_size,
69 t_obqueue_type * type,
70 void * closure)
71 {
72 if (!oq)
73 return;
74
75 if (type && type->uninit)
76 {
77 ssize_t r;
78 ssize_t h;
79 ssize_t t;
80
81 r = obqueue__room (oq, limits, elt_size, type, closure);
82 h = obqueue__head (oq, limits, elt_size, type, closure);
83 t = obqueue__tail (oq, limits, elt_size, type, closure);
84
85 if (h < t)
86 {
87 type->uninit (oq, limits, elt_size, type, closure, (void *)(oq->_storage + h * elt_size), t - h);
88 }
89 else if (t < h)
90 {
91 type->uninit (oq, limits, elt_size, type, closure, (void *)(oq->_storage), t);
92 type->uninit (oq, limits, elt_size, type, closure, (void *)(oq->_storage + h * elt_size), r - h);
93 }
94 }
95 ar_free ((void **)&oq->_storage, limits);
96 mem_set0 ((t_uchar *)oq, sizeof (*oq));
97 }
98
99
100
101 ssize_t
obqueue__room(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)102 obqueue__room (t_obqueue * oq,
103 alloc_limits limits,
104 ssize_t elt_size,
105 t_obqueue_type * type,
106 void * closure)
107 {
108 if (!oq)
109 return 0;
110 else
111 return (ssize_t)ar_size ((void *)oq->_storage, limits, elt_size);
112 }
113
114
115 static ssize_t
obqueue__head(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)116 obqueue__head (t_obqueue * oq,
117 alloc_limits limits,
118 ssize_t elt_size,
119 t_obqueue_type * type,
120 void * closure)
121 {
122 if (!oq)
123 return 0;
124 else
125 return oq->_head;
126 }
127
128
129 static ssize_t
obqueue__tail(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)130 obqueue__tail (t_obqueue * oq,
131 alloc_limits limits,
132 ssize_t elt_size,
133 t_obqueue_type * type,
134 void * closure)
135 {
136 if (!oq)
137 return 0;
138 else
139 return oq->_tail;
140 }
141
142
143
144 int
obqueue_is_empty(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)145 obqueue_is_empty (t_obqueue * oq,
146 alloc_limits limits,
147 ssize_t elt_size,
148 t_obqueue_type * type,
149 void * closure)
150 {
151 return ( obqueue__head (oq, limits, elt_size, type, closure)
152 == obqueue__tail (oq, limits, elt_size, type, closure));
153 }
154
155
156 int
obqueue_size(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)157 obqueue_size (t_obqueue * oq,
158 alloc_limits limits,
159 ssize_t elt_size,
160 t_obqueue_type * type,
161 void * closure)
162 {
163 ssize_t h;
164 ssize_t t;
165 ssize_t r;
166
167 h = obqueue__head (oq, limits, elt_size, type, closure);
168 t = obqueue__tail (oq, limits, elt_size, type, closure);
169 r = obqueue__room (oq, limits, elt_size, type, closure);
170
171 if (h <= t)
172 return t - h;
173 else
174 return (t + (r - h));
175 }
176
177
178 ssize_t
obqueue__nth_place(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)179 obqueue__nth_place (t_obqueue * oq,
180 alloc_limits limits,
181 ssize_t elt_size,
182 t_obqueue_type * type,
183 void * closure,
184 ssize_t n)
185 {
186 ssize_t s;
187 ssize_t h;
188 ssize_t t;
189 ssize_t r;
190
191 s = obqueue_size (oq, limits, elt_size, type, closure);
192
193 if (n < 0)
194 n += s;
195
196 if (n < 0)
197 return -1;
198
199 if (n >= s)
200 return -1;
201
202 h = obqueue__head (oq, limits, elt_size, type, closure);
203 t = obqueue__tail (oq, limits, elt_size, type, closure);
204 r = obqueue__room (oq, limits, elt_size, type, closure);
205
206 if (h < t)
207 {
208 return h + n;
209 }
210 else if ((r - h) > n)
211 {
212 return h + n;
213 }
214 else
215 {
216 return n - (r - h);
217 }
218 }
219
220
221 void *
obqueue_peek(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)222 obqueue_peek (t_obqueue * oq,
223 alloc_limits limits,
224 ssize_t elt_size,
225 t_obqueue_type * type,
226 void * closure)
227 {
228 return obqueue_n (oq, limits, elt_size, type, closure, 0);
229 }
230
231
232 void *
obqueue_n(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)233 obqueue_n (t_obqueue * oq,
234 alloc_limits limits,
235 ssize_t elt_size,
236 t_obqueue_type * type,
237 void * closure,
238 ssize_t n)
239 {
240 ssize_t place;
241
242 place = obqueue__nth_place (oq, limits, elt_size, type, closure, n);
243
244 if (place < 0)
245 return 0;
246
247 return oq->_storage + place * elt_size;
248 }
249
250
251 void *
obqueue_burst(ssize_t * len_returned,t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n,ssize_t len)252 obqueue_burst (ssize_t * len_returned,
253 t_obqueue * oq,
254 alloc_limits limits,
255 ssize_t elt_size,
256 t_obqueue_type * type,
257 void * closure,
258 ssize_t n,
259 ssize_t len)
260 {
261 ssize_t s;
262 ssize_t h;
263 ssize_t t;
264 ssize_t r;
265 ssize_t n_place;
266 ssize_t end_place;
267 void * answer;
268
269
270 s = obqueue_size (oq, limits, elt_size, type, closure);
271 h = obqueue__head (oq, limits, elt_size, type, closure);
272 t = obqueue__tail (oq, limits, elt_size, type, closure);
273 r = obqueue__room (oq, limits, elt_size, type, closure);
274
275 n_place = obqueue__nth_place (oq, limits, elt_size, type, closure, n);
276 end_place = obqueue__nth_place (oq, limits, elt_size, type, closure, n + len - 1);
277
278 if ((n_place < 0) || (end_place < 0))
279 return 0;
280
281 answer = oq->_storage + n_place * elt_size;
282
283 if (len_returned)
284 {
285 if (n_place >= h)
286 {
287 if (end_place >= n_place)
288 *len_returned = len;
289 else
290 *len_returned = (r - n_place);
291 }
292 else
293 {
294 if (end_place < t)
295 *len_returned = len;
296 else
297 *len_returned = t - n_place;
298 }
299 }
300 return answer;
301 }
302
303
304 void *
obqueue_range(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n,ssize_t len)305 obqueue_range (t_obqueue * oq,
306 alloc_limits limits,
307 ssize_t elt_size,
308 t_obqueue_type * type,
309 void * closure,
310 ssize_t n,
311 ssize_t len)
312 {
313 ssize_t s;
314 ssize_t h;
315 ssize_t t;
316 ssize_t r;
317 ssize_t n_place;
318 ssize_t end_place;
319 void * answer;
320
321 s = obqueue_size (oq, limits, elt_size, type, closure);
322 h = obqueue__head (oq, limits, elt_size, type, closure);
323 t = obqueue__tail (oq, limits, elt_size, type, closure);
324 r = obqueue__room (oq, limits, elt_size, type, closure);
325
326 n_place = obqueue__nth_place (oq, limits, elt_size, type, closure, n);
327 end_place = obqueue__nth_place (oq, limits, elt_size, type, closure, n + len - 1);
328
329 if ((n_place < 0) || (end_place < 0))
330 return 0;
331
332 answer = oq->_storage + n_place * elt_size;
333
334 if (n_place >= h)
335 {
336 if (end_place >= n_place)
337 return answer;
338 }
339 else
340 {
341 if (end_place <= t)
342 return answer;
343 }
344
345 /* buffer needs to be rotated.
346 *
347 * stuff-a tail=gap head=stuff-b
348 * ^
349 * N
350 */
351 {
352 t_uchar * new_array = 0;
353 ssize_t new_r;
354 ssize_t h_len;
355
356 new_r = ideal_room_for_size (s);
357
358 if (0 > ar_setsize ((void **)&new_array, limits, new_r, elt_size))
359 {
360 return 0;
361 }
362
363 h_len = (r - h);
364
365 mem_move (new_array, oq->_storage + h * elt_size, h_len * elt_size);
366 mem_move (new_array + h_len * elt_size, oq->_storage, t * elt_size);
367 ar_free ((void **)&oq->_storage, limits);
368 oq->_storage = new_array;
369 oq->_head = 0;
370 oq->_tail = s;
371 }
372
373 return oq->_storage + n * elt_size;
374 }
375
376 static ssize_t
ideal_room_for_size(ssize_t s)377 ideal_room_for_size (ssize_t s)
378 {
379 s += 1;
380 if (s <= 0)
381 return 0;
382 if (s < 256)
383 return 16 * ((s + 15) / 16);
384 if (s < 10240)
385 return 256 * ((s + 255) / 256);
386 return 10240 * ((s + 10239) / 10240);
387 }
388
389 void *
obqueue_push(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)390 obqueue_push (t_obqueue * oq,
391 alloc_limits limits,
392 ssize_t elt_size,
393 t_obqueue_type * type,
394 void * closure)
395 {
396 ssize_t h;
397 ssize_t r;
398 void * answer;
399
400 if (0 > ensure_room (oq, limits, elt_size, type, closure, 1))
401 return 0;
402
403 h = obqueue__head (oq, limits, elt_size, type, closure);
404 r = obqueue__room (oq, limits, elt_size, type, closure);
405
406 --h;
407 if (h < 0)
408 h = (r - 1);
409
410 answer = oq->_storage + h * elt_size;
411
412 if (type && type->init)
413 {
414 if (0 > type->init (oq, limits, elt_size, type, closure, answer, 1))
415 return 0;
416 }
417 else
418 {
419 mem_set0 ((t_uchar *)answer, elt_size);
420 }
421
422 oq->_head = h;
423
424 return answer;
425 }
426
427
428 int
obqueue_push_n(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)429 obqueue_push_n (t_obqueue * oq,
430 alloc_limits limits,
431 ssize_t elt_size,
432 t_obqueue_type * type,
433 void * closure,
434 ssize_t n)
435 {
436 ssize_t h;
437 ssize_t saved_head;
438 ssize_t r;
439
440 if (0 > ensure_room (oq, limits, elt_size, type, closure, n))
441 return -1;
442
443 h = obqueue__head (oq, limits, elt_size, type, closure);
444 saved_head = h;
445 r = obqueue__room (oq, limits, elt_size, type, closure);
446
447 h = h - n;
448 if (h < 0)
449 h = (r + h);
450
451 oq->_head = h;
452 if (0 > init_elements (oq, limits, elt_size, type, closure, 0, n))
453 {
454 oq->_head = saved_head;
455 return -1;
456 }
457
458 return 0;
459 }
460
461
462 void
obqueue_pop(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)463 obqueue_pop (t_obqueue * oq,
464 alloc_limits limits,
465 ssize_t elt_size,
466 t_obqueue_type * type,
467 void * closure)
468 {
469 if (obqueue_is_empty (oq, limits, elt_size, type, closure))
470 return;
471
472 if (type && type->uninit)
473 type->uninit (oq, limits, elt_size, type, closure, (void *)(oq->_storage + oq->_head * elt_size), 1);
474
475 ++oq->_head;
476
477 if (oq->_head >= obqueue__room (oq, limits, elt_size, type, closure))
478 oq->_head = 0;
479 }
480
481
482 void
obqueue_pop_n(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)483 obqueue_pop_n (t_obqueue * oq,
484 alloc_limits limits,
485 ssize_t elt_size,
486 t_obqueue_type * type,
487 void * closure,
488 ssize_t n)
489 {
490 if (obqueue_is_empty (oq, limits, elt_size, type, closure))
491 return;
492
493 if (n > obqueue_size (oq, limits, elt_size, type, closure))
494 n = obqueue_size (oq, limits, elt_size, type, closure);
495
496 if (n <= 0)
497 return;
498
499 uninit_elements (oq, limits, elt_size, type, closure, 0, n);
500
501 oq->_head += n;
502
503 if (oq->_head >= obqueue__room (oq, limits, elt_size, type, closure))
504 oq->_head = (oq->_head - obqueue__room (oq, limits, elt_size, type, closure));
505 }
506
507
508 void *
obqueue_append(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)509 obqueue_append (t_obqueue * oq,
510 alloc_limits limits,
511 ssize_t elt_size,
512 t_obqueue_type * type,
513 void * closure)
514 {
515 void * answer;
516 ssize_t t;
517
518 if (0 > ensure_room (oq, limits, elt_size, type, closure, 1))
519 return 0;
520
521 answer = oq->_storage + oq->_tail * elt_size;
522
523 t = oq->_tail + 1;
524 if (t >= obqueue__room (oq, limits, elt_size, type, closure))
525 t = 0;
526
527 if (type && type->init)
528 {
529 if (0 > type->init (oq, limits, elt_size, type, closure, answer, 1))
530 return 0;
531 }
532 else
533 {
534 mem_set0 ((t_uchar *)answer, elt_size);
535 }
536
537 oq->_tail = t;
538
539 return answer;
540 }
541
542
543 int
obqueue_append_n(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)544 obqueue_append_n (t_obqueue * oq,
545 alloc_limits limits,
546 ssize_t elt_size,
547 t_obqueue_type * type,
548 void * closure,
549 ssize_t n)
550 {
551 ssize_t saved_s;
552 ssize_t t;
553 ssize_t saved_t;
554 ssize_t r;
555
556 if (0 > ensure_room (oq, limits, elt_size, type, closure, n))
557 return -1;
558
559 saved_s = obqueue_size (oq, limits, elt_size, type, closure);
560
561 saved_t = obqueue__tail (oq, limits, elt_size, type, closure);
562 t = n + saved_t;
563 r = obqueue__room (oq, limits, elt_size, type, closure);
564
565 if (t >= r)
566 t = t - r;
567
568 oq->_tail = t;
569
570 if (0 > init_elements (oq, limits, elt_size, type, closure, saved_s, saved_s + n))
571 {
572 oq->_tail = saved_t;
573 return -1;
574 }
575 return 0;
576 }
577
578
579 void
obqueue_pop_last(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure)580 obqueue_pop_last (t_obqueue * oq,
581 alloc_limits limits,
582 ssize_t elt_size,
583 t_obqueue_type * type,
584 void * closure)
585 {
586 if (obqueue_is_empty (oq, limits, elt_size, type, closure))
587 return;
588
589 --oq->_tail;
590
591 if (oq->_tail < 0)
592 oq->_tail = (obqueue__room (oq, limits, elt_size, type, closure) - 1);
593
594 if (type && type->uninit)
595 {
596 type->uninit (oq, limits, elt_size, type, closure, (void *)(oq->_storage + oq->_tail * elt_size), 1);
597 }
598 }
599
600
601
602 void
obqueue_pop_last_n(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n)603 obqueue_pop_last_n (t_obqueue * oq,
604 alloc_limits limits,
605 ssize_t elt_size,
606 t_obqueue_type * type,
607 void * closure,
608 ssize_t n)
609 {
610 ssize_t s;
611
612 if (obqueue_is_empty (oq, limits, elt_size, type, closure))
613 return;
614
615 s = obqueue_size (oq, limits, elt_size, type, closure);
616
617 if (n > s)
618 n = s;
619
620 uninit_elements (oq, limits, elt_size, type, closure, (s - n), s);
621
622 oq->_tail -= n;
623
624 if (oq->_tail < 0)
625 oq->_tail = (obqueue__room (oq, limits, elt_size, type, closure) + oq->_tail);
626 }
627
628
629
630 static int
ensure_room(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t n_more)631 ensure_room (t_obqueue * oq,
632 alloc_limits limits,
633 ssize_t elt_size,
634 t_obqueue_type * type,
635 void * closure,
636 ssize_t n_more)
637 {
638 ssize_t h;
639 ssize_t t;
640 ssize_t s;
641 ssize_t r;
642 ssize_t new_r;
643
644 if (n_more < 0)
645 return -1;
646
647 h = obqueue__head (oq, limits, elt_size, type, closure);
648 t = obqueue__tail (oq, limits, elt_size, type, closure);
649 s = obqueue_size (oq, limits, elt_size, type, closure);
650 r = obqueue__room (oq, limits, elt_size, type, closure);
651
652 if ((r - s) > n_more)
653 return 0;
654
655 new_r = ideal_room_for_size (s + n_more);
656
657 if (0 > ar_setsize ((void **)&oq->_storage, limits, new_r, elt_size))
658 return -1;
659
660 if (h > t)
661 {
662 mem_move (oq->_storage + (new_r - (r - h)) * elt_size,
663 oq->_storage + h * elt_size,
664 (r - h) * elt_size);
665 oq->_head = (new_r - (r - h));
666 }
667
668 return 0;
669 }
670
671
672 static void
uninit_elements(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t from,ssize_t to)673 uninit_elements (t_obqueue * oq,
674 alloc_limits limits,
675 ssize_t elt_size,
676 t_obqueue_type * type,
677 void * closure,
678 ssize_t from,
679 ssize_t to)
680 {
681 if (type && type->uninit)
682 {
683 ssize_t pos;
684 ssize_t todo;
685
686 pos = from;
687 todo = (to - from);
688 while (todo)
689 {
690 void * burst;
691 ssize_t burst_amt;
692
693 burst = obqueue_burst (&burst_amt, oq, limits, elt_size, type, closure, pos, todo);
694 type->uninit (oq, limits, elt_size, type, closure, burst, burst_amt);
695 pos += burst_amt;
696 todo -= burst_amt;
697 }
698 }
699 }
700
701
702 static int
init_elements(t_obqueue * oq,alloc_limits limits,ssize_t elt_size,t_obqueue_type * type,void * closure,ssize_t from,ssize_t to)703 init_elements (t_obqueue * oq,
704 alloc_limits limits,
705 ssize_t elt_size,
706 t_obqueue_type * type,
707 void * closure,
708 ssize_t from,
709 ssize_t to)
710 {
711 ssize_t pos;
712 ssize_t todo;
713
714 pos = from;
715 todo = (to - from);
716 while (todo)
717 {
718 void * burst;
719 ssize_t burst_amt;
720
721 burst = obqueue_burst (&burst_amt, oq, limits, elt_size, type, closure, pos, todo);
722 if (!type || !type->init)
723 {
724 mem_set0 ((t_uchar *)burst, burst_amt);
725 }
726 else
727 {
728 if (0 > type->init (oq, limits, elt_size, type, closure, burst, burst_amt))
729 {
730 uninit_elements (oq, limits, elt_size, type, closure, from, to - todo);
731 return -1;
732 }
733 }
734 pos += burst_amt;
735 todo -= burst_amt;
736 }
737 return 0;
738 }
739
740
741
742
743
744
745
746 /* tag: Tom Lord Fri Oct 22 16:27:00 2004 (obqueue.c)
747 */
748