3 * oFono - Open Source Telephony
5 * Copyright (C) 2008-2011 Intel Corporation. All rights reserved.
6 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 as
10 * published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
34 #define BITS_PER_LONG (sizeof(unsigned long) * 8)
43 static inline int ffz(unsigned long word)
45 return __builtin_ctzl(~word);
49 * Stolen from linux kernel lib/find_next_bit.c
51 static unsigned int find_next_zero_bit(const unsigned long *addr,
55 const unsigned long *p = addr + offset / BITS_PER_LONG;
56 unsigned int result = offset & ~(BITS_PER_LONG-1);
63 offset %= BITS_PER_LONG;
67 tmp |= ~0UL >> (BITS_PER_LONG - offset);
69 if (size < BITS_PER_LONG)
75 size -= BITS_PER_LONG;
76 result += BITS_PER_LONG;
79 while (size & ~(BITS_PER_LONG-1)) {
83 size -= BITS_PER_LONG;
84 result += BITS_PER_LONG;
95 if (tmp == ~0UL) /* Are any bits zero? */
96 return result + size; /* Nope. */
99 return result + ffz(tmp);
102 struct idmap *idmap_new_from_range(unsigned int min, unsigned int max)
104 struct idmap *ret = g_new0(struct idmap, 1);
105 unsigned int size = max - min + 1;
107 ret->bits = g_new0(unsigned long,
108 (size + BITS_PER_LONG - 1) / BITS_PER_LONG);
116 struct idmap *idmap_new(unsigned int size)
118 return idmap_new_from_range(1, size);
121 void idmap_free(struct idmap *idmap)
127 void idmap_put(struct idmap *idmap, unsigned int id)
129 unsigned int offset = (id - idmap->min) / BITS_PER_LONG;
133 if (id > idmap->size)
138 idmap->bits[offset] &= ~(1 << id);
141 unsigned int idmap_alloc(struct idmap *idmap)
146 bit = find_next_zero_bit(idmap->bits, idmap->size, 0);
148 if (bit >= idmap->size)
149 return idmap->max + 1;
151 offset = bit / BITS_PER_LONG;
152 idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
154 return bit + idmap->min;
157 void idmap_take(struct idmap *idmap, unsigned int id)
159 unsigned int bit = id - idmap->min;
162 if (bit >= idmap->size)
165 offset = bit / BITS_PER_LONG;
166 idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
170 * Allocate the next bit skipping the ids up to and including last. If there
171 * is no free ids until the max id is encountered, the counter is wrapped back
172 * to min and the search starts again.
174 unsigned int idmap_alloc_next(struct idmap *idmap, unsigned int last)
179 if (last < idmap->min || last > idmap->max)
180 return idmap->max + 1;
182 bit = find_next_zero_bit(idmap->bits, idmap->size,
183 last - idmap->min + 1);
185 if (bit >= idmap->size)
186 return idmap_alloc(idmap);
188 offset = bit / BITS_PER_LONG;
189 idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
191 return bit + idmap->min;
194 unsigned int idmap_get_min(struct idmap *idmap)
199 unsigned int idmap_get_max(struct idmap *idmap)