alarm: Do not hold the tchain lock during handlers
[akaros.git] / kern / src / find_next_bit.c
1 /* find_next_bit.c: fallback find next bit implementation
2  *
3  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells (dhowells@redhat.com)
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version
9  * 2 of the License, or (at your option) any later version.
10  */
11
12 #include <arch/arch.h>
13 #include <error.h>
14 #include <atomic.h>
15 #include <string.h>
16 #include <assert.h>
17 #include <bitops.h>
18 #include <bitmap.h>
19
20 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
21
22 /*
23  * Find the next set bit in a memory region.
24  */
25 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
26                             unsigned long offset)
27 {
28         const unsigned long *p = addr + BITOP_WORD(offset);
29         unsigned long result = offset & ~(BITS_PER_LONG-1);
30         unsigned long tmp;
31
32         if (offset >= size)
33                 return size;
34         size -= result;
35         offset %= BITS_PER_LONG;
36         if (offset) {
37                 tmp = *(p++);
38                 tmp &= (~0UL << offset);
39                 if (size < BITS_PER_LONG)
40                         goto found_first;
41                 if (tmp)
42                         goto found_middle;
43                 size -= BITS_PER_LONG;
44                 result += BITS_PER_LONG;
45         }
46         while (size & ~(BITS_PER_LONG-1)) {
47                 if ((tmp = *(p++)))
48                         goto found_middle;
49                 result += BITS_PER_LONG;
50                 size -= BITS_PER_LONG;
51         }
52         if (!size)
53                 return result;
54         tmp = *p;
55
56 found_first:
57         tmp &= (~0UL >> (BITS_PER_LONG - size));
58         if (tmp == 0UL)         /* Are any bits set? */
59                 return result + size;   /* Nope. */
60 found_middle:
61         return result + __ffs(tmp);
62 }
63
64 /*
65  * This implementation of find_{first,next}_zero_bit was stolen from
66  * Linus' asm-alpha/bitops.h.
67  */
68 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
69                                  unsigned long offset)
70 {
71         const unsigned long *p = addr + BITOP_WORD(offset);
72         unsigned long result = offset & ~(BITS_PER_LONG-1);
73         unsigned long tmp;
74
75         if (offset >= size)
76                 return size;
77         size -= result;
78         offset %= BITS_PER_LONG;
79         if (offset) {
80                 tmp = *(p++);
81                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
82                 if (size < BITS_PER_LONG)
83                         goto found_first;
84                 if (~tmp)
85                         goto found_middle;
86                 size -= BITS_PER_LONG;
87                 result += BITS_PER_LONG;
88         }
89         while (size & ~(BITS_PER_LONG-1)) {
90                 if (~(tmp = *(p++)))
91                         goto found_middle;
92                 result += BITS_PER_LONG;
93                 size -= BITS_PER_LONG;
94         }
95         if (!size)
96                 return result;
97         tmp = *p;
98
99 found_first:
100         tmp |= ~0UL << size;
101         if (tmp == ~0UL)        /* Are any bits zero? */
102                 return result + size;   /* Nope. */
103 found_middle:
104         return result + ffz(tmp);
105 }
106
107 /*
108  * Find the first set bit in a memory region.
109  */
110 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
111 {
112         const unsigned long *p = addr;
113         unsigned long result = 0;
114         unsigned long tmp;
115
116         while (size & ~(BITS_PER_LONG-1)) {
117                 if ((tmp = *(p++)))
118                         goto found;
119                 result += BITS_PER_LONG;
120                 size -= BITS_PER_LONG;
121         }
122         if (!size)
123                 return result;
124
125         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
126         if (tmp == 0UL)         /* Are any bits set? */
127                 return result + size;   /* Nope. */
128 found:
129         return result + __ffs(tmp);
130 }
131
132 /*
133  * Find the first cleared bit in a memory region.
134  */
135 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
136 {
137         const unsigned long *p = addr;
138         unsigned long result = 0;
139         unsigned long tmp;
140
141         while (size & ~(BITS_PER_LONG-1)) {
142                 if (~(tmp = *(p++)))
143                         goto found;
144                 result += BITS_PER_LONG;
145                 size -= BITS_PER_LONG;
146         }
147         if (!size)
148                 return result;
149
150         tmp = (*p) | (~0UL << size);
151         if (tmp == ~0UL)        /* Are any bits zero? */
152                 return result + size;   /* Nope. */
153 found:
154         return result + ffz(tmp);
155 }
156