pw/bitmap.c

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