2 * Copyright (C) 2015-2020 "IoT.bzh"
3 * Author José Bollo <jose.bollo@iot.bzh>
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
24 /* compute P, the count of bits of pointers */
25 #if UINTPTR_MAX == (18446744073709551615UL)
27 #elif UINTPTR_MAX == (4294967295U)
29 #elif UINTPTR_MAX == (65535U)
32 # error "Unsupported pointer size"
35 /* granule of allocation */
39 * The u16id maps are made of a single block of memory structured
40 * as an array of uint16_t followed by an array of void*. To ensure
41 * that void* pointers are correctly aligned, the array of uint16_t
42 * at head is a multiple of N items, with N being a multiple of 2
43 * if void* is 32 bits or 4 if void* is 64 bits.
45 * The first item of the array of uint16_t is used to record the
46 * upper index of valid uint16_t ids.
48 * +-----+-----+-----+-----+ - - - - - - - - +-----+-----+-----+-----+ - - - - - - - -
49 * |upper| id1 | id2 | id3 | | ptr1 |
50 * +-----+-----+-----+-----+ - - - - - - - - +-----+-----+-----+-----+ - - - - - - - -
53 static inline uint16_t get_capacity(uint16_t upper)
55 /* capacity is the smallest kN-1 such that kN-1 >= upper) */
56 #if N == 2 || N == 4 || N == 8 || N == 16
57 return upper | (N - 1);
59 # error "not supported"
70 static void flatofup(flat_t *flat, void *base, uint16_t up)
75 flat->capacity = cap = get_capacity(up);
76 flat->ids = ids = base;
77 flat->ptrs = ((void**)(&ids[cap + 1])) - 1;
80 static void flatof(flat_t *flat, void *base)
83 flatofup(flat, base, *(uint16_t*)base);
85 flat->upper = flat->capacity = 0;
91 static inline size_t size(uint16_t capacity)
93 return sizeof(uint16_t) * (capacity + 1)
94 + sizeof(void*) * capacity;
97 static inline uint16_t search(flat_t *flat, uint16_t id)
99 uint16_t *ids = flat->ids;
100 uint16_t r = flat->upper;
101 while(r && ids[r] != id)
106 static void *add(flat_t *flat, uint16_t id, void *ptr)
108 void *grown, *result;
110 uint16_t nupper, oupper;
112 oupper = flat->upper;
113 nupper = (uint16_t)(oupper + 1);
115 if (nupper > flat->capacity) {
116 grown = realloc(result, size(get_capacity(nupper)));
120 flatofup(flat, grown, nupper);
122 flatofup(&oflat, grown, oupper);
124 flat->ptrs[oupper] = oflat.ptrs[oupper];
129 /* flat->upper = nupper; NOT DONE BECAUSE NOT NEEDED */
130 flat->ids[0] = nupper;
131 flat->ids[nupper] = id;
132 flat->ptrs[nupper] = ptr;
136 static void *drop(flat_t *flat, uint16_t index)
138 void **ptrs, *result;
139 uint16_t upper, idx, capa;
142 if (index != upper) {
143 flat->ids[index] = flat->ids[upper];
144 flat->ptrs[index] = flat->ptrs[upper];
146 flat->ids[0] = --upper;
147 capa = get_capacity(upper);
149 if (capa != flat->capacity) {
151 flatofup(flat, result, upper);
153 while(idx <= upper) {
154 flat->ptrs[idx] = ptrs[idx];
157 #if U16ID_ALWAYS_SHRINK
158 result = realloc(flat->ids, size(capa));
166 static void dropall(void **pbase)
172 *(uint16_t*)base = 0;
175 static void destroy(void **pbase)
184 static int create(void **pbase)
188 *pbase = base = malloc(size(get_capacity(0)));
191 *(uint16_t*)base = 0;
195 /**********************************************************************/
197 /**********************************************************************/
199 int u16id2ptr_create(struct u16id2ptr **pi2p)
201 return create((void**)pi2p);
204 void u16id2ptr_destroy(struct u16id2ptr **pi2p)
206 destroy((void**)pi2p);
209 void u16id2ptr_dropall(struct u16id2ptr **pi2p)
211 dropall((void**)pi2p);
214 int u16id2ptr_has(struct u16id2ptr *i2p, uint16_t id)
219 return search(&flat, id) != 0;
222 int u16id2ptr_add(struct u16id2ptr **pi2p, uint16_t id, void *ptr)
224 struct u16id2ptr *i2p;
230 index = search(&flat, id);
235 i2p = add(&flat, id, ptr);
242 int u16id2ptr_set(struct u16id2ptr **pi2p, uint16_t id, void *ptr)
244 struct u16id2ptr *i2p;
250 index = search(&flat, id);
252 flat.ptrs[index] = ptr;
254 i2p = add(&flat, id, ptr);
262 int u16id2ptr_put(struct u16id2ptr *i2p, uint16_t id, void *ptr)
268 index = search(&flat, id);
270 flat.ptrs[index] = ptr;
277 int u16id2ptr_get(struct u16id2ptr *i2p, uint16_t id, void **pptr)
283 index = search(&flat, id);
285 *pptr = flat.ptrs[index];
292 int u16id2ptr_drop(struct u16id2ptr **pi2p, uint16_t id, void **pptr)
294 struct u16id2ptr *i2p;
300 index = search(&flat, id);
306 *pptr = flat.ptrs[index];
307 i2p = drop(&flat, index);
314 int u16id2ptr_count(struct u16id2ptr *i2p)
316 return i2p ? ((int)*(uint16_t*)i2p) : 0;
319 int u16id2ptr_at(struct u16id2ptr *i2p, int index, uint16_t *pid, void **pptr)
324 if (index >= 0 && index < (int)flat.upper) {
325 *pid = flat.ids[index + 1];
326 *pptr = flat.ptrs[index + 1];
333 void u16id2ptr_forall(struct u16id2ptr *i2p, void (*callback)(void*closure, uint16_t id, void *ptr), void *closure)
339 callback(closure, flat.ids[flat.upper], flat.ptrs[flat.upper]);
344 /**********************************************************************/
346 /**********************************************************************/
348 int u16id2bool_create(struct u16id2bool **pi2b)
350 return create((void**)pi2b);
353 void u16id2bool_destroy(struct u16id2bool **pi2b)
355 destroy((void**)pi2b);
358 void u16id2bool_clearall(struct u16id2bool **pi2b)
360 dropall((void**)pi2b);
363 int u16id2bool_get(struct u16id2bool *i2b, uint16_t id)
365 uintptr_t mask, field;
370 idm = (uint16_t)(id & ~(P - 1));
371 index = search(&flat, idm);
375 field = (uintptr_t)flat.ptrs[index];
376 mask = (uintptr_t)((uintptr_t)1 << (id & (P - 1)));
377 return (field & mask) != 0;
380 int u16id2bool_set(struct u16id2bool **pi2b, uint16_t id, int value)
382 struct u16id2bool *i2b;
383 uintptr_t mask, field, ofield;
389 idm = (uint16_t)(id & ~(P - 1));
390 index = search(&flat, idm);
391 ofield = index ? (uintptr_t)flat.ptrs[index] : 0;
392 mask = (uintptr_t)((uintptr_t)1 << (id & (P - 1)));
394 field = ofield | mask;
396 field = ofield & ~mask;
397 if (field != ofield) {
400 flat.ptrs[index] = (void*)field;
402 i2b = add(&flat, idm, (void*)field);
409 i2b = drop(&flat, index);
416 return (ofield & mask) != 0;