xref: /freebsd/share/man/man3/bitstring.3 (revision db33c6f3ae9d1231087710068ee4ea5398aacca7)
1.\" Copyright (c) 1989, 1991, 1993
2.\"	The Regents of the University of California.  All rights reserved.
3.\"
4.\" This code is derived from software contributed to Berkeley by
5.\" Paul Vixie.
6.\" Redistribution and use in source and binary forms, with or without
7.\" modification, are permitted provided that the following conditions
8.\" are met:
9.\" 1. Redistributions of source code must retain the above copyright
10.\"    notice, this list of conditions and the following disclaimer.
11.\" 2. Redistributions in binary form must reproduce the above copyright
12.\"    notice, this list of conditions and the following disclaimer in the
13.\"    documentation and/or other materials provided with the distribution.
14.\" 3. Neither the name of the University nor the names of its contributors
15.\"    may be used to endorse or promote products derived from this software
16.\"    without specific prior written permission.
17.\"
18.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28.\" SUCH DAMAGE.
29.\"
30.\" Copyright (c) 2014,2016 Spectra Logic Corporation
31.\" All rights reserved.
32.\"
33.\" Redistribution and use in source and binary forms, with or without
34.\" modification, are permitted provided that the following conditions
35.\" are met:
36.\" 1. Redistributions of source code must retain the above copyright
37.\"    notice, this list of conditions, and the following disclaimer,
38.\"    without modification.
39.\" 2. Redistributions in binary form must reproduce at minimum a disclaimer
40.\"    substantially similar to the "NO WARRANTY" disclaimer below
41.\"    ("Disclaimer") and any redistribution must be conditioned upon
42.\"    including a substantially similar Disclaimer requirement for further
43.\"    binary redistribution.
44.\"
45.\" NO WARRANTY
46.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
47.\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
48.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
49.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
50.\" HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
54.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
55.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
56.\" POSSIBILITY OF SUCH DAMAGES.
57.\"
58.Dd November 21, 2023
59.Dt BITSTRING 3
60.Os
61.Sh NAME
62.Nm bit_alloc ,
63.Nm bit_clear ,
64.Nm bit_count ,
65.Nm bit_decl ,
66.Nm bit_ffc ,
67.Nm bit_ffs ,
68.Nm bit_ff_at ,
69.Nm bit_ffc_at ,
70.Nm bit_ffs_at ,
71.Nm bit_ffc_area ,
72.Nm bit_ffs_area ,
73.Nm bit_ff_area_at ,
74.Nm bit_ffc_area_at ,
75.Nm bit_ffs_area_at ,
76.Nm bit_nclear ,
77.Nm bit_nset ,
78.Nm bit_ntest ,
79.Nm bit_set ,
80.Nm bit_test ,
81.Nm bitstr_size
82.Nd bit-string manipulation functions and macros
83.Sh SYNOPSIS
84.In bitstring.h
85.Ft bitstr_t *
86.Fn bit_alloc "size_t nbits"
87.Ft void
88.Fn bit_decl "bitstr_t *name" "size_t nbits"
89.Ft void
90.Fn bit_clear "bitstr_t *name" "size_t bit"
91.Ft void
92.Fn bit_count "bitstr_t *name" "size_t count" "size_t nbits" "ssize_t *value"
93.Ft void
94.Fn bit_ffc "bitstr_t *name" "size_t nbits" "ssize_t *value"
95.Ft void
96.Fn bit_ffs "bitstr_t *name" "size_t nbits" "ssize_t *value"
97.Ft void
98.Fn bit_ffc_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value"
99.Ft void
100.Fn bit_ffs_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value"
101.Ft void
102.Fn bit_ff_at "bitstr_t *name" "size_t start" "size_t nbits" "int match" "ssize_t *value"
103.Ft void
104.Fn bit_ffc_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value"
105.Ft void
106.Fn bit_ffs_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value"
107.Ft void
108.Fn bit_ffc_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value"
109.Ft void
110.Fn bit_ffs_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value"
111.Ft void
112.Fn bit_ff_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "int match" "ssize_t *value"
113.Fn bit_foreach "bitstr_t *name" "size_t nbits" "size_t var"
114.Fn bit_foreach_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var"
115.Fn bit_foreach_unset "bitstr_t *name" "size_t nbits" "size_t var"
116.Fn bit_foreach_unset_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var"
117.Ft void
118.Fn bit_nclear "bitstr_t *name" "size_t start" "size_t stop"
119.Ft void
120.Fn bit_nset "bitstr_t *name" "size_t start" "size_t stop"
121.Ft int
122.Fn bit_ntest "bitstr_t *name" "size_t start" "size_t stop" "int match"
123.Ft void
124.Fn bit_set "bitstr_t *name" "size_t bit"
125.Ft int
126.Fn bitstr_size "size_t nbits"
127.Ft int
128.Fn bit_test "bitstr_t *name" "size_t bit"
129.Sh DESCRIPTION
130These macros operate on strings of bits.
131.Pp
132The function
133.Fn bit_alloc
134returns a pointer of type
135.Dq Fa "bitstr_t *"
136to sufficient space to store
137.Fa nbits
138bits, or
139.Dv NULL
140if no space is available.
141If successful, the returned bit string is initialized with all bits cleared.
142.Pp
143The macro
144.Fn bit_decl
145declares a bit string with sufficient space to store
146.Fa nbits
147bits.
148.Fn bit_decl
149may be used to include statically sized bit strings in structure
150definitions or to create bit strings on the stack.
151Users of this macro are responsible for initialization of the bit string,
152typically via a global initialization of the containing struct or use of the
153.Fn bit_nset
154or
155.Fn bin_nclear
156functions.
157.Pp
158The macro
159.Fn bitstr_size
160returns the number of bytes necessary to store
161.Fa nbits
162bits.
163This is useful for copying bit strings.
164.Pp
165The functions
166.Fn bit_clear
167and
168.Fn bit_set
169clear or set the zero-based numbered bit
170.Fa bit ,
171in the bit string
172.Ar name .
173.Pp
174The
175.Fn bit_nset
176and
177.Fn bit_nclear
178functions
179set or clear the zero-based numbered bits from
180.Fa start
181through
182.Fa stop
183in the bit string
184.Ar name .
185.Pp
186The
187.Fn bit_test
188function
189evaluates to non-zero if the zero-based numbered bit
190.Fa bit
191of bit string
192.Fa name
193is set, and zero otherwise.
194.Pp
195The
196.Fn bit_ntest
197function
198evaluates to non-zero if the zero-based numbered bits from
199.Fa start
200through
201.Fa stop
202in the bit string
203.Ar name
204all have the value
205.Ar match .
206.Pp
207The function
208.Fn bit_ffc
209stores in the location referenced by
210.Fa value
211the zero-based number of the first bit not set in the array of
212.Fa nbits
213bits referenced by
214.Fa name .
215If all bits are set, the location referenced by
216.Fa value
217is set to \-1.
218.Pp
219The
220.Fn bit_ffs
221function
222stores in the location referenced by
223.Fa value
224the zero-based number of the first bit set in the array of
225.Fa nbits
226bits referenced by
227.Fa name .
228If no bits are set, the location referenced by
229.Fa value
230is set to \-1.
231.Pp
232The function
233.Fn bit_ffc_at
234stores in the location referenced by
235.Fa value
236the zero-based number of the first bit not set in the array of
237.Fa nbits
238bits referenced by
239.Fa name ,
240at or after the zero-based bit index
241.Fa start .
242If all bits at or after
243.Fa start
244are set, the location referenced by
245.Fa value
246is set to \-1.
247.Pp
248The
249.Fn bit_ffs_at
250function
251stores in the location referenced by
252.Fa value
253the zero-based number of the first bit set in the array of
254.Fa nbits
255bits referenced by
256.Fa name ,
257at or after the zero-based bit index
258.Fa start .
259If no bits are set after
260.Fa start ,
261the location referenced by
262.Fa value
263is set to \-1.
264.Pp
265The
266.Fn bit_ff_at
267function
268stores in the location referenced by
269.Fa value
270the zero-based number of the first bit in the array of
271.Fa nbits
272bits referenced by
273.Fa name ,
274at or after the zero-based bit index
275.Fa start
276that has value
277.Fa match .
278If no bits after
279.Fa start
280match that value, the location referenced by
281.Fa value
282is set to \-1.
283.Pp
284The
285.Fn bit_ffc_area
286function stores in the location referenced by
287.Fa value
288the zero-based number of the first bit beginning a sequence of unset bits of
289at least
290.Fa size
291unset bits in the array of
292.Fa nbits
293bits referenced by
294.Fa name .
295If no sequence of contiguous unset bits of the specified
296.Fa size
297can be found, the location referenced by
298.Fa value
299is set to \-1.
300.Pp
301The
302.Fn bit_ffs_area
303function stores in the location referenced by
304.Fa value
305the zero-based number of the first bit beginning a sequence of set bits of
306at least
307.Fa size
308set bits in the array of
309.Fa nbits
310bits referenced by
311.Fa name .
312If no sequence of contiguous set bits of the specified
313.Fa size
314can be found, the location referenced by
315.Fa value
316is set to \-1.
317.Pp
318The
319.Fn bit_ffc_area_at
320function stores in the location referenced by
321.Fa value
322the zero-based number of the first bit beginning a sequence of unset bits of
323at least
324.Fa size
325unset bits in the array of
326.Fa nbits
327bits referenced by
328.Fa name ,
329at or after the zero-based bit index
330.Fa start .
331If no sequence of contiguous unset bits of the specified
332.Fa size
333can be found at or after
334.Fa start ,
335the location referenced by
336.Fa value
337is set to \-1.
338.Pp
339The
340.Fn bit_ffs_area_at
341function stores in the location referenced by
342.Fa value
343the zero-based number of the first bit beginning a sequence of set bits of
344at least
345.Fa size
346set bits in the array of
347.Fa nbits
348bits referenced by
349.Fa name ,
350at or after the zero-based bit index
351.Fa start .
352If no sequence of contiguous set bits of the specified
353.Fa size
354can be found at or after
355.Fa start ,
356the location referenced by
357.Fa value
358is set to \-1.
359.Pp
360The
361.Fn bit_ff_area_at
362function stores in the location referenced by
363.Fa value
364the zero-based number of the first bit beginning a sequence of bits of
365at least
366.Fa size
367bits in the array of
368.Fa nbits
369bits referenced by
370.Fa name ,
371at or after the zero-based bit index
372.Fa start
373in which all bits have the value
374.Fa match .
375If no sequence of contiguous such bits of the specified
376.Fa size
377can be found at or after
378.Fa start ,
379the location referenced by
380.Fa value
381is set to \-1.
382.Pp
383The
384.Fn bit_count
385function stores in the location referenced by
386.Fa value
387the number of bits set in the array of
388.Fa nbits
389bits referenced by
390.Fa name ,
391at or after the zero-based bit index
392.Fa start .
393.Pp
394The macro
395.Fn bit_foreach
396traverses all set bits in the array of
397.Fa nbits
398referenced by
399.Fa name
400in the forward direction, assigning each location in turn to
401.Fa var .
402.Pp
403The macro
404.Fn bit_foreach_at
405traverses all set bits in the array of
406.Fa nbits
407referenced by
408.Fa name
409in the forward direction at or after the zero-based bit index
410.Fa start ,
411assigning each location in turn to
412.Fa var .
413.Pp
414The macro
415.Fn bit_foreach_unset
416traverses all unset bits in the array of
417.Fa nbits
418referenced by
419.Fa name
420in the forward direction, assigning each location in turn to
421.Fa var .
422.Pp
423The macro
424.Fn bit_foreach_unset_at
425traverses all unset bits in the array of
426.Fa nbits
427referenced by
428.Fa name
429in the forward direction at or after the zero-based bit index
430.Fa start ,
431assigning each location in turn to
432.Fa var .
433.Pp
434The arguments in bit string macros are evaluated only once and may safely
435have side effects.
436.Sh EXAMPLES
437.Bd -literal -offset indent
438#include <limits.h>
439#include <bitstring.h>
440
441\&...
442#define	LPR_BUSY_BIT		0
443#define	LPR_FORMAT_BIT		1
444#define	LPR_DOWNLOAD_BIT	2
445\&...
446#define	LPR_AVAILABLE_BIT	9
447#define	LPR_MAX_BITS		10
448
449make_lpr_available()
450{
451	bitstr_t bit_decl(bitlist, LPR_MAX_BITS);
452	...
453	bit_nclear(bitlist, 0, LPR_MAX_BITS - 1);
454	...
455	if (!bit_test(bitlist, LPR_BUSY_BIT)) {
456		bit_clear(bitlist, LPR_FORMAT_BIT);
457		bit_clear(bitlist, LPR_DOWNLOAD_BIT);
458		bit_set(bitlist, LPR_AVAILABLE_BIT);
459	}
460}
461.Ed
462.Sh SEE ALSO
463.Xr malloc 3 ,
464.Xr bitset 9
465.Sh HISTORY
466The
467.Nm bitstring
468functions first appeared in
469.Bx 4.4 .
470