--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <errno.h>
+#include <string.h>
+#include <stdint.h>
+
+#include <check.h>
+
+#include "u16id.h"
+
+/*********************************************************************/
+
+#define S 29
+
+void cbi2p(void*closure, uint16_t id, void *ptr)
+{
+ int *y = closure;
+ int ni = y[0];
+ ck_assert((ni >> id) & 1);
+ ck_assert((uintptr_t)ptr == (uintptr_t)(ni + id));
+ y[1]++;
+}
+
+void test_i2ptr(struct u16id2ptr **pi2p)
+{
+ int i, ni, n, x, y[2];
+ uint16_t j;
+ void *p;
+
+ i = 0;
+ while (!(i >> S)) {
+ ni = i * 3 + 1;
+ n = 0;
+ for (j = 0 ; j < S ; j++) {
+ if ((i >> j) & 1) {
+ ck_assert_int_eq(1, u16id2ptr_has(*pi2p, j));
+ ck_assert_int_eq(0, u16id2ptr_get(*pi2p, j, &p));
+ ck_assert((uintptr_t)p == (uintptr_t)(i + j));
+ ck_assert_int_eq(-1, u16id2ptr_add(pi2p, j, p));
+ ck_assert_int_eq(0, u16id2ptr_put(*pi2p, j, p));
+ } else {
+ ck_assert_int_eq(0, u16id2ptr_has(*pi2p, j));
+ ck_assert_int_eq(-1, u16id2ptr_get(*pi2p, j, &p));
+ ck_assert_int_eq(-1, u16id2ptr_put(*pi2p, j, p));
+ }
+ if ((ni >> j) & 1) {
+ p = (void*)(uintptr_t)(ni + j);
+ ck_assert_int_eq(0, u16id2ptr_set(pi2p, j, p));
+ n++;
+ } else if ((i >> j) & 1) {
+ ck_assert_int_eq(0, u16id2ptr_drop(pi2p, j, &p));
+ ck_assert((uintptr_t)p == (uintptr_t)(i + j));
+ } else {
+ ck_assert_int_eq(-1, u16id2ptr_drop(pi2p, j, NULL));
+ }
+ }
+ ck_assert_int_eq(n, u16id2ptr_count(*pi2p));
+ for (x = 0 ; x < n ; x++) {
+ ck_assert_int_eq(0, u16id2ptr_at(*pi2p, x, &j, &p));
+ ck_assert((ni >> j) & 1);
+ ck_assert((uintptr_t)p == (uintptr_t)(ni + j));
+ }
+ y[0] = ni;
+ y[1] = 0;
+ u16id2ptr_forall(*pi2p, cbi2p, y);
+ ck_assert_int_eq(n, y[1]);
+ i = ni;
+ }
+}
+
+START_TEST (check_u16id2ptr)
+{
+ struct u16id2ptr *i2p;
+
+ i2p = NULL;
+ test_i2ptr(&i2p);
+ ck_assert(i2p);
+ u16id2ptr_destroy(&i2p);
+ ck_assert(!i2p);
+ ck_assert_int_eq(0, u16id2ptr_create(&i2p));
+ test_i2ptr(&i2p);
+ ck_assert(i2p);
+ u16id2ptr_destroy(&i2p);
+ ck_assert(!i2p);
+}
+END_TEST
+
+/*********************************************************************/
+
+void test_i2bool(struct u16id2bool **pi2b)
+{
+ int i, j, ni, v;
+ uint16_t x;
+
+ i = 0;
+ while (!(i >> S)) {
+ ni = i * 3 + 1;
+ for (j = 0 ; j < S ; j++) {
+ x = (uint16_t)(j * 5);
+ v = (i >> j) & 1;
+ ck_assert_int_eq(v, u16id2bool_get(*pi2b, x));
+ ck_assert_int_eq(v, u16id2bool_set(pi2b, x, (ni >> j) & 1));
+ }
+ i = ni;
+ }
+ for (j = 0 ; j < S ; j++) {
+ x = (uint16_t)(j * 5);
+ v = (i >> j) & 1;
+ ck_assert_int_eq(v, u16id2bool_get(*pi2b, x));
+ ck_assert_int_eq(v, u16id2bool_set(pi2b, x, 0));
+ }
+}
+
+START_TEST (check_u16id2bool)
+{
+ struct u16id2bool *i2b;
+
+ i2b = NULL;
+ test_i2bool(&i2b);
+ ck_assert(i2b);
+ u16id2bool_destroy(&i2b);
+ ck_assert(!i2b);
+ ck_assert_int_eq(0, u16id2bool_create(&i2b));
+ test_i2bool(&i2b);
+ ck_assert(i2b);
+ u16id2bool_destroy(&i2b);
+ ck_assert(!i2b);
+}
+END_TEST
+
+/*********************************************************************/
+
+static Suite *suite;
+static TCase *tcase;
+
+void mksuite(const char *name) { suite = suite_create(name); }
+void addtcase(const char *name) { tcase = tcase_create(name); suite_add_tcase(suite, tcase); tcase_set_timeout(tcase, 120); }
+void addtest(TFun fun) { tcase_add_test(tcase, fun); }
+int srun()
+{
+ int nerr;
+ SRunner *srunner = srunner_create(suite);
+ srunner_run_all(srunner, CK_NORMAL);
+ nerr = srunner_ntests_failed(srunner);
+ srunner_free(srunner);
+ return nerr;
+}
+
+int main(int ac, char **av)
+{
+ mksuite("u16id");
+ addtcase("u16id");
+ addtest(check_u16id2ptr);
+ addtest(check_u16id2bool);
+ return !!srun();
+}
--- /dev/null
+/*
+ * Copyright (C) 2015-2019 "IoT.bzh"
+ * Author José Bollo <jose.bollo@iot.bzh>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdint.h>
+#include <malloc.h>
+#include <errno.h>
+
+#include "u16id.h"
+
+/* compute P, the count of bits of pointers */
+#if UINTPTR_MAX == (18446744073709551615UL)
+# define P 64
+#elif UINTPTR_MAX == (4294967295U)
+# define P 32
+#elif UINTPTR_MAX == (65535U)
+# define P 16
+#else
+# error "Unsupported pointer size"
+#endif
+
+/* granule of allocation */
+#define N 4
+
+/*
+ * The u16id maps are made of a single block of memory structured
+ * as an array of uint16_t followed by an array of void*. To ensure
+ * that void* pointers are correctly aligned, the array of uint16_t
+ * at head is a multiple of N items, with N being a multiple of 2
+ * if void* is 32 bits or 4 if void* is 64 bits.
+ *
+ * The first item of the array of uint16_t is used to record the
+ * upper index of valid uint16_t ids.
+ *
+ * +-----+-----+-----+-----+ - - - - - - - - +-----+-----+-----+-----+ - - - - - - - -
+ * |upper| id1 | id2 | id3 | | ptr1 |
+ * +-----+-----+-----+-----+ - - - - - - - - +-----+-----+-----+-----+ - - - - - - - -
+ */
+
+static inline uint16_t get_capacity(uint16_t upper)
+{
+ /* capacity is the smallest kN-1 such that kN-1 >= upper) */
+#if N == 2 || N == 4 || N == 8 || N == 16
+ return upper | (N - 1);
+#else
+# error "not supported"
+#endif
+}
+
+typedef struct {
+ uint16_t upper;
+ uint16_t capacity;
+ uint16_t *ids;
+ void **ptrs;
+} flat_t;
+
+static void flatofup(flat_t *flat, void *base, uint16_t up)
+{
+ uint16_t cap, *ids;
+
+ flat->upper = up;
+ flat->capacity = cap = get_capacity(up);
+ flat->ids = ids = base;
+ flat->ptrs = ((void**)(&ids[cap + 1])) - 1;
+}
+
+static void flatof(flat_t *flat, void *base)
+{
+ if (base)
+ flatofup(flat, base, *(uint16_t*)base);
+ else {
+ flat->upper = flat->capacity = 0;
+ flat->ids = NULL;
+ flat->ptrs = NULL;
+ }
+}
+
+static inline size_t size(uint16_t capacity)
+{
+ return sizeof(uint16_t) * (capacity + 1)
+ + sizeof(void*) * capacity;
+}
+
+static inline uint16_t search(flat_t *flat, uint16_t id)
+{
+ uint16_t *ids = flat->ids;
+ uint16_t r = flat->upper;
+ while(r && ids[r] != id)
+ r--;
+ return r;
+}
+
+static void *add(flat_t *flat, uint16_t id, void *ptr)
+{
+ void *grown, *result;
+ flat_t oflat;
+ uint16_t nupper, oupper;
+
+ oupper = flat->upper;
+ nupper = (uint16_t)(oupper + 1);
+ result = flat->ids;
+ if (nupper > flat->capacity) {
+ grown = realloc(result, size(get_capacity(nupper)));
+ if (grown == NULL)
+ return NULL;
+ result = grown;
+ flatofup(flat, grown, nupper);
+ if (oupper) {
+ flatofup(&oflat, grown, oupper);
+ while (oupper) {
+ flat->ptrs[oupper] = oflat.ptrs[oupper];
+ oupper--;
+ }
+ }
+ }
+ /* flat->upper = nupper; NOT DONE BECAUSE NOT NEEDED */
+ flat->ids[0] = nupper;
+ flat->ids[nupper] = id;
+ flat->ptrs[nupper] = ptr;
+ return result;
+}
+
+static void *drop(flat_t *flat, uint16_t index)
+{
+ void **ptrs, *result;
+ uint16_t upper, idx, capa;
+
+ upper = flat->upper;
+ if (index != upper) {
+ flat->ids[index] = flat->ids[upper];
+ flat->ptrs[index] = flat->ptrs[upper];
+ }
+ flat->ids[0] = --upper;
+ capa = get_capacity(upper);
+ result = flat->ids;
+ if (capa != flat->capacity) {
+ ptrs = flat->ptrs;
+ flatofup(flat, result, upper);
+ idx = 1;
+ while(idx <= upper) {
+ flat->ptrs[idx] = ptrs[idx];
+ idx++;
+ }
+#if U16ID_ALWAYS_SHRINK
+ result = realloc(flat->ids, size(capa));
+ if (result == NULL)
+ result = flat->ids;
+#endif
+ }
+ return result;
+}
+
+static void dropall(void **pbase)
+{
+ void *base;
+
+ base = *pbase;
+ if (base)
+ *(uint16_t*)base = 0;
+}
+
+static void destroy(void **pbase)
+{
+ void *base;
+
+ base = *pbase;
+ *pbase = NULL;
+ free(base);
+}
+
+static int create(void **pbase)
+{
+ void *base;
+
+ *pbase = base = malloc(size(get_capacity(0)));
+ if (base == NULL)
+ return -1;
+ *(uint16_t*)base = 0;
+ return 0;
+}
+
+/**********************************************************************/
+/** u16id2ptr **/
+/**********************************************************************/
+
+int u16id2ptr_create(struct u16id2ptr **pi2p)
+{
+ return create((void**)pi2p);
+}
+
+void u16id2ptr_destroy(struct u16id2ptr **pi2p)
+{
+ destroy((void**)pi2p);
+}
+
+void u16id2ptr_dropall(struct u16id2ptr **pi2p)
+{
+ dropall((void**)pi2p);
+}
+
+int u16id2ptr_has(struct u16id2ptr *i2p, uint16_t id)
+{
+ flat_t flat;
+
+ flatof(&flat, i2p);
+ return search(&flat, id) != 0;
+}
+
+int u16id2ptr_add(struct u16id2ptr **pi2p, uint16_t id, void *ptr)
+{
+ struct u16id2ptr *i2p;
+ uint16_t index;
+ flat_t flat;
+
+ i2p = *pi2p;
+ flatof(&flat, i2p);
+ index = search(&flat, id);
+ if (index) {
+ errno = EEXIST;
+ return -1;
+ }
+ i2p = add(&flat, id, ptr);
+ if (!i2p)
+ return -1;
+ *pi2p = i2p;
+ return 0;
+}
+
+int u16id2ptr_set(struct u16id2ptr **pi2p, uint16_t id, void *ptr)
+{
+ struct u16id2ptr *i2p;
+ uint16_t index;
+ flat_t flat;
+
+ i2p = *pi2p;
+ flatof(&flat, i2p);
+ index = search(&flat, id);
+ if (index)
+ flat.ptrs[index] = ptr;
+ else {
+ i2p = add(&flat, id, ptr);
+ if (!i2p)
+ return -1;
+ *pi2p = i2p;
+ }
+ return 0;
+}
+
+int u16id2ptr_put(struct u16id2ptr *i2p, uint16_t id, void *ptr)
+{
+ uint16_t index;
+ flat_t flat;
+
+ flatof(&flat, i2p);
+ index = search(&flat, id);
+ if (index) {
+ flat.ptrs[index] = ptr;
+ return 0;
+ }
+ errno = ENOENT;
+ return -1;
+}
+
+int u16id2ptr_get(struct u16id2ptr *i2p, uint16_t id, void **pptr)
+{
+ uint16_t index;
+ flat_t flat;
+
+ flatof(&flat, i2p);
+ index = search(&flat, id);
+ if (index) {
+ *pptr = flat.ptrs[index];
+ return 0;
+ }
+ errno = ENOENT;
+ return -1;
+}
+
+int u16id2ptr_drop(struct u16id2ptr **pi2p, uint16_t id, void **pptr)
+{
+ struct u16id2ptr *i2p;
+ uint16_t index;
+ flat_t flat;
+
+ i2p = *pi2p;
+ flatof(&flat, i2p);
+ index = search(&flat, id);
+ if (!index) {
+ errno = ENOENT;
+ return -1;
+ }
+ if (pptr)
+ *pptr = flat.ptrs[index];
+ i2p = drop(&flat, index);
+ if (!i2p)
+ return -1;
+ *pi2p = i2p;
+ return 0;
+}
+
+int u16id2ptr_count(struct u16id2ptr *i2p)
+{
+ return i2p ? ((int)*(uint16_t*)i2p) : 0;
+}
+
+int u16id2ptr_at(struct u16id2ptr *i2p, int index, uint16_t *pid, void **pptr)
+{
+ flat_t flat;
+
+ flatof(&flat, i2p);
+ if (index >= 0 && index < (int)flat.upper) {
+ *pid = flat.ids[index + 1];
+ *pptr = flat.ptrs[index + 1];
+ return 0;
+ }
+ errno = EINVAL;
+ return -1;
+}
+
+void u16id2ptr_forall(struct u16id2ptr *i2p, void (*callback)(void*closure, uint16_t id, void *ptr), void *closure)
+{
+ flat_t flat;
+
+ flatof(&flat, i2p);
+ while (flat.upper) {
+ callback(closure, flat.ids[flat.upper], flat.ptrs[flat.upper]);
+ flat.upper--;
+ }
+}
+
+/**********************************************************************/
+/** u16id2bool **/
+/**********************************************************************/
+
+int u16id2bool_create(struct u16id2bool **pi2b)
+{
+ return create((void**)pi2b);
+}
+
+void u16id2bool_destroy(struct u16id2bool **pi2b)
+{
+ destroy((void**)pi2b);
+}
+
+void u16id2bool_clearall(struct u16id2bool **pi2b)
+{
+ dropall((void**)pi2b);
+}
+
+int u16id2bool_get(struct u16id2bool *i2b, uint16_t id)
+{
+ uintptr_t mask, field;
+ uint16_t index, idm;
+ flat_t flat;
+
+ flatof(&flat, i2b);
+ idm = (uint16_t)(id & ~(P - 1));
+ index = search(&flat, idm);
+ if (!index)
+ return 0;
+
+ field = (uintptr_t)flat.ptrs[index];
+ mask = (uintptr_t)((uintptr_t)1 << (id & (P - 1)));
+ return (field & mask) != 0;
+}
+
+int u16id2bool_set(struct u16id2bool **pi2b, uint16_t id, int value)
+{
+ struct u16id2bool *i2b;
+ uintptr_t mask, field, ofield;
+ uint16_t index, idm;
+ flat_t flat;
+
+ i2b = *pi2b;
+ flatof(&flat, i2b);
+ idm = (uint16_t)(id & ~(P - 1));
+ index = search(&flat, idm);
+ ofield = index ? (uintptr_t)flat.ptrs[index] : 0;
+ mask = (uintptr_t)((uintptr_t)1 << (id & (P - 1)));
+ if (value)
+ field = ofield | mask;
+ else
+ field = ofield & ~mask;
+ if (field != ofield) {
+ if (field) {
+ if (index)
+ flat.ptrs[index] = (void*)field;
+ else {
+ i2b = add(&flat, idm, (void*)field);
+ if (!i2b)
+ return -1;
+ *pi2b = i2b;
+ }
+ } else {
+ if (index) {
+ i2b = drop(&flat, index);
+ if (!i2b)
+ return -1;
+ *pi2b = i2b;
+ }
+ }
+ }
+ return (ofield & mask) != 0;
+}
--- /dev/null
+/*
+ * Copyright (C) 2015-2019 "IoT.bzh"
+ * Author José Bollo <jose.bollo@iot.bzh>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+struct u16id2ptr;
+struct u16id2bool;
+
+/**********************************************************************/
+/** u16id2ptr **/
+/**********************************************************************/
+
+extern int u16id2ptr_create(struct u16id2ptr **pi2p);
+extern void u16id2ptr_destroy(struct u16id2ptr **pi2p);
+extern void u16id2ptr_dropall(struct u16id2ptr **pi2p);
+extern int u16id2ptr_has(struct u16id2ptr *i2p, uint16_t id);
+extern int u16id2ptr_add(struct u16id2ptr **pi2p, uint16_t id, void *ptr);
+extern int u16id2ptr_set(struct u16id2ptr **pi2p, uint16_t id, void *ptr);
+extern int u16id2ptr_put(struct u16id2ptr *i2p, uint16_t id, void *ptr);
+extern int u16id2ptr_get(struct u16id2ptr *i2p, uint16_t id, void **ptr);
+extern int u16id2ptr_drop(struct u16id2ptr **pi2p, uint16_t id, void **ptr);
+extern int u16id2ptr_count(struct u16id2ptr *i2p);
+extern int u16id2ptr_at(struct u16id2ptr *i2p, int index, uint16_t *pid, void **pptr);
+extern void u16id2ptr_forall(
+ struct u16id2ptr *i2p,
+ void (*callback)(void*closure, uint16_t id, void *ptr),
+ void *closure);
+
+/**********************************************************************/
+/** u16id2bool **/
+/**********************************************************************/
+
+extern int u16id2bool_create(struct u16id2bool **pi2b);
+extern void u16id2bool_destroy(struct u16id2bool **pi2b);
+extern void u16id2bool_clearall(struct u16id2bool **pi2b);
+extern int u16id2bool_get(struct u16id2bool *i2b, uint16_t id);
+extern int u16id2bool_set(struct u16id2bool **pi2b, uint16_t id, int value);
Code Review / src / app-framework-binder.git / commitdiff