#define BLOCKS_PER_UNIT (1U << UNIT_SHIFT)
#define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1)
-#define firstfree_valid(b) ((b)->first_free != (uint64_t) -1)
-
static const unsigned long bit_masks[] = {
0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
#endif
};
+/**
+ * struct axmap_level - a bitmap used to implement struct axmap
+ * @level: Level index. Each map has at least one level with index zero. The
+ * higher the level index, the fewer bits a struct axmap_level contains.
+ * @map_size: Number of elements of the @map array.
+ * @map: A bitmap with @map_size elements.
+ */
struct axmap_level {
int level;
unsigned long map_size;
unsigned long *map;
};
+/**
+ * struct axmap - a set that can store numbers 0 .. @nr_bits - 1
+ * @nr_level: Number of elements of the @levels array.
+ * @levels: struct axmap_level array in which lower levels contain more bits
+ * than higher levels.
+ * @nr_bits: One more than the highest value stored in the set.
+ */
struct axmap {
unsigned int nr_levels;
struct axmap_level *levels;
- uint64_t first_free;
uint64_t nr_bits;
};
-static inline unsigned long ulog64(unsigned long val, unsigned int log)
-{
- while (log-- && val)
- val >>= UNIT_SHIFT;
-
- return val;
-}
-
+/* Remove all elements from the @axmap set */
void axmap_reset(struct axmap *axmap)
{
int i;
memset(al->map, 0, al->map_size * sizeof(unsigned long));
}
-
- axmap->first_free = 0;
}
void axmap_free(struct axmap *axmap)
free(axmap);
}
-struct axmap *axmap_new(unsigned long nr_bits)
+/* Allocate memory for a set that can store the numbers 0 .. @nr_bits - 1. */
+struct axmap *axmap_new(uint64_t nr_bits)
{
struct axmap *axmap;
unsigned int i, levels;
axmap->nr_levels = levels;
axmap->levels = calloc(axmap->nr_levels, sizeof(struct axmap_level));
+ if (!axmap->levels)
+ goto free_axmap;
axmap->nr_bits = nr_bits;
for (i = 0; i < axmap->nr_levels; i++) {
struct axmap_level *al = &axmap->levels[i];
+ nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
+
al->level = i;
- al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
+ al->map_size = nr_bits;
al->map = malloc(al->map_size * sizeof(unsigned long));
if (!al->map)
- goto err;
+ goto free_levels;
- nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
}
axmap_reset(axmap);
return axmap;
-err:
+
+free_levels:
for (i = 0; i < axmap->nr_levels; i++)
- if (axmap->levels[i].map)
- free(axmap->levels[i].map);
+ free(axmap->levels[i].map);
free(axmap->levels);
+
+free_axmap:
free(axmap);
return NULL;
}
+/*
+ * Call @func for each level, starting at level zero, until a level is found
+ * for which @func returns true. Return false if none of the @func calls
+ * returns true.
+ */
static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr,
- bool (*func)(struct axmap_level *, unsigned long, unsigned int,
+ bool (*func)(struct axmap_level *, uint64_t, unsigned int,
void *), void *data)
{
struct axmap_level *al;
return false;
}
+/*
+ * Call @func for each level, starting at the highest level, until a level is
+ * found for which @func returns true. Return false if none of the @func calls
+ * returns true.
+ */
static bool axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
- bool (*func)(struct axmap_level *, unsigned long, unsigned int, void *))
+ bool (*func)(struct axmap_level *, uint64_t, unsigned int, void *))
{
int i;
for (i = axmap->nr_levels - 1; i >= 0; i--) {
- unsigned long index = ulog64(bit_nr, i);
+ uint64_t index = bit_nr >> (UNIT_SHIFT * i);
unsigned long offset = index >> UNIT_SHIFT;
unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
return false;
}
-static bool axmap_clear_fn(struct axmap_level *al, unsigned long offset,
- unsigned int bit, void *unused)
-{
- if (!(al->map[offset] & (1UL << bit)))
- return true;
-
- al->map[offset] &= ~(1UL << bit);
- return false;
-}
-
-void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
-{
- axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
-
- if (bit_nr < axmap->first_free)
- axmap->first_free = bit_nr;
-}
-
struct axmap_set_data {
unsigned int nr_bits;
unsigned int set_bits;
};
-static bool axmap_set_fn(struct axmap_level *al, unsigned long offset,
+/*
+ * Set at most @__data->nr_bits bits in @al at offset @offset. Do not exceed
+ * the boundary of the element at offset @offset. Return the number of bits
+ * that have been set in @__data->set_bits if @al->level == 0.
+ */
+static bool axmap_set_fn(struct axmap_level *al, uint64_t offset,
unsigned int bit, void *__data)
{
struct axmap_set_data *data = __data;
*/
overlap = al->map[offset] & mask;
if (overlap == mask) {
-done:
data->set_bits = 0;
return true;
}
if (overlap) {
- const int __bit = ffz(~overlap);
-
- nr_bits = __bit - bit;
+ nr_bits = ffz(~overlap) - bit;
if (!nr_bits)
- goto done;
-
+ return true;
mask = bit_masks[nr_bits] << bit;
}
if (!al->level)
data->set_bits = nr_bits;
+ /* For the next level */
data->nr_bits = 1;
+
return al->map[offset] != -1UL;
}
+/*
+ * Set up to @data->nr_bits starting from @bit_nr in @axmap. Start at
+ * @bit_nr. If that bit has not yet been set then set it and continue until
+ * either @data->nr_bits have been set or a 1 bit is found. Store the number
+ * of bits that have been set in @data->set_bits. It is guaranteed that all
+ * bits that have been requested to set fit in the same unsigned long word of
+ * level 0 of @axmap.
+ */
static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
struct axmap_set_data *data)
{
- unsigned int set_bits, nr_bits = data->nr_bits;
-
- if (axmap->first_free >= bit_nr &&
- axmap->first_free < bit_nr + data->nr_bits)
- axmap->first_free = -1ULL;
+ unsigned int nr_bits = data->nr_bits;
if (bit_nr > axmap->nr_bits)
return;
else if (bit_nr + nr_bits > axmap->nr_bits)
nr_bits = axmap->nr_bits - bit_nr;
- set_bits = 0;
- while (nr_bits) {
- axmap_handler(axmap, bit_nr, axmap_set_fn, data);
- set_bits += data->set_bits;
-
- if (!data->set_bits ||
- data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
- break;
+ assert(nr_bits <= BLOCKS_PER_UNIT);
- nr_bits -= data->set_bits;
- bit_nr += data->set_bits;
-
- data->nr_bits = nr_bits;
- }
-
- data->set_bits = set_bits;
+ axmap_handler(axmap, bit_nr, axmap_set_fn, data);
}
void axmap_set(struct axmap *axmap, uint64_t bit_nr)
__axmap_set(axmap, bit_nr, &data);
}
+/*
+ * Set up to @nr_bits starting from @bit in @axmap. Start at @bit. If that
+ * bit has not yet been set then set it and continue until either @nr_bits
+ * have been set or a 1 bit is found. Return the number of bits that have been
+ * set.
+ */
unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr,
unsigned int nr_bits)
{
return set_bits;
}
-static bool axmap_isset_fn(struct axmap_level *al, unsigned long offset,
+static bool axmap_isset_fn(struct axmap_level *al, uint64_t offset,
unsigned int bit, void *unused)
{
- return (al->map[offset] & (1UL << bit)) != 0;
+ return (al->map[offset] & (1ULL << bit)) != 0;
}
bool axmap_isset(struct axmap *axmap, uint64_t bit_nr)