1 /*
2 * Copyright (c) 2018-2021 Free Software Foundation, Inc.
3 *
4 * This file is part of libwget.
5 *
6 * Libwget is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser 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 * Libwget 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 Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with libwget. If not, see <https://www.gnu.org/licenses/>.
18 */
19
20 #include <config.h>
21
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <stdbool.h>
25
26 #include <wget.h>
27 #include "private.h"
28
29 /**
30 * \file
31 * \brief Functions for bitmap
32 * \defgroup libwget-bitmap Bitmap management functions
33 *
34 * @{
35 *
36 * Bitmap (bit array) implementation.
37 *
38 * This is useful when you need a bitmap with more than 64 bits. Up to 64 bits you can
39 * use the C99 uint64_t as a standard C bitfield.
40 *
41 * As a usage example, Wget2 uses bitmaps for options with lists of HTTP status codes, which have values
42 * of 100-699.
43 *
44 */
45
46 #define bitmap_type uint64_t
47 #define bitmap_bits (sizeof(bitmap_type) * 8)
48 #define bitmap_shift 6 // ln(bitmap_bits)/ln(2)
49
50 #define map(n) (((wget_bitmap *)b)->map[(n) >> bitmap_shift])
51 #define bit(n) (((bitmap_type) 1) << ((n) & (bitmap_bits - 1)))
52
53 struct wget_bitmap_st {
54 bitmap_type
55 bits;
56 bitmap_type
57 map[];
58 };
59
60 /**
61 * \param b Bitmap to act on
62 * \param n Number of the bit to set (0-...)
63 *
64 * Set the bit \p n in the bitmap \p b.
65 */
66
wget_bitmap_set(wget_bitmap * b,unsigned n)67 void wget_bitmap_set(wget_bitmap *b, unsigned n)
68 {
69 if (b && n < ((wget_bitmap *) b)->bits)
70 map(n) |= bit(n);
71 }
72
73 /**
74 * \param b Bitmap to act on
75 * \param n Number of the bit to clear (0-...)
76 *
77 * Clear the bit \p n in the bitmap \p b.
78 */
wget_bitmap_clear(wget_bitmap * b,unsigned n)79 void wget_bitmap_clear(wget_bitmap *b, unsigned n)
80 {
81 if (b && n < ((wget_bitmap *) b)->bits)
82 map(n) &= ~bit(n);
83 }
84
85 /**
86 * \param[in] b Bitmap to read from
87 * \param[in] n Number of the bit of interest (0-...)
88 * \return
89 * 0 if bit \p n is cleared or if \p n is out of range
90 * 1 if bit \p is set
91 *
92 * Returns whether the bit \p n is set or not.
93 */
wget_bitmap_get(const wget_bitmap * b,unsigned n)94 bool wget_bitmap_get(const wget_bitmap *b, unsigned n)
95 {
96 if (b && n < ((wget_bitmap *) b)->bits)
97 return (map(n) & bit(n)) != 0;
98
99 return 0;
100 }
101
102 /**
103 * \param[out] b Pointer to the allocated bitmap
104 * \param[in] bits Number of bits
105 * \return A \ref wget_error value
106 *
107 * Allocates a bitmap with a capacity of \p bits.
108 * It must be freed by wget_bitmap_free() after usage.
109 */
wget_bitmap_init(wget_bitmap ** b,unsigned bits)110 int wget_bitmap_init(wget_bitmap **b, unsigned bits)
111 {
112 if (!b)
113 return WGET_E_INVALID;
114
115 wget_bitmap *_b =
116 wget_calloc((bits + sizeof(bitmap_type) - 1) / sizeof(bitmap_type) + 1, sizeof(bitmap_type));
117
118 if (!_b)
119 return WGET_E_MEMORY;
120
121 _b->bits = bits;
122 *b = _b;
123
124 return WGET_E_SUCCESS;
125 }
126
127 /**
128 * \param[in] b Pointer to bitmap to free
129 *
130 * Frees and clears the bitmap pointed to by \p b.
131 */
wget_bitmap_free(wget_bitmap ** b)132 void wget_bitmap_free(wget_bitmap **b)
133 {
134 if (b)
135 xfree(*b);
136 }
137
138 /** @} */
139