diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/Makefile.am | 2 | ||||
| -rw-r--r-- | include/my_base.h | 1 | ||||
| -rw-r--r-- | include/my_bitmap.h | 94 | ||||
| -rw-r--r-- | include/my_global.h | 88 | ||||
| -rw-r--r-- | include/my_trie.h | 142 | ||||
| -rw-r--r-- | include/mysql_com.h | 2 | ||||
| -rw-r--r-- | include/queues.h | 3 |
7 files changed, 318 insertions, 14 deletions
diff --git a/include/Makefile.am b/include/Makefile.am index b8e420bff0e..9f5570f8af4 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -28,7 +28,7 @@ noinst_HEADERS = config-win.h config-os2.h config-netware.h \ myisam.h myisampack.h myisammrg.h ft_global.h\ mysys_err.h my_base.h help_start.h help_end.h \ my_nosys.h my_alarm.h queues.h rijndael.h sha1.h \ - my_aes.h my_tree.h hash.h thr_alarm.h \ + my_aes.h my_tree.h my_trie.h hash.h thr_alarm.h \ thr_lock.h t_ctype.h violite.h md5.h base64.h \ mysql_version.h.in my_handler.h my_time.h decimal.h diff --git a/include/my_base.h b/include/my_base.h index ba3edfad0c8..4a6a384c438 100644 --- a/include/my_base.h +++ b/include/my_base.h @@ -388,6 +388,7 @@ enum data_file_type { #define EQ_RANGE 32 #define NULL_RANGE 64 #define GEOM_FLAG 128 +#define SKIP_RANGE 256 typedef struct st_key_range { diff --git a/include/my_bitmap.h b/include/my_bitmap.h index f4fe28266e4..98dd49a1228 100644 --- a/include/my_bitmap.h +++ b/include/my_bitmap.h @@ -21,10 +21,13 @@ #define MY_BIT_NONE (~(uint) 0) + typedef struct st_bitmap { - uchar *bitmap; - uint bitmap_size; /* number of bytes occupied by the above */ + uint32 *bitmap; + uint n_bits; /* number of bits occupied by the above */ + uint32 last_word_mask; + uint32 *last_word_ptr; /* mutex will be acquired for the duration of each bitmap operation if thread_safe flag in bitmap_init was set. Otherwise, we optimize by not @@ -38,33 +41,98 @@ typedef struct st_bitmap #ifdef __cplusplus extern "C" { #endif -extern my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2); -extern my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe); +extern my_bool bitmap_init(MY_BITMAP *map, uint32 *buf, uint n_bits, my_bool thread_safe); extern my_bool bitmap_is_clear_all(const MY_BITMAP *map); extern my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size); -extern my_bool bitmap_is_set(const MY_BITMAP *map, uint bitmap_bit); extern my_bool bitmap_is_set_all(const MY_BITMAP *map); extern my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2); extern my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit); extern my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit); extern uint bitmap_set_next(MY_BITMAP *map); extern uint bitmap_get_first(const MY_BITMAP *map); +extern uint bitmap_get_first_set(const MY_BITMAP *map); extern uint bitmap_bits_set(const MY_BITMAP *map); -extern void bitmap_clear_all(MY_BITMAP *map); -extern void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit); extern void bitmap_free(MY_BITMAP *map); -extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit); -extern void bitmap_set_all(MY_BITMAP *map); -extern void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit); extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size); +extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2); +extern uint bitmap_lock_set_next(MY_BITMAP *map); +extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit); +#ifdef NOT_USED +extern uint bitmap_lock_bits_set(const MY_BITMAP *map); +extern my_bool bitmap_lock_is_set_all(const MY_BITMAP *map); +extern uint bitmap_lock_get_first(const MY_BITMAP *map); +extern uint bitmap_lock_get_first_set(const MY_BITMAP *map); +extern my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, + const MY_BITMAP *map2); +extern my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size); +extern my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit); +extern my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map); +extern my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2); +extern void bitmap_lock_set_all(MY_BITMAP *map); +extern void bitmap_lock_clear_all(MY_BITMAP *map); +extern void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit); +extern void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit); +extern void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size); +extern void bitmap_lock_intersect(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_subtract(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_union(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_xor(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_invert(MY_BITMAP *map); +#endif /* Fast, not thread safe, bitmap functions */ -#define bitmap_fast_set_bit(MAP, BIT) (MAP)->bitmap[(BIT) / 8] |= (1 << ((BIT) & 7)) -#define bitmap_fast_clear_bit(MAP, BIT) (MAP)->bitmap[(BIT) / 8] &= ~ (1 << ((BIT) & 7)) -#define bitmap_fast_is_set(MAP, BIT) (MAP)->bitmap[(BIT) / 8] & (1 << ((BIT) & 7)) +#define no_bytes_in_map(map) (((map)->n_bits + 7)/8) +#define no_words_in_map(map) (((map)->n_bits + 31)/32) +#define bytes_word_aligned(bytes) (4*((bytes + 3)/4)) +#define _bitmap_set_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + |= (1 << ((BIT) & 7))) +#define _bitmap_flip_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + ^= (1 << ((BIT) & 7))) +#define _bitmap_clear_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + &= ~ (1 << ((BIT) & 7))) +#define _bitmap_is_set(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + & (1 << ((BIT) & 7))) +#ifndef DBUG_OFF +inline uint32 +bitmap_set_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_set_bit(map,bit); +} +inline uint32 +bitmap_flip_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_flip_bit(map,bit); +} +inline uint32 +bitmap_clear_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_clear_bit(map,bit); +} +inline uint32 +bitmap_is_set(const MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_is_set(map,bit); +} +#else +#define bitmap_set_bit(MAP, BIT) _bitmap_set_bit(MAP, BIT) +#define bitmap_flip_bit(MAP, BIT) _bitmap_flip_bit(MAP, BIT) +#define bitmap_clear_bit(MAP, BIT) _bitmap_clear_bit(MAP, BIT) +#define bitmap_is_set(MAP, BIT) _bitmap_is_set(MAP, BIT) +#endif +#define bitmap_cmp(MAP1, MAP2) \ + (memcmp((MAP1)->bitmap, (MAP2)->bitmap, 4*no_words_in_map((MAP1)))==0) +#define bitmap_clear_all(MAP) \ + { memset((MAP)->bitmap, 0, 4*no_words_in_map((MAP))); \ + *(MAP)->last_word_ptr|= (MAP)->last_word_mask; } +#define bitmap_set_all(MAP) \ + (memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP)))) #ifdef __cplusplus } diff --git a/include/my_global.h b/include/my_global.h index b32a8fe6baa..a26c02a687e 100644 --- a/include/my_global.h +++ b/include/my_global.h @@ -101,6 +101,94 @@ #define unlikely(x) __builtin_expect((x),0) +/* + The macros below are useful in optimising places where it has been + discovered that cache misses stall the process and where a prefetch + of the cache line can improve matters. This is available in GCC 3.1.1 + and later versions. + PREFETCH_READ says that addr is going to be used for reading and that + it is to be kept in caches if possible for a while + PREFETCH_WRITE also says that the item to be cached is likely to be + updated. + The *LOCALITY scripts are also available for experimentation purposes + mostly and should only be used if they are verified to improve matters. + For more input see GCC manual (available in GCC 3.1.1 and later) +*/ + +#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR > 10) +#define PREFETCH_READ(addr) __builtin_prefetch(addr, 0, 3) +#define PREFETCH_WRITE(addr) \ + __builtin_prefetch(addr, 1, 3) +#define PREFETCH_READ_LOCALITY(addr, locality) \ + __builtin_prefetch(addr, 0, locality) +#define PREFETCH_WRITE_LOCALITY(addr, locality) \ + __builtin_prefetch(addr, 1, locality) +#else +#define PREFETCH_READ(addr) +#define PREFETCH_READ_LOCALITY(addr, locality) +#define PREFETCH_WRITE(addr) +#define PREFETCH_WRITE_LOCALITY(addr, locality) +#endif + +/* + The following macro is used to ensure that code often used in most + SQL statements and definitely for parts of the SQL processing are + kept in a code segment by itself. This has the advantage that the + risk of common code being overlapping in caches of the CPU is less. + This can be a cause of big performance problems. + Routines should be put in this category with care and when they are + put there one should also strive to make as much of the error handling + as possible (or uncommon code of the routine) to execute in a + separate method to avoid moving to much code to this code segment. + + It is very easy to use, simply add HOT_METHOD at the end of the + function declaration. + For more input see GCC manual (available in GCC 2.95 and later) +*/ + +#if (__GNUC__ > 2) || (__GNUC__ == 2 && __GNUC_MINOR > 94) +#define HOT_METHOD \ + __attribute__ ((section ("hot_code_section"))) +#else +#define HOT_METHOD +#endif + +/* + The following macro is used to ensure that popular global variables + are located next to each other to avoid that they contend for the + same cache lines. + + It is very easy to use, simply add HOT_DATA at the end of the declaration + of the variable, the variable must be initialised because of the way + that linker works so a declaration using HOT_DATA should look like: + uint global_hot_data HOT_DATA = 0; + For more input see GCC manual (available in GCC 2.95 and later) +*/ + +#if (__GNUC__ > 2) || (__GNUC__ == 2 && __GNUC_MINOR > 94) +#define HOT_DATA \ + __attribute__ ((section ("hot_data_section"))) +#else +#define HOT_DATA +#endif + + +/* + The following macros are used to control inlining a bit more than + usual. These macros are used to ensure that inlining always or + never occurs (independent of compilation mode). + For more input see GCC manual (available in GCC 3.1.1 and later) +*/ + +#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR > 10) +#define ALWAYS_INLINE __attribute__ ((always_inline)) +#define NEVER_INLINE __attribute__ ((noinline)) +#else +#define ALWAYS_INLINE +#define NEVER_INLINE +#endif + + /* Fix problem with S_ISLNK() on Linux */ #if defined(TARGET_OS_LINUX) #undef _GNU_SOURCE diff --git a/include/my_trie.h b/include/my_trie.h new file mode 100644 index 00000000000..a8534cb11c1 --- /dev/null +++ b/include/my_trie.h @@ -0,0 +1,142 @@ +/* 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 */ + +#ifndef _trie_h +#define _trie_h +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct st_trie_node +{ + uint16 leaf; /* Depth from root node if match, 0 else */ + byte c; /* Label on this edge */ + struct st_trie_node *next; /* Next label */ + struct st_trie_node *links; /* Array of edges leaving this node */ + struct st_trie_node *fail; /* AC failure function */ +} TRIE_NODE; + +typedef struct st_trie +{ + TRIE_NODE root; + MEM_ROOT mem_root; + CHARSET_INFO *charset; + uint32 nnodes; + uint32 nwords; +} TRIE; + +typedef struct st_ac_trie_state +{ + TRIE *trie; + TRIE_NODE *node; +} AC_TRIE_STATE; + +extern TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset); +extern void trie_free (TRIE *trie); +extern my_bool trie_insert (TRIE *trie, const byte *key, uint keylen); +extern my_bool ac_trie_prepare (TRIE *trie); +extern void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state); + + +/* `trie_goto' is internal function and shouldn't be used. */ + +static inline TRIE_NODE *trie_goto (TRIE_NODE *root, TRIE_NODE *node, byte c) +{ + TRIE_NODE *next; + DBUG_ENTER("trie_goto"); + for (next= node->links; next; next= next->next) + if (next->c == c) + DBUG_RETURN(next); + if (root == node) + DBUG_RETURN(root); + DBUG_RETURN(NULL); +} + + +/* + SYNOPSIS + int ac_trie_next (AC_TRIE_STATE *state, byte *c); + state - valid pointer to `AC_TRIE_STATE' + c - character to lookup + + DESCRIPTION + Implementation of search using Aho-Corasick automaton. + Performs char-by-char search. + + RETURN VALUE + `ac_trie_next' returns length of matched word or 0. +*/ + +static inline int ac_trie_next (AC_TRIE_STATE *state, byte *c) +{ + TRIE_NODE *root, *node; + DBUG_ENTER("ac_trie_next"); + DBUG_ASSERT(state && c); + root= &state->trie->root; + node= state->node; + while (! (state->node= trie_goto(root, node, *c))) + node= node->fail; + DBUG_RETURN(state->node->leaf); +} + + +/* + SYNOPSIS + my_bool trie_search (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 + Performs key lookup in trie. + + RETURN VALUE + `trie_search' returns `true' if key is in `trie'. Otherwise, + `false' is returned. + + NOTES + Consecutive search here is "best by test". arrays are very short, so + binary search or hashing would add too much complexity that would + overweight speed gain. Especially because compiler can optimize simple + consecutive loop better (tested) +*/ + +static inline my_bool trie_search (TRIE *trie, const byte *key, uint keylen) +{ + TRIE_NODE *node; + uint k; + DBUG_ENTER("trie_search"); + DBUG_ASSERT(trie && key && keylen); + node= &trie->root; + + for (k= 0; k < keylen; k++) + { + byte p; + if (! (node= node->links)) + DBUG_RETURN(FALSE); + p= key[k]; + while (p != node->c) + if (! (node= node->next)) + DBUG_RETURN(FALSE); + } + + DBUG_RETURN(node->leaf > 0); +} + +#ifdef __cplusplus +} +#endif +#endif diff --git a/include/mysql_com.h b/include/mysql_com.h index 1e595cdbba3..cef63115ad3 100644 --- a/include/mysql_com.h +++ b/include/mysql_com.h @@ -88,6 +88,8 @@ enum enum_server_command #define GROUP_FLAG 32768 /* Intern: Group field */ #define UNIQUE_FLAG 65536 /* Intern: Used by sql_yacc */ #define BINCMP_FLAG 131072 /* Intern: Used by sql_yacc */ +#define GET_FIXED_FIELDS_FLAG (1 << 18) /* Used to get fields in item tree */ +#define FIELD_IN_PART_FUNC_FLAG (1 << 19)/* Field part of partition func */ #define REFRESH_GRANT 1 /* Refresh grant tables */ #define REFRESH_LOG 2 /* Start on new log file */ diff --git a/include/queues.h b/include/queues.h index 02ab768198e..a8b676b763c 100644 --- a/include/queues.h +++ b/include/queues.h @@ -41,6 +41,9 @@ typedef struct st_queue { #define queue_element(queue,index) ((queue)->root[index+1]) #define queue_end(queue) ((queue)->root[(queue)->elements]) #define queue_replaced(queue) _downheap(queue,1) +#define queue_set_cmp_arg(queue, set_arg) (queue)->first_cmp_arg= set_arg +#define queue_set_max_at_top(queue, set_arg) \ + (queue)->max_at_top= set_arg ? (-1 ^ 1) : 0 typedef int (*queue_compare)(void *,byte *, byte *); int init_queue(QUEUE *queue,uint max_elements,uint offset_to_key, |