libisdn
bitmap.c
Go to the documentation of this file.
00001 /*
00002  *
00003  *
00004  */
00005 #ifdef HAVE_CONFIG_H
00006 #include "config.h"
00007 #endif
00008 
00009 #include <stdio.h>
00010 #include <stdlib.h>
00011 #include <string.h>
00012 
00013 #include "common.h"
00014 #include "bitmap.h"
00015 
00016 #define BITMAP_GET(m, b)        (!!((m)[BITMAP_OFFSET(b)] & (1 << BITMAP_BIT(b))))
00017 #define BITMAP_SET(m, b)        ((m)[BITMAP_OFFSET(b)] |= (1 << BITMAP_BIT(b)))
00018 #define BITMAP_UNSET(m, b)      ((m)[BITMAP_OFFSET(b)] &= ~(1 << BITMAP_BIT(b)))
00019 
00020 
00021 //#define bitmap_debug(x, ...)          printf(x, __VA_ARGS__)
00022 #define bitmap_debug(x, ...)
00023 
00024 int bitmap_create(bitmap_t **bm, const int nbits)
00025 {
00026         int bytes = BITMAP_SIZE_BYTES(nbits);
00027 
00028         if (bm == NULL || nbits <= 0)
00029                 return -1;
00030         if ((*bm = calloc(1, bytes)) == NULL)
00031                 return -1;
00032         return 0;
00033 }
00034 
00035 int bitmap_destroy(bitmap_t *bm)
00036 {
00037         if (!bm)
00038                 return -1;
00039         free(bm);
00040         return 0;
00041 }
00042 
00043 int bitmap_init(bitmap_t *bm, const int nbits)
00044 {
00045         if (bm == NULL || nbits <= 0)
00046                 return -1;
00047         memset(bm, 0, BITMAP_SIZE_BYTES(nbits));
00048         return 0;
00049 }
00050 
00051 int bitmap_is_set(const bitmap_t *bm, const int nbits, const int pos)
00052 {
00053         if (!bm || nbits <= 0 || pos < 0 || pos >= nbits)
00054                 return -1;
00055         return BITMAP_GET(bm, pos);
00056 }
00057 
00058 int bitmap_set(bitmap_t *bm, const int nbits, const int pos)
00059 {
00060         if (!bm || nbits <= 0 || pos < 0 || pos >= nbits)
00061                 return -1;
00062         BITMAP_SET(bm, pos);
00063         return 0;
00064 }
00065 
00066 int bitmap_unset(bitmap_t *bm, const int nbits, const int pos)
00067 {
00068         if (!bm || nbits <= 0 || pos < 0 || pos >= nbits)
00069                 return -1;
00070         BITMAP_UNSET(bm, pos);
00071         return 0;
00072 }
00073 
00074 int bitmap_clear(bitmap_t *bm, const int nbits)
00075 {
00076         if (!bm || nbits <= 0)
00077                 return -1;
00078         memset(bm, 0, BITMAP_SIZE_BYTES(nbits));
00079         return 0;
00080 }
00081 
00082 int bitmap_is_empty(const bitmap_t *bm, const int nbits)
00083 {
00084         bitmap_t *p = (bitmap_t *)bm;
00085 
00086         for (int i = 0; i < BITMAP_SIZE_BYTES(nbits); i++)
00087                 if (*(p++)) return 0;
00088         return 1;
00089 }
00090 
00091 int bitmap_next_bit(const bitmap_t *bm, const int nbits, const int last)
00092 {
00093         bitmap_t *ptr = NULL;
00094         bitmap_t mask = 0;
00095 
00096         if (!bm || !nbits)
00097                 return -1;
00098         if (!(last >= -1 || last < nbits))
00099                 return -1;
00100 
00101         ptr  = (bitmap_t *)&bm[BITMAP_OFFSET(last + 1)];
00102         mask = (~0ul) << BITMAP_BIT(last + 1);
00103 
00104         bitmap_debug("starting new search at last %d, mask %#lx (row %d)\n", last, mask, BITMAP_OFFSET(last + 1));
00105 
00106         for (int i = last + 1; i < nbits;) {
00107                 bitmap_debug("%d/%d: last %d, mask %#lx, bm[%d] = %#lx\n", i, nbits, last, mask, BITMAP_OFFSET(i), bm[BITMAP_OFFSET(i)]);
00108                 /* nothing in this row left? skip */
00109                 if ((*ptr & mask) == 0) {
00110                         i += BITS_PER_LONG - BITMAP_BIT(i);
00111                         mask = ~0ul;
00112                         ptr++;
00113                         bitmap_debug("remaining row empty, fast forwarding to %d/%d\n", i, nbits);
00114                         continue;
00115                 }
00116                 if ((*ptr & (1ul << BITMAP_BIT(i))) != 0) {
00117                         bitmap_debug("%d/%d found bit %d\n", i, nbits, i);
00118                         return i;
00119                 }
00120                 if (BITMAP_BIT(++i) == 0)
00121                         ptr++;
00122         }
00123         return -1;
00124 }
00125 
00126 int bitmap_first_bit(const bitmap_t *bm, const int nbits)
00127 {
00128         return bitmap_next_bit(bm, nbits, -1);
00129 }
00130 
00131 int bitmap_count(const bitmap_t *bm, const int nbits)
00132 {
00133         int count = 0;
00134 
00135         for (int i = bitmap_first_bit(bm, nbits); i >= 0; i = bitmap_next_bit(bm, nbits, i)) count++;
00136 
00137         return count;
00138 }
00139 
00140 int bitmap_dump(const bitmap_t *bm, const int nbits)
00141 {
00142         if (!bm || nbits <= 0)
00143                 return -1;
00144 
00145         for (int i = 0; i < BITMAP_SIZE(nbits); i++)
00146                 printf("map[%05d]: %#lx\n", i, bm[i]);
00147 
00148         return 0;
00149 }