bitmap_element Struct Reference

#include <bitmap.h>

Collaboration diagram for bitmap_element:

Data Fields
struct bitmap_element *	next
struct bitmap_element *	prev
unsigned int	indx
BITMAP_WORD	bits [BITMAP_ELEMENT_WORDS]

Detailed Description

Bitmap set element.  We use a linked list to hold only the bits that
are set.  This allows for use to grow the bitset dynamically without
having to realloc and copy a giant bit array.

The free list is implemented as a list of lists.  There is one
outer list connected together by prev fields.  Each element of that
outer is an inner list (that may consist only of the outer list
element) that are connected by the next fields.  The prev pointer
is undefined for interior elements.  This allows
bitmap_elt_clear_from to be implemented in unit time rather than
linear in the number of elements to be freed.   

Field Documentation

bits

BITMAP_WORD bitmap_element::bits[BITMAP_ELEMENT_WORDS]

Referenced by bitmap_bit_p(), bitmap_clear_bit(), bitmap_clear_range(), bitmap_compl_and_into(), bitmap_count_bits(), bitmap_element_allocate(), bitmap_element_zerop(), bitmap_elt_copy(), bitmap_first_set_bit_worker(), bitmap_get_aligned_chunk(), bitmap_hash(), bitmap_last_set_bit(), bitmap_set_aligned_chunk(), bitmap_set_bit(), bitmap_set_range(), bitmap_single_bit_set_p(), bitmap_xor(), bitmap_xor_into(), bmp_iter_and(), bmp_iter_and_compl(), bmp_iter_and_compl_init(), bmp_iter_and_init(), bmp_iter_set(), bmp_iter_set_init(), and debug_bitmap_elt_file().

indx

unsigned int bitmap_element::indx

Referenced by bitmap_clear(), bitmap_clear_range(), bitmap_elem_to_freelist(), bitmap_elt_clear_from(), bitmap_elt_copy(), bitmap_first_set_bit_worker(), bitmap_hash(), bitmap_last_set_bit(), bitmap_list_find_element(), bitmap_list_link_element(), bitmap_set_aligned_chunk(), bitmap_set_bit(), bitmap_set_range(), bitmap_tree_find_element(), bitmap_tree_link_element(), bitmap_tree_listify_from(), bitmap_tree_splay(), bitmap_tree_unlink_element(), bitmap_xor(), bmp_iter_and(), bmp_iter_and_compl(), bmp_iter_and_compl_init(), bmp_iter_and_init(), bmp_iter_set(), bmp_iter_set_init(), and debug_bitmap_elt_file().

next

struct bitmap_element* bitmap_element::next

Referenced by bitmap_clear_range(), bitmap_count_bits(), bitmap_elem_to_freelist(), bitmap_element_allocate(), bitmap_elt_clear_from(), bitmap_hash(), bitmap_last_set_bit(), bitmap_list_find_element(), bitmap_list_insert_element_after(), bitmap_list_link_element(), bitmap_list_unlink_element(), bitmap_set_range(), bitmap_single_bit_set_p(), bitmap_tree_link_element(), bitmap_tree_link_left(), bitmap_tree_listify_from(), bitmap_tree_rotate_left(), bitmap_tree_rotate_right(), bitmap_tree_splay(), bitmap_tree_to_vec(), bitmap_tree_unlink_element(), bitmap_tree_view(), bmp_iter_and(), bmp_iter_and_compl(), bmp_iter_and_compl_init(), bmp_iter_and_init(), bmp_iter_set(), bmp_iter_set_init(), debug_bitmap_elt_file(), and debug_bitmap_file().

prev

struct bitmap_element* bitmap_element::prev

Referenced by bitmap_clear(), bitmap_elem_to_freelist(), bitmap_element_allocate(), bitmap_elt_clear_from(), bitmap_first_set_bit_worker(), bitmap_list_find_element(), bitmap_list_insert_element_after(), bitmap_list_link_element(), bitmap_list_unlink_element(), bitmap_list_view(), bitmap_set_range(), bitmap_single_bit_set_p(), bitmap_tree_link_element(), bitmap_tree_link_right(), bitmap_tree_listify_from(), bitmap_tree_rotate_left(), bitmap_tree_rotate_right(), bitmap_tree_splay(), bitmap_tree_to_vec(), bitmap_tree_unlink_element(), bitmap_tree_view(), and debug_bitmap_elt_file().

---

The documentation for this struct was generated from the following file:

• bitmap.h