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