2 * bitext.c: kernel little helper (of bit shuffling variety).
4 * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com>
6 * The algorithm to search a zero bit string is geared towards its application.
7 * We expect a couple of fixed sizes of requests, so a rotating counter, reset
8 * by align size, should provide fast enough search while maintaining low
12 #include <linux/smp_lock.h>
13 #include <linux/bitops.h>
15 #include <asm/bitext.h>
18 * bit_map_string_get - find and set a bit string in bit map.
20 * @len: requested string length
21 * @align: requested alignment
23 * Returns offset in the map or -1 if out of space.
25 * Not safe to call from an interrupt (uses spin_lock).
27 int bit_map_string_get(struct bit_map *t, int len, int align)
29 int offset, count; /* siamese twins */
37 if ((align & align1) != 0)
39 if (align < 0 || align >= t->size)
41 if (len <= 0 || len > t->size)
45 if (len < t->last_size)
46 offset = t->first_free;
48 offset = t->last_off & ~align1;
51 off_new = find_next_zero_bit(t->map, t->size, offset);
52 off_new = (off_new + align1) & ~align1;
53 count += off_new - offset;
55 if (offset >= t->size)
57 if (count + len > t->size) {
58 spin_unlock(&t->lock);
59 /* P3 */ printk(KERN_ERR
60 "bitmap out: size %d used %d off %d len %d align %d count %d\n",
61 t->size, t->used, offset, len, align, count);
65 if (offset + len > t->size) {
66 count += t->size - offset;
72 while (test_bit(offset + i, t->map) == 0) {
75 for (i = 0; i < len; i++)
76 __set_bit(offset + i, t->map);
77 if (offset == t->first_free)
78 t->first_free = find_next_zero_bit
81 if ((t->last_off = offset + len) >= t->size)
85 spin_unlock(&t->lock);
90 if ((offset += i + 1) >= t->size)
95 void bit_map_clear(struct bit_map *t, int offset, int len)
100 BUG(); /* Much too late to do any good, but alas... */
102 for (i = 0; i < len; i++) {
103 if (test_bit(offset + i, t->map) == 0)
105 __clear_bit(offset + i, t->map);
107 if (offset < t->first_free)
108 t->first_free = offset;
110 spin_unlock(&t->lock);
113 void bit_map_init(struct bit_map *t, unsigned long *map, int size)
116 if ((size & 07) != 0)
118 memset(map, 0, size>>3);
120 memset(t, 0, sizeof *t);
121 spin_lock_init(&t->lock);