1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019-2020 Broadcom
11 /* Bitalloc works on uint32_t as its word size */
12 typedef uint32_t bitalloc_word_t;
16 bitalloc_word_t free_count;
17 bitalloc_word_t storage[1];
20 #define BA_L0(s) (((s) + 31) / 32)
21 #define BA_L1(s) ((BA_L0(s) + 31) / 32)
22 #define BA_L2(s) ((BA_L1(s) + 31) / 32)
23 #define BA_L3(s) ((BA_L2(s) + 31) / 32)
24 #define BA_L4(s) ((BA_L3(s) + 31) / 32)
26 #define BITALLOC_SIZEOF(size) \
27 (sizeof(struct bitalloc) * \
28 (((sizeof(struct bitalloc) + \
29 sizeof(struct bitalloc) - 1 + \
30 (sizeof(bitalloc_word_t) * \
31 ((BA_L0(size) - 1) + \
32 ((BA_L0(size) == 1) ? 0 : (BA_L1(size) + 1)) + \
33 ((BA_L1(size) == 1) ? 0 : (BA_L2(size) + 1)) + \
34 ((BA_L2(size) == 1) ? 0 : (BA_L3(size) + 1)) + \
35 ((BA_L3(size) == 1) ? 0 : (BA_L4(size) + 1)))))) / \
36 sizeof(struct bitalloc)))
38 #define BITALLOC_MAX_SIZE (32 * 32 * 32 * 32 * 32 * 32)
40 /* The instantiation of a bitalloc looks a bit odd. Since a
41 * bit allocator has variable storage, we need a way to get a
42 * a pointer to a bitalloc structure that points to the correct
43 * amount of storage. We do this by creating an array of
44 * bitalloc where the first element in the array is the
45 * actual bitalloc base structure, and the remaining elements
46 * in the array provide the storage for it. This approach allows
47 * instances to be individual variables or members of larger
50 #define BITALLOC_INST(name, size) \
51 struct bitalloc name[(BITALLOC_SIZEOF(size) / \
52 sizeof(struct bitalloc))]
54 /* Symbolic return codes */
57 #define BA_ENTRY_FREE 0
58 #define BA_ENTRY_IN_USE 1
59 #define BA_NO_ENTRY_FOUND -1
62 * Initializates the bitallocator
64 * Returns 0 on success, -1 on failure. Size is arbitrary up to
67 int ba_init(struct bitalloc *pool, int size);
70 * Returns -1 on failure, or index of allocated entry
72 int ba_alloc(struct bitalloc *pool);
73 int ba_alloc_index(struct bitalloc *pool, int index);
76 * Query a particular index in a pool to check if its in use.
78 * Returns -1 on invalid index, 1 if the index is allocated, 0 if it
81 int ba_inuse(struct bitalloc *pool, int index);
84 * Variant of ba_inuse that frees the index if it is allocated, same
85 * return codes as ba_inuse
87 int ba_inuse_free(struct bitalloc *pool, int index);
90 * Find next index that is in use, start checking at index 'idx'
92 * Returns next index that is in use on success, or
93 * -1 if no in use index is found
95 int ba_find_next_inuse(struct bitalloc *pool, int idx);
98 * Variant of ba_find_next_inuse that also frees the next in use index,
99 * same return codes as ba_find_next_inuse
101 int ba_find_next_inuse_free(struct bitalloc *pool, int idx);
104 * Multiple freeing of the same index has no negative side effects,
105 * but will return -1. returns -1 on failure, 0 on success.
107 int ba_free(struct bitalloc *pool, int index);
110 * Returns the pool's free count
112 int ba_free_count(struct bitalloc *pool);
115 * Returns the pool's in use count
117 int ba_inuse_count(struct bitalloc *pool);
119 #endif /* _BITALLOC_H_ */