1 /*-
2 * Copyright (C) 1996
3 * David L. Nugent. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY DAVID L. NUGENT AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL DAVID L. NUGENT OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: src/usr.sbin/pw/bitmap.c,v 1.5 1999/08/28 01:19:15 peter Exp $
27 * $DragonFly: src/usr.sbin/pw/bitmap.c,v 1.2 2003/06/17 04:30:01 dillon Exp $
28 */
29
30 #include <stdlib.h>
31 #include <string.h>
32
33 #include "bitmap.h"
34
35 struct bitmap
bm_alloc(int size)36 bm_alloc(int size)
37 {
38 struct bitmap bm;
39 int szmap = (size / 8) + !!(size % 8);
40
41 bm.size = size;
42 bm.map = malloc(szmap);
43 if (bm.map)
44 memset(bm.map, 0, szmap);
45 return bm;
46 }
47
48 void
bm_dealloc(struct bitmap * bm)49 bm_dealloc(struct bitmap * bm)
50 {
51 if (bm->map)
52 free(bm->map);
53 }
54
55 static void
bm_getmask(int * pos,unsigned char * bmask)56 bm_getmask(int *pos, unsigned char *bmask)
57 {
58 *bmask = (unsigned char) (1 << (*pos % 8));
59 *pos /= 8;
60 }
61
62 void
bm_setbit(struct bitmap * bm,int pos)63 bm_setbit(struct bitmap * bm, int pos)
64 {
65 unsigned char bmask;
66
67 bm_getmask(&pos, &bmask);
68 bm->map[pos] |= bmask;
69 }
70
71 void
bm_clrbit(struct bitmap * bm,int pos)72 bm_clrbit(struct bitmap * bm, int pos)
73 {
74 unsigned char bmask;
75
76 bm_getmask(&pos, &bmask);
77 bm->map[pos] &= ~bmask;
78 }
79
80 int
bm_isset(struct bitmap * bm,int pos)81 bm_isset(struct bitmap * bm, int pos)
82 {
83 unsigned char bmask;
84
85 bm_getmask(&pos, &bmask);
86 return !!(bm->map[pos] & bmask);
87 }
88
89 int
bm_firstunset(struct bitmap * bm)90 bm_firstunset(struct bitmap * bm)
91 {
92 int szmap = (bm->size / 8) + !!(bm->size % 8);
93 int at = 0;
94 int pos = 0;
95
96 while (pos < szmap) {
97 unsigned char bmv = bm->map[pos++];
98 unsigned char bmask = 1;
99
100 while (bmask & 0xff) {
101 if ((bmv & bmask) == 0)
102 return at;
103 bmask <<= 1;
104 ++at;
105 }
106 }
107 return at;
108 }
109
110 int
bm_lastset(struct bitmap * bm)111 bm_lastset(struct bitmap * bm)
112 {
113 int szmap = (bm->size / 8) + !!(bm->size % 8);
114 int at = 0;
115 int pos = 0;
116 int ofs = 0;
117
118 while (pos < szmap) {
119 unsigned char bmv = bm->map[pos++];
120 unsigned char bmask = 1;
121
122 while (bmask & 0xff) {
123 if ((bmv & bmask) != 0)
124 ofs = at;
125 bmask <<= 1;
126 ++at;
127 }
128 }
129 return ofs;
130 }
131