1 #include <asm/errno.h>
2 #include <linux/ctype.h>
3 #include <linux/kernel.h>
4
5 #define DECLARE_HEAP(type, name) \
6 struct { \
7 size_t size, heap_size; \
8 type *data; \
9 } name
10
11 #define DEFINE_HEAP(type, name, s) \
12 struct { \
13 size_t size; \
14 const size_t heap_size; \
15 type data[s]; \
16 } name = { .size = 0, .heap_size = s }
17
18 #define heap_for_each(c, heap) \
19 for (size_t _i = 0; c = (heap)->data[_i], _i < (heap)->size; _i++)
20
21 #define init_heap(h, s, gfp) \
22 ({ \
23 (h)->size = 0; \
24 (h)->heap_size = s; \
25 if ((h)->heap_size * sizeof(*(h)->data) >= KMALLOC_MAX_SIZE) \
26 (h)->data = vmalloc(s * sizeof(*(h)->data)); \
27 else if (s > 0) \
28 (h)->data = kmalloc(s * sizeof(*(h)->data), gfp); \
29 (h)->data; \
30 })
31
32 #define free_heap(h) \
33 do { \
34 if ((h)->heap_size * sizeof(*(h)->data) >= KMALLOC_MAX_SIZE) \
35 vfree((h)->data); \
36 else \
37 kfree((h)->data); \
38 } while (0)
39
40 #define heap_swap(h, i, j, member) \
41 do { \
42 swap((h)->data[i], (h)->data[j]); \
43 (h)->data[i]->member = i; \
44 (h)->data[j]->member = j; \
45 } while (0)
46
47 #define heap_sift(h, i, cmp, member) \
48 do { \
49 long _r, _i = i; \
50 \
51 for (; _i * 2 + 1 < (h)->size; _i = _r) { \
52 _r = _i * 2 + 1; \
53 if (_r + 1 < (h)->size && \
54 cmp((h)->data[_r], (h)->data[_r + 1])) \
55 _r++; \
56 \
57 if (cmp((h)->data[_r], (h)->data[_i])) \
58 break; \
59 heap_swap(h, _r, _i, member); \
60 } \
61 } while (0)
62
63 #define heap_add(h, d, member, cmp) \
64 do { \
65 long _p, _i = (d)->member; \
66 \
67 if (_i == -1) { \
68 _i = (h)->size++; \
69 (h)->data[_i] = d; \
70 (d)->member = _i; \
71 } \
72 \
73 while (_i) { \
74 _p = (_i - 1) / 2; \
75 if (cmp((h)->data[_i], (h)->data[_p])) \
76 break; \
77 heap_swap(h, _i, _p, member); \
78 _i = _p; \
79 } \
80 \
81 heap_sift(h, _i, cmp, member); \
82 } while (0)
83
84 #define heap_pop(h, member, cmp) \
85 ({ \
86 typeof ((h)->data[0]) _r = (h)->data[0]; \
87 \
88 if ((h)->size) { \
89 (h)->size--; \
90 heap_swap(h, 0, (h)->size, member); \
91 heap_sift(h, 0, cmp, member); \
92 (h)->data[(h)->size] = NULL; \
93 _r->member = -1; \
94 } else \
95 _r = NULL; \
96 _r; \
97 })
98
99 #define heap_peek(h) ((h)->size ? (h)->data[0] : NULL)
100
101 #define DECLARE_FIFO(type, name) \
102 struct { \
103 size_t front, back, size; \
104 type *data; \
105 } name;
106
107 #define fifo_for_each(c, fifo) \
108 for (size_t _i = (fifo)->front; \
109 c = (fifo)->data[_i], _i != (fifo)->back; \
110 _i = (_i + 1) & (fifo)->size)
111
112 #define init_fifo(f, s, gfp) \
113 ({ \
114 BUG_ON(!s); \
115 (f)->front = (f)->back = 0; \
116 (f)->size = roundup_pow_of_two(s); \
117 (f)->data = ((f)->size * sizeof(*(f)->data) >= KMALLOC_MAX_SIZE)\
118 ? vmalloc((f)->size-- * sizeof(*(f)->data)) \
119 : kmalloc((f)->size-- * sizeof(*(f)->data), gfp); \
120 (f)->data; \
121 })
122
123 #define free_fifo(fifo) \
124 do { \
125 if ((fifo)->size * sizeof(*(fifo)->data) >= KMALLOC_MAX_SIZE) \
126 vfree((fifo)->data); \
127 else \
128 kfree((fifo)->data); \
129 (fifo)->data = NULL; \
130 } while (0)
131
132 #define fifo_used(fifo) (((fifo)->back - (fifo)->front) & (fifo)->size)
133 #define fifo_full(fifo) (fifo_used(fifo) == (fifo)->size)
134 #define fifo_empty(fifo) ((fifo)->front == (fifo)->back)
135
136 #define fifo_push(fifo, i) \
137 ({ \
138 bool _r = false; \
139 if (!fifo_full(fifo)) { \
140 _r = true; \
141 (fifo)->data[(fifo)->back++] = i; \
142 (fifo)->back &= (fifo)->size; \
143 } \
144 _r; \
145 })
146
147 #define fifo_pop(fifo, i) \
148 ({ \
149 bool _r = false; \
150 if (!fifo_empty(fifo)) { \
151 _r = true; \
152 i = (fifo)->data[(fifo)->front++]; \
153 (fifo)->front &= (fifo)->size; \
154 } \
155 _r; \
156 })
157
158 /*
159 * These are subject to the infamous aba problem...
160 */
161
162 #define lockless_list_push(new, list, member) \
163 do { \
164 (new)->member = list; \
165 } while (cmpxchg(&(list), (new)->member, new) != (new)->member) \
166
167 #define lockless_list_pop(list, member) ({ \
168 typeof(list) _r; \
169 do { \
170 _r = list; \
171 } while (_r && cmpxchg(&(list), _r, _r->member) != _r); \
172 _r; })
173
174 #define ANYSINT_MAX(t) \
175 ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1)
176
177 int strtol_h(const char *, long *);
178 int strtoll_h(const char *, long long *);
179 int strtoul_h(const char *, unsigned long *);
180 int strtoull_h(const char *, unsigned long long *);
181
182 #define strtoi_h(cp, res) \
183 (__builtin_types_compatible_p(typeof(*res), long) \
184 ? strtol_h(cp, (void *) res) \
185 : __builtin_types_compatible_p(typeof(*res), long long) \
186 ? strtoll_h(cp, (void *) res) \
187 : __builtin_types_compatible_p(typeof(*res), unsigned long) \
188 ? strtoul_h(cp, (void *) res) \
189 : __builtin_types_compatible_p(typeof(*res), unsigned long long)\
190 ? strtoull_h(cp, (void *) res) : -EINVAL)
191