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