1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Bitset vectors. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is free software; you can redistribute it and/or modify 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation; either version 2 of the License, or 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (at your option) any later version. 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is distributed in the hope that it will be useful, 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project along with this program; if not, write to the Free Software Foundation, 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifdef HAVE_CONFIG_H 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# include <config.h> 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdlib.h> 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "bitsetv.h" 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Create a vector of N_VECS bitsets, each of N_BITS, and of 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project type TYPE. */ 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitset * 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits, 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project enum bitset_type type) 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t vector_bytes; 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bytes; 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset *bsetv; 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Determine number of bytes for each set. */ 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bytes = bitset_bytes (type, n_bits); 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If size calculation overflows, memory is exhausted. */ 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs) 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project xalloc_die (); 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Allocate vector table at head of bitset array. */ 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1; 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project vector_bytes -= vector_bytes % bytes; 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bsetv = xcalloc (1, vector_bytes + bytes * n_vecs); 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < n_vecs; i++) 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes); 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_init (bsetv[i], n_bits, type); 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Null terminate table. */ 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bsetv[i] = 0; 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bsetv; 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Create a vector of N_VECS bitsets, each of N_BITS, and with 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project attribute hints specified by ATTR. */ 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitset * 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned int attr) 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project enum bitset_type type; 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project type = bitset_type_choose (n_bits, attr); 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bitsetv_alloc (n_vecs, n_bits, type); 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Free bitset vector BSETV. */ 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_free (bitsetv bsetv) 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_FREE_ (bsetv[i]); 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (bsetv); 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Zero a vector of bitsets. */ 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_zero (bitsetv bsetv) 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_zero (bsetv[i]); 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set a vector of bitsets to ones. */ 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_ones (bitsetv bsetv) 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_ones (bsetv[i]); 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Given a vector BSETV of N bitsets of size N, modify its contents to 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project be the transitive closure of what was given. */ 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_transitive_closure (bitsetv bsetv) 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex j; 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; bsetv[j]; j++) 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bitset_test (bsetv[j], i)) 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_or (bsetv[j], bsetv[j], bsetv[i]); 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Given a vector BSETV of N bitsets of size N, modify its contents to 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project be the reflexive transitive closure of what was given. This is 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the same as transitive closure but with all bits on the diagonal 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of the bit matrix set. */ 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_reflexive_transitive_closure (bitsetv bsetv) 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_bindex i; 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitsetv_transitive_closure (bsetv); 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_set (bsetv[i], i); 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Dump the contents of a bitset vector BSETV with N_VECS elements to 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project FILE. */ 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbitsetv_dump (FILE *file, char const *title, char const *subtitle, 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitsetv bsetv) 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (file, "%s\n", title); 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (file, "%s %lu\n", subtitle, (unsigned long int) i); 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_dump (file, bsetv[i]); 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (file, "\n"); 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectdebug_bitsetv (bitsetv bsetv) 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_windex i; 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; bsetv[i]; i++) 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "%lu: ", (unsigned long int) i); 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project debug_bitset (bsetv[i]); 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "\n"); 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 170