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