1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Functions to support link list bitsets. 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 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 "lbitset.h" 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "obstack.h" 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stddef.h> 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdlib.h> 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdio.h> 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <string.h> 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* This file implements linked-list bitsets. These bitsets can be of 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project arbitrary length and are more efficient than arrays of bits for 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project large sparse sets. 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Usually if all the bits in an element are zero we remove the element 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project from the list. However, a side effect of the bit caching is that we 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project do not always notice when an element becomes zero. Hence the 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed function which removes zero elements. */ 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Number of words to use for each element. The larger the value the 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project greater the size of the cache and the shorter the time to find a given bit 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but the more memory wasted for sparse bitsets and the longer the time 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project to search for set bits. 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The routines that dominate timing profiles are lbitset_elt_find 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project and lbitset_elt_link, especially when accessing the bits randomly. */ 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_ELT_WORDS 2 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef bitset_word lbitset_word; 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_WORD_BITS BITSET_WORD_BITS 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Number of bits stored in each element. */ 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_ELT_BITS \ 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Lbitset element. We use an array of bits for each element. 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project These are linked together in a doubly-linked list. */ 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct lbitset_elt_struct 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct lbitset_elt_struct *next; /* Next element. */ 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct lbitset_elt_struct *prev; /* Previous element. */ 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex index; /* bitno / BITSET_WORD_BITS. */ 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt; 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectenum lbitset_find_mode 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Obstack to allocate bitset elements from. */ 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic struct obstack lbitset_obstack; 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool lbitset_obstack_init = false; 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectextern void debug_lbitset (bitset); 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_CURRENT1(X) \ 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words))) 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata) 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_HEAD(X) ((X)->l.head) 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define LBITSET_TAIL(X) ((X)->l.tail) 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Allocate a lbitset element. The bits are not cleared. */ 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline lbitset_elt * 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_alloc (void) 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (lbitset_free_list != 0) 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = lbitset_free_list; 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_free_list = elt->next; 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!lbitset_obstack_init) 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_obstack_init = true; 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Let particular systems override the size of a chunk. */ 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef OBSTACK_CHUNK_SIZE 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define OBSTACK_CHUNK_SIZE 0 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Let them override the alloc and free routines too. */ 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef OBSTACK_CHUNK_ALLOC 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define OBSTACK_CHUNK_ALLOC xmalloc 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef OBSTACK_CHUNK_FREE 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define OBSTACK_CHUNK_FREE free 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if ! defined __GNUC__ || __GNUC__ < 2 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define __alignof__(type) 0 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project __alignof__ (lbitset_elt), 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project OBSTACK_CHUNK_ALLOC, 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project OBSTACK_CHUNK_FREE); 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Perhaps we should add a number of new elements to the free 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list. */ 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack, 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sizeof (lbitset_elt)); 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return elt; 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Allocate a lbitset element. The bits are cleared. */ 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline lbitset_elt * 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_calloc (void) 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = lbitset_elt_alloc (); 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memset (elt->words, 0, sizeof (elt->words)); 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return elt; 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_free (lbitset_elt *elt) 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->next = lbitset_free_list; 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_free_list = elt; 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Unlink element ELT from bitset BSET. */ 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_unlink (bitset bset, lbitset_elt *elt) 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *next = elt->next; 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *prev = elt->prev; 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (prev) 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project prev->next = next; 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (next) 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next->prev = prev; 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (LBITSET_HEAD (bset) == elt) 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (bset) = next; 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (LBITSET_TAIL (bset) == elt) 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (bset) = prev; 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Update cache pointer. Since the first thing we try is to insert 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project before current, make current the next entry in preference to the 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project previous. */ 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (LBITSET_CURRENT (bset) == elt) 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (next) 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = next->words; 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = next->index; 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (prev) 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = prev->words; 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = prev->index; 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.csize = 0; 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = 0; 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_free (elt); 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Cut the chain of bitset BSET before element ELT and free the 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elements. */ 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_prune (bitset bset, lbitset_elt *elt) 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *next; 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!elt) 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (elt->prev) 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (bset) = elt->prev; 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = elt->prev->words; 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = elt->prev->index; 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->prev->next = 0; 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (bset) = 0; 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (bset) = 0; 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = 0; 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.csize = 0; 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; elt; elt = next) 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = elt->next; 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_free (elt); 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Are all bits in an element zero? */ 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline bool 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_zero_p (lbitset_elt *elt) 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++) 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (elt->words[i]) 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Link the bitset element into the current bitset linked list. */ 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_link (bitset bset, lbitset_elt *elt) 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex = elt->index; 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *ptr; 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *current; 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bset->b.csize) 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project current = LBITSET_CURRENT (bset); 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project current = LBITSET_HEAD (bset); 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If this is the first and only element, add it in. */ 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (LBITSET_HEAD (bset) == 0) 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->next = elt->prev = 0; 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (bset) = elt; 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (bset) = elt; 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If this index is less than that of the current element, it goes 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project somewhere before the current element. */ 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (windex < bset->b.cindex) 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (ptr = current; 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->prev && ptr->prev->index > windex; ptr = ptr->prev) 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ptr->prev) 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->prev->next = elt; 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (bset) = elt; 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->prev = ptr->prev; 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->next = ptr; 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->prev = elt; 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Otherwise, it must go somewhere after the current element. */ 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (ptr = current; 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->next && ptr->next->index < windex; ptr = ptr->next) 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ptr->next) 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->next->prev = elt; 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (bset) = elt; 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->next = ptr->next; 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->prev = ptr; 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ptr->next = elt; 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Set up so this is the first element searched. */ 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = windex; 313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.csize = LBITSET_ELT_WORDS; 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = elt->words; 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic lbitset_elt * 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_elt_find (bitset bset, bitset_windex windex, 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project enum lbitset_find_mode mode) 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *current; 324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bset->b.csize) 326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project current = LBITSET_CURRENT (bset); 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Check if element is the cached element. */ 329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((windex - bset->b.cindex) < bset->b.csize) 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return current; 331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project current = LBITSET_HEAD (bset); 335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (current) 338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (windex < bset->b.cindex) 340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = current; 342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->prev && elt->index > windex; elt = elt->prev) 343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = current; 348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex; 349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = elt->next) 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* ELT is the nearest to the one we want. If it's not the one 354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project we want, the one we want does not exist. */ 35505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (windex - elt->index < LBITSET_ELT_WORDS) 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cindex = elt->index; 358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.csize = LBITSET_ELT_WORDS; 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.cdata = elt->words; 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return elt; 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project switch (mode) 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project default: 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case LBITSET_FIND: 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 371cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 372cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case LBITSET_CREATE: 373cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex -= windex % LBITSET_ELT_WORDS; 374cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 375cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = lbitset_elt_calloc (); 376cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt->index = windex; 377cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_link (bset, elt); 378cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return elt; 379cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 380cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case LBITSET_SUBST: 381cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return &lbitset_zero_elts[0]; 382cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 383cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 384cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 385cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 386cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Weed out the zero elements from the list. */ 387cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 388cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_weed (bitset bset) 389cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 390cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 391cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *next; 392cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 393cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = LBITSET_HEAD (bset); elt; elt = next) 394cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 395cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = elt->next; 396cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (lbitset_elt_zero_p (elt)) 397cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_unlink (bset, elt); 398cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 399cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 400cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 401cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 402cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set all bits in the bitset to zero. */ 403cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 404cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_zero (bitset bset) 405cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 406cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *head; 407cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 408cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project head = LBITSET_HEAD (bset); 409cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!head) 410cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 411cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 412cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Clear a bitset by freeing the linked list at the head element. */ 413cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_prune (bset, head); 414cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 415cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 416cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 417cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Is DST == SRC? */ 418cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline bool 419cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_equal_p (bitset dst, bitset src) 420cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 421cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt; 422cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *delt; 423cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j; 424cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 425cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (src == dst) 426cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 427cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 428cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (src); 429cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (dst); 430cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 431cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt && delt; selt = selt->next, delt = delt->next) 432cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 433cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (selt->index != delt->index) 434cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 435cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 436cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < LBITSET_ELT_WORDS; j++) 437cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delt->words[j] != selt->words[j]) 438cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 439cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 440cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return !selt && !delt; 441cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 442cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 443cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 444cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Copy bits from bitset SRC to bitset DST. */ 445cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 446cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_copy (bitset dst, bitset src) 447cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 448cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 449cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *head; 450cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *prev; 451cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *tmp; 452cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 453cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (src == dst) 454cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 455cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 456cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero (dst); 457cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 458cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project head = LBITSET_HEAD (src); 459cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!head) 460cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 461cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 462cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project prev = 0; 463cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = head; elt; elt = elt->next) 464cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 465cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tmp = lbitset_elt_alloc (); 466cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tmp->index = elt->index; 467cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tmp->prev = prev; 468cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tmp->next = 0; 469cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (prev) 470cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project prev->next = tmp; 471cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 472cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (dst) = tmp; 473cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project prev = tmp; 474cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 475cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (tmp->words, elt->words, sizeof (elt->words)); 476cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 477cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_TAIL (dst) = tmp; 478cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 479cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.csize = LBITSET_ELT_WORDS; 480cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.cdata = LBITSET_HEAD (dst)->words; 481cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.cindex = LBITSET_HEAD (dst)->index; 482cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 483cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 484cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 485cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Copy bits from bitset SRC to bitset DST. Return true if 486cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitsets different. */ 487cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline bool 488cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_copy_cmp (bitset dst, bitset src) 489cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 490cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (src == dst) 491cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 492cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 493cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!LBITSET_HEAD (dst)) 494cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 495cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_copy (dst, src); 496cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return LBITSET_HEAD (src) != 0; 497cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 498cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 499cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (lbitset_equal_p (dst, src)) 500cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 501cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 502cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_copy (dst, src); 503cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 504cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 505cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 506cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 507cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 508cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_resize (bitset src, bitset_bindex size) 509cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 510cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_NBITS_ (src) = size; 511cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 512cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Need to prune any excess bits. FIXME. */ 513cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return size; 514cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 515cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 516cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set bit BITNO in bitset DST. */ 517cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 518cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_set (bitset dst, bitset_bindex bitno) 519cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 520cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex = bitno / BITSET_WORD_BITS; 521cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 522cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_find (dst, windex, LBITSET_CREATE); 523cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 524cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.cdata[windex - dst->b.cindex] |= 525cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (bitset_word) 1 << (bitno % BITSET_WORD_BITS); 526cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 527cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 528cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 529cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Reset bit BITNO in bitset DST. */ 530cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 531cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_reset (bitset dst, bitset_bindex bitno) 532cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 533cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex = bitno / BITSET_WORD_BITS; 534cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 535cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!lbitset_elt_find (dst, windex, LBITSET_FIND)) 536cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 537cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 538cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.cdata[windex - dst->b.cindex] &= 539cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); 540cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 541cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If all the data is zero, perhaps we should unlink it now... */ 542cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 543cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 544cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 545cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Test bit BITNO in bitset SRC. */ 546cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 547cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_test (bitset src, bitset_bindex bitno) 548cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 549cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex = bitno / BITSET_WORD_BITS; 550cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 551cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return (lbitset_elt_find (src, windex, LBITSET_FIND) 552cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && ((src->b.cdata[windex - src->b.cindex] 553cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project >> (bitno % BITSET_WORD_BITS)) 554cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project & 1)); 555cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 556cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 557cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 558cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 559cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_free (bitset bset) 560cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 561cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero (bset); 562cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 563cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 564cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 565cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET starting from and including 566cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT and store in array LIST. Return with actual number of bits 567cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project found and with *NEXT indicating where search stopped. */ 568cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 569cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_list_reverse (bitset bset, bitset_bindex *list, 570cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex num, bitset_bindex *next) 571cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 572cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex rbitno; 573cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno; 574cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int bcount; 575cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex boffset; 576cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 577cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex count; 578cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 579cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 580cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex n_bits; 581cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 582cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = LBITSET_TAIL (bset); 583cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!elt) 584cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 585cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 586cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; 587cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rbitno = *next; 588cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 589cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rbitno >= n_bits) 590cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 591cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 592cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = n_bits - (rbitno + 1); 593cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 594cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = bitno / BITSET_WORD_BITS; 595cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 596cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Skip back to starting element. */ 597cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; elt && elt->index > windex; elt = elt->prev) 598cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 599cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 600cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!elt) 601cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 602cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 603cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (windex >= elt->index + LBITSET_ELT_WORDS) 604cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 605cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* We are trying to start in no-mans land so start 606cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project at end of current elt. */ 607cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bcount = BITSET_WORD_BITS - 1; 608cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index + LBITSET_ELT_WORDS - 1; 609cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 610cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 611cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 612cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bcount = bitno % BITSET_WORD_BITS; 613cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 614cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 615cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count = 0; 616cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project boffset = windex * BITSET_WORD_BITS; 617cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 618cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If num is 1, we could speed things up with a binary search 619cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the word of interest. */ 620cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 621cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (elt) 622cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 623cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = elt->words; 624cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 625cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; (windex - elt->index) < LBITSET_ELT_WORDS; 626cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex--, boffset -= BITSET_WORD_BITS, 627cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bcount = BITSET_WORD_BITS - 1) 628cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 629cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = 630cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount); 631cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 632cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bcount--) 633cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 634cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & BITSET_MSB) 635cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 636cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = boffset + bcount; 637cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 638cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 639cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = n_bits - (boffset + bcount); 640cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 641cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 642cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 643cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word <<= 1; 644cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 645cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 646cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 647cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = elt->prev; 648cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (elt) 649cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 650cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index + LBITSET_ELT_WORDS - 1; 651cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project boffset = windex * BITSET_WORD_BITS; 652cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 653cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 654cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 655cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = n_bits - (boffset + 1); 656cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 657cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 658cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 659cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 660cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Find list of up to NUM bits set in BSET starting from and including 661cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *NEXT and store in array LIST. Return with actual number of bits 662cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project found and with *NEXT indicating where search stopped. */ 663cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitset_bindex 664cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_list (bitset bset, bitset_bindex *list, 665cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex num, bitset_bindex *next) 666cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 667cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex bitno; 668cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 669cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex count; 670cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 671cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *head; 672cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 673cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 674cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project head = LBITSET_HEAD (bset); 675cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!head) 676cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 677cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 678cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = *next; 679cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count = 0; 680cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 681cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!bitno) 682cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 683cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This is the most common case. */ 684cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 685cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Start with the first element. */ 686cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = head; 687cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index; 688cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 689cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 690cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 691cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 692cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = bitno / BITSET_WORD_BITS; 693cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 694cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Skip to starting element. */ 695cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = head; 696cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex; 697cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = elt->next) 698cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 699cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 700cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!elt) 701cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 702cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 703cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (windex < elt->index) 704cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 705cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index; 706cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 707cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 708cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 709cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 710cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = elt->words; 711cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 712cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* We are starting within an element. */ 713cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 714cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) 715cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 716cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS); 717cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 718cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bitno++) 719cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 720cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 721cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 722cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 723cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 724cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 725cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno + 1; 726cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 727cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 728cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 729cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 730cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 731cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = (windex + 1) * BITSET_WORD_BITS; 732cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 733cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 734cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = elt->next; 735cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (elt) 736cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 737cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index; 738cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 739cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 740cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 741cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 742cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 743cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 744cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If num is 1, we could speed things up with a binary search 745cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the word of interest. */ 746cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 747cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (elt) 748cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 749cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 750cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp = elt->words; 751cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 752cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((count + LBITSET_ELT_BITS) < num) 753cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 754cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* The coast is clear, plant boot! */ 755cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 756cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if LBITSET_ELT_WORDS == 2 757cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[0]; 758cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word) 759cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 760cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word & 0xffff)) 761cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 762cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 16; 763cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno += 16; 764cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 765cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word & 0xff)) 766cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 767cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 8; 768cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno += 8; 769cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 770cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bitno++) 771cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 772cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 773cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 774cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 775cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 776cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 777cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 778cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 779cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 780cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[1]; 781cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word) 782cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 783cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word & 0xffff)) 784cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 785cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 16; 786cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno += 16; 787cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 788cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bitno++) 789cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 790cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 791cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 792cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 793cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 794cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 795cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 796cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 797cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#else 798cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++) 799cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 800cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = srcp[i]; 801cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word) 802cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 803cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word & 0xffff)) 804cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 805cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 16; 806cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno += 16; 807cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 808cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(word & 0xff)) 809cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 810cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 8; 811cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno += 8; 812cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 813cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; word; bitno++) 814cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 815cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 816cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 817cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 818cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 819cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 820cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 821cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 822cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 823cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 824cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 825cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 826cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 827cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Tread more carefully since we need to check 828cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if array overflows. */ 829cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 830cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++) 831cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 832cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (word = srcp[i]; word; bitno++) 833cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 834cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (word & 1) 835cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 836cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project list[count++] = bitno; 837cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count >= num) 838cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 839cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno + 1; 840cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 841cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 842cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 843cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word >>= 1; 844cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 845cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 846cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 847cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 848cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 849cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 850cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = elt->next; 851cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (elt) 852cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 853cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = elt->index; 854cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitno = windex * BITSET_WORD_BITS; 855cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 856cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 857cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 858cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *next = bitno; 859cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return count; 860cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 861cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 862cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 863cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 864cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_empty_p (bitset dst) 865cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 866cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 867cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *next; 868cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 869cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = LBITSET_HEAD (dst); elt; elt = next) 870cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 871cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = elt->next; 872cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!lbitset_elt_zero_p (elt)) 873cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 0; 874cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Weed as we go. */ 875cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_unlink (dst, elt); 876cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 877cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 878cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return 1; 879cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 880cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 881cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 882cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Ensure that any unused bits within the last element are clear. */ 883cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline void 884cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_unused_clear (bitset dst) 885cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 886cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int last_bit; 887cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex n_bits; 888cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 889cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project n_bits = BITSET_SIZE_ (dst); 890cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project last_bit = n_bits % LBITSET_ELT_BITS; 891cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 892cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (last_bit) 893cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 894cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 895cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 896cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp; 897cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 898cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = LBITSET_TAIL (dst); 899cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp = elt->words; 900cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = n_bits / BITSET_WORD_BITS; 901cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 902cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1; 903cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex++; 904cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 905cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) 906cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp[windex - elt->index] = 0; 907cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 908cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 909cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 910cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 911cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 912cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_ones (bitset dst) 913cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 914cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 915cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 916cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 917cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 918cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This is a decidedly unfriendly operation for a linked list 919cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset! It makes a sparse bitset become dense. An alternative 920cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project is to have a flag that indicates that the bitset stores the 921cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project complement of what it indicates. */ 922cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 923cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; 924cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 925cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < windex; i += LBITSET_ELT_WORDS) 926cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 927cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Create new elements if they cannot be found. */ 928cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elt = lbitset_elt_find (dst, i, LBITSET_CREATE); 929cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memset (elt->words, -1, sizeof (elt->words)); 930cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 931cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 932cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_unused_clear (dst); 933cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 934cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 935cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 936cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 937cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_not (bitset dst, bitset src) 938cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 939cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt; 940cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *delt; 941cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 942cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int j; 943cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 944cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 945cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; 946cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 947cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < windex; i += LBITSET_ELT_WORDS) 948cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 949cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Create new elements for dst if they cannot be found 950cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project or substitute zero elements if src elements not found. */ 951cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt = lbitset_elt_find (src, i, LBITSET_SUBST); 952cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = lbitset_elt_find (dst, i, LBITSET_CREATE); 953cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 954cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < LBITSET_ELT_WORDS; j++) 955cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt->words[j] = ~selt->words[j]; 956cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 957cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_unused_clear (dst); 958cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (dst); 959cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 960cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 961cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 962cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 963cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Is DST == DST | SRC? */ 964cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 965cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_subset_p (bitset dst, bitset src) 966cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 967cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt; 968cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *delt; 969cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int j; 970cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 971cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 972cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt || delt; selt = selt->next, delt = delt->next) 973cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 974cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!selt) 975cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt = &lbitset_zero_elts[0]; 976cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (!delt) 977cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = &lbitset_zero_elts[0]; 978cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (selt->index != delt->index) 979cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 980cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (selt->index < delt->index) 981cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 982cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero_elts[2].next = delt; 983cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = &lbitset_zero_elts[2]; 984cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 985cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 986cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 987cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero_elts[1].next = selt; 988cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt = &lbitset_zero_elts[1]; 989cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 990cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 991cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 992cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < LBITSET_ELT_WORDS; j++) 993cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delt->words[j] != (selt->words[j] | delt->words[j])) 994cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 995cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 996cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 997cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 998cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 999cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1000cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Is DST & SRC == 0? */ 1001cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1002cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_disjoint_p (bitset dst, bitset src) 1003cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1004cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt; 1005cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *delt; 1006cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int j; 1007cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1008cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 1009cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt && delt; selt = selt->next, delt = delt->next) 1010cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1011cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (selt->index != delt->index) 1012cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1013cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (selt->index < delt->index) 1014cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1015cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero_elts[2].next = delt; 1016cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = &lbitset_zero_elts[2]; 1017cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1018cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 1019cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1020cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero_elts[1].next = selt; 1021cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt = &lbitset_zero_elts[1]; 1022cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1023cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Since the elements are different, there is no 1024cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project intersection of these elements. */ 1025cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project continue; 1026cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1027cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1028cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < LBITSET_ELT_WORDS; j++) 1029cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (selt->words[j] & delt->words[j]) 1030cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 1031cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1032cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 1033cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1034cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1035cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1036cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1037cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) 1038cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1039cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt1 = LBITSET_HEAD (src1); 1040cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt2 = LBITSET_HEAD (src2); 1041cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *delt = LBITSET_HEAD (dst); 1042cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex1; 1043cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex2; 1044cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex windex; 1045cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *stmp1; 1046cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *stmp2; 1047cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *dtmp; 1048cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp1; 1049cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *srcp2; 1050cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word *dstp; 1051cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed = false; 1052cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int i; 1053cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1054cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LBITSET_HEAD (dst) = 0; 1055cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dst->b.csize = 0; 1056cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1057cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1058cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1059cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1060cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (selt1 || selt2) 1061cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1062cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Figure out whether we need to substitute zero elements for 1063cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project missing links. */ 1064cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (windex1 == windex2) 1065cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1066cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = windex1; 1067cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp1 = selt1; 1068cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp2 = selt2; 1069cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt1 = selt1->next; 1070cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1071cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt2 = selt2->next; 1072cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1073cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1074cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (windex1 < windex2) 1075cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1076cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = windex1; 1077cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp1 = selt1; 1078cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp2 = &lbitset_zero_elts[0]; 1079cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt1 = selt1->next; 1080cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1081cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1082cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 1083cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1084cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex = windex2; 1085cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp1 = &lbitset_zero_elts[0]; 1086cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project stmp2 = selt2; 1087cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project selt2 = selt2->next; 1088cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1089cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1090cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1091cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find the appropriate element from DST. Begin by discarding 1092cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project elements that we've skipped. */ 1093cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (delt && delt->index < windex) 1094cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1095cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1096cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dtmp = delt; 1097cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = delt->next; 1098cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_free (dtmp); 1099cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delt && delt->index == windex) 1101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dtmp = delt; 1103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project delt = delt->next; 1104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 1106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dtmp = lbitset_elt_calloc (); 1107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Do the operation, and if any bits are set, link it into the 1109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project linked list. */ 1110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp1 = stmp1->words; 1111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project srcp2 = stmp2->words; 1112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dstp = dtmp->words; 1113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project switch (op) 1114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project default: 1116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 1117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case BITSET_OP_OR: 1119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *srcp1++ | *srcp2++; 1122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 1124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 1127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project break; 1130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case BITSET_OP_AND: 1132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *srcp1++ & *srcp2++; 1135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 1137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 1140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project break; 1143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case BITSET_OP_XOR: 1145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *srcp1++ ^ *srcp2++; 1148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 1150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 1153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project break; 1156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project case BITSET_OP_ANDN: 1158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word tmp = *srcp1++ & ~(*srcp2++); 1161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (*dstp != tmp) 1163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *dstp = tmp; 1166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project break; 1169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!lbitset_elt_zero_p (dtmp)) 1172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project dtmp->index = windex; 1174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Perhaps this could be optimised... */ 1175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_link (dst, dtmp); 1176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 1178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt_free (dtmp); 1180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If we have elements of DST left over, free them all. */ 1184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delt) 1185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = true; 1187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_prune (dst, delt); 1188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 1191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_and_cmp (bitset dst, bitset src1, bitset src2) 1196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt1 = LBITSET_HEAD (src1); 1198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt2 = LBITSET_HEAD (src2); 1199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed; 1200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!selt2) 1202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (dst); 1204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = !LBITSET_HEAD (dst); 1205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero (dst); 1206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 1207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (!selt1) 1209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (dst); 1211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = !LBITSET_HEAD (dst); 1212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero (dst); 1213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 1214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); 1216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 1220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_and (bitset dst, bitset src1, bitset src2) 1221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_and_cmp (dst, src1, src2); 1223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_andn_cmp (bitset dst, bitset src1, bitset src2) 1228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt1 = LBITSET_HEAD (src1); 1230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt2 = LBITSET_HEAD (src2); 1231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool changed; 1232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!selt2) 1234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_copy_cmp (dst, src1); 1236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (!selt1) 1238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_weed (dst); 1240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project changed = !LBITSET_HEAD (dst); 1241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero (dst); 1242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return changed; 1243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); 1245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 1249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_andn (bitset dst, bitset src1, bitset src2) 1250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_andn_cmp (dst, src1, src2); 1252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_or_cmp (bitset dst, bitset src1, bitset src2) 1257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt1 = LBITSET_HEAD (src1); 1259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt2 = LBITSET_HEAD (src2); 1260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!selt2) 1262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_copy_cmp (dst, src1); 1264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (!selt1) 1266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_copy_cmp (dst, src2); 1268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); 1270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 1274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_or (bitset dst, bitset src1, bitset src2) 1275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_or_cmp (dst, src1, src2); 1277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 1281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_xor_cmp (bitset dst, bitset src1, bitset src2) 1282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt1 = LBITSET_HEAD (src1); 1284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *selt2 = LBITSET_HEAD (src2); 1285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!selt2) 1287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_copy_cmp (dst, src1); 1289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (!selt1) 1291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_copy_cmp (dst, src2); 1293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); 1295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 1299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_xor (bitset dst, bitset src1, bitset src2) 1300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_xor_cmp (dst, src1, src2); 1302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Vector of operations for linked-list bitsets. */ 1307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct bitset_vtable lbitset_vtable = { 1308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_set, 1309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_reset, 1310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_toggle_, 1311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_test, 1312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_resize, 1313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_size_, 1314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_count_, 1315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_empty_p, 1316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_ones, 1317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_zero, 1318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_copy, 1319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_disjoint_p, 1320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_equal_p, 1321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_not, 1322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_subset_p, 1323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_and, 1324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_and_cmp, 1325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_andn, 1326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_andn_cmp, 1327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_or, 1328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_or_cmp, 1329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_xor, 1330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_xor_cmp, 1331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_and_or_, 1332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_and_or_cmp_, 1333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_andn_or_, 1334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_andn_or_cmp_, 1335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_or_and_, 1336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_or_and_cmp_, 1337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_list, 1338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_list_reverse, 1339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_free, 1340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_LIST 1341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project}; 1342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return size of initial structure. */ 1345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 1346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) 1347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return sizeof (struct lbitset_struct); 1349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Initialize a bitset. */ 1353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitset 1354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED) 1355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_NBITS_ (bset) = n_bits; 1357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bset->b.vtable = &lbitset_vtable; 1358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bset; 1359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 1363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlbitset_release_memory (void) 1364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_free_list = 0; 1366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (lbitset_obstack_init) 1367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_obstack_init = false; 1369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_free (&lbitset_obstack, NULL); 1370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1371cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1372cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1373cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1374cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Function to be called from debugger to debug lbitset. */ 1375cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 1376cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectdebug_lbitset (bitset bset) 1377cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1378cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project lbitset_elt *elt; 1379cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int i; 1380cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1381cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!bset) 1382cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 1383cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1384cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) 1385cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1386cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index); 1387cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < LBITSET_ELT_WORDS; i++) 1388cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1389cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned int j; 1390cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_word word; 1391cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1392cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project word = elt->words[i]; 1393cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1394cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, " Word %u:", i); 1395cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < LBITSET_WORD_BITS; j++) 1396cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((word & ((bitset_word) 1 << j))) 1397cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, " %u", j); 1398cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "\n"); 1399cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1400cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1401cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1402