00001 #ifndef LIBNAGIOS_bitmap_h__ 00002 #define LIBNAGIOS_bitmap_h__ 00003 00004 /** 00005 * @file bitmap.h 00006 * @brief Bit map API 00007 * 00008 * The bitmap api is useful for running set operations on objects 00009 * indexed by unsigned integers. 00010 * @{ 00011 */ 00012 struct bitmap; 00013 typedef struct bitmap bitmap; 00014 00015 /** 00016 * Resize a bitmap 00017 * If the bitmap is made smaller, data will silently be lost. 00018 * 00019 * @param bm The bitmap to resize 00020 * @param size The new desired size of the bitmap 00021 * @return 0 on success, -1 on errors. 00022 */ 00023 extern int bitmap_resize(bitmap *bm, unsigned long size); 00024 00025 /** 00026 * Create a bitmaptor of size 'size' 00027 * @param size Desired storage capacity 00028 * @return A bitmap pointer on success, NULL on errors 00029 */ 00030 extern bitmap *bitmap_create(unsigned long size); 00031 00032 /** 00033 * Destroy a bitmaptor by freeing all the memory it uses 00034 * @param bm The bitmaptor to destroy 00035 */ 00036 extern void bitmap_destroy(bitmap *bm); 00037 00038 /** 00039 * Copy a bitmaptor 00040 * @param bm The bitmaptor to copy 00041 * @return Pointer to an identical bitmap on success, NULL on errors 00042 */ 00043 extern bitmap *bitmap_copy(const bitmap *bm); 00044 00045 /** 00046 * Set a bit in the map 00047 * @param bm The bitmaptor to operate on 00048 * @param pos Position of the bit to set 00049 * @return 0 on success, -1 on errors 00050 */ 00051 extern int bitmap_set(bitmap *bm, unsigned long pos); 00052 00053 /** 00054 * Check if a particular bit is set in the map 00055 * @param bm The bitmaptor to check 00056 * @param pos Position of the bit to check 00057 * @return 1 if set, otherwise 0 00058 */ 00059 extern int bitmap_isset(const bitmap *bm, unsigned long pos); 00060 00061 /** 00062 * Unset a particular bit in the map 00063 * @param bm The bitmaptor to operate on 00064 * @param pos Position of the bit to unset 00065 */ 00066 extern int bitmap_unset(bitmap *bm, unsigned long pos); 00067 00068 /** 00069 * Obtain cardinality (max number of elements) of the bitmaptor 00070 * @param bm The bitmaptor to check 00071 * @return The cardinality of the bitmaptor 00072 */ 00073 extern unsigned long bitmap_cardinality(const bitmap *bm); 00074 #define bitmap_size bitmap_cardinality 00075 00076 /** 00077 * Count set bits in map. Completed in O(n/8) time. 00078 * @param bm The bitmaptor to count bits in 00079 * @return The number of set bits 00080 */ 00081 extern unsigned long bitmap_count_set_bits(const bitmap *bm); 00082 00083 /** 00084 * Count unset bits in map. Completed in O(n/8) time. 00085 * @param bm The bitmaptor to count bits in 00086 * @return The number of set bits 00087 */ 00088 extern unsigned long bitmap_count_unset_bits(const bitmap *bm); 00089 00090 /** 00091 * Unset all bits in a bitmap 00092 * @param bm The bitmap to clear 00093 */ 00094 extern void bitmap_clear(bitmap *bm); 00095 00096 /** 00097 * Calculate intersection of two bitmaps 00098 * The intersection is defined as all bits that are members of 00099 * both A and B. It's equivalent to bitwise AND. 00100 * This function completes in O(n/sizeof(long)) operations. 00101 * @param a The first bitmaptor 00102 * @param b The second bitmaptor 00103 * @return NULL on errors; A newly created bitmaptor on success. 00104 */ 00105 extern bitmap *bitmap_intersect(const bitmap *a, const bitmap *b); 00106 00107 /** 00108 * Calculate union of two bitmaps 00109 * The union is defined as all bits that are members of 00110 * A or B or both A and B. It's equivalent to bitwise OR. 00111 * This function completes in O(n/sizeof(long)) operations. 00112 * @param a The first bitmaptor 00113 * @param b The second bitmaptor 00114 * @return NULL on errors; A newly created bitmaptor on success. 00115 */ 00116 extern bitmap *bitmap_union(const bitmap *a, const bitmap *b); 00117 00118 /** 00119 * Calculate union of two bitmaps and store result in one of them 00120 * @param res The first bitmap 00121 * @param addme The bitmap to unite to the first bitmap 00122 * @return NULL on errors, res on success 00123 */ 00124 extern bitmap *bitmap_unite(bitmap *res, const bitmap *addme); 00125 00126 /** 00127 * Calculate set difference between two bitmaps 00128 * The set difference of A / B is defined as all members of A 00129 * that isn't members of B. Note that parameter ordering matters 00130 * for this function. 00131 * This function completes in O(n/sizeof(long)) operations. 00132 * @param a The first bitmaptor (numerator) 00133 * @param b The first bitmaptor (denominator) 00134 * @return NULL on errors; A newly created bitmaptor on success. 00135 */ 00136 extern bitmap *bitmap_diff(const bitmap *a, const bitmap *b); 00137 00138 /** 00139 * Calculate symmetric difference between two bitmaps 00140 * The symmetric difference between A and B is the set that 00141 * contains all elements in either set but not in both. 00142 * This function completes in O(n/sizeof(long)) operations. 00143 * @param a The first bitmaptor 00144 * @param b The second bitmaptor 00145 */ 00146 extern bitmap *bitmap_symdiff(const bitmap *a, const bitmap *b); 00147 00148 /** 00149 * Compare two bitmaps for equality 00150 * @param a The first bitmaptor 00151 * @param b The other bitmaptor 00152 * @return Similar to memcmp(), with tiebreaks determined by cardinality 00153 */ 00154 extern int bitmap_cmp(const bitmap *a, const bitmap *b); 00155 /** @} */ 00156 #endif /* LIBNAGIOS_bitmap_h__ */
1.5.6