Mercurial > gnulib
annotate lib/bitsetv.c @ 40159:069b50a66104
bitsetv: allow free on NULL.
* lib/bitsetv.c (bitsetv_free): Do nothing when the bitsetv is NULL.
| author | Akim Demaille <akim.demaille@gmail.com> |
|---|---|
| date | Sun, 27 Jan 2019 18:49:36 +0100 |
| parents | b5d7b6ac3542 |
| children |
| 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 { | |
|
40159
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
74 if (bsetv) |
|
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
75 { |
|
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
76 for (bitset_bindex i = 0; bsetv[i]; i++) |
|
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
77 BITSET_FREE_ (bsetv[i]); |
|
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
78 free (bsetv); |
|
069b50a66104
bitsetv: allow free on NULL.
Akim Demaille <akim.demaille@gmail.com>
parents:
40067
diff
changeset
|
79 } |
| 39975 | 80 } |
| 81 | |
| 82 | |
| 83 /* Zero a vector of bitsets. */ | |
| 84 void | |
| 85 bitsetv_zero (bitsetv bsetv) | |
| 86 { | |
| 87 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 88 bitset_zero (bsetv[i]); | |
| 89 } | |
| 90 | |
| 91 | |
| 92 /* Set a vector of bitsets to ones. */ | |
| 93 void | |
| 94 bitsetv_ones (bitsetv bsetv) | |
| 95 { | |
| 96 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 97 bitset_ones (bsetv[i]); | |
| 98 } | |
| 99 | |
| 100 | |
| 101 /* Given a vector BSETV of N bitsets of size N, modify its contents to | |
| 102 be the transitive closure of what was given. */ | |
| 103 void | |
| 104 bitsetv_transitive_closure (bitsetv bsetv) | |
| 105 { | |
| 106 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 107 for (bitset_bindex j = 0; bsetv[j]; j++) | |
| 108 if (bitset_test (bsetv[j], i)) | |
| 109 bitset_or (bsetv[j], bsetv[j], bsetv[i]); | |
| 110 } | |
| 111 | |
| 112 | |
| 113 /* Given a vector BSETV of N bitsets of size N, modify its contents to | |
| 114 be the reflexive transitive closure of what was given. This is | |
| 115 the same as transitive closure but with all bits on the diagonal | |
| 116 of the bit matrix set. */ | |
| 117 void | |
| 118 bitsetv_reflexive_transitive_closure (bitsetv bsetv) | |
| 119 { | |
| 120 bitsetv_transitive_closure (bsetv); | |
| 121 for (bitset_bindex i = 0; bsetv[i]; i++) | |
| 122 bitset_set (bsetv[i], i); | |
| 123 } | |
| 124 | |
| 125 | |
| 126 /* Dump the contents of a bitset vector BSETV with N_VECS elements to | |
| 127 FILE. */ | |
| 128 void | |
| 129 bitsetv_dump (FILE *file, char const *title, char const *subtitle, | |
| 130 bitsetv bsetv) | |
| 131 { | |
| 132 fprintf (file, "%s\n", title); | |
| 133 for (bitset_windex i = 0; bsetv[i]; i++) | |
| 134 { | |
| 135 fprintf (file, "%s %lu\n", subtitle, (unsigned long) i); | |
| 136 bitset_dump (file, bsetv[i]); | |
| 137 } | |
| 138 | |
| 139 fprintf (file, "\n"); | |
| 140 } | |
| 141 | |
| 142 | |
| 143 void | |
| 144 debug_bitsetv (bitsetv bsetv) | |
| 145 { | |
| 146 for (bitset_windex i = 0; bsetv[i]; i++) | |
| 147 { | |
| 148 fprintf (stderr, "%lu: ", (unsigned long) i); | |
| 149 debug_bitset (bsetv[i]); | |
| 150 } | |
| 151 | |
| 152 fprintf (stderr, "\n"); | |
| 153 } | |
| 154 | |
| 155 | |
| 156 /*--------------------------------------------------------. | |
| 157 | Display the MATRIX array of SIZE bitsets of size SIZE. | | |
| 158 `--------------------------------------------------------*/ | |
| 159 | |
| 160 void | |
| 161 bitsetv_matrix_dump (FILE *out, const char *title, bitsetv bset) | |
| 162 { | |
| 163 bitset_bindex hsize = bitset_size (bset[0]); | |
| 164 | |
| 165 /* Title. */ | |
| 166 fprintf (out, "%s BEGIN\n", title); | |
| 167 | |
| 168 /* Column numbers. */ | |
| 169 fputs (" ", out); | |
| 170 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 171 putc (i / 10 ? '0' + i / 10 : ' ', out); | |
| 172 putc ('\n', out); | |
| 173 fputs (" ", out); | |
| 174 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 175 fprintf (out, "%d", (int) (i % 10)); | |
| 176 putc ('\n', out); | |
| 177 | |
| 178 /* Bar. */ | |
| 179 fputs (" .", out); | |
| 180 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 181 putc ('-', out); | |
| 182 fputs (".\n", out); | |
| 183 | |
| 184 /* Contents. */ | |
| 185 for (bitset_bindex i = 0; bset[i]; ++i) | |
| 186 { | |
| 187 fprintf (out, "%2lu|", (unsigned long) i); | |
| 188 for (bitset_bindex j = 0; j < hsize; ++j) | |
| 189 fputs (bitset_test (bset[i], j) ? "1" : " ", out); | |
| 190 fputs ("|\n", out); | |
| 191 } | |
| 192 | |
| 193 /* Bar. */ | |
| 194 fputs (" `", out); | |
| 195 for (bitset_bindex i = 0; i < hsize; ++i) | |
| 196 putc ('-', out); | |
| 197 fputs ("'\n", out); | |
| 198 | |
| 199 /* End title. */ | |
| 200 fprintf (out, "%s END\n\n", title); | |
| 201 } |