summaryrefslogtreecommitdiff
path: root/mysys
diff options
context:
space:
mode:
Diffstat (limited to 'mysys')
-rw-r--r--mysys/Makefile.am11
-rw-r--r--mysys/array.c25
-rw-r--r--mysys/base64.c2
-rw-r--r--mysys/charset-def.c1
-rw-r--r--mysys/hash.c2
-rw-r--r--mysys/mf_dirname.c5
-rw-r--r--mysys/mf_format.c3
-rw-r--r--mysys/mf_pack.c27
-rw-r--r--mysys/mf_tempdir.c26
-rw-r--r--mysys/my_alloc.c1
-rw-r--r--mysys/my_bitmap.c1010
-rw-r--r--mysys/my_compress.c128
-rw-r--r--mysys/my_init.c1
-rw-r--r--mysys/my_malloc.c2
-rw-r--r--mysys/my_once.c2
-rw-r--r--mysys/my_static.c7
-rw-r--r--mysys/my_thr_init.c2
-rw-r--r--mysys/my_vle.c113
-rw-r--r--mysys/queues.c465
-rw-r--r--mysys/raid.cc799
-rw-r--r--mysys/raid2.c31
-rw-r--r--mysys/safemalloc.c2
-rw-r--r--mysys/testhash.c2
-rw-r--r--mysys/thr_lock.c211
-rw-r--r--mysys/thr_mutex.c77
-rw-r--r--mysys/trie.c237
26 files changed, 2116 insertions, 1076 deletions
diff --git a/mysys/Makefile.am b/mysys/Makefile.am
index ee0dcb544b6..121342bec87 100644
--- a/mysys/Makefile.am
+++ b/mysys/Makefile.am
@@ -35,6 +35,7 @@ libmysys_a_SOURCES = my_init.c my_getwd.c mf_getdate.c my_mmap.c \
mf_tempdir.c my_lock.c mf_brkhant.c my_alarm.c \
my_malloc.c my_realloc.c my_once.c mulalloc.c \
my_alloc.c safemalloc.c my_new.cc \
+ my_vle.c \
my_fopen.c my_fstream.c my_getsystime.c \
my_error.c errors.c my_div.c my_messnc.c \
mf_format.c mf_same.c mf_dirname.c mf_fn_ext.c \
@@ -43,14 +44,14 @@ libmysys_a_SOURCES = my_init.c my_getwd.c mf_getdate.c my_mmap.c \
mf_wcomp.c mf_wfile.c my_gethwaddr.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 \
+ tree.c trie.c list.c hash.c array.c string.c typelib.c \
my_copy.c my_append.c my_lib.c \
my_delete.c my_rename.c my_redel.c \
my_chsize.c my_lread.c my_lwrite.c my_clock.c \
my_quick.c my_lockmem.c my_static.c \
my_sync.c my_getopt.c my_mkdir.c \
default_modify.c default.c \
- my_compress.c checksum.c raid.cc \
+ my_compress.c checksum.c \
my_net.c my_semaphore.c my_port.c my_sleep.c \
charset.c charset-def.c my_bitmap.c my_bit.c md5.c \
my_gethostbyname.c rijndael.c my_aes.c sha1.c \
@@ -82,6 +83,12 @@ FLAGS=$(DEFS) $(INCLUDES) $(CPPFLAGS) $(CFLAGS) @NOINST_LDFLAGS@
# which automaticly removes the object files you use to compile a final program
#
+test_bitmap$(EXEEXT): my_bitmap.c $(LIBRARIES)
+ $(LINK) $(FLAGS) -DMAIN ./my_bitmap.c $(LDADD) $(LIBS)
+
+test_priority_queue$(EXEEXT): queues.c $(LIBRARIES)
+ $(LINK) $(FLAGS) -DMAIN ./queues.c $(LDADD) $(LIBS)
+
test_thr_alarm$(EXEEXT): thr_alarm.c $(LIBRARIES)
$(CP) $(srcdir)/thr_alarm.c ./test_thr_alarm.c
$(LINK) $(FLAGS) -DMAIN ./test_thr_alarm.c $(LDADD) $(LIBS)
diff --git a/mysys/array.c b/mysys/array.c
index 6d00585f24d..a50d8b78178 100644
--- a/mysys/array.c
+++ b/mysys/array.c
@@ -278,3 +278,28 @@ void freeze_size(DYNAMIC_ARRAY *array)
array->max_element=elements;
}
}
+
+
+/*
+ Get the index of a dynamic element
+
+ SYNOPSIS
+ get_index_dynamic()
+ array Array
+ element Whose element index
+
+*/
+
+int get_index_dynamic(DYNAMIC_ARRAY *array, gptr element)
+{
+ uint ret;
+ if (array->buffer > element)
+ return -1;
+
+ ret= (element - array->buffer) / array->size_of_element;
+ if (ret > array->elements)
+ return -1;
+
+ return ret;
+
+}
diff --git a/mysys/base64.c b/mysys/base64.c
index b29c8ff8360..60218993c42 100644
--- a/mysys/base64.c
+++ b/mysys/base64.c
@@ -16,6 +16,7 @@
#include <base64.h>
#include <m_string.h> /* strchr() */
+#include <m_ctype.h> /* my_isspace() */
#ifndef MAIN
@@ -115,7 +116,6 @@ pos(unsigned char c)
} \
if (i == size) \
{ \
- i= size + 1; \
break; \
} \
}
diff --git a/mysys/charset-def.c b/mysys/charset-def.c
index 0559fe59d06..835ce064b2c 100644
--- a/mysys/charset-def.c
+++ b/mysys/charset-def.c
@@ -78,6 +78,7 @@ my_bool init_compiled_charsets(myf flags __attribute__((unused)))
CHARSET_INFO *cs;
add_compiled_collation(&my_charset_bin);
+ add_compiled_collation(&my_charset_filename);
add_compiled_collation(&my_charset_latin1);
add_compiled_collation(&my_charset_latin1_bin);
diff --git a/mysys/hash.c b/mysys/hash.c
index 99479ef6769..165745986dc 100644
--- a/mysys/hash.c
+++ b/mysys/hash.c
@@ -109,7 +109,7 @@ static inline void hash_free_elements(HASH *hash)
void hash_free(HASH *hash)
{
DBUG_ENTER("hash_free");
- DBUG_PRINT("enter",("hash: 0x%lxd",hash));
+ DBUG_PRINT("enter",("hash: 0x%lx", hash));
hash_free_elements(hash);
hash->free= 0;
diff --git a/mysys/mf_dirname.c b/mysys/mf_dirname.c
index 9206aa28078..378fe7080b8 100644
--- a/mysys/mf_dirname.c
+++ b/mysys/mf_dirname.c
@@ -73,7 +73,7 @@ uint dirname_part(my_string to, const char *name)
SYNPOSIS
convert_dirname()
to Store result here
- from Original filename
+ from Original filename. May be == to
from_end Pointer at end of filename (normally end \0)
IMPLEMENTATION
@@ -101,6 +101,7 @@ char *convert_dirname(char *to, const char *from, const char *from_end)
#ifdef BACKSLASH_MBTAIL
CHARSET_INFO *fs= fs_character_set();
#endif
+ DBUG_ENTER("convert_dirname");
/* We use -2 here, becasue we need place for the last FN_LIBCHAR */
if (!from_end || (from_end - from) > FN_REFLEN-2)
@@ -149,5 +150,5 @@ char *convert_dirname(char *to, const char *from, const char *from_end)
*to++=FN_LIBCHAR;
*to=0;
}
- return to; /* Pointer to end of dir */
+ DBUG_RETURN(to); /* Pointer to end of dir */
} /* convert_dirname */
diff --git a/mysys/mf_format.c b/mysys/mf_format.c
index 50f354df1cd..697d8d9b364 100644
--- a/mysys/mf_format.c
+++ b/mysys/mf_format.c
@@ -54,7 +54,8 @@ my_string fn_format(my_string to, const char *name, const char *dir,
if (flag & MY_UNPACK_FILENAME)
(void) unpack_dirname(dev,dev); /* Replace ~/.. with dir */
- if ((pos= (char*) strchr(name,FN_EXTCHAR)) != NullS)
+ if (!(flag & MY_APPEND_EXT) &&
+ (pos= (char*) strchr(name,FN_EXTCHAR)) != NullS)
{
if ((flag & MY_REPLACE_EXT) == 0) /* If we should keep old ext */
{
diff --git a/mysys/mf_pack.c b/mysys/mf_pack.c
index 049aa59a578..9dd2a6a8276 100644
--- a/mysys/mf_pack.c
+++ b/mysys/mf_pack.c
@@ -107,16 +107,27 @@ void pack_dirname(my_string to, const char *from)
} /* pack_dirname */
- /* remove unwanted chars from dirname */
- /* if "/../" removes prev dir; "/~/" removes all before ~ */
- /* "//" is same as "/", except on Win32 at start of a file */
- /* "/./" is removed */
- /* Unpacks home_dir if "~/.." used */
- /* Unpacks current dir if if "./.." used */
+/*
+ remove unwanted chars from dirname
-uint cleanup_dirname(register my_string to, const char *from)
- /* to may be == from */
+ SYNOPSIS
+ cleanup_dirname()
+ to Store result here
+ from Dirname to fix. May be same as to
+
+ IMPLEMENTATION
+ "/../" removes prev dir
+ "/~/" removes all before ~
+ //" is same as "/", except on Win32 at start of a file
+ "/./" is removed
+ Unpacks home_dir if "~/.." used
+ Unpacks current dir if if "./.." used
+ RETURN
+ # length of new name
+*/
+
+uint cleanup_dirname(register my_string to, const char *from)
{
reg5 uint length;
reg2 my_string pos;
diff --git a/mysys/mf_tempdir.c b/mysys/mf_tempdir.c
index 4d244aa7d74..e79980ab931 100644
--- a/mysys/mf_tempdir.c
+++ b/mysys/mf_tempdir.c
@@ -28,9 +28,12 @@ my_bool init_tmpdir(MY_TMPDIR *tmpdir, const char *pathlist)
char *end, *copy;
char buff[FN_REFLEN];
DYNAMIC_ARRAY t_arr;
+ DBUG_ENTER("init_tmpdir");
+ DBUG_PRINT("enter", ("pathlist: %s", pathlist ? pathlist : "NULL"));
+
pthread_mutex_init(&tmpdir->mutex, MY_MUTEX_INIT_FAST);
if (my_init_dynamic_array(&t_arr, sizeof(char*), 1, 5))
- return TRUE;
+ goto err;
if (!pathlist || !pathlist[0])
{
/* Get default temporary directory */
@@ -46,12 +49,13 @@ my_bool init_tmpdir(MY_TMPDIR *tmpdir, const char *pathlist)
}
do
{
+ uint length;
end=strcend(pathlist, DELIM);
- convert_dirname(buff, pathlist, end);
- if (!(copy=my_strdup(buff, MYF(MY_WME))))
- return TRUE;
- if (insert_dynamic(&t_arr, (gptr)&copy))
- return TRUE;
+ strmake(buff, pathlist, (uint) (end-pathlist));
+ length= cleanup_dirname(buff, buff);
+ if (!(copy= my_strndup(buff, length, MYF(MY_WME))) ||
+ insert_dynamic(&t_arr, (gptr) &copy))
+ DBUG_RETURN(TRUE);
pathlist=end+1;
}
while (*end);
@@ -59,12 +63,20 @@ my_bool init_tmpdir(MY_TMPDIR *tmpdir, const char *pathlist)
tmpdir->list=(char **)t_arr.buffer;
tmpdir->max=t_arr.elements-1;
tmpdir->cur=0;
- return FALSE;
+ DBUG_RETURN(FALSE);
+
+err:
+ delete_dynamic(&t_arr); /* Safe to free */
+ pthread_mutex_destroy(&tmpdir->mutex);
+ DBUG_RETURN(TRUE);
}
+
char *my_tmpdir(MY_TMPDIR *tmpdir)
{
char *dir;
+ if (!tmpdir->max)
+ return tmpdir->list[0];
pthread_mutex_lock(&tmpdir->mutex);
dir=tmpdir->list[tmpdir->cur];
tmpdir->cur= (tmpdir->cur == tmpdir->max) ? 0 : tmpdir->cur+1;
diff --git a/mysys/my_alloc.c b/mysys/my_alloc.c
index d5346d530c3..9f3676618eb 100644
--- a/mysys/my_alloc.c
+++ b/mysys/my_alloc.c
@@ -396,6 +396,7 @@ char *strdup_root(MEM_ROOT *root,const char *str)
return strmake_root(root, str, (uint) strlen(str));
}
+
char *strmake_root(MEM_ROOT *root,const char *str, uint len)
{
char *pos;
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 49c23aaeae5..70edb507b5f 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -20,26 +20,70 @@
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))
-
- If THREAD is defined all bitmap operations except bitmap_init/bitmap_free
- are thread-safe.
+ * the internal size is a set of 32 bit words
+ * the number of bits specified in creation can be any number > 0
+ * there are THREAD safe versions of most calls called bitmap_lock_*
+ many of those are not used and not compiled normally but the code
+ already exist for them in an #ifdef:ed part. These can only be used
+ if THREAD was specified in bitmap_init
TODO:
Make assembler THREAD safe versions of these using test-and-set instructions
+
+ Original version created by Sergei Golubchik 2001 - 2004.
+ New version written and test program added and some changes to the interface
+ was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
+ Kindahl.
*/
#include "mysys_priv.h"
#include <my_bitmap.h>
#include <m_string.h>
+void create_last_word_mask(MY_BITMAP *map)
+{
+ /* Get the number of used bits (1..8) in the last byte */
+ unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
+
+ /*
+ * Create a mask with the upper 'unused' bits set and the lower 'used'
+ * bits clear. The bits within each byte is stored in big-endian order.
+ */
+ unsigned char const mask= (~((1 << used) - 1)) & 255;
+
+ /*
+ The first bytes are to be set to zero since they represent real bits
+ in the bitvector. The last bytes are set to 0xFF since they represent
+ bytes not used by the bitvector. Finally the last byte contains bits
+ as set by the mask above.
+ */
+ unsigned char *ptr= (unsigned char*)&map->last_word_mask;
+
+ map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
+ switch (no_bytes_in_map(map)&3)
+ {
+ case 1:
+ map->last_word_mask= ~0U;
+ ptr[0]= mask;
+ return;
+
+ case 2:
+ map->last_word_mask= ~0U;
+ ptr[0]= 0;
+ ptr[1]= mask;
+ return;
+ case 3:
+ map->last_word_mask= 0U;
+ ptr[2]= mask;
+ ptr[3]= 0xFFU;
+ return;
+ case 0:
+ map->last_word_mask= 0U;
+ ptr[3]= mask;
+ return;
+ }
+}
+
static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
{
#ifdef THREAD
@@ -57,29 +101,39 @@ static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
}
-my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size,
+my_bool bitmap_init(MY_BITMAP *map, uint32 *buf, uint n_bits,
my_bool thread_safe)
{
DBUG_ENTER("bitmap_init");
-
- 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))))
- DBUG_RETURN(1);
- map->bitmap_size=bitmap_size;
+ DBUG_ASSERT(n_bits > 0);
+ if (!buf)
+ {
+ uint size_in_bytes= ((n_bits+31)/32)*4
+#ifdef THREAD
+ +(thread_safe ? sizeof(pthread_mutex_t) : 0)
+#endif
+ ;
+ if (!(buf= (uint32*) my_malloc(size_in_bytes, MYF(MY_WME))))
+ DBUG_RETURN(1);
+ }
+#ifdef THREAD
+ else
+ DBUG_ASSERT(thread_safe == 0);
+#endif
#ifdef THREAD
if (thread_safe)
{
- map->mutex=(pthread_mutex_t *)(map->bitmap+bitmap_size);
+ map->mutex=(pthread_mutex_t *)buf;
pthread_mutex_init(map->mutex, MY_MUTEX_INIT_FAST);
+ buf+= sizeof(pthread_mutex_t)/4;
}
else
map->mutex=0;
#endif
+ map->bitmap= buf;
+ map->n_bits=n_bits;
+ create_last_word_mask(map);
+ bitmap_clear_all(map);
DBUG_RETURN(0);
}
@@ -90,25 +144,21 @@ void bitmap_free(MY_BITMAP *map)
if (map->bitmap)
{
#ifdef THREAD
- if (map->mutex)
+ char *buf= (char *)map->mutex;
+ if (buf)
pthread_mutex_destroy(map->mutex);
-#endif
+ else
+ buf=(char*) map->bitmap;
+ my_free(buf, MYF(0));
+#else
my_free((char*) map->bitmap, MYF(0));
+#endif
map->bitmap=0;
}
DBUG_VOID_RETURN;
}
-void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
-{
- DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8);
- bitmap_lock(map);
- bitmap_fast_set_bit(map, bitmap_bit);
- bitmap_unlock(map);
-}
-
-
/*
test if bit already set and set it if it was not (thread unsafe method)
@@ -124,7 +174,7 @@ void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
{
- uchar *byte= map->bitmap + (bitmap_bit / 8);
+ uchar *byte= (uchar*)map->bitmap + (bitmap_bit / 8);
uchar bit= 1 << ((bitmap_bit) & 7);
uchar res= (*byte) & bit;
*byte|= bit;
@@ -148,7 +198,7 @@ my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
{
my_bool res;
- DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8);
+ DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
bitmap_lock(map);
res= bitmap_fast_test_and_set(map, bitmap_bit);
bitmap_unlock(map);
@@ -157,173 +207,113 @@ my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
uint bitmap_set_next(MY_BITMAP *map)
{
- uchar *bitmap=map->bitmap;
- uint bit_found = MY_BIT_NONE;
- uint bitmap_size=map->bitmap_size*8;
- uint i;
-
+ uint bit_found;
DBUG_ASSERT(map->bitmap);
- bitmap_lock(map);
- for (i=0; i < bitmap_size ; i++, bitmap++)
- {
- if (*bitmap != 0xff)
- { /* Found slot with free bit */
- uint b;
- for (b=0; ; b++)
- {
- if (!(*bitmap & (1 << b)))
- {
- *bitmap |= 1<<b;
- bit_found = (i*8)+b;
- break;
- }
- }
- break; /* Found bit */
- }
- }
- bitmap_unlock(map);
+ if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
+ bitmap_set_bit(map, bit_found);
return bit_found;
}
-void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit)
-{
- DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8);
- bitmap_lock(map);
- bitmap_fast_clear_bit(map, bitmap_bit);
- bitmap_unlock(map);
-}
-
-
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
{
- uint prefix_bytes, prefix_bits;
+ uint prefix_bytes, prefix_bits, d;
+ uchar *m= (uchar *)map->bitmap;
DBUG_ASSERT(map->bitmap &&
- (prefix_size <= map->bitmap_size*8 || prefix_size == (uint) ~0));
- bitmap_lock(map);
- set_if_smaller(prefix_size, map->bitmap_size*8);
+ (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
+ set_if_smaller(prefix_size, map->n_bits);
if ((prefix_bytes= prefix_size / 8))
- memset(map->bitmap, 0xff, prefix_bytes);
+ memset(m, 0xff, prefix_bytes);
+ m+= 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);
+ *m++= (1 << prefix_bits)-1;
+ if ((d= no_bytes_in_map(map)-prefix_bytes))
+ bzero(m, d);
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits*/
}
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);
+ uint prefix_bits= prefix_size & 0x7, res;
+ uchar *m= (uchar*)map->bitmap;
+ uchar *end_prefix= m+prefix_size/8;
+ uchar *end;
+ DBUG_ASSERT(m && prefix_size <= map->n_bits);
+ end= m+no_bytes_in_map(map);
- bitmap_lock((MY_BITMAP *)map);
while (m < end_prefix)
if (*m++ != 0xff)
- goto ret;
+ return 0;
+ *map->last_word_ptr^= map->last_word_mask; /*Clear bits*/
+ res= 0;
if (prefix_bits && *m++ != (1 << prefix_bits)-1)
goto ret;
while (m < end)
if (*m++ != 0)
goto ret;
-
- res=1;
+ res= 1;
ret:
- bitmap_unlock((MY_BITMAP *)map);
- return res;
+ *map->last_word_ptr|= map->last_word_mask; /*Set bits again*/
+ return res;
}
-my_bool bitmap_is_clear_all(const MY_BITMAP *map)
-{
- return bitmap_is_prefix(map, 0);
-}
-
my_bool bitmap_is_set_all(const MY_BITMAP *map)
{
- return bitmap_is_prefix(map, map->bitmap_size*8);
+ uint32 *data_ptr= map->bitmap;
+ uint32 *end= map->last_word_ptr;
+ for (; data_ptr <= end; data_ptr++)
+ if (*data_ptr != 0xFFFFFFFF)
+ return FALSE;
+ return TRUE;
}
-my_bool bitmap_is_set(const MY_BITMAP *map, uint bitmap_bit)
+my_bool bitmap_is_clear_all(const MY_BITMAP *map)
{
- DBUG_ASSERT(map->bitmap && bitmap_bit < map->bitmap_size*8);
- return bitmap_fast_is_set(map, bitmap_bit);
+ uint32 *data_ptr= map->bitmap;
+ uint32 *end;
+ if (*map->last_word_ptr != map->last_word_mask)
+ return FALSE;
+ end= map->last_word_ptr;
+ for (; data_ptr < end; data_ptr++)
+ if (*data_ptr)
+ return FALSE;
+ return TRUE;
}
my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
{
- uint res=0;
- uchar *m1=map1->bitmap, *m2=map2->bitmap, *end;
+ uint32 *m1= map1->bitmap, *m2= map2->bitmap, *end;
DBUG_ASSERT(map1->bitmap && map2->bitmap &&
- map1->bitmap_size==map2->bitmap_size);
- bitmap_lock((MY_BITMAP *)map1);
- bitmap_lock((MY_BITMAP *)map2);
+ map1->n_bits==map2->n_bits);
- end= m1+map1->bitmap_size;
+ end= map1->last_word_ptr;
- while (m1 < end)
+ while (m1 <= end)
{
if ((*m1++) & ~(*m2++))
- goto ret;
+ return 0;
}
-
- res=1;
-ret:
- bitmap_unlock((MY_BITMAP *)map2);
- bitmap_unlock((MY_BITMAP *)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((MY_BITMAP *)map1);
- bitmap_lock((MY_BITMAP *)map2);
-
- res= memcmp(map1->bitmap, map2->bitmap, map1->bitmap_size)==0;
-
- bitmap_unlock((MY_BITMAP *)map2);
- bitmap_unlock((MY_BITMAP *)map1);
- return res;
+ return 1;
}
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_size;
+ uint32 *to= map->bitmap, *from= map2->bitmap, *end;
+ uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
DBUG_ASSERT(map->bitmap && map2->bitmap);
- bitmap_lock(map);
- bitmap_lock((MY_BITMAP *)map2);
end= to+min(len,len2);
-
+ *map2->last_word_ptr^= map2->last_word_mask; /*Clear last bits in map2*/
while (to < end)
*to++ &= *from++;
@@ -333,9 +323,8 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
while (to < end)
*to++=0;
}
-
- bitmap_unlock((MY_BITMAP *)map2);
- bitmap_unlock(map);
+ *map2->last_word_ptr|= map2->last_word_mask; /*Set last bits in map*/
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits in map2*/
}
@@ -362,47 +351,291 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
{
uchar use_byte= use_bit ? 0xff : 0;
- uchar *to= map->bitmap + from_byte;
- uchar *end= map->bitmap + map->bitmap_size;
+ uchar *to= (uchar *)map->bitmap + from_byte;
+ uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
while (to < end)
*to++= use_byte;
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits again*/
}
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
{
- uchar *to=map->bitmap, *from=map2->bitmap, *end;
+ uint32 *to= map->bitmap, *from= map2->bitmap, *end;
+ DBUG_ASSERT(map->bitmap && map2->bitmap &&
+ map->n_bits==map2->n_bits);
+
+ end= map->last_word_ptr;
+
+ while (to <= end)
+ *to++ &= ~(*from++);
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits again*/
+}
+
+
+void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ uint32 *to= map->bitmap, *from= map2->bitmap, *end;
+
+ DBUG_ASSERT(map->bitmap && map2->bitmap &&
+ map->n_bits==map2->n_bits);
+ end= map->last_word_ptr;
+ while (to <= end)
+ *to++ |= *from++;
+}
+
+
+void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ uint32 *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
DBUG_ASSERT(map->bitmap && map2->bitmap &&
- map->bitmap_size==map2->bitmap_size);
+ map->n_bits==map2->n_bits);
+ while (to <= end)
+ *to++ ^= *from++;
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits again*/
+}
+
+
+void bitmap_invert(MY_BITMAP *map)
+{
+ uint32 *to= map->bitmap, *end;
+
+ DBUG_ASSERT(map->bitmap);
+ end= map->last_word_ptr;
+
+ while (to <= end)
+ *to++ ^= 0xFFFFFFFF;
+ *map->last_word_ptr|= map->last_word_mask; /*Set last bits again*/
+}
+
+
+uint bitmap_bits_set(const MY_BITMAP *map)
+{
+ uchar *m= (uchar*)map->bitmap;
+ uchar *end= m + no_bytes_in_map(map);
+ uint res= 0;
+
+ DBUG_ASSERT(map->bitmap);
+ *map->last_word_ptr^=map->last_word_mask; /*Reset last bits to zero*/
+ while (m < end)
+ res+= my_count_bits_ushort(*m++);
+ *map->last_word_ptr^=map->last_word_mask; /*Set last bits to one again*/
+ return res;
+}
+
+uint bitmap_get_first_set(const MY_BITMAP *map)
+{
+ uchar *byte_ptr;
+ uint bit_found,i,j,k;
+ uint32 *data_ptr, *end= map->last_word_ptr;
+
+ DBUG_ASSERT(map->bitmap);
+ data_ptr= map->bitmap;
+ for (i=0; data_ptr <= end; data_ptr++, i++)
+ {
+ if (*data_ptr)
+ {
+ byte_ptr= (uchar*)data_ptr;
+ for (j=0; ; j++, byte_ptr++)
+ {
+ if (*byte_ptr)
+ {
+ for (k=0; ; k++)
+ {
+ if (*byte_ptr & (1 << k))
+ {
+ bit_found= (i*32) + (j*8) + k;
+ if (bit_found == map->n_bits)
+ return MY_BIT_NONE;
+ return bit_found;
+ }
+ }
+ DBUG_ASSERT(0);
+ }
+ }
+ DBUG_ASSERT(0);
+ }
+ }
+ return MY_BIT_NONE;
+}
+
+
+uint bitmap_get_first(const MY_BITMAP *map)
+{
+ uchar *byte_ptr;
+ uint bit_found= MY_BIT_NONE, i,j,k;
+ uint32 *data_ptr, *end= map->last_word_ptr;
+
+ DBUG_ASSERT(map->bitmap);
+ data_ptr= map->bitmap;
+ for (i=0; data_ptr <= end; data_ptr++, i++)
+ {
+ if (*data_ptr != 0xFFFFFFFF)
+ {
+ byte_ptr= (uchar*)data_ptr;
+ for (j=0; ; j++, byte_ptr++)
+ {
+ if (*byte_ptr != 0xFF)
+ {
+ for (k=0; ; k++)
+ {
+ if (!(*byte_ptr & (1 << k)))
+ {
+ bit_found= (i*32) + (j*8) + k;
+ if (bit_found == map->n_bits)
+ return MY_BIT_NONE;
+ return bit_found;
+ }
+ }
+ DBUG_ASSERT(0);
+ }
+ }
+ DBUG_ASSERT(0);
+ }
+ }
+ return MY_BIT_NONE;
+}
+
+
+uint bitmap_lock_set_next(MY_BITMAP *map)
+{
+ uint bit_found;
bitmap_lock(map);
- bitmap_lock((MY_BITMAP *)map2);
+ bit_found= bitmap_set_next(map);
+ bitmap_unlock(map);
+ return bit_found;
+}
- end= to+map->bitmap_size;
- while (to < end)
- *to++ &= ~(*from++);
+void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
+{
+ bitmap_lock(map);
+ DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
+ bitmap_clear_bit(map, bitmap_bit);
+ bitmap_unlock(map);
+}
- bitmap_unlock((MY_BITMAP *)map2);
+
+#ifdef NOT_USED
+my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
+{
+ my_bool res;
+ bitmap_lock((MY_BITMAP *)map);
+ res= bitmap_is_prefix(map, prefix_size);
+ bitmap_unlock((MY_BITMAP *)map);
+ return res;
+}
+
+
+void bitmap_lock_set_all(MY_BITMAP *map)
+{
+ bitmap_lock(map);
+ bitmap_set_all(map);
bitmap_unlock(map);
}
-void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
+void bitmap_lock_clear_all(MY_BITMAP *map)
{
- uchar *to=map->bitmap, *from=map2->bitmap, *end;
+ bitmap_lock(map);
+ bitmap_clear_all(map);
+ bitmap_unlock(map);
+}
- DBUG_ASSERT(map->bitmap && map2->bitmap &&
- map->bitmap_size==map2->bitmap_size);
+
+void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
+{
bitmap_lock(map);
+ bitmap_set_prefix(map, prefix_size);
+ bitmap_unlock(map);
+}
+
+
+my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
+{
+ uint res;
+ bitmap_lock((MY_BITMAP *)map);
+ res= bitmap_is_clear_all(map);
+ bitmap_unlock((MY_BITMAP *)map);
+ return res;
+}
+
+
+my_bool bitmap_lock_is_set_all(const MY_BITMAP *map)
+{
+ uint res;
+ bitmap_lock((MY_BITMAP *)map);
+ res= bitmap_is_set_all(map);
+ bitmap_unlock((MY_BITMAP *)map);
+ return res;
+}
+
+
+my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
+{
+ my_bool res;
+ DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
+ bitmap_lock((MY_BITMAP *)map);
+ res= bitmap_is_set(map, bitmap_bit);
+ bitmap_unlock((MY_BITMAP *)map);
+ return res;
+}
+
+
+my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
+{
+ uint res;
+ bitmap_lock((MY_BITMAP *)map1);
bitmap_lock((MY_BITMAP *)map2);
+ res= bitmap_is_subset(map1, map2);
+ bitmap_unlock((MY_BITMAP *)map2);
+ bitmap_unlock((MY_BITMAP *)map1);
+ return res;
+}
- end= to+map->bitmap_size;
- while (to < end)
- *to++ |= *from++;
+my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
+{
+ uint res;
+
+ DBUG_ASSERT(map1->bitmap && map2->bitmap &&
+ map1->n_bits==map2->n_bits);
+ bitmap_lock((MY_BITMAP *)map1);
+ bitmap_lock((MY_BITMAP *)map2);
+ res= bitmap_cmp(map1, map2);
+ bitmap_unlock((MY_BITMAP *)map2);
+ bitmap_unlock((MY_BITMAP *)map1);
+ return res;
+}
+
+
+void bitmap_lock_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ bitmap_lock(map);
+ bitmap_lock((MY_BITMAP *)map2);
+ bitmap_intersect(map, map2);
+ bitmap_unlock((MY_BITMAP *)map2);
+ bitmap_unlock(map);
+}
+
+void bitmap_lock_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ bitmap_lock(map);
+ bitmap_lock((MY_BITMAP *)map2);
+ bitmap_subtract(map, map2);
+ bitmap_unlock((MY_BITMAP *)map2);
+ bitmap_unlock(map);
+}
+
+
+void bitmap_lock_union(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ bitmap_lock(map);
+ bitmap_lock((MY_BITMAP *)map2);
+ bitmap_union(map, map2);
bitmap_unlock((MY_BITMAP *)map2);
bitmap_unlock(map);
}
@@ -415,19 +648,12 @@ void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
RETURN
Number of set bits in the bitmap.
*/
-
-uint bitmap_bits_set(const MY_BITMAP *map)
-{
- uchar *m= map->bitmap;
- uchar *end= m + map->bitmap_size;
- uint res= 0;
-
- DBUG_ASSERT(map->bitmap);
+uint bitmap_lock_bits_set(const MY_BITMAP *map)
+{
+ uint res;
bitmap_lock((MY_BITMAP *)map);
- while (m < end)
- {
- res+= my_count_bits_ushort(*m++);
- }
+ DBUG_ASSERT(map->bitmap);
+ res= bitmap_bits_set(map);
bitmap_unlock((MY_BITMAP *)map);
return res;
}
@@ -440,33 +666,421 @@ uint bitmap_bits_set(const MY_BITMAP *map)
RETURN
Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
*/
+uint bitmap_lock_get_first(const MY_BITMAP *map)
+{
+ uint res;
+ bitmap_lock((MY_BITMAP*)map);
+ res= bitmap_get_first(map);
+ bitmap_unlock((MY_BITMAP*)map);
+ return res;
+}
-uint bitmap_get_first(const MY_BITMAP *map)
+
+uint bitmap_lock_get_first_set(const MY_BITMAP *map)
+{
+ uint res;
+ bitmap_lock((MY_BITMAP*)map);
+ res= bitmap_get_first_set(map);
+ bitmap_unlock((MY_BITMAP*)map);
+ return res;
+}
+
+
+void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
+{
+ DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
+ bitmap_lock(map);
+ bitmap_set_bit(map, bitmap_bit);
+ bitmap_unlock(map);
+}
+
+
+void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
+{
+ DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
+ bitmap_lock(map);
+ bitmap_flip_bit(map, bitmap_bit);
+ bitmap_unlock(map);
+}
+#endif
+#ifdef MAIN
+
+static void bitmap_print(MY_BITMAP *map)
+{
+ uint32 *to= map->bitmap, *end= map->last_word_ptr;
+ while (to <= end)
+ {
+ fprintf(stderr,"0x%x ", *to++);
+ }
+ fprintf(stderr,"\n");
+}
+
+uint get_rand_bit(uint bitsize)
+{
+ return (rand() % bitsize);
+}
+
+bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
+{
+ uint i, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit= get_rand_bit(bitsize);
+ bitmap_set_bit(map, test_bit);
+ if (!bitmap_is_set(map, test_bit))
+ goto error1;
+ bitmap_clear_bit(map, test_bit);
+ if (bitmap_is_set(map, test_bit))
+ goto error2;
+ }
+ return FALSE;
+error1:
+ printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
+ return TRUE;
+error2:
+ printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
+ return TRUE;
+}
+
+bool test_flip_bit(MY_BITMAP *map, uint bitsize)
+{
+ uint i, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit= get_rand_bit(bitsize);
+ bitmap_flip_bit(map, test_bit);
+ if (!bitmap_is_set(map, test_bit))
+ goto error1;
+ bitmap_flip_bit(map, test_bit);
+ if (bitmap_is_set(map, test_bit))
+ goto error2;
+ }
+ return FALSE;
+error1:
+ printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
+ return TRUE;
+error2:
+ printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
+ return TRUE;
+}
+
+bool test_operators(MY_BITMAP *map, uint bitsize)
+{
+ return FALSE;
+}
+
+bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
{
- uchar *bitmap=map->bitmap;
- uint bit_found = MY_BIT_NONE;
- uint bitmap_size=map->bitmap_size*8;
uint i;
+ bitmap_set_all(map);
+ if (!bitmap_is_set_all(map))
+ goto error1;
+ if (!bitmap_is_prefix(map, bitsize))
+ goto error5;
+ bitmap_clear_all(map);
+ if (!bitmap_is_clear_all(map))
+ goto error2;
+ if (!bitmap_is_prefix(map, 0))
+ goto error6;
+ for (i=0; i<bitsize;i++)
+ bitmap_set_bit(map, i);
+ if (!bitmap_is_set_all(map))
+ goto error3;
+ for (i=0; i<bitsize;i++)
+ bitmap_clear_bit(map, i);
+ if (!bitmap_is_clear_all(map))
+ goto error4;
+ return FALSE;
+error1:
+ printf("Error in set_all, bitsize = %u", bitsize);
+ return TRUE;
+error2:
+ printf("Error in clear_all, bitsize = %u", bitsize);
+ return TRUE;
+error3:
+ printf("Error in bitmap_is_set_all, bitsize = %u", bitsize);
+ return TRUE;
+error4:
+ printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
+ return TRUE;
+error5:
+ printf("Error in set_all through set_prefix, bitsize = %u", bitsize);
+ return TRUE;
+error6:
+ printf("Error in clear_all through set_prefix, bitsize = %u", bitsize);
+ return TRUE;
+}
- DBUG_ASSERT(map->bitmap);
- bitmap_lock((MY_BITMAP *)map);
- for (i=0; i < bitmap_size ; i++, bitmap++)
+bool test_compare_operators(MY_BITMAP *map, uint bitsize)
+{
+ uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ MY_BITMAP map2_obj, map3_obj;
+ MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
+ uint32 map2buf[1024];
+ uint32 map3buf[1024];
+ bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
+ bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
+ bitmap_clear_all(map2);
+ bitmap_clear_all(map3);
+ for (i=0; i < no_loops; i++)
{
- if (*bitmap != 0xff)
- { /* Found slot with free bit */
- uint b;
- for (b=0; ; b++)
- {
- if (!(*bitmap & (1 << b)))
- {
- bit_found = (i*8)+b;
- break;
- }
- }
- break; /* Found bit */
+ test_bit1=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit1);
+ test_bit2=get_rand_bit(bitsize);
+ bitmap_set_prefix(map2, test_bit2);
+ bitmap_intersect(map, map2);
+ test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
+ bitmap_set_prefix(map3, test_bit3);
+ if (!bitmap_cmp(map, map3))
+ goto error1;
+ bitmap_clear_all(map);
+ bitmap_clear_all(map2);
+ bitmap_clear_all(map3);
+ test_bit1=get_rand_bit(bitsize);
+ test_bit2=get_rand_bit(bitsize);
+ test_bit3=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit1);
+ bitmap_set_prefix(map2, test_bit2);
+ test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
+ bitmap_set_prefix(map3, test_bit3);
+ bitmap_union(map, map2);
+ if (!bitmap_cmp(map, map3))
+ goto error2;
+ bitmap_clear_all(map);
+ bitmap_clear_all(map2);
+ bitmap_clear_all(map3);
+ test_bit1=get_rand_bit(bitsize);
+ test_bit2=get_rand_bit(bitsize);
+ test_bit3=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit1);
+ bitmap_set_prefix(map2, test_bit2);
+ bitmap_xor(map, map2);
+ test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
+ test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
+ bitmap_set_prefix(map3, test_bit3);
+ for (j=0; j < test_bit4; j++)
+ bitmap_clear_bit(map3, j);
+ if (!bitmap_cmp(map, map3))
+ goto error3;
+ bitmap_clear_all(map);
+ bitmap_clear_all(map2);
+ bitmap_clear_all(map3);
+ test_bit1=get_rand_bit(bitsize);
+ test_bit2=get_rand_bit(bitsize);
+ test_bit3=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit1);
+ bitmap_set_prefix(map2, test_bit2);
+ bitmap_subtract(map, map2);
+ if (test_bit2 < test_bit1)
+ {
+ bitmap_set_prefix(map3, test_bit1);
+ for (j=0; j < test_bit2; j++)
+ bitmap_clear_bit(map3, j);
}
+ if (!bitmap_cmp(map, map3))
+ goto error4;
+ bitmap_clear_all(map);
+ bitmap_clear_all(map2);
+ bitmap_clear_all(map3);
+ test_bit1=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit1);
+ bitmap_invert(map);
+ bitmap_set_all(map3);
+ for (j=0; j < test_bit1; j++)
+ bitmap_clear_bit(map3, j);
+ if (!bitmap_cmp(map, map3))
+ goto error5;
+ bitmap_clear_all(map);
+ bitmap_clear_all(map3);
}
- bitmap_unlock((MY_BITMAP *)map);
- return bit_found;
+ return FALSE;
+error1:
+ printf("intersect error bitsize=%u,size1=%u,size2=%u", bitsize,
+ test_bit1,test_bit2);
+ return TRUE;
+error2:
+ printf("union error bitsize=%u,size1=%u,size2=%u", bitsize,
+ test_bit1,test_bit2);
+ return TRUE;
+error3:
+ printf("xor error bitsize=%u,size1=%u,size2=%u", bitsize,
+ test_bit1,test_bit2);
+ return TRUE;
+error4:
+ printf("subtract error bitsize=%u,size1=%u,size2=%u", bitsize,
+ test_bit1,test_bit2);
+ return TRUE;
+error5:
+ printf("invert error bitsize=%u,size=%u", bitsize,
+ test_bit1);
+ return TRUE;
+}
+
+bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
+{
+ uint i, bit_count=0, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit=get_rand_bit(bitsize);
+ if (!bitmap_is_set(map, test_bit))
+ {
+ bitmap_set_bit(map, test_bit);
+ bit_count++;
+ }
+ }
+ if (bit_count==0 && bitsize > 0)
+ goto error1;
+ if (bitmap_bits_set(map) != bit_count)
+ goto error2;
+ return FALSE;
+error1:
+ printf("No bits set bitsize = %u", bitsize);
+ return TRUE;
+error2:
+ printf("Wrong count of bits set, bitsize = %u", bitsize);
+ return TRUE;
+}
+
+bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
+{
+ uint i, j, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit=get_rand_bit(bitsize);
+ bitmap_set_bit(map, test_bit);
+ if (bitmap_get_first_set(map) != test_bit)
+ goto error1;
+ bitmap_set_all(map);
+ bitmap_clear_bit(map, test_bit);
+ if (bitmap_get_first(map) != test_bit)
+ goto error2;
+ bitmap_clear_all(map);
+ }
+ return FALSE;
+error1:
+ printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
+ return TRUE;
+error2:
+ printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
+ return TRUE;
+}
+
+bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
+{
+ uint i, j, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit=get_rand_bit(bitsize);
+ for (j=0; j < test_bit; j++)
+ bitmap_set_next(map);
+ if (!bitmap_is_prefix(map, test_bit))
+ goto error1;
+ bitmap_clear_all(map);
+ }
+ return FALSE;
+error1:
+ printf("get_next error bitsize= %u, prefix_size= %u", bitsize,test_bit);
+ return TRUE;
+}
+
+bool test_prefix(MY_BITMAP *map, uint bitsize)
+{
+ uint i, j, test_bit;
+ uint no_loops= bitsize > 128 ? 128 : bitsize;
+ for (i=0; i < no_loops; i++)
+ {
+ test_bit=get_rand_bit(bitsize);
+ bitmap_set_prefix(map, test_bit);
+ if (!bitmap_is_prefix(map, test_bit))
+ goto error1;
+ bitmap_clear_all(map);
+ for (j=0; j < test_bit; j++)
+ bitmap_set_bit(map, j);
+ if (!bitmap_is_prefix(map, test_bit))
+ goto error2;
+ bitmap_set_all(map);
+ for (j=bitsize - 1; ~(j-test_bit); j--)
+ bitmap_clear_bit(map, j);
+ if (!bitmap_is_prefix(map, test_bit))
+ goto error3;
+ bitmap_clear_all(map);
+ }
+ return FALSE;
+error1:
+ printf("prefix1 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
+ return TRUE;
+error2:
+ printf("prefix2 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
+ return TRUE;
+error3:
+ printf("prefix3 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
+ return TRUE;
}
+
+bool do_test(uint bitsize)
+{
+ MY_BITMAP map;
+ uint32 buf[1024];
+ if (bitmap_init(&map, buf, bitsize, FALSE))
+ {
+ printf("init error for bitsize %d", bitsize);
+ goto error;
+ }
+ if (test_set_get_clear_bit(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_flip_bit(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_operators(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_get_all_bits(&map, bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_compare_operators(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_count_bits_set(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_get_first_bit(&map,bitsize))
+ goto error;
+ bitmap_clear_all(&map);
+ if (test_get_next_bit(&map,bitsize))
+ goto error;
+ if (test_prefix(&map,bitsize))
+ goto error;
+ return FALSE;
+error:
+ printf("\n");
+ return TRUE;
+}
+
+int main()
+{
+ int i;
+ for (i= 1; i < 4096; i++)
+ {
+ printf("Start test for bitsize=%u\n",i);
+ if (do_test(i))
+ return -1;
+ }
+ printf("OK\n");
+ return 0;
+}
+
+/*
+ In directory mysys:
+ make test_bitmap
+ will build the bitmap tests and ./test_bitmap will execute it
+*/
+
+#endif
diff --git a/mysys/my_compress.c b/mysys/my_compress.c
index 0e37d2fef9b..2643d4d16ac 100644
--- a/mysys/my_compress.c
+++ b/mysys/my_compress.c
@@ -95,4 +95,132 @@ my_bool my_uncompress (byte *packet, ulong *len, ulong *complen)
}
DBUG_RETURN(0);
}
+
+/*
+ Internal representation of the frm blob
+*/
+
+struct frm_blob_header
+{
+ uint ver; /* Version of header */
+ uint orglen; /* Original length of compressed data */
+ uint complen; /* Compressed length of data, 0=uncompressed */
+};
+
+struct frm_blob_struct
+{
+ struct frm_blob_header head;
+ char data[1];
+};
+
+/*
+ packfrm is a method used to compress the frm file for storage in a
+ handler. This method was developed for the NDB handler and has been moved
+ here to serve also other uses.
+
+ SYNOPSIS
+ packfrm()
+ data Data reference to frm file data
+ len Length of frm file data
+ out:pack_data Reference to the pointer to the packed frm data
+ out:pack_len Length of packed frm file data
+
+ RETURN VALUES
+ 0 Success
+ >0 Failure
+*/
+
+int packfrm(const void *data, uint len,
+ const void **pack_data, uint *pack_len)
+{
+ int error;
+ ulong org_len, comp_len;
+ uint blob_len;
+ struct frm_blob_struct *blob;
+ DBUG_ENTER("packfrm");
+ DBUG_PRINT("enter", ("data: %x, len: %d", data, len));
+
+ error= 1;
+ org_len= len;
+ if (my_compress((byte*)data, &org_len, &comp_len))
+ goto err;
+
+ DBUG_PRINT("info", ("org_len: %d, comp_len: %d", org_len, comp_len));
+ DBUG_DUMP("compressed", (char*)data, org_len);
+
+ error= 2;
+ blob_len= sizeof(struct frm_blob_header)+org_len;
+ if (!(blob= (struct frm_blob_struct*) my_malloc(blob_len,MYF(MY_WME))))
+ goto err;
+
+ /* Store compressed blob in machine independent format */
+ int4store((char*)(&blob->head.ver), 1);
+ int4store((char*)(&blob->head.orglen), comp_len);
+ int4store((char*)(&blob->head.complen), org_len);
+
+ /* Copy frm data into blob, already in machine independent format */
+ memcpy(blob->data, data, org_len);
+
+ *pack_data= blob;
+ *pack_len= blob_len;
+ error= 0;
+
+ DBUG_PRINT("exit", ("pack_data: %x, pack_len: %d", *pack_data, *pack_len));
+err:
+ DBUG_RETURN(error);
+
+}
+
+/*
+ unpackfrm is a method used to decompress the frm file received from a
+ handler. This method was developed for the NDB handler and has been moved
+ here to serve also other uses for other clustered storage engines.
+
+ SYNOPSIS
+ unpackfrm()
+ pack_data Data reference to packed frm file data
+ out:unpack_data Reference to the pointer to the unpacked frm data
+ out:unpack_len Length of unpacked frm file data
+
+ RETURN VALUES¨
+ 0 Success
+ >0 Failure
+*/
+
+int unpackfrm(const void **unpack_data, uint *unpack_len,
+ const void *pack_data)
+{
+ const struct frm_blob_struct *blob= (struct frm_blob_struct*)pack_data;
+ byte *data;
+ ulong complen, orglen, ver;
+ DBUG_ENTER("unpackfrm");
+ DBUG_PRINT("enter", ("pack_data: %x", pack_data));
+
+ complen= uint4korr((char*)&blob->head.complen);
+ orglen= uint4korr((char*)&blob->head.orglen);
+ ver= uint4korr((char*)&blob->head.ver);
+
+ DBUG_PRINT("blob",("ver: %d complen: %d orglen: %d",
+ ver,complen,orglen));
+ DBUG_DUMP("blob->data", (char*) blob->data, complen);
+
+ if (ver != 1)
+ DBUG_RETURN(1);
+ if (!(data= my_malloc(max(orglen, complen), MYF(MY_WME))))
+ DBUG_RETURN(2);
+ memcpy(data, blob->data, complen);
+
+
+ if (my_uncompress(data, &complen, &orglen))
+ {
+ my_free((char*)data, MYF(0));
+ DBUG_RETURN(3);
+ }
+
+ *unpack_data= data;
+ *unpack_len= complen;
+
+ DBUG_PRINT("exit", ("frmdata: %x, len: %d", *unpack_data, *unpack_len));
+ DBUG_RETURN(0);
+}
#endif /* HAVE_COMPRESS */
diff --git a/mysys/my_init.c b/mysys/my_init.c
index c2bfdde0ddd..efeee0fbc76 100644
--- a/mysys/my_init.c
+++ b/mysys/my_init.c
@@ -214,6 +214,7 @@ Voluntary context switches %ld, Involuntary context switches %ld\n",
WSACleanup();
#endif /* __WIN__ */
my_init_done=0;
+ DBUG_VOID_RETURN;
} /* my_end */
diff --git a/mysys/my_malloc.c b/mysys/my_malloc.c
index 3f601a42dc9..3fb3866f79c 100644
--- a/mysys/my_malloc.c
+++ b/mysys/my_malloc.c
@@ -83,7 +83,7 @@ char *my_strdup(const char *from, myf my_flags)
}
-char *my_strdup_with_length(const byte *from, uint length, myf my_flags)
+char *my_strndup(const byte *from, uint length, myf my_flags)
{
gptr ptr;
if ((ptr=my_malloc(length+1,my_flags)) != 0)
diff --git a/mysys/my_once.c b/mysys/my_once.c
index ab5fcc51c0e..52f8c4309d5 100644
--- a/mysys/my_once.c
+++ b/mysys/my_once.c
@@ -75,6 +75,8 @@ gptr my_once_alloc(unsigned int Size, myf MyFlags)
point= (gptr) ((char*) next+ (next->size-next->left));
next->left-= Size;
+ if (MyFlags & MY_ZEROFILL)
+ bzero(point, Size);
return(point);
} /* my_once_alloc */
diff --git a/mysys/my_static.c b/mysys/my_static.c
index 8448afdc158..17094548dbd 100644
--- a/mysys/my_static.c
+++ b/mysys/my_static.c
@@ -92,13 +92,6 @@ struct st_irem *sf_malloc_root = NULL;
int volatile my_have_got_alarm=0; /* declare variable to reset */
ulong my_time_to_wait_for_lock=2; /* In seconds */
- /*
- We need to have this define here as otherwise linking will fail
- on OSF1 when compiling --without-raid --with-debug
- */
-
-const char *raid_type_string[]={"none","striped"};
-
/* from errors.c */
#ifdef SHARED_LIBRARY
char * NEAR globerrs[GLOBERRS]; /* my_error_messages is here */
diff --git a/mysys/my_thr_init.c b/mysys/my_thr_init.c
index 4d23d01cd82..d93f45091c6 100644
--- a/mysys/my_thr_init.c
+++ b/mysys/my_thr_init.c
@@ -282,7 +282,7 @@ const char *my_thread_name(void)
if (!tmp->name[0])
{
long id=my_thread_id();
- sprintf(name_buff,"T@%ld", id);
+ sprintf(name_buff,"T@%lu", id);
strmake(tmp->name,name_buff,THREAD_NAME_SIZE);
}
return tmp->name;
diff --git a/mysys/my_vle.c b/mysys/my_vle.c
new file mode 100644
index 00000000000..3ddc1e4c6e0
--- /dev/null
+++ b/mysys/my_vle.c
@@ -0,0 +1,113 @@
+/*
+ Copyright (C) 2005 MySQL AB
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ USA
+*/
+
+/*
+ Variable length encoding.
+
+ A method to store an arbitrary-size non-negative integer. We let the
+ most significant bit of the number indicate that the next byte
+ should be contatenated to form the real number.
+*/
+
+#include "my_vle.h"
+
+/*
+ Function to encode an unsigned long as VLE. The bytes for the VLE
+ will be written to the location pointed to by 'out'. The maximum
+ number of bytes written will be 'max'.
+
+ PARAMETERS
+
+ out Pointer to beginning of where to store VLE bytes.
+ max Maximum number of bytes to write.
+ n Number to encode.
+
+ RETURN VALUE
+ On success, one past the end of the array containing the VLE
+ bytes. On failure, the 'out' pointer is returned.
+*/
+
+byte*
+my_vle_encode(byte* out, my_size_t max, ulong n)
+{
+ byte buf[my_vle_sizeof(n)];
+ byte *ptr= buf;
+ my_size_t len;
+
+ do
+ {
+ *ptr++= (n & 0x7F);
+ n>>= 7;
+ }
+ while (n > 0);
+
+ len= ptr - buf;
+
+ if (len <= max)
+ {
+ /*
+ The bytes are stored in reverse order in 'buf'. Let's write them
+ in correct order to the output buffer and set the MSB at the
+ same time.
+ */
+ while (ptr-- > buf)
+ {
+ byte v= *ptr;
+ if (ptr > buf)
+ v|= 0x80;
+ *out++= v;
+ }
+ }
+
+ return out;
+}
+
+/*
+ Function to decode a VLE representation of an integral value.
+
+
+ PARAMETERS
+
+ result_ptr Pointer to an unsigned long where the value will be written.
+ vle Pointer to the VLE bytes.
+
+ RETURN VALUE
+
+ One-past the end of the VLE bytes. The routine will never read
+ more than sizeof(*result_ptr) + 1 bytes.
+*/
+
+byte const*
+my_vle_decode(ulong *result_ptr, byte const *vle)
+{
+ ulong result= 0;
+ my_size_t cnt= 1;
+
+ do
+ {
+ result<<= 7;
+ result|= (*vle & 0x7F);
+ }
+ while ((*vle++ & 0x80) && ++cnt <= sizeof(*result_ptr) + 1);
+
+ if (cnt <= sizeof(*result_ptr) + 1)
+ *result_ptr= result;
+
+ return vle;
+}
diff --git a/mysys/queues.c b/mysys/queues.c
index ecf1058af41..8e572a0f195 100644
--- a/mysys/queues.c
+++ b/mysys/queues.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 2000 MySQL AB
+/* Copyright (C) 2000, 2005 MySQL AB
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -17,6 +17,10 @@
/*
Code for generell handling of priority Queues.
Implemention of queues from "Algoritms in C" by Robert Sedgewick.
+ An optimisation of _downheap suggested in Exercise 7.51 in "Data
+ Structures & Algorithms in C++" by Mark Allen Weiss, Second Edition
+ was implemented by Mikael Ronstrom 2005. Also the O(N) algorithm
+ of queue_fix was implemented.
*/
#include "mysys_priv.h"
@@ -63,6 +67,46 @@ int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
}
+
+/*
+ Init queue, uses init_queue internally for init work but also accepts
+ auto_extent as parameter
+
+ SYNOPSIS
+ init_queue_ex()
+ queue Queue to initialise
+ max_elements Max elements that will be put in queue
+ offset_to_key Offset to key in element stored in queue
+ Used when sending pointers to compare function
+ max_at_top Set to 1 if you want biggest element on top.
+ compare Compare function for elements, takes 3 arguments.
+ first_cmp_arg First argument to compare function
+ auto_extent When the queue is full and there is insert operation
+ extend the queue.
+
+ NOTES
+ Will allocate max_element pointers for queue array
+
+ RETURN
+ 0 ok
+ 1 Could not allocate memory
+*/
+
+int init_queue_ex(QUEUE *queue, uint max_elements, uint offset_to_key,
+ pbool max_at_top, int (*compare) (void *, byte *, byte *),
+ void *first_cmp_arg, uint auto_extent)
+{
+ int ret;
+ DBUG_ENTER("init_queue_ex");
+
+ if ((ret= init_queue(queue, max_elements, offset_to_key, max_at_top, compare,
+ first_cmp_arg)))
+ DBUG_RETURN(ret);
+
+ queue->auto_extent= auto_extent;
+ DBUG_RETURN(0);
+}
+
/*
Reinitialize queue for other usage
@@ -188,6 +232,31 @@ void queue_insert(register QUEUE *queue, byte *element)
}
}
+/*
+ Does safe insert. If no more space left on the queue resize it.
+ Return codes:
+ 0 - OK
+ 1 - Cannot allocate more memory
+ 2 - auto_extend is 0, the operation would
+
+*/
+
+int queue_insert_safe(register QUEUE *queue, byte *element)
+{
+
+ if (queue->elements == queue->max_elements)
+ {
+ if (!queue->auto_extent)
+ return 2;
+ else if (resize_queue(queue, queue->max_elements + queue->auto_extent))
+ return 1;
+ }
+
+ queue_insert(queue, element);
+ return 0;
+}
+
+
/* Remove item from queue */
/* Returns pointer to removed element */
@@ -214,8 +283,64 @@ void queue_replaced(QUEUE *queue)
}
#endif
- /* Fix heap when index have changed */
+#ifndef OLD_VERSION
+
+void _downheap(register QUEUE *queue, uint idx)
+{
+ byte *element;
+ uint elements,half_queue,offset_to_key, next_index;
+ bool first= TRUE;
+ uint start_idx= idx;
+
+ offset_to_key=queue->offset_to_key;
+ element=queue->root[idx];
+ half_queue=(elements=queue->elements) >> 1;
+ while (idx <= half_queue)
+ {
+ int cmp;
+ next_index=idx+idx;
+ if (next_index < elements &&
+ (queue->compare(queue->first_cmp_arg,
+ queue->root[next_index]+offset_to_key,
+ queue->root[next_index+1]+offset_to_key) ^
+ queue->max_at_top) > 0)
+ next_index++;
+ if (first &&
+ (((cmp=queue->compare(queue->first_cmp_arg,
+ queue->root[next_index]+offset_to_key,
+ element+offset_to_key)) == 0) ||
+ ((cmp ^ queue->max_at_top) > 0)))
+ {
+ queue->root[idx]= element;
+ return;
+ }
+ queue->root[idx]=queue->root[next_index];
+ idx=next_index;
+ first= FALSE;
+ }
+
+ next_index= idx >> 1;
+ while (next_index > start_idx)
+ {
+ if ((queue->compare(queue->first_cmp_arg,
+ queue->root[next_index]+offset_to_key,
+ element+offset_to_key) ^
+ queue->max_at_top) < 0)
+ break;
+ queue->root[idx]=queue->root[next_index];
+ idx=next_index;
+ next_index= idx >> 1;
+ }
+ queue->root[idx]=element;
+}
+
+#else
+ /*
+ The old _downheap version is kept for comparisons with the benchmark
+ suit or new benchmarks anyone wants to run for comparisons.
+ */
+ /* Fix heap when index have changed */
void _downheap(register QUEUE *queue, uint idx)
{
byte *element;
@@ -247,20 +372,336 @@ void _downheap(register QUEUE *queue, uint idx)
}
-static int queue_fix_cmp(QUEUE *queue, void **a, void **b)
-{
- return queue->compare(queue->first_cmp_arg,
- (byte*) (*a)+queue->offset_to_key,
- (byte*) (*b)+queue->offset_to_key);
-}
+#endif
/*
- Fix heap when every element was changed,
- actually, it can be done better, in linear time, not in n*log(n)
+ Fix heap when every element was changed.
*/
void queue_fix(QUEUE *queue)
{
- qsort2(queue->root+1,queue->elements, sizeof(void *),
- (qsort2_cmp)queue_fix_cmp, queue);
+ uint i;
+ for (i= queue->elements >> 1; i > 0; i--)
+ _downheap(queue, i);
+}
+
+#ifdef MAIN
+ /*
+ A test program for the priority queue implementation.
+ It can also be used to benchmark changes of the implementation
+ Build by doing the following in the directory mysys
+ make test_priority_queue
+ ./test_priority_queue
+
+ Written by Mikael Ronström, 2005
+ */
+
+static uint num_array[1025];
+static uint tot_no_parts= 0;
+static uint tot_no_loops= 0;
+static uint expected_part= 0;
+static uint expected_num= 0;
+static bool max_ind= 0;
+static bool fix_used= 0;
+static ulonglong start_time= 0;
+
+static bool is_divisible_by(uint num, uint divisor)
+{
+ uint quotient= num / divisor;
+ if (quotient * divisor == num)
+ return TRUE;
+ return FALSE;
}
+
+void calculate_next()
+{
+ uint part= expected_part, num= expected_num;
+ uint no_parts= tot_no_parts;
+ if (max_ind)
+ {
+ do
+ {
+ while (++part <= no_parts)
+ {
+ if (is_divisible_by(num, part) &&
+ (num <= ((1 << 21) + part)))
+ {
+ expected_part= part;
+ expected_num= num;
+ return;
+ }
+ }
+ part= 0;
+ } while (--num);
+ }
+ else
+ {
+ do
+ {
+ while (--part > 0)
+ {
+ if (is_divisible_by(num, part))
+ {
+ expected_part= part;
+ expected_num= num;
+ return;
+ }
+ }
+ part= no_parts + 1;
+ } while (++num);
+ }
+}
+
+void calculate_end_next(uint part)
+{
+ uint no_parts= tot_no_parts, num;
+ num_array[part]= 0;
+ if (max_ind)
+ {
+ expected_num= 0;
+ for (part= no_parts; part > 0 ; part--)
+ {
+ if (num_array[part])
+ {
+ num= num_array[part] & 0x3FFFFF;
+ if (num >= expected_num)
+ {
+ expected_num= num;
+ expected_part= part;
+ }
+ }
+ }
+ if (expected_num == 0)
+ expected_part= 0;
+ }
+ else
+ {
+ expected_num= 0xFFFFFFFF;
+ for (part= 1; part <= no_parts; part++)
+ {
+ if (num_array[part])
+ {
+ num= num_array[part] & 0x3FFFFF;
+ if (num <= expected_num)
+ {
+ expected_num= num;
+ expected_part= part;
+ }
+ }
+ }
+ if (expected_num == 0xFFFFFFFF)
+ expected_part= 0;
+ }
+ return;
+}
+static int test_compare(void *null_arg, byte *a, byte *b)
+{
+ uint a_num= (*(uint*)a) & 0x3FFFFF;
+ uint b_num= (*(uint*)b) & 0x3FFFFF;
+ uint a_part, b_part;
+ if (a_num > b_num)
+ return +1;
+ if (a_num < b_num)
+ return -1;
+ a_part= (*(uint*)a) >> 22;
+ b_part= (*(uint*)b) >> 22;
+ if (a_part < b_part)
+ return +1;
+ if (a_part > b_part)
+ return -1;
+ return 0;
+}
+
+bool check_num(uint num_part)
+{
+ uint part= num_part >> 22;
+ uint num= num_part & 0x3FFFFF;
+ if (part == expected_part)
+ if (num == expected_num)
+ return FALSE;
+ printf("Expect part %u Expect num 0x%x got part %u num 0x%x max_ind %u fix_used %u \n",
+ expected_part, expected_num, part, num, max_ind, fix_used);
+ return TRUE;
+}
+
+
+void perform_insert(QUEUE *queue)
+{
+ uint i= 1, no_parts= tot_no_parts;
+ uint backward_start= 0;
+
+ expected_part= 1;
+ expected_num= 1;
+
+ if (max_ind)
+ backward_start= 1 << 21;
+
+ do
+ {
+ uint num= (i + backward_start);
+ if (max_ind)
+ {
+ while (!is_divisible_by(num, i))
+ num--;
+ if (max_ind && (num > expected_num ||
+ (num == expected_num && i < expected_part)))
+ {
+ expected_num= num;
+ expected_part= i;
+ }
+ }
+ num_array[i]= num + (i << 22);
+ if (fix_used)
+ queue_element(queue, i-1)= (byte*)&num_array[i];
+ else
+ queue_insert(queue, (byte*)&num_array[i]);
+ } while (++i <= no_parts);
+ if (fix_used)
+ {
+ queue->elements= no_parts;
+ queue_fix(queue);
+ }
+}
+
+bool perform_ins_del(QUEUE *queue, bool max_ind)
+{
+ uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
+ do
+ {
+ uint num_part= *(uint*)queue_top(queue);
+ uint part= num_part >> 22;
+ if (check_num(num_part))
+ return TRUE;
+ if (j++ >= no_loops)
+ {
+ calculate_end_next(part);
+ queue_remove(queue, (uint) 0);
+ }
+ else
+ {
+ calculate_next();
+ if (max_ind)
+ num_array[part]-= part;
+ else
+ num_array[part]+= part;
+ queue_top(queue)= (byte*)&num_array[part];
+ queue_replaced(queue);
+ }
+ } while (++i < no_loops);
+ return FALSE;
+}
+
+bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
+{
+ QUEUE queue;
+ bool result;
+ max_ind= l_max_ind;
+ fix_used= l_fix_used;
+ init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL);
+ tot_no_parts= no_parts;
+ tot_no_loops= 1024;
+ perform_insert(&queue);
+ if ((result= perform_ins_del(&queue, max_ind)))
+ delete_queue(&queue);
+ if (result)
+ {
+ printf("Error\n");
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static void start_measurement()
+{
+ start_time= my_getsystime();
+}
+
+static void stop_measurement()
+{
+ ulonglong stop_time= my_getsystime();
+ uint time_in_micros;
+ stop_time-= start_time;
+ stop_time/= 10; /* Convert to microseconds */
+ time_in_micros= (uint)stop_time;
+ printf("Time expired is %u microseconds \n", time_in_micros);
+}
+
+static void benchmark_test()
+{
+ QUEUE queue_real;
+ QUEUE *queue= &queue_real;
+ uint i, add;
+ fix_used= TRUE;
+ max_ind= FALSE;
+ tot_no_parts= 1024;
+ init_queue(queue, tot_no_parts, 0, max_ind, test_compare, NULL);
+ /*
+ First benchmark whether queue_fix is faster than using queue_insert
+ for sizes of 16 partitions.
+ */
+ for (tot_no_parts= 2, add=2; tot_no_parts < 128;
+ tot_no_parts+= add, add++)
+ {
+ printf("Start benchmark queue_fix, tot_no_parts= %u \n", tot_no_parts);
+ start_measurement();
+ for (i= 0; i < 128; i++)
+ {
+ perform_insert(queue);
+ queue_remove_all(queue);
+ }
+ stop_measurement();
+
+ fix_used= FALSE;
+ printf("Start benchmark queue_insert\n");
+ start_measurement();
+ for (i= 0; i < 128; i++)
+ {
+ perform_insert(queue);
+ queue_remove_all(queue);
+ }
+ stop_measurement();
+ }
+ /*
+ Now benchmark insertion and deletion of 16400 elements.
+ Used in consecutive runs this shows whether the optimised _downheap
+ is faster than the standard implementation.
+ */
+ printf("Start benchmarking _downheap \n");
+ start_measurement();
+ perform_insert(queue);
+ for (i= 0; i < 65536; i++)
+ {
+ uint num, part;
+ num= *(uint*)queue_top(queue);
+ num+= 16;
+ part= num >> 22;
+ num_array[part]= num;
+ queue_top(queue)= (byte*)&num_array[part];
+ queue_replaced(queue);
+ }
+ for (i= 0; i < 16; i++)
+ queue_remove(queue, (uint) 0);
+ queue_remove_all(queue);
+ stop_measurement();
+}
+
+int main()
+{
+ int i, add= 1;
+ for (i= 1; i < 1024; i+=add, add++)
+ {
+ printf("Start test for priority queue of size %u\n", i);
+ if (do_test(i, 0, 1))
+ return -1;
+ if (do_test(i, 1, 1))
+ return -1;
+ if (do_test(i, 0, 0))
+ return -1;
+ if (do_test(i, 1, 0))
+ return -1;
+ }
+ benchmark_test();
+ printf("OK\n");
+ return 0;
+}
+#endif
diff --git a/mysys/raid.cc b/mysys/raid.cc
deleted file mode 100644
index 29819a878c4..00000000000
--- a/mysys/raid.cc
+++ /dev/null
@@ -1,799 +0,0 @@
-/* Copyright (C) 2000 MySQL AB
-
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
-
-/*
-
- RAID support for MySQL. Raid 0 (stiping) only implemented yet.
-
- Why RAID? Why it must be in MySQL?
-
- This is because then you can:
- 1. Have bigger tables than your OS limit. In time of writing this
- we are hitting to 2GB limit under linux/ext2
- 2. You can get more speed from IO bottleneck by putting
- Raid dirs on different physical disks.
- 3. Getting more fault tolerance (not implemented yet)
-
- Why not to use RAID:
-
- 1. You are losing some processor power to calculate things,
- do more syscalls and interrupts.
-
- Functionality is supplied by two classes: RaidFd and RaidName.
- RaidFd supports funtionality over file descriptors like
- open/create/write/seek/close. RaidName supports functionality
- like rename/delete where we have no relations to filedescriptors.
- RaidName can be prorably unchanged for different Raid levels. RaidFd
- have to be virtual I think ;).
- You can speed up some calls in MySQL code by skipping RAID code.
- For example LOAD DATA INFILE never needs to read RAID-ed files.
- This can be done adding proper "#undef my_read" or similar undef-s
- in your code. Check out the raid.h!
-
- Some explanation about _seek_vector[]
- This is seek cache. RAID seeks too much and we cacheing this. We
- fool it and just storing new position in file to _seek_vector.
- When there is no seeks to do, we are putting RAID_SEEK_DONE into it.
- Any other value requires seeking to that position.
-
- TODO:
-
-
- - Implement other fancy things like RAID 1 (mirroring) and RAID 5.
- Should not to be very complex.
-
- - Optimize big blob writes by resorting write buffers and writing
- big chunks at once instead of doing many syscalls. - after thinking I
- found this is useless. This is because same thing one can do with just
- increasing RAID_CHUNKSIZE. Monty, what do you think? tonu.
-
- - If needed, then implement missing syscalls. One known to miss is stat();
-
- - Make and use a thread safe dynamic_array buffer. The used one
- will not work if needs to be extended at the same time someone is
- accessing it.
-
-
- tonu@mysql.com & monty@mysql.com
-*/
-
-#ifdef USE_PRAGMA_IMPLEMENTATION
-#pragma implementation // gcc: Class implementation
-#endif
-
-#include "mysys_priv.h"
-#include <my_dir.h>
-#include <m_string.h>
-#include <assert.h>
-
-#if defined(USE_RAID) && !defined(MYSQL_CLIENT)
-
-#define RAID_SEEK_DONE ~(off_t) 0
-#define RAID_SIZE_UNKNOWN ~(my_off_t) 0
-
-DYNAMIC_ARRAY RaidFd::_raid_map;
-
-
-/* --------------- C compatibility ---------------*/
-
-extern "C" {
-
- void init_raid(void)
- {
- /* Allocate memory for global file to raid map */
- my_init_dynamic_array(&RaidFd::_raid_map, sizeof(RaidFd*), 4096, 1024);
- }
- void end_raid(void)
- {
- /* Free memory used by raid */
- delete_dynamic(&RaidFd::_raid_map);
- }
-
- bool is_raid(File fd)
- {
- return RaidFd::IsRaid(fd);
- }
-
- File my_raid_create(const char *FileName, int CreateFlags, int access_flags,
- uint raid_type, uint raid_chunks, ulong raid_chunksize,
- myf MyFlags)
- {
- DBUG_ENTER("my_raid_create");
- DBUG_PRINT("enter",("Filename: %s CreateFlags: %d access_flags: %d MyFlags: %d",
- FileName, CreateFlags, access_flags, MyFlags));
- if (raid_type)
- {
- RaidFd *raid = new RaidFd(raid_type, raid_chunks , raid_chunksize);
- File res = raid->Create(FileName,CreateFlags,access_flags,MyFlags);
- if (res < 0 || set_dynamic(&RaidFd::_raid_map,(char*) &raid,res))
- {
- delete raid;
- DBUG_RETURN(-1);
- }
- DBUG_RETURN(res);
- }
- else
- DBUG_RETURN(my_create(FileName, CreateFlags, access_flags, MyFlags));
- }
-
- File my_raid_open(const char *FileName, int Flags,
- uint raid_type, uint raid_chunks, ulong raid_chunksize,
- myf MyFlags)
- {
- DBUG_ENTER("my_raid_open");
- DBUG_PRINT("enter",("Filename: %s Flags: %d MyFlags: %d",
- FileName, Flags, MyFlags));
- if (raid_type)
- {
- RaidFd *raid = new RaidFd(raid_type, raid_chunks , raid_chunksize);
- File res = raid->Open(FileName,Flags,MyFlags);
- if (res < 0 || set_dynamic(&RaidFd::_raid_map,(char*) &raid,res))
- {
- delete raid;
- DBUG_RETURN(-1);
- }
- DBUG_RETURN(res);
- }
- else
- DBUG_RETURN(my_open(FileName, Flags, MyFlags));
- }
-
- my_off_t my_raid_seek(File fd, my_off_t pos,int whence,myf MyFlags)
- {
- DBUG_ENTER("my_raid_seek");
- DBUG_PRINT("enter",("Fd: %d pos: %lu whence: %d MyFlags: %d",
- fd, (ulong) pos, whence, MyFlags));
-
- if (is_raid(fd))
- {
- assert(pos != MY_FILEPOS_ERROR);
-
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Seek(pos,whence,MyFlags));
- }
- else
- DBUG_RETURN(my_seek(fd, pos, whence, MyFlags));
- }
-
- my_off_t my_raid_tell(File fd,myf MyFlags)
- {
- DBUG_ENTER("my_raid_tell");
- DBUG_PRINT("enter",("Fd: %d MyFlags: %d",
- fd, MyFlags));
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Tell(MyFlags));
- }
- else
- DBUG_RETURN(my_tell(fd, MyFlags));
- }
-
- uint my_raid_write(File fd,const byte *Buffer, uint Count, myf MyFlags)
- {
- DBUG_ENTER("my_raid_write");
- DBUG_PRINT("enter",("Fd: %d Buffer: 0x%lx Count: %u MyFlags: %d",
- fd, Buffer, Count, MyFlags));
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Write(Buffer,Count,MyFlags));
- } else
- DBUG_RETURN(my_write(fd,Buffer,Count,MyFlags));
- }
-
- uint my_raid_read(File fd, byte *Buffer, uint Count, myf MyFlags)
- {
- DBUG_ENTER("my_raid_read");
- DBUG_PRINT("enter",("Fd: %d Buffer: 0x%lx Count: %u MyFlags: %d",
- fd, Buffer, Count, MyFlags));
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Read(Buffer,Count,MyFlags));
- } else
- DBUG_RETURN(my_read(fd,Buffer,Count,MyFlags));
- }
-
- uint my_raid_pread(File Filedes, byte *Buffer, uint Count, my_off_t offset,
- myf MyFlags)
- {
- DBUG_ENTER("my_raid_pread");
- DBUG_PRINT("enter",
- ("Fd: %d Buffer: 0x%lx Count: %u offset: %u MyFlags: %d",
- Filedes, Buffer, Count, offset, MyFlags));
- if (is_raid(Filedes))
- {
- assert(offset != MY_FILEPOS_ERROR);
-
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,Filedes,RaidFd**));
- /* Returning value isn't important because real seek is done later. */
- raid->Seek(offset,MY_SEEK_SET,MyFlags);
- DBUG_RETURN(raid->Read(Buffer,Count,MyFlags));
- }
- else
- DBUG_RETURN(my_pread(Filedes, Buffer, Count, offset, MyFlags));
- }
-
- uint my_raid_pwrite(int Filedes, const byte *Buffer, uint Count,
- my_off_t offset, myf MyFlags)
- {
- DBUG_ENTER("my_raid_pwrite");
- DBUG_PRINT("enter",
- ("Fd: %d Buffer: 0x %lx Count: %u offset: %u MyFlags: %d",
- Filedes, Buffer, Count, offset, MyFlags));
- if (is_raid(Filedes))
- {
- assert(offset != MY_FILEPOS_ERROR);
-
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,Filedes,RaidFd**));
- /* Returning value isn't important because real seek is done later. */
- raid->Seek(offset,MY_SEEK_SET,MyFlags);
- DBUG_RETURN(raid->Write(Buffer,Count,MyFlags));
- }
- else
- DBUG_RETURN(my_pwrite(Filedes, Buffer, Count, offset, MyFlags));
- }
-
- int my_raid_lock(File fd, int locktype, my_off_t start, my_off_t length,
- myf MyFlags)
- {
- DBUG_ENTER("my_raid_lock");
- DBUG_PRINT("enter",("Fd: %d start: %u length: %u MyFlags: %d",
- fd, start, length, MyFlags));
- if (my_disable_locking)
- DBUG_RETURN(0);
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Lock(locktype, start, length, MyFlags));
- }
- else
- DBUG_RETURN(my_lock(fd, locktype, start, length, MyFlags));
- }
-
- int my_raid_close(File fd, myf MyFlags)
- {
- DBUG_ENTER("my_raid_close");
- DBUG_PRINT("enter",("Fd: %d MyFlags: %d",
- fd, MyFlags));
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- RaidFd *tmp=0;
- set_dynamic(&RaidFd::_raid_map,(char*) &tmp,fd);
- int res = raid->Close(MyFlags);
- delete raid;
- DBUG_RETURN(res);
- }
- else
- DBUG_RETURN(my_close(fd, MyFlags));
- }
-
- int my_raid_chsize(File fd, my_off_t newlength, int filler, myf MyFlags)
- {
- DBUG_ENTER("my_raid_chsize");
- DBUG_PRINT("enter",("Fd: %d newlength: %u MyFlags: %d",
- fd, newlength, MyFlags));
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Chsize(fd, newlength, filler, MyFlags));
- }
- else
- DBUG_RETURN(my_chsize(fd, newlength, filler, MyFlags));
- }
-
- int my_raid_rename(const char *from, const char *to,
- uint raid_chunks, myf MyFlags)
- {
- char from_tmp[FN_REFLEN];
- char to_tmp[FN_REFLEN];
- DBUG_ENTER("my_raid_rename");
-
- uint from_pos = dirname_length(from);
- uint to_pos = dirname_length(to);
- memcpy(from_tmp, from, from_pos);
- memcpy(to_tmp, to, to_pos);
- for (uint i = 0 ; i < raid_chunks ; i++ )
- {
- sprintf(from_tmp+from_pos,"%02x/%s", i, from + from_pos);
- sprintf(to_tmp+to_pos,"%02x/%s", i, to+ to_pos);
- /* Convert if not unix */
- unpack_filename(from_tmp, from_tmp);
- unpack_filename(to_tmp,to_tmp);
- if (my_rename(from_tmp, to_tmp, MyFlags))
- DBUG_RETURN(-1);
- }
- DBUG_RETURN(0);
- }
-
- int my_raid_delete(const char *from, uint raid_chunks, myf MyFlags)
- {
- char from_tmp[FN_REFLEN];
- uint from_pos = dirname_length(from);
- DBUG_ENTER("my_raid_delete");
-
- if (!raid_chunks)
- DBUG_RETURN(my_delete(from,MyFlags));
- for (uint i = 0 ; i < raid_chunks ; i++ )
- {
- memcpy(from_tmp, from, from_pos);
- sprintf(from_tmp+from_pos,"%02x/%s", i, from + from_pos);
- /* Convert if not unix */
- unpack_filename(from_tmp, from_tmp);
- if (my_delete(from_tmp, MyFlags))
- DBUG_RETURN(-1);
- }
- DBUG_RETURN(0);
- }
-
- int my_raid_redel(const char *old_name, const char *new_name,
- uint raid_chunks, myf MyFlags)
- {
- char new_name_buff[FN_REFLEN], old_name_buff[FN_REFLEN];
- char *new_end, *old_end;
- uint i,old_length,new_length;
- int error=0;
- DBUG_ENTER("my_raid_redel");
-
- old_end=old_name_buff+dirname_part(old_name_buff,old_name);
- old_length=dirname_length(old_name);
- new_end=new_name_buff+dirname_part(new_name_buff,new_name);
- new_length=dirname_length(new_name);
- for (i=0 ; i < raid_chunks ; i++)
- {
- MY_STAT status;
- sprintf(new_end,"%02x",i);
- if (my_stat(new_name_buff,&status, MYF(0)))
- {
- DBUG_PRINT("info",("%02x exists, skipping directory creation",i));
- }
- else
- {
- if (my_mkdir(new_name_buff,0777,MYF(0)))
- {
- DBUG_PRINT("error",("mkdir failed for %02x",i));
- DBUG_RETURN(-1);
- }
- }
- strxmov(strend(new_end),"/",new_name+new_length,NullS);
- sprintf(old_end,"%02x/%s",i, old_name+old_length);
- if (my_redel(old_name_buff, new_name_buff, MyFlags))
- error=1;
- }
- DBUG_RETURN(error);
- }
-}
-
-int my_raid_fstat(int fd, MY_STAT *stat_area, myf MyFlags )
-{
- DBUG_ENTER("my_raid_fstat");
- if (is_raid(fd))
- {
- RaidFd *raid= (*dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
- DBUG_RETURN(raid->Fstat(fd, stat_area, MyFlags));
- }
- else
- DBUG_RETURN(my_fstat(fd, stat_area, MyFlags));
-}
-
-
-/* -------------- RaidFd base class begins ----------------*/
-/*
- RaidFd - raided file is identified by file descriptor
- this is useful when we open/write/read/close files
-*/
-
-
-bool RaidFd::
-IsRaid(File fd)
-{
- DBUG_ENTER("RaidFd::IsRaid");
- DBUG_RETURN((uint) fd < _raid_map.elements &&
- *dynamic_element(&RaidFd::_raid_map,fd,RaidFd**));
-}
-
-
-RaidFd::
-RaidFd(uint raid_type, uint raid_chunks, ulong raid_chunksize)
- :_raid_type(raid_type), _raid_chunks(raid_chunks),
- _raid_chunksize(raid_chunksize), _position(0), _size(RAID_SIZE_UNKNOWN),
- _fd_vector(0)
-{
- DBUG_ENTER("RaidFd::RaidFd");
- DBUG_PRINT("enter",("RaidFd_type: %u Disks: %u Chunksize: %d",
- raid_type, raid_chunks, raid_chunksize));
-
- /* TODO: Here we should add checks if the malloc fails */
- _seek_vector=0; /* In case of errors */
- my_multi_malloc(MYF(MY_WME),
- &_seek_vector,sizeof(off_t)*_raid_chunks,
- &_fd_vector, sizeof(File) *_raid_chunks,
- NullS);
- if (!RaidFd::_raid_map.buffer)
- { /* Not initied */
- pthread_mutex_lock(&THR_LOCK_open); /* Ensure that no other thread */
- if (!RaidFd::_raid_map.buffer) /* has done init in between */
- init_raid();
- pthread_mutex_unlock(&THR_LOCK_open);
- }
- DBUG_VOID_RETURN;
-}
-
-
-RaidFd::
-~RaidFd() {
- DBUG_ENTER("RaidFd::~RaidFd");
- /* We don't have to free _fd_vector ! */
- my_free((char*) _seek_vector, MYF(MY_ALLOW_ZERO_PTR));
- DBUG_VOID_RETURN;
-}
-
-
-File RaidFd::
-Create(const char *FileName, int CreateFlags, int access_flags, myf MyFlags)
-{
- char RaidFdFileName[FN_REFLEN];
- DBUG_ENTER("RaidFd::Create");
- DBUG_PRINT("enter",
- ("FileName: %s CreateFlags: %d access_flags: %d MyFlags: %d",
- FileName, CreateFlags, access_flags, MyFlags));
- char DirName[FN_REFLEN];
- uint pos = dirname_part(DirName, FileName);
- MY_STAT status;
- if (!_seek_vector)
- DBUG_RETURN(-1); /* Not enough memory */
-
- uint i = _raid_chunks-1;
- do
- {
- /* Create subdir */
- (void)sprintf(RaidFdFileName,"%s%02x", DirName,i);
- unpack_dirname(RaidFdFileName,RaidFdFileName); /* Convert if not unix */
- if (my_stat(RaidFdFileName,&status, MYF(0)))
- {
- DBUG_PRINT("info",("%02x exists, skipping directory creation",i));
- }
- else
- {
- if (my_mkdir(RaidFdFileName,0777,MYF(0)))
- {
- DBUG_PRINT("error",("mkdir failed for %d",i));
- goto error;
- }
- }
- /* Create file */
- sprintf(RaidFdFileName,"%s%02x/%s",DirName, i, FileName + pos);
- unpack_filename(RaidFdFileName,RaidFdFileName); /* Convert if not unix */
- _fd = my_create(RaidFdFileName, CreateFlags ,access_flags, (myf)MyFlags);
- if (_fd < 0)
- goto error;
- _fd_vector[i]=_fd;
- _seek_vector[i]=RAID_SEEK_DONE;
- } while (i--);
- _size=0;
- DBUG_RETURN(_fd); /* Last filenr is pointer to map */
-
-error:
- {
- int save_errno=my_errno;
- while (++i < _raid_chunks)
- {
- my_close(_fd_vector[i],MYF(0));
- sprintf(RaidFdFileName,"%s%02x/%s",DirName, i, FileName + pos);
- unpack_filename(RaidFdFileName,RaidFdFileName);
- my_delete(RaidFdFileName,MYF(0));
- }
- my_errno=save_errno;
- }
- DBUG_RETURN(-1);
-}
-
-
-File RaidFd::
-Open(const char *FileName, int Flags, myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Open");
- DBUG_PRINT("enter",("FileName: %s Flags: %d MyFlags: %d",
- FileName, Flags, MyFlags));
- char DirName[FN_REFLEN];
- uint pos = dirname_part(DirName, FileName);
- if (!_seek_vector)
- DBUG_RETURN(-1); /* Not enough memory */
-
- for( uint i = 0 ; i < _raid_chunks ; i++ )
- {
- char RaidFdFileName[FN_REFLEN];
- sprintf(RaidFdFileName,"%s%02x/%s",DirName, i, FileName + pos);
- unpack_filename(RaidFdFileName,RaidFdFileName); /* Convert if not unix */
- _fd = my_open(RaidFdFileName, Flags, MyFlags);
- if (_fd < 0)
- {
- int save_errno=my_errno;
- while (i-- != 0)
- my_close(_fd_vector[i],MYF(0));
- my_errno=save_errno;
- DBUG_RETURN(_fd);
- }
- _fd_vector[i]=_fd;
- _seek_vector[i]=RAID_SEEK_DONE;
- }
- Seek(0L,MY_SEEK_END,MYF(0)); // Trick. We just need to know, how big the file is
- DBUG_PRINT("info",("MYD file logical size: %llu", _size));
- DBUG_RETURN(_fd);
-}
-
-
-int RaidFd::
-Write(const byte *Buffer, uint Count, myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Write");
- DBUG_PRINT("enter",("Count: %d MyFlags: %d",
- Count, MyFlags));
- const byte *bufptr = Buffer;
- uint res=0, GotBytes, ReadNowCount;
-
- // Loop until data is written
- do {
- Calculate();
- // Do seeks when neccessary
- if (_seek_vector[_this_block] != RAID_SEEK_DONE)
- {
- if (my_seek(_fd_vector[_this_block], _seek_vector[_this_block],
- MY_SEEK_SET,
- MyFlags) == MY_FILEPOS_ERROR)
- DBUG_RETURN(-1);
- _seek_vector[_this_block]=RAID_SEEK_DONE;
- }
- ReadNowCount = min(Count, _remaining_bytes);
- GotBytes = my_write(_fd_vector[_this_block], bufptr, ReadNowCount,
- MyFlags);
- DBUG_PRINT("loop",("Wrote bytes: %d", GotBytes));
- if (GotBytes == MY_FILE_ERROR)
- DBUG_RETURN(-1);
- res+= GotBytes;
- if (MyFlags & (MY_NABP | MY_FNABP))
- GotBytes=ReadNowCount;
- bufptr += GotBytes;
- Count -= GotBytes;
- _position += GotBytes;
- } while(Count);
- set_if_bigger(_size,_position);
- DBUG_RETURN(res);
-}
-
-
-int RaidFd::
-Read(const byte *Buffer, uint Count, myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Read");
- DBUG_PRINT("enter",("Count: %d MyFlags: %d",
- Count, MyFlags));
- byte *bufptr = (byte *)Buffer;
- uint res= 0, GotBytes, ReadNowCount;
-
- // Loop until all data is read (Note that Count may be 0)
- while (Count)
- {
- Calculate();
- // Do seek when neccessary
- if (_seek_vector[_this_block] != RAID_SEEK_DONE)
- {
- if (my_seek(_fd_vector[_this_block], _seek_vector[_this_block],
- MY_SEEK_SET,
- MyFlags) == MY_FILEPOS_ERROR)
- DBUG_RETURN(-1);
- _seek_vector[_this_block]=RAID_SEEK_DONE;
- }
- // and read
- ReadNowCount = min(Count, _remaining_bytes);
- GotBytes = my_read(_fd_vector[_this_block], bufptr, ReadNowCount,
- MyFlags & ~(MY_NABP | MY_FNABP));
- DBUG_PRINT("loop",("Got bytes: %u", GotBytes));
- if (GotBytes == MY_FILE_ERROR)
- DBUG_RETURN(-1);
- if (!GotBytes) // End of file.
- {
- DBUG_RETURN((MyFlags & (MY_NABP | MY_FNABP)) ? -1 : (int) res);
- }
- res+= GotBytes;
- bufptr += GotBytes;
- Count -= GotBytes;
- _position += GotBytes;
- }
- DBUG_RETURN((MyFlags & (MY_NABP | MY_FNABP)) ? 0 : res);
-}
-
-
-int RaidFd::
-Lock(int locktype, my_off_t start, my_off_t length, myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Lock");
- DBUG_PRINT("enter",("locktype: %d start: %lu length: %lu MyFlags: %d",
- locktype, start, length, MyFlags));
- my_off_t bufptr = start;
- // Loop until all data is locked
- while(length)
- {
- Calculate();
- for (uint i = _this_block ; (i < _raid_chunks) && length ; i++ )
- {
- uint ReadNowCount = min(length, _remaining_bytes);
- uint GotBytes = my_lock(_fd_vector[i], locktype, bufptr, ReadNowCount,
- MyFlags);
- if ((int) GotBytes == -1)
- DBUG_RETURN(-1);
- bufptr += ReadNowCount;
- length -= ReadNowCount;
- Calculate();
- }
- }
- DBUG_RETURN(0);
-}
-
-
-int RaidFd::
-Close(myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Close");
- DBUG_PRINT("enter",("MyFlags: %d",
- MyFlags));
- for (uint i = 0 ; i < _raid_chunks ; ++i )
- {
- int err = my_close(_fd_vector[i], MyFlags);
- if (err != 0)
- DBUG_RETURN(err);
- }
- /* _fd_vector is erased when RaidFd is released */
- DBUG_RETURN(0);
-}
-
-
-my_off_t RaidFd::
-Seek(my_off_t pos,int whence,myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Seek");
- DBUG_PRINT("enter",("Pos: %lu Whence: %d MyFlags: %d",
- (ulong) pos, whence, MyFlags));
- switch (whence) {
- case MY_SEEK_CUR:
- // FIXME: This is wrong, what is going on there
- // Just I am relied on fact that MySQL 3.23.7 never uses MY_SEEK_CUR
- // for anything else except things like ltell()
- break;
- case MY_SEEK_SET:
- if ( _position != pos) // we can be already in right place
- {
- uint i;
- off_t _rounds;
- _position = pos;
- Calculate();
- _rounds = _total_block / _raid_chunks; // INT() assumed
- _rounds*= _raid_chunksize;
- for (i = 0; i < _raid_chunks ; i++ )
- if ( i < _this_block )
- _seek_vector[i] = _rounds + _raid_chunksize;
- else if ( i == _this_block )
- _seek_vector[i] = _rounds + _raid_chunksize -_remaining_bytes;
- else // if ( i > _this_block )
- _seek_vector[i] = _rounds;
- }
- break;
- case MY_SEEK_END:
- if (_size==RAID_SIZE_UNKNOWN) // We don't know table size yet
- {
- uint i;
- _position = 0;
- for (i = 0; i < _raid_chunks ; i++ )
- {
- my_off_t newpos = my_seek(_fd_vector[i], 0L, MY_SEEK_END, MyFlags);
- if (newpos == MY_FILEPOS_ERROR)
- DBUG_RETURN (MY_FILEPOS_ERROR);
- _seek_vector[i]=RAID_SEEK_DONE;
- _position += newpos;
- }
- _size=_position;
- }
- else if (_position != _size) // Aren't we also already in the end?
- {
- uint i;
- off_t _rounds;
- _position = _size;
- Calculate();
- _rounds = _total_block / _raid_chunks; // INT() assumed
- _rounds*= _raid_chunksize;
- for (i = 0; i < _raid_chunks ; i++ )
- if ( i < _this_block )
- _seek_vector[i] = _rounds + _raid_chunksize;
- else if ( i == _this_block )
- _seek_vector[i] = _rounds + _raid_chunksize - _remaining_bytes;
- else // if ( i > _this_block )
- _seek_vector[i] = _rounds;
- _position=_size;
- }
- }
- DBUG_RETURN(_position);
-}
-
-
-my_off_t RaidFd::
-Tell(myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Tell");
- DBUG_PRINT("enter",("MyFlags: %d _position %d",
- MyFlags,_position));
- DBUG_RETURN(_position);
-}
-
-int RaidFd::
-Chsize(File fd, my_off_t newlength, int filler, myf MyFlags)
-{
- DBUG_ENTER("RaidFd::Chsize");
- DBUG_PRINT("enter",("Fd: %d, newlength: %d, MyFlags: %d",
- fd, newlength,MyFlags));
- _position = newlength;
- Calculate();
- uint _rounds = _total_block / _raid_chunks; // INT() assumed
- for (uint i = 0; i < _raid_chunks ; i++ )
- {
- int newpos;
- if ( i < _this_block )
- newpos = my_chsize(_fd_vector[i],
- _this_block * _raid_chunksize + (_rounds + 1) *
- _raid_chunksize, filler, MyFlags);
- else if ( i == _this_block )
- newpos = my_chsize(_fd_vector[i],
- _this_block * _raid_chunksize + _rounds *
- _raid_chunksize + (newlength % _raid_chunksize),
- filler, MyFlags);
- else // this means: i > _this_block
- newpos = my_chsize(_fd_vector[i],
- _this_block * _raid_chunksize + _rounds *
- _raid_chunksize, filler, MyFlags);
- if (newpos)
- DBUG_RETURN(1);
- }
- DBUG_RETURN(0);
-}
-
-
-int RaidFd::
-Fstat(int fd, MY_STAT *stat_area, myf MyFlags )
-{
- DBUG_ENTER("RaidFd::Fstat");
- DBUG_PRINT("enter",("fd: %d MyFlags: %d",fd,MyFlags));
- uint i;
- int error=0;
- MY_STAT status;
- stat_area->st_size=0;
- stat_area->st_mtime=0;
- stat_area->st_atime=0;
- stat_area->st_ctime=0;
-
- for(i=0 ; i < _raid_chunks ; i++)
- {
- if (my_fstat(_fd_vector[i],&status,MyFlags))
- error=1;
- stat_area->st_size+=status.st_size;
- set_if_bigger(stat_area->st_mtime,status.st_mtime);
- set_if_bigger(stat_area->st_atime,status.st_atime);
- set_if_bigger(stat_area->st_ctime,status.st_ctime);
- }
- DBUG_RETURN(error);
-}
-
-#endif /* defined(USE_RAID) && !defined(MYSQL_CLIENT) */
diff --git a/mysys/raid2.c b/mysys/raid2.c
deleted file mode 100644
index 94b085b0074..00000000000
--- a/mysys/raid2.c
+++ /dev/null
@@ -1,31 +0,0 @@
-/* Copyright (C) 2002 MySQL AB
-
- This library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Library General Public
- License as published by the Free Software Foundation; either
- version 2 of the License, or (at your option) any later version.
-
- This library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Library General Public License for more details.
-
- You should have received a copy of the GNU Library General Public
- License along with this library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- MA 02111-1307, USA */
-
-/*
- RAID support for MySQL. For full comments, check raid.cc
- This is in a separate file to not cause problems on OS that can't
- put C++ files in archives.
-*/
-
-#include "mysys_priv.h"
-
-const char *raid_type_string[]={"none","striped"};
-
-const char *my_raid_type(int raid_type)
-{
- return raid_type_string[raid_type];
-}
diff --git a/mysys/safemalloc.c b/mysys/safemalloc.c
index 6cdf98c5f5f..e40fd751037 100644
--- a/mysys/safemalloc.c
+++ b/mysys/safemalloc.c
@@ -525,7 +525,7 @@ char *_my_strdup(const char *from, const char *filename, uint lineno,
} /* _my_strdup */
-char *_my_strdup_with_length(const byte *from, uint length,
+char *_my_strndup(const byte *from, uint length,
const char *filename, uint lineno,
myf MyFlags)
{
diff --git a/mysys/testhash.c b/mysys/testhash.c
index d15016113cd..a0bc6685d61 100644
--- a/mysys/testhash.c
+++ b/mysys/testhash.c
@@ -250,7 +250,6 @@ err:
static int get_options(int argc, char **argv)
{
char *pos,*progname;
- DEBUGGER_OFF;
progname= argv[0];
@@ -270,7 +269,6 @@ static int get_options(int argc, char **argv)
printf("Usage: %s [-?ABIKLWv] [-m#] [-t#]\n",progname);
exit(0);
case '#':
- DEBUGGER_ON;
DBUG_PUSH (++pos);
break;
}
diff --git a/mysys/thr_lock.c b/mysys/thr_lock.c
index f5a8b618949..4b3e03750c8 100644
--- a/mysys/thr_lock.c
+++ b/mysys/thr_lock.c
@@ -1009,7 +1009,7 @@ void thr_multi_unlock(THR_LOCK_DATA **data,uint count)
TL_WRITE_ONLY to abort any new accesses to the lock
*/
-void thr_abort_locks(THR_LOCK *lock)
+void thr_abort_locks(THR_LOCK *lock, bool upgrade_lock)
{
THR_LOCK_DATA *data;
DBUG_ENTER("thr_abort_locks");
@@ -1031,7 +1031,7 @@ void thr_abort_locks(THR_LOCK *lock)
lock->read_wait.last= &lock->read_wait.data;
lock->write_wait.last= &lock->write_wait.data;
lock->read_wait.data=lock->write_wait.data=0;
- if (lock->write.data)
+ if (upgrade_lock && lock->write.data)
lock->write.data->type=TL_WRITE_ONLY;
pthread_mutex_unlock(&lock->mutex);
DBUG_VOID_RETURN;
@@ -1089,6 +1089,213 @@ my_bool thr_abort_locks_for_thread(THR_LOCK *lock, pthread_t thread)
}
+/*
+ Downgrade a WRITE_* to a lower WRITE level
+ SYNOPSIS
+ thr_downgrade_write_lock()
+ in_data Lock data of thread downgrading its lock
+ new_lock_type New write lock type
+ RETURN VALUE
+ NONE
+ DESCRIPTION
+ This can be used to downgrade a lock already owned. When the downgrade
+ occurs also other waiters, both readers and writers can be allowed to
+ start.
+ The previous lock is often TL_WRITE_ONLY but can also be
+ TL_WRITE and TL_WRITE_ALLOW_READ. The normal downgrade variants are
+ TL_WRITE_ONLY => TL_WRITE_ALLOW_READ After a short exclusive lock
+ TL_WRITE_ALLOW_READ => TL_WRITE_ALLOW_WRITE After discovering that the
+ operation didn't need such a high lock.
+ TL_WRITE_ONLY => TL_WRITE after a short exclusive lock while holding a
+ write table lock
+ TL_WRITE_ONLY => TL_WRITE_ALLOW_WRITE After a short exclusive lock after
+ already earlier having dongraded lock to TL_WRITE_ALLOW_WRITE
+ The implementation is conservative and rather don't start rather than
+ go on unknown paths to start, the common cases are handled.
+
+ NOTE:
+ In its current implementation it is only allowed to downgrade from
+ TL_WRITE_ONLY. In this case there are no waiters. Thus no wake up
+ logic is required.
+*/
+
+void thr_downgrade_write_lock(THR_LOCK_DATA *in_data,
+ enum thr_lock_type new_lock_type)
+{
+ THR_LOCK *lock=in_data->lock;
+ THR_LOCK_DATA *data, *next;
+ enum thr_lock_type old_lock_type= in_data->type;
+ bool start_writers= FALSE;
+ bool start_readers= FALSE;
+ DBUG_ENTER("thr_downgrade_write_only_lock");
+
+ pthread_mutex_lock(&lock->mutex);
+ DBUG_ASSERT(old_lock_type == TL_WRITE_ONLY);
+ DBUG_ASSERT(old_lock_type > new_lock_type);
+ in_data->type= new_lock_type;
+ check_locks(lock,"after downgrading lock",0);
+#if 0
+ switch (old_lock_type)
+ {
+ case TL_WRITE_ONLY:
+ case TL_WRITE:
+ case TL_WRITE_LOW_PRIORITY:
+ /*
+ Previous lock was exclusive we are now ready to start up most waiting
+ threads.
+ */
+ switch (new_lock_type)
+ {
+ case TL_WRITE_ALLOW_READ:
+ /* Still cannot start WRITE operations. Can only start readers. */
+ start_readers= TRUE;
+ break;
+ case TL_WRITE:
+ case TL_WRITE_LOW_PRIORITY:
+ /*
+ Still cannot start anything, but new requests are no longer
+ aborted.
+ */
+ break;
+ case TL_WRITE_ALLOW_WRITE:
+ /*
+ We can start both writers and readers.
+ */
+ start_writers= TRUE;
+ start_readers= TRUE;
+ break;
+ case TL_WRITE_CONCURRENT_INSERT:
+ case TL_WRITE_DELAYED:
+ /*
+ This routine is not designed for those. Lock will be downgraded
+ but no start of waiters will occur. This is not the optimal but
+ should be a correct behaviour.
+ */
+ break;
+ default:
+ DBUG_ASSERT(0);
+ }
+ break;
+ case TL_WRITE_DELAYED:
+ case TL_WRITE_CONCURRENT_INSERT:
+ /*
+ This routine is not designed for those. Lock will be downgraded
+ but no start of waiters will occur. This is not the optimal but
+ should be a correct behaviour.
+ */
+ break;
+ case TL_WRITE_ALLOW_READ:
+ DBUG_ASSERT(new_lock_type == TL_WRITE_ALLOW_WRITE);
+ /*
+ Previously writers were not allowed to start, now it is ok to
+ start them again. Readers are already allowed so no reason to
+ handle them.
+ */
+ start_writers= TRUE;
+ break;
+ default:
+ DBUG_ASSERT(0);
+ break;
+ }
+ if (start_writers)
+ {
+ /*
+ At this time the only active writer can be ourselves. Thus we need
+ not worry about that there are other concurrent write operations
+ active on the table. Thus we only need to worry about starting
+ waiting operations.
+ We also only come here with TL_WRITE_ALLOW_WRITE as the new
+ lock type, thus we can start other writers also of the same type.
+ If we find a lock at exclusive level >= TL_WRITE_LOW_PRIORITY we
+ don't start any more operations that would be mean those operations
+ will have to wait for things started afterwards.
+ */
+ DBUG_ASSERT(new_lock_type == TL_WRITE_ALLOW_WRITE);
+ for (data=lock->write_wait.data; data ; data= next)
+ {
+ /*
+ All WRITE requests compatible with new lock type are also
+ started
+ */
+ next= data->next;
+ if (start_writers && data->type == new_lock_type)
+ {
+ pthread_cond_t *cond= data->cond;
+ /*
+ It is ok to start this waiter.
+ Move from being first in wait queue to be last in write queue.
+ */
+ if (((*data->prev)= data->next))
+ data->next->prev= data->prev;
+ else
+ lock->write_wait.last= data->prev;
+ data->prev= lock->write.last;
+ lock->write.last= &data->next;
+ data->next= 0;
+ check_locks(lock, "Started write lock after downgrade",0);
+ data->cond= 0;
+ pthread_cond_signal(cond);
+ }
+ else
+ {
+ /*
+ We found an incompatible lock, we won't start any more write
+ requests to avoid letting writers pass other writers in the
+ queue.
+ */
+ start_writers= FALSE;
+ if (data->type >= TL_WRITE_LOW_PRIORITY)
+ {
+ /*
+ We have an exclusive writer in the queue so we won't start
+ readers either.
+ */
+ start_readers= FALSE;
+ }
+ }
+ }
+ }
+ if (start_readers)
+ {
+ DBUG_ASSERT(new_lock_type == TL_WRITE_ALLOW_WRITE ||
+ new_lock_type == TL_WRITE_ALLOW_READ);
+ /*
+ When we come here we know that the write locks are
+ TL_WRITE_ALLOW_WRITE or TL_WRITE_ALLOW_READ. This means that reads
+ are ok
+ */
+ for (data=lock->read_wait.data; data ; data=next)
+ {
+ next= data->next;
+ /*
+ All reads are ok to start now except TL_READ_NO_INSERT when
+ write lock is TL_WRITE_ALLOW_READ.
+ */
+ if (new_lock_type != TL_WRITE_ALLOW_READ ||
+ data->type != TL_READ_NO_INSERT)
+ {
+ pthread_cond_t *cond= data->cond;
+ if (((*data->prev)= data->next))
+ data->next->prev= data->prev;
+ else
+ lock->read_wait.last= data->prev;
+ data->prev= lock->read.last;
+ lock->read.last= &data->next;
+ data->next= 0;
+
+ if (data->type == TL_READ_NO_INSERT)
+ lock->read_no_write_count++;
+ check_locks(lock, "Started read lock after downgrade",0);
+ data->cond= 0;
+ pthread_cond_signal(cond);
+ }
+ }
+ }
+ check_locks(lock,"after starting waiters after downgrading lock",0);
+#endif
+ pthread_mutex_unlock(&lock->mutex);
+ DBUG_VOID_RETURN;
+}
/* Upgrade a WRITE_DELAY lock to a WRITE_LOCK */
diff --git a/mysys/thr_mutex.c b/mysys/thr_mutex.c
index 1791bb6e4c4..7d6c762f455 100644
--- a/mysys/thr_mutex.c
+++ b/mysys/thr_mutex.c
@@ -357,3 +357,80 @@ void safe_mutex_end(FILE *file __attribute__((unused)))
}
#endif /* THREAD && SAFE_MUTEX */
+
+#if defined(THREAD) && defined(MY_PTHREAD_FASTMUTEX) && !defined(SAFE_MUTEX)
+
+#include "mysys_priv.h"
+#include "my_static.h"
+#include <m_string.h>
+
+#include <m_ctype.h>
+#include <hash.h>
+#include <myisampack.h>
+#include <mysys_err.h>
+#include <my_sys.h>
+
+#undef pthread_mutex_t
+#undef pthread_mutex_init
+#undef pthread_mutex_lock
+#undef pthread_mutex_trylock
+#undef pthread_mutex_unlock
+#undef pthread_mutex_destroy
+#undef pthread_cond_wait
+#undef pthread_cond_timedwait
+
+ulong mutex_delay(ulong delayloops)
+{
+ ulong i;
+ volatile ulong j;
+
+ j = 0;
+
+ for (i = 0; i < delayloops * 50; i++)
+ j += i;
+
+ return(j);
+}
+
+#define MY_PTHREAD_FASTMUTEX_SPINS 8
+#define MY_PTHREAD_FASTMUTEX_DELAY 4
+
+int my_pthread_fastmutex_init(my_pthread_fastmutex_t *mp,
+ const pthread_mutexattr_t *attr)
+{
+ static int cpu_count= 0;
+#ifdef _SC_NPROCESSORS_CONF
+ if (!cpu_count && (attr == MY_MUTEX_INIT_FAST))
+ cpu_count= sysconf(_SC_NPROCESSORS_CONF);
+#endif
+
+ if ((cpu_count > 1) && (attr == MY_MUTEX_INIT_FAST))
+ mp->spins= MY_PTHREAD_FASTMUTEX_SPINS;
+ else
+ mp->spins= 0;
+ return pthread_mutex_init(&mp->mutex, attr);
+}
+
+int my_pthread_fastmutex_lock(my_pthread_fastmutex_t *mp)
+{
+ int res;
+ uint i;
+ uint maxdelay= MY_PTHREAD_FASTMUTEX_DELAY;
+
+ for (i= 0; i < mp->spins; i++)
+ {
+ res= pthread_mutex_trylock(&mp->mutex);
+
+ if (res == 0)
+ return 0;
+
+ if (res != EBUSY)
+ return res;
+
+ mutex_delay(maxdelay);
+ maxdelay += ((double) random() / (double) RAND_MAX) *
+ MY_PTHREAD_FASTMUTEX_DELAY + 1;
+ }
+ return pthread_mutex_lock(&mp->mutex);
+}
+#endif /* defined(THREAD) && defined(MY_PTHREAD_FASTMUTEX) && !defined(SAFE_MUTEX) */
diff --git a/mysys/trie.c b/mysys/trie.c
new file mode 100644
index 00000000000..1f638f8f732
--- /dev/null
+++ b/mysys/trie.c
@@ -0,0 +1,237 @@
+/* Copyright (C) 2005 MySQL AB
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/*
+ Implementation of trie and Aho-Corasick automaton.
+ Supports only charsets that can be compared byte-wise.
+
+ TODO:
+ Add character frequencies. Can increase lookup speed
+ up to 30%.
+ Implement character-wise comparision.
+*/
+
+
+#include "mysys_priv.h"
+#include <m_string.h>
+#include <my_trie.h>
+#include <my_base.h>
+
+
+/*
+ SYNOPSIS
+ TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset);
+
+ DESCRIPTION
+ Allocates or initializes a `TRIE' object. If `trie' is a `NULL'
+ pointer, the function allocates, initializes, and returns a new
+ object. Otherwise, the object is initialized and the address of
+ the object is returned. If `trie_init()' allocates a new object,
+ it will be freed when `trie_free()' is called.
+
+ RETURN VALUE
+ An initialized `TRIE*' object. `NULL' if there was insufficient
+ memory to allocate a new object.
+*/
+
+TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset)
+{
+ MEM_ROOT mem_root;
+ DBUG_ENTER("trie_init");
+ DBUG_ASSERT(charset);
+ init_alloc_root(&mem_root,
+ (sizeof(TRIE_NODE) * 128) + ALLOC_ROOT_MIN_BLOCK_SIZE,
+ sizeof(TRIE_NODE) * 128);
+ if (! trie)
+ {
+ if (! (trie= (TRIE *)alloc_root(&mem_root, sizeof(TRIE))))
+ {
+ free_root(&mem_root, MYF(0));
+ DBUG_RETURN(NULL);
+ }
+ }
+
+ memcpy(&trie->mem_root, &mem_root, sizeof(MEM_ROOT));
+ trie->root.leaf= 0;
+ trie->root.c= 0;
+ trie->root.next= NULL;
+ trie->root.links= NULL;
+ trie->root.fail= NULL;
+ trie->charset= charset;
+ trie->nnodes= 0;
+ trie->nwords= 0;
+ DBUG_RETURN(trie);
+}
+
+
+/*
+ SYNOPSIS
+ void trie_free (TRIE *trie);
+ trie - valid pointer to `TRIE'
+
+ DESCRIPTION
+ Frees the memory allocated for a `trie'.
+
+ RETURN VALUE
+ None.
+*/
+
+void trie_free (TRIE *trie)
+{
+ MEM_ROOT mem_root;
+ DBUG_ENTER("trie_free");
+ DBUG_ASSERT(trie);
+ memcpy(&mem_root, &trie->mem_root, sizeof(MEM_ROOT));
+ free_root(&mem_root, MYF(0));
+ DBUG_VOID_RETURN;
+}
+
+
+/*
+ SYNOPSIS
+ my_bool trie_insert (TRIE *trie, const byte *key, uint keylen);
+ trie - valid pointer to `TRIE'
+ key - valid pointer to key to insert
+ keylen - non-0 key length
+
+ DESCRIPTION
+ Inserts new key into trie.
+
+ RETURN VALUE
+ Upon successful completion, `trie_insert' returns `FALSE'. Otherwise
+ `TRUE' is returned.
+
+ NOTES
+ If this function fails you must assume `trie' is broken.
+ However it can be freed with trie_free().
+*/
+
+my_bool trie_insert (TRIE *trie, const byte *key, uint keylen)
+{
+ TRIE_NODE *node;
+ TRIE_NODE *next;
+ byte p;
+ uint k;
+ DBUG_ENTER("trie_insert");
+ DBUG_ASSERT(trie && key && keylen);
+ node= &trie->root;
+ trie->root.fail= NULL;
+ for (k= 0; k < keylen; k++)
+ {
+ p= key[k];
+ for (next= node->links; next; next= next->next)
+ if (next->c == p)
+ break;
+
+ if (! next)
+ {
+ TRIE_NODE *tmp= (TRIE_NODE *)alloc_root(&trie->mem_root,
+ sizeof(TRIE_NODE));
+ if (! tmp)
+ DBUG_RETURN(TRUE);
+ tmp->leaf= 0;
+ tmp->c= p;
+ tmp->links= tmp->fail= tmp->next= NULL;
+ trie->nnodes++;
+ if (! node->links)
+ {
+ node->links= tmp;
+ }
+ else
+ {
+ for (next= node->links; next->next; next= next->next) /* no-op */;
+ next->next= tmp;
+ }
+ node= tmp;
+ }
+ else
+ {
+ node= next;
+ }
+ }
+ node->leaf= keylen;
+ trie->nwords++;
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ SYNOPSIS
+ my_bool trie_prepare (TRIE *trie);
+ trie - valid pointer to `TRIE'
+
+ DESCRIPTION
+ Constructs Aho-Corasick automaton.
+
+ RETURN VALUE
+ Upon successful completion, `trie_prepare' returns `FALSE'. Otherwise
+ `TRUE' is returned.
+*/
+
+my_bool ac_trie_prepare (TRIE *trie)
+{
+ TRIE_NODE **tmp_nodes;
+ TRIE_NODE *node;
+ uint32 fnode= 0;
+ uint32 lnode= 0;
+ DBUG_ENTER("trie_prepare");
+ DBUG_ASSERT(trie);
+
+ tmp_nodes= (TRIE_NODE **)my_malloc(trie->nnodes * sizeof(TRIE_NODE *), MYF(0));
+ if (! tmp_nodes)
+ DBUG_RETURN(TRUE);
+
+ trie->root.fail= &trie->root;
+ for (node= trie->root.links; node; node= node->next)
+ {
+ node->fail= &trie->root;
+ tmp_nodes[lnode++]= node;
+ }
+
+ while (fnode < lnode)
+ {
+ TRIE_NODE *current= (TRIE_NODE *)tmp_nodes[fnode++];
+ for (node= current->links; node; node= node->next)
+ {
+ TRIE_NODE *fail= current->fail;
+ tmp_nodes[lnode++]= node;
+ while (! (node->fail= trie_goto(&trie->root, fail, node->c)))
+ fail= fail->fail;
+ }
+ }
+ my_free((gptr)tmp_nodes, MYF(0));
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ SYNOPSIS
+ void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state);
+ trie - valid pointer to `TRIE'
+ state - value pointer to `AC_TRIE_STATE'
+
+ DESCRIPTION
+ Initializes `AC_TRIE_STATE' object.
+*/
+
+void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state)
+{
+ DBUG_ENTER("ac_trie_init");
+ DBUG_ASSERT(trie && state);
+ state->trie= trie;
+ state->node= &trie->root;
+ DBUG_VOID_RETURN;
+}
View Lorry Controller Status