libisdn
|
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 }