bitmap.c

/*
 * Copyright (c) 2000, 2001, 2002
 *      The President and Fellows of Harvard College.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * Fixed-size array of bits. (Intended for storage management.)
 */

#include <types.h>
#include <kern/errno.h>
#include <lib.h>
#include <bitmap.h>

/*
 * It would be a lot more efficient on most platforms to use uint32_t
 * or unsigned long as the base type for holding bits. But we don't,
 * because if one uses any data type more than a single byte wide,
 * bitmap data saved on disk becomes endian-dependent, which is a
 * severe nuisance.
 */
#define BITS_PER_WORD   (CHAR_BIT)
#define WORD_TYPE       unsigned char
#define WORD_ALLBITS    (0xff)

struct bitmap {
        unsigned nbits;
        WORD_TYPE *v;
};


struct bitmap *
bitmap_create(unsigned nbits)
{
        struct bitmap *b; 
        unsigned words;

        words = DIVROUNDUP(nbits, BITS_PER_WORD);
        b = kmalloc(sizeof(struct bitmap));
        if (b == NULL) {
                return NULL;
        }
        b->v = kmalloc(words*sizeof(WORD_TYPE));
        if (b->v == NULL) {
                kfree(b);
                return NULL;
        }

        bzero(b->v, words*sizeof(WORD_TYPE));
        b->nbits = nbits;

        /* Mark any leftover bits at the end in use */
        if (words > nbits / BITS_PER_WORD) {
                unsigned j, ix = words-1;
                unsigned overbits = nbits - ix*BITS_PER_WORD;

                KASSERT(nbits / BITS_PER_WORD == words-1);
                KASSERT(overbits > 0 && overbits < BITS_PER_WORD);
                
                for (j=overbits; j<BITS_PER_WORD; j++) {
                        b->v[ix] |= ((WORD_TYPE)1 << j);
                }
        }

        return b;
}

void *
bitmap_getdata(struct bitmap *b)
{
        return b->v;
}

int
bitmap_alloc(struct bitmap *b, unsigned *index)
{
        unsigned ix;
        unsigned maxix = DIVROUNDUP(b->nbits, BITS_PER_WORD);
        unsigned offset;

        for (ix=0; ix<maxix; ix++) {
                if (b->v[ix]!=WORD_ALLBITS) {
                        for (offset = 0; offset < BITS_PER_WORD; offset++) {
                                WORD_TYPE mask = ((WORD_TYPE)1) << offset;

                                if ((b->v[ix] & mask)==0) {
                                        b->v[ix] |= mask;
                                        *index = (ix*BITS_PER_WORD)+offset;
                                        KASSERT(*index < b->nbits);
                                        return 0;
                                }
                        }
                        KASSERT(0);
                }
        }
        return ENOSPC;
}

static
inline
void
bitmap_translate(unsigned bitno, unsigned *ix, WORD_TYPE *mask)
{
        unsigned offset;
        *ix = bitno / BITS_PER_WORD;
        offset = bitno % BITS_PER_WORD;
        *mask = ((WORD_TYPE)1) << offset;
}

void
bitmap_mark(struct bitmap *b, unsigned index)
{
        unsigned ix;
        WORD_TYPE mask;

        KASSERT(index < b->nbits);
        bitmap_translate(index, &ix, &mask);

        KASSERT((b->v[ix] & mask)==0);
        b->v[ix] |= mask;
}

void
bitmap_unmark(struct bitmap *b, unsigned index)
{
        unsigned ix;
        WORD_TYPE mask;

        KASSERT(index < b->nbits);
        bitmap_translate(index, &ix, &mask);

        KASSERT((b->v[ix] & mask)!=0);
        b->v[ix] &= ~mask;
}


int
bitmap_isset(struct bitmap *b, unsigned index) 
{
        unsigned ix;
        WORD_TYPE mask;

        bitmap_translate(index, &ix, &mask);
        return (b->v[ix] & mask);
}

void
bitmap_destroy(struct bitmap *b)
{
        kfree(b->v);
        kfree(b);
}