1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Array bitsets. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2002-2003, 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 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 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 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (at your option) any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is distributed in the hope that it will be useful, 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 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 2105436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <config.h> 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "abitset.h" 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stddef.h> 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdlib.h> 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <string.h> 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* This file implements fixed size bitsets stored as an array 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of words. Any unused bits in the last word must be zero. */ 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define ABITSET_WORDS(X) ((X)->a.words) 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_resize (bitset src, bitset_bindex size) 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* These bitsets have a fixed size. */ 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (BITSET_SIZE_ (src) != size) 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return size; 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET starting from and including 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT and store in array LIST. Return with actual number of bits 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project found and with *NEXT indicating where search stopped. */ 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_small_list (bitset src, bitset_bindex *list, 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex num, bitset_bindex *next) 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno; 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex count; 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size; 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = ABITSET_WORDS (src)[0]; 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Short circuit common case. */ 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!word) 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size = BITSET_SIZE_ (src); 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = *next; 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bitno >= size) 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= bitno; 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If num is 1, we could speed things up with a binary search 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the word of interest. */ 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (num >= BITSET_WORD_BITS) 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (count = 0; word; bitno++) 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (count = 0; word; bitno++) 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno++; 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project break; 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno; 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set bit BITNO in bitset DST. */ 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED) 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This should never occur for abitsets since we should always hit 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the cache. It is likely someone is trying to access outside the 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bounds of the bitset. */ 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Reset bit BITNO in bitset DST. */ 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_reset (bitset dst ATTRIBUTE_UNUSED, 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno ATTRIBUTE_UNUSED) 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This should never occur for abitsets since we should always hit 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the cache. It is likely someone is trying to access outside the 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bounds of the bitset. Since the bit is zero anyway, let it pass. */ 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Test bit BITNO in bitset SRC. */ 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_test (bitset src ATTRIBUTE_UNUSED, 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno ATTRIBUTE_UNUSED) 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This should never occur for abitsets since we should always 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project hit the cache. */ 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET in reverse order, starting 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project from and including NEXT and store in array LIST. Return with 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project actual number of bits found and with *NEXT indicating where search 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stopped. */ 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_list_reverse (bitset src, bitset_bindex *list, 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex num, bitset_bindex *next) 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno; 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex rbitno; 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex count; 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int bitcnt; 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitoff; 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex n_bits = BITSET_SIZE_ (src); 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rbitno = *next; 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If num is 1, we could speed things up with a binary search 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the word of interest. */ 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rbitno >= n_bits) 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count = 0; 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = n_bits - (rbitno + 1); 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = bitno / BITSET_WORD_BITS; 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitcnt = bitno % BITSET_WORD_BITS; 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitoff = windex * BITSET_WORD_BITS; 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project do 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bitcnt--) 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & BITSET_MSB) 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitoff + bitcnt; 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = n_bits - (bitoff + bitcnt); 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word <<= 1; 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitoff -= BITSET_WORD_BITS; 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitcnt = BITSET_WORD_BITS - 1; 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (windex--); 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = n_bits - (bitoff + 1); 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET starting from and including 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT and store in array LIST. Return with actual number of bits 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project found and with *NEXT indicating where search stopped. */ 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_list (bitset src, bitset_bindex *list, 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex num, bitset_bindex *next) 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno; 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex count; 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitoff; 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = src->b.csize; 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = *next; 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count = 0; 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!bitno) 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Many bitsets are zero, so make this common case fast. */ 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (windex = 0; windex < size && !srcp[windex]; windex++) 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (windex >= size) 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If num is 1, we could speed things up with a binary search 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the current word. */ 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitoff = windex * BITSET_WORD_BITS; 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bitno >= BITSET_SIZE_ (src)) 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = bitno / BITSET_WORD_BITS; 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = bitno % BITSET_WORD_BITS; 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bitno) 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Handle the case where we start within a word. 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Most often, this is executed with large bitsets 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project with many set bits where we filled the array 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project on the previous call to this function. */ 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitoff = windex * BITSET_WORD_BITS; 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[windex] >> bitno; 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bitno = bitoff + bitno; word; bitno++) 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno + 1; 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitoff = windex * BITSET_WORD_BITS; 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word = srcp[windex])) 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((count + BITSET_WORD_BITS) < num) 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bitno = bitoff; word; bitno++) 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bitno = bitoff; word; bitno++) 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno + 1; 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitoff; 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Ensure that any unused bits within the last word are clear. */ 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_unused_clear (bitset dst) 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int last_bit; 306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (last_bit) 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ABITSET_WORDS (dst)[dst->b.csize - 1] &= 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((bitset_word) 1 << last_bit) - 1; 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_ones (bitset dst) 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bytes; 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes = sizeof (bitset_word) * dst->b.csize; 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memset (dstp, -1, bytes); 323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_unused_clear (dst); 324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_zero (bitset dst) 329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bytes; 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes = sizeof (bitset_word) * dst->b.csize; 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memset (dstp, 0, bytes); 336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_empty_p (bitset dst) 341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < dst->b.csize; i++) 346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (dstp[i]) 347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_copy1 (bitset dst, bitset src) 355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (srcp == dstp) 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (dstp, srcp, sizeof (bitset_word) * size); 363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_not (bitset dst, bitset src) 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 371cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 372cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 373cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 374cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 375cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = ~(*srcp++); 376cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_unused_clear (dst); 377cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 378cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 379cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 380cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 381cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_equal_p (bitset dst, bitset src) 382cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 383cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 384cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 385cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 386cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 387cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 388cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 389cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*srcp++ != *dstp++) 390cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 391cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 392cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 393cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 394cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 395cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 396cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_subset_p (bitset dst, bitset src) 397cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 398cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 399cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 400cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 401cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 402cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 403cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++, srcp++) 404cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != (*srcp | *dstp)) 405cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 406cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 407cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 408cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 409cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 410cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 411cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_disjoint_p (bitset dst, bitset src) 412cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 413cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 414cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = ABITSET_WORDS (src); 415cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 416cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 417cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 418cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 419cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*srcp++ & *dstp++) 420cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 421cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 422cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 423cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 424cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 425cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 426cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 427cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_and (bitset dst, bitset src1, bitset src2) 428cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 429cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 430cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 431cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 432cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 433cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 434cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 435cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 436cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = *src1p++ & *src2p++; 437cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 438cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 439cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 440cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 441cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_and_cmp (bitset dst, bitset src1, bitset src2) 442cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 443cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 444cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 445cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 446cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 447cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 448cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 449cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 450cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 451cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 452cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *src1p++ & *src2p++; 453cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 454cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 455cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 456cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 457cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 458cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 459cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 460cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 461cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 462cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 463cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 464cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 465cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_andn (bitset dst, bitset src1, bitset src2) 466cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 467cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 468cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 469cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 470cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 471cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 472cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 473cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 474cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = *src1p++ & ~(*src2p++); 475cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 476cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 477cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 478cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 479cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_andn_cmp (bitset dst, bitset src1, bitset src2) 480cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 481cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 482cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 483cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 484cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 485cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 486cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 487cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 488cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 489cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 490cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *src1p++ & ~(*src2p++); 491cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 492cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 493cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 494cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 495cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 496cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 497cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 498cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 499cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 500cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 501cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 502cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 503cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_or (bitset dst, bitset src1, bitset src2) 504cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 505cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 506cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 507cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 508cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 509cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 510cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 511cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 512cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = *src1p++ | *src2p++; 513cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 514cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 515cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 516cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 517cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_or_cmp (bitset dst, bitset src1, bitset src2) 518cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 519cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 520cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 521cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 522cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 523cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 524cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 525cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 526cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 527cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 528cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *src1p++ | *src2p++; 529cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 530cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 531cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 532cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 533cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 534cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 535cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 536cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 537cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 538cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 539cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 540cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 541cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_xor (bitset dst, bitset src1, bitset src2) 542cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 543cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 544cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 545cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 546cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 547cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 548cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 549cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 550cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = *src1p++ ^ *src2p++; 551cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 552cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 553cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 554cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 555cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_xor_cmp (bitset dst, bitset src1, bitset src2) 556cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 557cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 558cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 559cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 560cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 561cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 562cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 563cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 564cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 565cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 566cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *src1p++ ^ *src2p++; 567cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 568cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 569cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 570cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 571cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 572cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 573cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 574cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 575cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 576cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 577cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 578cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 579cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) 580cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 581cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 582cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 583cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 584cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 585cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 586cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 587cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 588cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 589cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = (*src1p++ & *src2p++) | *src3p++; 590cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 591cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 592cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 593cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 594cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 595cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 596cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 597cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 598cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 599cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 600cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 601cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 602cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 603cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 604cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 605cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 606cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; 607cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 608cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 609cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 610cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 611cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 612cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 613cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 614cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 615cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 616cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 617cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 618cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 619cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) 620cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 621cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 622cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 623cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 624cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 625cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 626cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 627cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 628cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 629cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; 630cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 631cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 632cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 633cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 634cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 635cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 636cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 637cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 638cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 639cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 640cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 641cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 642cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 643cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 644cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 645cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 646cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; 647cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 648cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 649cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 650cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 651cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 652cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 653cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 654cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 655cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 656cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 657cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 658cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 659cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) 660cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 661cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 662cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 663cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 664cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 665cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 666cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 667cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 668cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++) 669cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp++ = (*src1p++ | *src2p++) & *src3p++; 670cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 671cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 672cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 673cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 674cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 675cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 676cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 677cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 678cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src1p = ABITSET_WORDS (src1); 679cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src2p = ABITSET_WORDS (src2); 680cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *src3p = ABITSET_WORDS (src3); 681cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp = ABITSET_WORDS (dst); 682cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size = dst->b.csize; 683cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 684cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < size; i++, dstp++) 685cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 686cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; 687cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 688cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 689cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 690cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 691cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 692cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 693cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 694cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 695cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 696cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 697cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 698cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 699cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_copy (bitset dst, bitset src) 700cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 701cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (BITSET_COMPATIBLE_ (dst, src)) 702cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_copy1 (dst, src); 703cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 704cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_copy_ (dst, src); 705cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 706cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 707cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 708cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Vector of operations for single word bitsets. */ 709cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct bitset_vtable abitset_small_vtable = { 710cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_set, 711cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_reset, 712cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_toggle_, 713cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_test, 714cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_resize, 715cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_size_, 716cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_count_, 717cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_empty_p, 718cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_ones, 719cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_zero, 720cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_copy, 721cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_disjoint_p, 722cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_equal_p, 723cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_not, 724cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_subset_p, 725cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and, 726cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_cmp, 727cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn, 728cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_cmp, 729cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or, 730cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_cmp, 731cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_xor, 732cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_xor_cmp, 733cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_or, 734cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_or_cmp, 735cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_or, 736cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_or_cmp, 737cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_and, 738cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_and_cmp, 739cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_small_list, 740cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_list_reverse, 741cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project NULL, 742cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_ARRAY 743cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project}; 744cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 745cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 746cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Vector of operations for multiple word bitsets. */ 747cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct bitset_vtable abitset_vtable = { 748cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_set, 749cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_reset, 750cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_toggle_, 751cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_test, 752cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_resize, 753cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_size_, 754cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_count_, 755cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_empty_p, 756cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_ones, 757cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_zero, 758cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_copy, 759cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_disjoint_p, 760cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_equal_p, 761cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_not, 762cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_subset_p, 763cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and, 764cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_cmp, 765cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn, 766cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_cmp, 767cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or, 768cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_cmp, 769cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_xor, 770cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_xor_cmp, 771cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_or, 772cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_and_or_cmp, 773cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_or, 774cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_andn_or_cmp, 775cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_and, 776cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_or_and_cmp, 777cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_list, 778cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abitset_list_reverse, 779cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project NULL, 780cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_ARRAY 781cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project}; 782cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 783cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 784cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 785cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_bytes (bitset_bindex n_bits) 786cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 787cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size; 788cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bytes; 789cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t header_size = offsetof (union bitset_union, a.words); 790cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct bitset_align_struct { char a; union bitset_union b; }; 791cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bitset_alignment = offsetof (struct bitset_align_struct, b); 792cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 793cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size = ABITSET_N_WORDS (n_bits); 794cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes = header_size + size * sizeof (bitset_word); 795cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 796cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Align the size properly for a vector of abitset objects. */ 797cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (header_size % bitset_alignment != 0 798cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project || sizeof (bitset_word) % bitset_alignment != 0) 799cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 800cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes += bitset_alignment - 1; 801cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes -= bytes % bitset_alignment; 802cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 803cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 804cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bytes; 805cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 806cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 807cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 808cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitset 809cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectabitset_init (bitset bset, bitset_bindex n_bits) 810cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 811cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex size; 812cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 813cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size = ABITSET_N_WORDS (n_bits); 814cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_NBITS_ (bset) = n_bits; 815cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 816cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Use optimized routines if bitset fits within a single word. 817cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project There is probably little merit if using caching since 818cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the small bitset will always fit in the cache. */ 819cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (size == 1) 820cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.vtable = &abitset_small_vtable; 821cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 822cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.vtable = &abitset_vtable; 823cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 824cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = 0; 825cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.csize = size; 826cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = ABITSET_WORDS (bset); 827cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bset; 828cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 829