pw/bitmap.c

   1 /*-
   2  * Copyright (c) 1996 by David L. Nugent <davidn@blaze.net.au>.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer as
  10  *    the first lines of this file unmodified.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  * 3. All advertising materials mentioning features or use of this software
  15  *    must display the following acknowledgement:
  16  *      This product includes software developed by David L. Nugent.
  17  * 4. The name of the author may not be used to endorse or promote products
  18  *    derived from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE DAVID L. NUGENT ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL DAVID L. NUGENT BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  *      $Id$
  33  */
  34
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include "bitmap.h"
  39
  40 struct bitmap
  41 bm_alloc(int size)
  42 {
  43         struct bitmap   bm;
  44         int             szmap = (size / 8) + !!(size % 8);
  45
  46         bm.size = size;
  47         bm.map = malloc(szmap);
  48         if (bm.map)
  49                 memset(bm.map, 0, szmap);
  50         return bm;
  51 }
  52
  53 void
  54 bm_dealloc(struct bitmap * bm)
  55 {
  56         if (bm->map)
  57                 free(bm->map);
  58 }
  59
  60 static void
  61 bm_getmask(int *pos, unsigned char *bmask)
  62 {
  63         *bmask = (unsigned char) (1 << (*pos % 8));
  64         *pos /= 8;
  65 }
  66
  67 void
  68 bm_setbit(struct bitmap * bm, int pos)
  69 {
  70         unsigned char   bmask;
  71
  72         bm_getmask(&pos, &bmask);
  73         bm->map[pos] |= bmask;
  74 }
  75
  76 void
  77 bm_clrbit(struct bitmap * bm, int pos)
  78 {
  79         unsigned char   bmask;
  80
  81         bm_getmask(&pos, &bmask);
  82         bm->map[pos] &= ~bmask;
  83 }
  84
  85 int
  86 bm_isset(struct bitmap * bm, int pos)
  87 {
  88         unsigned char   bmask;
  89
  90         bm_getmask(&pos, &bmask);
  91         return !!(bm->map[pos] & bmask);
  92 }
  93
  94 int
  95 bm_firstunset(struct bitmap * bm)
  96 {
  97         int             szmap = (bm->size / 8) + !!(bm->size % 8);
  98         int             at = 0;
  99         int             pos = 0;
 100
 101         while (pos < szmap) {
 102                 unsigned char   bmv = bm->map[pos++];
 103                 unsigned char   bmask = 1;
 104
 105                 while (bmask & 0xff) {
 106                         if ((bmv & bmask) == 0)
 107                                 return at;
 108                         bmask <<= 1;
 109                         ++at;
 110                 }
 111         }
 112         return at;
 113 }
 114
 115 int
 116 bm_lastset(struct bitmap * bm)
 117 {
 118         int             szmap = (bm->size / 8) + !!(bm->size % 8);
 119         int             at = 0;
 120         int             pos = 0;
 121         int             ofs = 0;
 122
 123         while (pos < szmap) {
 124                 unsigned char   bmv = bm->map[pos++];
 125                 unsigned char   bmask = 1;
 126
 127                 while (bmask & 0xff) {
 128                         if ((bmv & bmask) != 0)
 129                                 ofs = at;
 130                         bmask <<= 1;
 131                         ++at;
 132                 }
 133         }
 134         return ofs;
 135 }