Mercurial > gnulib
annotate lib/bitsetv.c @ 40067:b5d7b6ac3542
bitsetv: Fix module dependencies.
* lib/bitsetv.c: Include xalloc.h.
* modules/bitsetv (Depends-on): Add 'xalloc'.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Fri, 04 Jan 2019 12:56:22 +0100 |
| parents | b06060465f09 |
| children | 069b50a66104 |
| rev | line source |
|---|---|
| 39975 | 1 /* Bitset vectors. |
| 2 | |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
39975
diff
changeset
|
3 Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018-2019 Free Software |
| 39975 | 4 Foundation, Inc. |
| 5 | |
| 6 This program is free software: you can redistribute it and/or modify | |
| 7 it under the terms of the GNU General Public License as published by | |
| 8 the Free Software Foundation, either version 3 of the License, or | |
| 9 (at your option) any later version. | |
| 10 | |
| 11 This program is distributed in the hope that it will be useful, | |
| 12 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 14 GNU General Public License for more details. | |
| 15 | |
| 16 You should have received a copy of the GNU General Public License | |
| 17 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 18 | |
| 19 #include <config.h> | |
| 20 | |
| 21 #include "bitsetv.h" | |
| 22 | |
| 23 #include <stdlib.h> | |
| 24 | |
|
40067
b5d7b6ac3542
bitsetv: Fix module dependencies.
Bruno Haible <bruno@clisp.org>
parents:
40057
diff
changeset
|
25 #include "xalloc.h" |
|
b5d7b6ac3542
bitsetv: Fix module dependencies.
Bruno Haible <bruno@clisp.org>
parents:
40057
diff
changeset
|
26 |
| 39975 | 27 |
| 28 /* Create a vector of N_VECS bitsets, each of N_BITS, and of | |
| 29 type TYPE. */ | |
| 30 bitset * | |
| 31 bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits, | |
| 32 enum bitset_type type) | |
| 33 { | |
| 34 /* Determine number of bytes for each set. */ | |
| 35 size_t bytes = bitset_bytes (type, n_bits); | |
| 36 | |
| 37 /* If size calculation overflows, memory is exhausted. */ | |
| 38 if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs) | |
| 39 xalloc_die (); | |
| 40 | |
| 41 /* Allocate vector table at head of bitset array. */ | |
| 42 size_t vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1; | |
| 43 vector_bytes -= vector_bytes % bytes; | |
| 44 bitset *bsetv = xcalloc (1, vector_bytes + bytes * n_vecs); | |
| 45 | |
| 46 bitset_bindex i = 0; | |
| 47 for (i = 0; i < n_vecs; i++) | |
| 48 { | |
| 49 bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes); | |
| 50 | |
| 51 bitset_init (bsetv[i], n_bits, type); | |
| 52 } | |
| 53 | |
| 54 /* Null terminate table. */ | |
| 55 bsetv[i] = 0; | |
| 56 return bsetv; | |
| 57 } | |
| 58 | |
| 59 | |
| 60 /* Create a vector of N_VECS bitsets, each of N_BITS, and with | |
| 61 attribute hints specified by ATTR. */ | |
| 62 bitset * | |
| 63 bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned attr) | |
| 64 { | |
| 65 enum bitset_type type = bitset_type_choose (n_bits, attr); | |
| 66 return bitsetv_alloc (n_vecs, n_bits, type); | |
| 67 } | |
| 68 | |
| 69 | |
| 70 /* Free bitset vector BSETV. */ | |
| 71 void | |
| 72 bitsetv_free (bitsetv bsetv) | |
| 73 { | |
| 74 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 75 BITSET_FREE_ (bsetv[i]); | |
| 76 free (bsetv); | |
| 77 } | |
| 78 | |
| 79 | |
| 80 /* Zero a vector of bitsets. */ | |
| 81 void | |
| 82 bitsetv_zero (bitsetv bsetv) | |
| 83 { | |
| 84 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 85 bitset_zero (bsetv[i]); | |
| 86 } | |
| 87 | |
| 88 | |
| 89 /* Set a vector of bitsets to ones. */ | |
| 90 void | |
| 91 bitsetv_ones (bitsetv bsetv) | |
| 92 { | |
| 93 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 94 bitset_ones (bsetv[i]); | |
| 95 } | |
| 96 | |
| 97 | |
| 98 /* Given a vector BSETV of N bitsets of size N, modify its contents to | |
| 99 be the transitive closure of what was given. */ | |
| 100 void | |
| 101 bitsetv_transitive_closure (bitsetv bsetv) | |
| 102 { | |
| 103 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 104 for (bitset_bindex j = 0; bsetv[j]; j++) | |
| 105 if (bitset_test (bsetv[j], i)) | |
| 106 bitset_or (bsetv[j], bsetv[j], bsetv[i]); | |
| 107 } | |
| 108 | |
| 109 | |
| 110 /* Given a vector BSETV of N bitsets of size N, modify its contents to | |
| 111 be the reflexive transitive closure of what was given. This is | |
| 112 the same as transitive closure but with all bits on the diagonal | |
| 113 of the bit matrix set. */ | |
| 114 void | |
| 115 bitsetv_reflexive_transitive_closure (bitsetv bsetv) | |
| 116 { | |
| 117 bitsetv_transitive_closure (bsetv); | |
| 118 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 119 bitset_set (bsetv[i], i); | |
| 120 } | |
| 121 | |
| 122 | |
| 123 /* Dump the contents of a bitset vector BSETV with N_VECS elements to | |
| 124 FILE. */ | |
| 125 void | |
| 126 bitsetv_dump (FILE *file, char const *title, char const *subtitle, | |
| 127 bitsetv bsetv) | |
| 128 { | |
| 129 fprintf (file, "%s\n", title); | |
| 130 for (bitset_windex i = 0; bsetv[i]; i++) | |
| 131 { | |
| 132 fprintf (file, "%s %lu\n", subtitle, (unsigned long) i); | |
| 133 bitset_dump (file, bsetv[i]); | |
| 134 } | |
| 135 | |
| 136 fprintf (file, "\n"); | |
| 137 } | |
| 138 | |
| 139 | |
| 140 void | |
| 141 debug_bitsetv (bitsetv bsetv) | |
| 142 { | |
| 143 for (bitset_windex i = 0; bsetv[i]; i++) | |
| 144 { | |
| 145 fprintf (stderr, "%lu: ", (unsigned long) i); | |
| 146 debug_bitset (bsetv[i]); | |
| 147 } | |
| 148 | |
| 149 fprintf (stderr, "\n"); | |
| 150 } | |
| 151 | |
| 152 | |
| 153 /*--------------------------------------------------------. | |
| 154 | Display the MATRIX array of SIZE bitsets of size SIZE. | | |
| 155 `--------------------------------------------------------*/ | |
| 156 | |
| 157 void | |
| 158 bitsetv_matrix_dump (FILE *out, const char *title, bitsetv bset) | |
| 159 { | |
| 160 bitset_bindex hsize = bitset_size (bset[0]); | |
| 161 | |
| 162 /* Title. */ | |
| 163 fprintf (out, "%s BEGIN\n", title); | |
| 164 | |
| 165 /* Column numbers. */ | |
| 166 fputs (" ", out); | |
| 167 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 168 putc (i / 10 ? '0' + i / 10 : ' ', out); | |
| 169 putc ('\n', out); | |
| 170 fputs (" ", out); | |
| 171 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 172 fprintf (out, "%d", (int) (i % 10)); | |
| 173 putc ('\n', out); | |
| 174 | |
| 175 /* Bar. */ | |
| 176 fputs (" .", out); | |
| 177 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 178 putc ('-', out); | |
| 179 fputs (".\n", out); | |
| 180 | |
| 181 /* Contents. */ | |
| 182 for (bitset_bindex i = 0; bset[i]; ++i) | |
| 183 { | |
| 184 fprintf (out, "%2lu|", (unsigned long) i); | |
| 185 for (bitset_bindex j = 0; j < hsize; ++j) | |
| 186 fputs (bitset_test (bset[i], j) ? "1" : " ", out); | |
| 187 fputs ("|\n", out); | |
| 188 } | |
| 189 | |
| 190 /* Bar. */ | |
| 191 fputs (" `", out); | |
| 192 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 193 putc ('-', out); | |
| 194 fputs ("'\n", out); | |
| 195 | |
| 196 /* End title. */ | |
| 197 fprintf (out, "%s END\n\n", title); | |
| 198 } |