/* bitset.h - bitset decls * **************************************************************** * Copyright (C) 1998, 2000 Thomas Lord * * See the file "COPYING" for further information about * the copyright and warranty status of this work. */ #include "hackerlab/os/limits.h" #include "hackerlab/mem/alloc-limits.h" #ifndef INCLUDE__BITSETS__BITSET_H #define INCLUDE__BITSETS__BITSET_H /************************************************************************ *(h2 "Bitset Types and Macros") * */ /*(c bit_t :category type) * typedef long bit_t; * * Values of type `bit_t' represent a bit address within * a bitset. The address of the first bit is 0. * * `bit_t' is a signed integer type. Some functions which return a * bit address use the value -1 to indicate `no such bit'. * */ typedef long bit_t; /* A bit address. */ /*end-insert */ /*(c bitset_subset :category type) * typedef unsigned long bitset_subset; * * A fragment of a bitset. A bitset is an array of these. */ typedef unsigned long bitset_subset; /*(c bitset :category type) * typedef bitset_subset * bitset; * * A packed array of bits. */ typedef bitset_subset * bitset; /*c bits_per_subset :category macro) * #define bits_per_subset (8 * sizeof (bitset_subset)) * * The number of bits in one value of type `subset'. The * implementation presumes that `sizeof (bitset_subset)' is a power of two. */ #if ULONG_MAX == 0xffffffffUL #define bits_per_subset (32) #elif ULONG_MAX == ((0xffffffffUL << 32) + 0xffffffffUL) #define bits_per_subset (64) #else #error "odd ULONG_MAX in bitset.h" #endif /*c bitset_subset_mask :category macro) * #define bitset_subset_mask (bits_per_subset - 1) * * A bitmask useful for finding the bit position within a subset * of a bitset element. */ #define bitset_subset_mask (bits_per_subset - 1) /*(c bitset_which_subset :category macro) * #define bitset_which_subset(N) ((N) / bits_per_subset) * * A macro useful for finding the subset index within a bitset of a * particular bitset element. The subset containing bit `N' bit * bitset `B' is: * * B[bitset_which_subset(N)] */ #define bitset_which_subset(N) ((N) / bits_per_subset) /*(c bitset_subset_offset :category macro) * #define bitset_subset_offset(N) \ * (((N) / bits_per_subset) * bits_per_subset) * * A macro useful for finding a subset offset within a bitset of the * subset containing a bitset element. Bit 0 (the low order bit) of * the subset containing bit `N' is the bit whose bit address is * `bitset_subset_offset(N)'. */ #define bitset_subset_offset(N) (((N) / bits_per_subset) * bits_per_subset) /*(c bitset_which_bit :category macro) * #define bitset_which_bit(N) ((N) & bitset_subset_mask) * * The bit number of a bitset index within its subset. */ #define bitset_which_bit(N) ((N) & bitset_subset_mask) /*c bitset_bit_mask :category macro) * #define bitset_bit_mask(N) \ * ((~(bitset_subset)0L) >> (bits_per_subset - bitset_which_bit (N))) * * A bitmask for all bits up to (but not including) element `N' of the * subset containing element `N'. */ #define bitset_bit_mask(N) ((~(bitset_subset)0L) >> (bits_per_subset - bitset_which_bit (N))) /*(c bitset_numb_subsets :category macro) * #define bitset_numb_subsets(N) * * As a function: * * bit_t bitset_numb_subsets (bit_t n); * * Return the number of values of type `subset' necessary to represent * a bitset with `n' elements. Because this is a macro, it can be used * in a declaration: * * { * // declare a bitset that can hold 12 elements: * // * bitset_subset options_set [bitset_numb_subsets(12)]; * } */ #define bitset_numb_subsets(n) (((n) + bits_per_subset - 1) / bits_per_subset) /*(c sizeof_bitset :category macro) * #define sizeof_bitset(N) * * As a function: * * size_t sizeof_bitset (bit_t n); * * Return the size, in bytes, of a bitset large enough to * hold `n' elements: * * // allocate a bitset that can hold 12 elements: * // * options_set = (bitset)must_malloc (sizeof_bitset (12)); */ #define sizeof_bitset(n) (bitset_numb_subsets(n) * sizeof(bitset_subset)) /* automatically generated __STDC__ prototypes */ extern bitset bitset_alloc (alloc_limits limits, bit_t size); extern void bitset_free (alloc_limits limits, bitset a); extern bitset bitset_dup (alloc_limits limits, bit_t size, bitset a); extern bitset bitset_realloc (alloc_limits limits, bit_t new_size, bit_t old_size, bitset a); extern int bitset_is_member (bitset b, bit_t n); extern int bitset_is_equal (bit_t size, bitset a, bitset b); extern int bitset_is_subset (bit_t size, bitset a, bitset b); extern int bitset_is_empty (bit_t size, bitset a); extern int bitset_is_empty_range (bitset a, bit_t from, bit_t to); extern int bitset_is_full (bit_t size, bitset a); extern int bitset_is_full_range (bitset a, bit_t from, bit_t to); extern void bitset_adjoin (bitset b, bit_t n); extern void bitset_remove (bitset b, bit_t n); extern void bitset_toggle (bitset b, bit_t n); extern void bitset_clear (bit_t size, bitset b); extern void bitset_clear_range (bitset b, bit_t from, bit_t to); extern void bitset_fill (bit_t size, bitset b); extern void bitset_fill_range (bitset b, bit_t from, bit_t to); extern void bitset_complement (bit_t size, bitset b); extern void bitset_assign (bit_t size, bitset a, bitset b); extern void bitset_union (bit_t size, bitset a, bitset b); extern void bitset_intersection (bit_t size, bitset a, bitset b); extern void bitset_difference (bit_t size, bitset a, bitset b); extern void bitset_revdifference (bit_t size, bitset a, bitset b); extern void bitset_xor (bit_t size, bitset a, bitset b); extern bit_t bitset_population (bit_t size, bitset a); extern bit_t bitset_population_range (bitset a, bit_t from, bit_t to); extern bit_t bitset_ffs (bit_t size, bitset b); extern bit_t bitset_ffs_range (bitset b, bit_t from, bit_t to); extern bit_t bitset_ffc (bit_t size, bitset b); extern bit_t bitset_ffc_range (bitset b, bit_t from, bit_t to); #endif /* INCLUDE__BITSETS__BITSET_H */