1 /* $OpenBSD: bitmap.h,v 1.1 2022/09/08 18:16:26 mglocker Exp $ */
2
3 /*
4 * Copyright 2004 Eric Anholt
5 * All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the next
15 * paragraph) shall be included in all copies or substantial portions of the
16 * Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21 * VA LINUX SYSTEMS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 */
26
27 static inline void
__clear_bit(u_int b,volatile void * p)28 __clear_bit(u_int b, volatile void *p)
29 {
30 volatile u_int *ptr = (volatile u_int *)p;
31 ptr[b >> 5] &= ~(1 << (b & 0x1f));
32 }
33
34 static inline void
__set_bit(u_int b,volatile void * p)35 __set_bit(u_int b, volatile void *p)
36 {
37 volatile u_int *ptr = (volatile u_int *)p;
38 ptr[b >> 5] |= (1 << (b & 0x1f));
39 }
40
41 static inline int
find_next_zero_bit(volatile void * p,int max,int b)42 find_next_zero_bit(volatile void *p, int max, int b)
43 {
44 volatile u_int *ptr = (volatile u_int *)p;
45
46 for (; b < max; b += 32) {
47 if (ptr[b >> 5] != ~0) {
48 for (;;) {
49 if ((ptr[b >> 5] & (1 << (b & 0x1f))) == 0)
50 return b;
51 b++;
52 }
53 }
54 }
55 return max;
56 }
57
58 static inline int
find_next_bit(volatile void * p,int max,int b)59 find_next_bit(volatile void *p, int max, int b)
60 {
61 volatile u_int *ptr = (volatile u_int *)p;
62
63 for (; b < max; b+= 32) {
64 if (ptr[b >> 5] != 0) {
65 for (;;) {
66 if (ptr[b >> 5] & (1 << (b & 0x1f)))
67 return b;
68 b++;
69 }
70 }
71 }
72 return max;
73 }
74
75 /*
76 * Copyright (c) 2013, 2014, 2015 Mark Kettenis
77 *
78 * Permission to use, copy, modify, and distribute this software for any
79 * purpose with or without fee is hereby granted, provided that the above
80 * copyright notice and this permission notice appear in all copies.
81 *
82 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
83 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
84 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
85 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
86 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
87 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
88 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
89 */
90
91 static inline void
bitmap_set(void * p,int b,u_int n)92 bitmap_set(void *p, int b, u_int n)
93 {
94 u_int end = b + n;
95
96 for (; b < end; b++)
97 __set_bit(b, p);
98 }
99
100 static inline void
bitmap_clear(void * p,int b,u_int n)101 bitmap_clear(void *p, int b, u_int n)
102 {
103 u_int end = b + n;
104
105 for (; b < end; b++)
106 __clear_bit(b, p);
107 }
108
109 static inline u_long
bitmap_find_next_zero_area_off(void * p,u_long size,u_long start,u_long n,u_long align_mask,u_long align_offset)110 bitmap_find_next_zero_area_off(void *p, u_long size, u_long start, u_long n,
111 u_long align_mask, u_long align_offset)
112 {
113 u_long index, end, i;
114
115 while (1) {
116 index = (((find_next_zero_bit(p, size, start) +
117 align_offset) + align_mask) & ~align_mask) - align_offset;
118
119 end = index + n;
120 if (end > size)
121 return end;
122
123 i = find_next_bit(p, end, index);
124 if (i >= end)
125 break;
126 start = i + 1;
127 }
128
129 return index;
130 }
131
132 static inline unsigned long
bitmap_find_next_zero_area(void * p,u_long size,u_long start,u_long n,u_long align_mask)133 bitmap_find_next_zero_area(void *p, u_long size, u_long start, u_long n,
134 u_long align_mask)
135 {
136 return bitmap_find_next_zero_area_off(p, size, start, n, align_mask, 0);
137 }
138