1 | /* The MIT License |
2 | |
3 | Copyright (c) 2008-2009, by Attractive Chaos <attractor@live.co.uk> |
4 | |
5 | Permission is hereby granted, free of charge, to any person obtaining |
6 | a copy of this software and associated documentation files (the |
7 | "Software"), to deal in the Software without restriction, including |
8 | without limitation the rights to use, copy, modify, merge, publish, |
9 | distribute, sublicense, and/or sell copies of the Software, and to |
10 | permit persons to whom the Software is furnished to do so, subject to |
11 | the following conditions: |
12 | |
13 | The above copyright notice and this permission notice shall be |
14 | included in all copies or substantial portions of the Software. |
15 | |
16 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
17 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
18 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
19 | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS |
20 | BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN |
21 | ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
22 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
23 | SOFTWARE. |
24 | */ |
25 | |
26 | #ifndef _AC_KLIST_H |
27 | #define _AC_KLIST_H |
28 | |
29 | #include <stdlib.h> |
30 | #include <assert.h> |
31 | |
32 | #include "nvim/memory.h" |
33 | #include "nvim/func_attr.h" |
34 | |
35 | |
36 | #define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f) \ |
37 | typedef struct { \ |
38 | size_t cnt, n, max; \ |
39 | kmptype_t **buf; \ |
40 | } kmp_##name##_t; \ |
41 | static inline kmp_##name##_t *kmp_init_##name(void) { \ |
42 | return xcalloc(1, sizeof(kmp_##name##_t)); \ |
43 | } \ |
44 | static inline void kmp_destroy_##name(kmp_##name##_t *mp) \ |
45 | REAL_FATTR_UNUSED; \ |
46 | static inline void kmp_destroy_##name(kmp_##name##_t *mp) { \ |
47 | size_t k; \ |
48 | for (k = 0; k < mp->n; k++) { \ |
49 | kmpfree_f(mp->buf[k]); XFREE_CLEAR(mp->buf[k]); \ |
50 | } \ |
51 | XFREE_CLEAR(mp->buf); XFREE_CLEAR(mp); \ |
52 | } \ |
53 | static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ |
54 | mp->cnt++; \ |
55 | if (mp->n == 0) { \ |
56 | return xcalloc(1, sizeof(kmptype_t)); \ |
57 | } \ |
58 | return mp->buf[--mp->n]; \ |
59 | } \ |
60 | static inline void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \ |
61 | mp->cnt--; \ |
62 | if (mp->n == mp->max) { \ |
63 | mp->max = mp->max ? (mp->max << 1) : 16; \ |
64 | mp->buf = xrealloc(mp->buf, sizeof(kmptype_t *) * mp->max); \ |
65 | } \ |
66 | mp->buf[mp->n++] = p; \ |
67 | } |
68 | |
69 | #define kmempool_t(name) kmp_##name##_t |
70 | #define kmp_init(name) kmp_init_##name() |
71 | #define kmp_destroy(name, mp) kmp_destroy_##name(mp) |
72 | #define kmp_alloc(name, mp) kmp_alloc_##name(mp) |
73 | #define kmp_free(name, mp, p) kmp_free_##name(mp, p) |
74 | |
75 | #define KLIST_INIT(name, kltype_t, kmpfree_t) \ |
76 | struct __kl1_##name { \ |
77 | kltype_t data; \ |
78 | struct __kl1_##name *next; \ |
79 | }; \ |
80 | typedef struct __kl1_##name kl1_##name; \ |
81 | KMEMPOOL_INIT(name, kl1_##name, kmpfree_t) \ |
82 | typedef struct { \ |
83 | kl1_##name *head, *tail; \ |
84 | kmp_##name##_t *mp; \ |
85 | size_t size; \ |
86 | } kl_##name##_t; \ |
87 | static inline kl_##name##_t *kl_init_##name(void) { \ |
88 | kl_##name##_t *kl = xcalloc(1, sizeof(kl_##name##_t)); \ |
89 | kl->mp = kmp_init(name); \ |
90 | kl->head = kl->tail = kmp_alloc(name, kl->mp); \ |
91 | kl->head->next = 0; \ |
92 | return kl; \ |
93 | } \ |
94 | static inline void kl_destroy_##name(kl_##name##_t *kl) \ |
95 | REAL_FATTR_UNUSED; \ |
96 | static inline void kl_destroy_##name(kl_##name##_t *kl) { \ |
97 | kl1_##name *p; \ |
98 | for (p = kl->head; p != kl->tail; p = p->next) { \ |
99 | kmp_free(name, kl->mp, p); \ |
100 | } \ |
101 | kmp_free(name, kl->mp, p); \ |
102 | kmp_destroy(name, kl->mp); \ |
103 | XFREE_CLEAR(kl); \ |
104 | } \ |
105 | static inline void kl_push_##name(kl_##name##_t *kl, kltype_t d) { \ |
106 | kl1_##name *q, *p = kmp_alloc(name, kl->mp); \ |
107 | q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p; \ |
108 | kl->size++; \ |
109 | q->data = d; \ |
110 | } \ |
111 | static inline kltype_t kl_shift_at_##name(kl_##name##_t *kl, \ |
112 | kl1_##name **n) { \ |
113 | assert((*n)->next); \ |
114 | kl1_##name *p; \ |
115 | kl->size--; \ |
116 | p = *n; \ |
117 | *n = (*n)->next; \ |
118 | if (p == kl->head) { \ |
119 | kl->head = *n; \ |
120 | } \ |
121 | kltype_t d = p->data; \ |
122 | kmp_free(name, kl->mp, p); \ |
123 | return d; \ |
124 | } |
125 | |
126 | #define kliter_t(name) kl1_##name |
127 | #define klist_t(name) kl_##name##_t |
128 | #define kl_val(iter) ((iter)->data) |
129 | #define kl_next(iter) ((iter)->next) |
130 | #define kl_begin(kl) ((kl)->head) |
131 | #define kl_end(kl) ((kl)->tail) |
132 | |
133 | #define kl_init(name) kl_init_##name() |
134 | #define kl_destroy(name, kl) kl_destroy_##name(kl) |
135 | #define kl_push(name, kl, d) kl_push_##name(kl, d) |
136 | #define kl_shift_at(name, kl, node) kl_shift_at_##name(kl, node) |
137 | #define kl_shift(name, kl) kl_shift_at(name, kl, &kl->head) |
138 | #define kl_empty(kl) ((kl)->size == 0) |
139 | // Iteration macros. It's ok to modify the list while iterating as long as a |
140 | // `break` statement is executed before the next iteration. |
141 | #define kl_iter(name, kl, p) kl_iter_at(name, kl, p, NULL) |
142 | #define kl_iter_at(name, kl, p, h) \ |
143 | for (kl1_##name **p = h ? h : &kl->head; *p != kl->tail; p = &(*p)->next) |
144 | |
145 | #endif |
146 | |