1 /*
2 * Copyright 2013 Christoph Bumiller
3 * SPDX-License-Identifier: MIT
4 */
5
6 #include "nine_helpers.h"
7
8 static struct nine_range *
nine_range_pool_more(struct nine_range_pool * pool)9 nine_range_pool_more(struct nine_range_pool *pool)
10 {
11 struct nine_range *r = MALLOC(64 * sizeof(struct nine_range));
12 int i;
13 assert(!pool->free);
14
15 if (pool->num_slabs == pool->num_slabs_max) {
16 unsigned p = pool->num_slabs_max;
17 unsigned n = pool->num_slabs_max * 2;
18 if (!n)
19 n = 4;
20 pool->slabs = REALLOC(pool->slabs,
21 p * sizeof(struct nine_range *),
22 n * sizeof(struct nine_range *));
23 pool->num_slabs_max = n;
24 }
25 pool->free = pool->slabs[pool->num_slabs++] = r;
26
27 for (i = 0; i < 63; ++i, r = r->next)
28 r->next = (struct nine_range *)
29 ((uint8_t *)r + sizeof(struct nine_range));
30 r->next = NULL;
31
32 return pool->free;
33 }
34
35 static inline struct nine_range *
nine_range_pool_get(struct nine_range_pool * pool,int16_t bgn,int16_t end)36 nine_range_pool_get(struct nine_range_pool *pool, int16_t bgn, int16_t end)
37 {
38 struct nine_range *r = pool->free;
39 if (!r)
40 r = nine_range_pool_more(pool);
41 assert(r);
42 pool->free = r->next;
43 r->bgn = bgn;
44 r->end = end;
45 return r;
46 }
47
48 static inline void
nine_ranges_coalesce(struct nine_range * r,struct nine_range_pool * pool)49 nine_ranges_coalesce(struct nine_range *r, struct nine_range_pool *pool)
50 {
51 struct nine_range *n;
52
53 while (r->next && r->end >= r->next->bgn) {
54 n = r->next->next;
55 r->end = (r->end >= r->next->end) ? r->end : r->next->end;
56 nine_range_pool_put(pool, r->next);
57 r->next = n;
58 }
59 }
60
61 void
nine_ranges_insert(struct nine_range ** head,int16_t bgn,int16_t end,struct nine_range_pool * pool)62 nine_ranges_insert(struct nine_range **head, int16_t bgn, int16_t end,
63 struct nine_range_pool *pool)
64 {
65 struct nine_range *r, **pn = head;
66
67 for (r = *head; r && bgn > r->end; pn = &r->next, r = r->next);
68
69 if (!r || end < r->bgn) {
70 *pn = nine_range_pool_get(pool, bgn, end);
71 (*pn)->next = r;
72 } else
73 if (bgn < r->bgn) {
74 r->bgn = bgn;
75 if (end > r->end)
76 r->end = end;
77 nine_ranges_coalesce(r, pool);
78 } else
79 if (end > r->end) {
80 r->end = end;
81 nine_ranges_coalesce(r, pool);
82 }
83 }
84