bitarray.h File Reference

API for compacted arrays of booleans. More...

#include <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <util/alloc.h>

Include dependency graph for bitarray.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	bitarray_t

Functions
static bitarray_t	bitarray_new (size_t size_bits)
	create an array of the given element length
static bool	bitarray_get (bitarray_t self, size_t index)
	get the value of the given element
static void	bitarray_set (bitarray_t *self, size_t index, bool value)
	set or clear the value of the given element
static void	bitarray_reset (bitarray_t *self)
	free underlying resources and leave a bit array empty

Detailed Description

The straightforward way to construct a dynamic array of booleans is to calloc an array of bool values. However, this wastes a lot of memory. Typically 8 bits per byte, which really adds up for large arrays.

The following implements an alternative that stores 8 array elements per byte. Using this over the bool implementation described above decreases heap pressure and increases locality of reference, at the cost of a few (inexpensive) shifts and masks.

As a bonus, short arrays are stored directly inline, avoiding heap allocation altogether. This is essentially Small String Optimization applied to a boolean array.

The above design is essentially what C++’s std::vector<bool> does.

This is deliberately implemented header-only so even Graphviz components that do not link against cgraph can use it.

Definition in file bitarray.h.

Function Documentation

bitarray_get()

static bool bitarray_get ( bitarray_t  self, size_t  index  )

inlinestatic

Definition at line 64 of file bitarray.h.

References bitarray_t::base, bitarray_t::block, bitarray_t::size_bits, and bitarray_t::u.

Referenced by beautify_leaves(), dfs(), dijkstra_sgd(), extract_adjacency(), findCComp(), processTbl(), and traverse_polygon().

Here is the caller graph for this function:

bitarray_new()

static bitarray_t bitarray_new ( size_t  size_bits )

inlinestatic

Definition at line 46 of file bitarray.h.

References bitarray_t::base, bitarray_t::block, gv_calloc(), bitarray_t::size_bits, and bitarray_t::u.

Referenced by beautify_leaves(), extract_adjacency(), findCComp(), monotonate_trapezoids(), and processTbl().

Here is the call graph for this function:

Here is the caller graph for this function:

bitarray_reset()

static void bitarray_reset ( bitarray_t *  self )

inlinestatic

Definition at line 98 of file bitarray.h.

References bitarray_t::base, bitarray_t::block, free(), NULL, bitarray_t::size_bits, and bitarray_t::u.

Referenced by beautify_leaves(), extract_adjacency(), findCComp(), free_adjacency(), monotonate_trapezoids(), and processTbl().

Here is the call graph for this function:

Here is the caller graph for this function:

bitarray_set()

static void bitarray_set ( bitarray_t *  self, size_t  index, bool  value  )

inlinestatic

Definition at line 79 of file bitarray.h.

References bitarray_t::base, bitarray_t::block, bitarray_t::size_bits, and bitarray_t::u.

Referenced by beautify_leaves(), dfs(), extract_adjacency(), processTbl(), and traverse_polygon().

Here is the caller graph for this function: