1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Base bitset stuff. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 2002, 2003, 2004, 2006 Free Software Foundation, Inc. 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectThis program is free software; you can redistribute it and/or modify 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectit under the terms of the GNU General Public License as published by 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectthe Free Software Foundation; either version 2 of the License, or 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project(at your option) any later version. 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectThis program is distributed in the hope that it will be useful, 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbut WITHOUT ANY WARRANTY; without even the implied warranty of 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectGNU General Public License for more details. 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectYou should have received a copy of the GNU General Public License 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectalong with this program; if not, write to the Free Software 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectFoundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef _BBITSET_H 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define _BBITSET_H 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "libiberty.h" 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdbool.h> 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <limits.h> 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stddef.h> 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Currently we support five flavours of bitsets: 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets). 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Memory for bit array and bitset structure allocated 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project contiguously. 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_LIST: Linked list of arrays of bits (variable size, least storage 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for large very sparse sets). 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_TABLE: Expandable table of pointers to arrays of bits 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (variable size, less storage for large sparse sets). 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Faster than BITSET_LIST for random access. 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_VARRAY: Variable array of bits (variable size, fast for 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dense bitsets). 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_STATS: Wrapper bitset for internal use only. Used for gathering 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project statistics and/or better run-time checking. 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project*/ 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectenum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VARRAY, 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_TYPE_NUM, BITSET_STATS}; 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"} 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern const char * const bitset_type_names[]; 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectenum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC}; 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Data type used to store a word of bits. */ 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef unsigned long int bitset_word; 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_WORD_BITS ((unsigned int) (CHAR_BIT * sizeof (bitset_word))) 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Bit index. In theory we might need a type wider than size_t, but 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project in practice we lose at most a factor of CHAR_BIT by going with 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t, and that is good enough. If this type is changed to be 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project wider than size_t, the code needs to be modified to check for 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project overflow when converting bit counts to byte or word counts. 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The bit and word index types must be unsigned. */ 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef size_t bitset_bindex; 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Word index. */ 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef size_t bitset_windex; 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Maximum values for commonly-used unsigned types. BITSET_SIZE_MAX 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project always equals SIZE_MAX, but some older systems lack SIZE_MAX. */ 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_BINDEX_MAX ((bitset_bindex) -1) 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Limit max word index to the maximum value of a signed integer 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project to simplify cache disabling. */ 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1) 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_SIZE_MAX ((size_t) -1) 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1)) 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_LIST_SIZE 1024 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectenum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_OP_COPY, BITSET_OP_NOT, 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P, 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P, 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN, 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR}; 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct bbitset_struct 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project const struct bitset_vtable *vtable; 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex cindex; /* Cache word index. */ 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex csize; /* Cache size in words. */ 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *cdata; /* Cache data pointer. */ 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex n_bits; /* Number of bits. */ 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Perhaps we could sacrifice another word to indicate 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project that the bitset is known to be zero, that a bit has been set 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project in the cache, and that a bit has been cleared in the cache. 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This would speed up some of the searches but slightly slow down 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bit set/reset operations of cached bits. */ 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project}; 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef union bitset_union *bitset; 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Private accessor macros to bitset structure. */ 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_VTABLE_(SRC) (SRC)->b.vtable 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CINDEX_(SRC) (SRC)->b.cindex 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CDATA_(SRC) (SRC)->b.cdata 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CSIZE_(SRC) (SRC)->b.csize 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_NBITS_(SRC) (SRC)->b.n_bits 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* The contents of this structure should be considered private. */ 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct bitset_vtable 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*set) (bitset, bitset_bindex); 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*reset) (bitset, bitset_bindex); 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*toggle) (bitset, bitset_bindex); 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*test) (bitset, bitset_bindex); 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex (*resize) (bitset, bitset_bindex); 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex (*size) (bitset); 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex (*count) (bitset); 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*empty_p) (bitset); 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*ones) (bitset); 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*zero) (bitset); 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*copy) (bitset, bitset); 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*disjoint_p) (bitset, bitset); 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*equal_p) (bitset, bitset); 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*not_) (bitset, bitset); 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*subset_p) (bitset, bitset); 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*and_) (bitset, bitset, bitset); 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*and_cmp) (bitset, bitset, bitset); 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*andn) (bitset, bitset, bitset); 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*andn_cmp) (bitset, bitset, bitset); 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*or_) (bitset, bitset, bitset); 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*or_cmp) (bitset, bitset, bitset); 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*xor_) (bitset, bitset, bitset); 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*xor_cmp) (bitset, bitset, bitset); 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*and_or) (bitset, bitset, bitset, bitset); 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*and_or_cmp) (bitset, bitset, bitset, bitset); 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*andn_or) (bitset, bitset, bitset, bitset); 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*andn_or_cmp) (bitset, bitset, bitset, bitset); 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*or_and) (bitset, bitset, bitset, bitset); 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool (*or_and_cmp) (bitset, bitset, bitset, bitset); 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex, 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex *); 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex, 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex *); 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void (*free) (bitset); 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project enum bitset_type type; 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project}; 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_COMPATIBLE_(BSET1, BSET2) \ 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project((BSET1)->b.vtable == (BSET2)->b.vtable) 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CHECK2_(DST, SRC) \ 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectif (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CHECK3_(DST, SRC1, SRC2) \ 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectif (!BITSET_COMPATIBLE_ (DST, SRC1) \ 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectif (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \ 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project || !BITSET_COMPATIBLE_ (DST, SRC3)) abort (); 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Redefine number of bits in bitset DST. */ 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE) 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return size in bits of bitset SRC. */ 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC) 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return number of bits set in bitset SRC. */ 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC) 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return type of bitset SRC. */ 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_TYPE_(DST) (DST)->b.vtable->type 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set bit BITNO in bitset DST. */ 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO) 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Reset bit BITNO in bitset DST. */ 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO) 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Toggle bit BITNO in bitset DST. */ 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO) 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return non-zero if bit BITNO in bitset SRC is set. */ 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO) 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Free bitset SRC. */ 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_FREE_(SRC)\ 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0) 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return SRC == 0. */ 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC) 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = ~0. */ 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST) 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = 0. */ 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST) 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = SRC. */ 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC) 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return DST & SRC == 0. */ 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC) 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return DST == SRC. */ 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC) 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = ~SRC. */ 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC) 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return DST == DST | SRC. */ 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC) 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = SRC1 & SRC2. */ 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2) 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2) 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = SRC1 & ~SRC2. */ 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2) 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2) 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = SRC1 | SRC2. */ 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2) 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2) 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = SRC1 ^ SRC2. */ 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2) 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2) 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DST != (SRC1 & SRC2) | SRC3. */ 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \ 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3) 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \ 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3) 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DST != (SRC1 & ~SRC2) | SRC3. */ 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \ 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3) 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \ 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3) 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DST != (SRC1 | SRC2) & SRC3. */ 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \ 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3) 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \ 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3) 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET starting from and including 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT. Return with actual number of bits found and with *NEXT 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project indicating where search stopped. */ 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_LIST_(BSET, LIST, NUM, NEXT) \ 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT) 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find reverse list of up to NUM bits set in BSET starting from and 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project including NEXT. Return with actual number of bits found and with 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT indicating where search stopped. */ 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \ 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT) 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Private functions for bitset implementations. */ 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bool bitset_toggle_ (bitset, bitset_bindex); 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bitset_bindex bitset_count_ (bitset); 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bitset_bindex bitset_size_ (bitset); 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bool bitset_copy_ (bitset, bitset); 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern void bitset_and_or_ (bitset, bitset, bitset, bitset); 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset); 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern void bitset_andn_or_ (bitset, bitset, bitset, bitset); 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset); 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern void bitset_or_and_ (bitset, bitset, bitset, bitset); 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset); 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif /* _BBITSET_H */ 303