diff options
Diffstat (limited to 'mysys')
| -rw-r--r-- | mysys/Makefile.am | 2 | ||||
| -rw-r--r-- | mysys/my_bitmap.c | 244 |
2 files changed, 204 insertions, 42 deletions
diff --git a/mysys/Makefile.am b/mysys/Makefile.am index 6ec1e1ec40d..5ff682fbc80 100644 --- a/mysys/Makefile.am +++ b/mysys/Makefile.am @@ -39,7 +39,7 @@ libmysys_a_SOURCES = my_init.c my_getwd.c mf_getdate.c\ mf_format.c mf_same.c mf_dirname.c mf_fn_ext.c \ my_symlink.c my_symlink2.c \ mf_pack.c mf_unixpath.c mf_strip.c \ - mf_soundex.c mf_wcomp.c mf_wfile.c \ + mf_wcomp.c mf_wfile.c \ mf_qsort.c mf_qsort2.c mf_sort.c \ ptr_cmp.c mf_radix.c queues.c \ tree.c list.c hash.c array.c string.c typelib.c \ diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index 8834dda98e1..336bf27d559 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -16,7 +16,18 @@ /* Handling of uchar arrays as large bitmaps. - We assume that the size of the used bitmap is less than ~(uint) 0 + + API limitations (or, rather asserted safety assumptions, + to encourage correct programming) + + * the size of the used bitmap is less than ~(uint) 0 + * it's a multiple of 8 (for efficiency reasons) + * when arguments are a bitmap and a bit number, the number + must be within bitmap size + * bitmap_set_prefix() is an exception - one can use ~0 to set all bits + * when both arguments are bitmaps, they must be of the same size + * bitmap_intersect() is an exception :) + (for for Bitmap::intersect(ulonglong map2buff)) TODO: Make assembler THREAD safe versions of these using test-and-set instructions @@ -27,67 +38,73 @@ #include <assert.h> #include <m_string.h> -inline void bitmap_lock(MY_BITMAP* map) +inline void bitmap_lock(MY_BITMAP *map) { #ifdef THREAD - if (map->thread_safe) - pthread_mutex_lock(&map->mutex); + if (map->mutex) + pthread_mutex_lock(map->mutex); #endif } -inline void bitmap_unlock(MY_BITMAP* map) +inline void bitmap_unlock(MY_BITMAP *map) { #ifdef THREAD - if (map->thread_safe) - pthread_mutex_unlock(&map->mutex); + if (map->mutex) + pthread_mutex_unlock(map->mutex); #endif } -my_bool bitmap_init(MY_BITMAP *map, uint bitmap_size, my_bool thread_safe) +my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe) { - if (!(map->bitmap=(uchar*) my_malloc((bitmap_size+7)/8, - MYF(MY_WME | MY_ZEROFILL)))) + DBUG_ASSERT((bitmap_size & 7) == 0); + bitmap_size/=8; + if (!(map->bitmap=buf) && + !(map->bitmap=(uchar*)my_malloc(bitmap_size + + (thread_safe ? sizeof(pthread_mutex_t) : 0), + MYF(MY_WME | MY_ZEROFILL)))) return 1; - DBUG_ASSERT(bitmap_size != ~(uint) 0); + map->bitmap_size=bitmap_size; #ifdef THREAD - if ((map->thread_safe = thread_safe)) - pthread_mutex_init(&map->mutex, MY_MUTEX_INIT_FAST); + if (thread_safe) + { + map->mutex=(pthread_mutex_t *)(map->bitmap+bitmap_size); + pthread_mutex_init(map->mutex, MY_MUTEX_INIT_FAST); + } + else + map->mutex=0; #endif - map->bitmap_size=bitmap_size; return 0; } void bitmap_free(MY_BITMAP *map) { +#ifdef THREAD + if (map->mutex) + pthread_mutex_destroy(map->mutex); +#endif if (map->bitmap) { my_free((char*) map->bitmap, MYF(0)); map->bitmap=0; -#ifdef THREAD - if (map->thread_safe) - pthread_mutex_destroy(&map->mutex); -#endif } } void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit) { - if (bitmap_bit < map->bitmap_size) - { - bitmap_lock(map); - map->bitmap[bitmap_bit / 8] |= (1 << (bitmap_bit & 7)); - bitmap_unlock(map); - } + DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8); + bitmap_lock(map); + map->bitmap[bitmap_bit / 8] |= (1 << (bitmap_bit & 7)); + bitmap_unlock(map); } - uint bitmap_set_next(MY_BITMAP *map) { uchar *bitmap=map->bitmap; uint bit_found = MY_BIT_NONE; - uint bitmap_size=map->bitmap_size; + uint bitmap_size=map->bitmap_size*8; uint i; + DBUG_ASSERT(map->bitmap); bitmap_lock(map); for (i=0; i < bitmap_size ; i++, bitmap++) { @@ -110,35 +127,180 @@ uint bitmap_set_next(MY_BITMAP *map) return bit_found; } - void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit) { - if (bitmap_bit < map->bitmap_size) - { - bitmap_lock(map); - map->bitmap[bitmap_bit / 8] &= ~ (1 << (bitmap_bit & 7)); - bitmap_unlock(map); - } + DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8); + bitmap_lock(map); + map->bitmap[bitmap_bit / 8] &= ~ (1 << (bitmap_bit & 7)); + bitmap_unlock(map); } +void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size) +{ + uint prefix_bytes, prefix_bits; -void bitmap_set_all(MY_BITMAP* map) + DBUG_ASSERT(map->bitmap && + (prefix_size <= map->bitmap_size*8 || prefix_size == ~0)); + bitmap_lock(map); + set_if_smaller(prefix_size, map->bitmap_size*8); + if ((prefix_bytes= prefix_size / 8)) + memset(map->bitmap, 0xff, prefix_bytes); + if ((prefix_bits= prefix_size & 7)) + map->bitmap[prefix_bytes++]= (1 << prefix_bits)-1; + if (prefix_bytes < map->bitmap_size) + bzero(map->bitmap+prefix_bytes, map->bitmap_size-prefix_bytes); + bitmap_unlock(map); +} + +void bitmap_clear_all(MY_BITMAP *map) +{ + bitmap_set_prefix(map, 0); +} + +void bitmap_set_all(MY_BITMAP *map) +{ + bitmap_set_prefix(map, ~0); +} + +my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size) { + uint prefix_bits= prefix_size & 7, res= 0; + uchar *m= map->bitmap, *end_prefix= map->bitmap+prefix_size/8, + *end= map->bitmap+map->bitmap_size; + + DBUG_ASSERT(map->bitmap && prefix_size <= map->bitmap_size*8); + bitmap_lock(map); - memset(map->bitmap, 0xff, (map->bitmap_size+7)/8); + while (m < end_prefix) + if (*m++ != 0xff) + goto ret; + + if (prefix_bits && *m++ != (1 << prefix_bits)-1) + goto ret; + + while (m < end) + if (*m++ != 0) + goto ret; + + res=1; +ret: bitmap_unlock(map); + return res; } -my_bool bitmap_is_set(MY_BITMAP* map, uint bitmap_bit) +my_bool bitmap_is_clear_all(const MY_BITMAP *map) { - return (bitmap_bit < map->bitmap_size) ? - (map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7))) : - 0; + return bitmap_is_prefix(map, 0); } -void bitmap_clear_all(MY_BITMAP* map) +my_bool bitmap_is_set_all(const MY_BITMAP *map) { + return bitmap_is_prefix(map, map->bitmap_size*8); +} + +my_bool bitmap_is_set(const MY_BITMAP *map, uint bitmap_bit) +{ + DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8); + return map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7)); +} + +my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2) +{ + uint length, res=0; + uchar *m1=map1->bitmap, *m2=map2->bitmap, *end; + + DBUG_ASSERT(map1->bitmap && map2->bitmap && + map1->bitmap_size==map2->bitmap_size); + bitmap_lock(map1); + bitmap_lock(map2); + + end= m1+map1->bitmap_size; + + while (m1 < end) + if ((*m1++) & ~(*m2++)) + goto ret; + + res=1; +ret: + bitmap_unlock(map2); + bitmap_unlock(map1); + return res; +} + +my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) +{ + uint res; + + DBUG_ASSERT(map1->bitmap && map2->bitmap && + map1->bitmap_size==map2->bitmap_size); + bitmap_lock(map1); + bitmap_lock(map2); + + res= memcmp(map1->bitmap, map2->bitmap, map1->bitmap_size)==0; + + bitmap_unlock(map2); + bitmap_unlock(map1); + return res; +} + +void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2) +{ + uchar *to=map->bitmap, *from=map2->bitmap, *end; + uint len=map->bitmap_size, len2=map2->bitmap; + + DBUG_ASSERT(map->bitmap && map2->bitmap); + bitmap_lock(map); + bitmap_lock(map2); + + end= to+min(len,len2); + + while (to < end) + *to++ &= *from++; + + if (len2 < len) + { + end+=len-len2; + while (to < end) + *to++=0; + } + + bitmap_unlock(map2); + bitmap_unlock(map); +} + +void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2) +{ + uchar *to=map->bitmap, *from=map2->bitmap, *end; + + DBUG_ASSERT(map->bitmap && map2->bitmap && + map->bitmap_size==map2->bitmap_size); + bitmap_lock(map); + bitmap_lock(map2); + + end= to+map->bitmap_size; + + while (to < end) + *to++ &= ~(*from++); + + bitmap_unlock(map2); + bitmap_unlock(map); +} + +void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2) +{ + uchar *to=map->bitmap, *from=map2->bitmap, *end; + + DBUG_ASSERT(map->bitmap && map2->bitmap && + map->bitmap_size==map2->bitmap_size); bitmap_lock(map); - bzero(map->bitmap,(map->bitmap_size+7)/8); + bitmap_lock(map2); + + end= to+map->bitmap_size; + + while (to < end) + *to++ |= *from++; + + bitmap_unlock(map2); bitmap_unlock(map); } + |