diff options
Diffstat (limited to 'mysys')
| -rw-r--r-- | mysys/mf_cache.c | 3 | ||||
| -rw-r--r-- | mysys/mf_format.c | 29 | ||||
| -rw-r--r-- | mysys/mf_qsort.c | 359 | ||||
| -rw-r--r-- | mysys/my_alloc.c | 40 | ||||
| -rw-r--r-- | mysys/ptr_cmp.c | 3 | ||||
| -rw-r--r-- | mysys/tree.c | 32 |
6 files changed, 231 insertions, 235 deletions
diff --git a/mysys/mf_cache.c b/mysys/mf_cache.c index ff29926ac50..4b8fc6fed17 100644 --- a/mysys/mf_cache.c +++ b/mysys/mf_cache.c @@ -28,7 +28,8 @@ this, just remember the file name for later removal */ -static my_bool cache_remove_open_tmp(IO_CACHE *cache, const char *name) +static my_bool cache_remove_open_tmp(IO_CACHE *cache __attribute__((unused)), + const char *name) { #if O_TEMPORARY == 0 #if !defined(CANT_DELETE_OPEN_FILES) diff --git a/mysys/mf_format.c b/mysys/mf_format.c index c4425806e01..216608fdee5 100644 --- a/mysys/mf_format.c +++ b/mysys/mf_format.c @@ -17,10 +17,6 @@ #include "mysys_priv.h" #include <m_string.h> -#ifdef HAVE_REALPATH -#include <sys/param.h> -#include <sys/stat.h> -#endif /* format a filename with replace of library and extension */ /* params to and name may be identicall */ @@ -33,21 +29,12 @@ /* 32 Resolve filename to full path */ /* 64 Return NULL if too long path */ -#ifdef SCO -#define BUFF_LEN 4097 -#else -#ifdef MAXPATHLEN -#define BUFF_LEN MAXPATHLEN -#else -#define BUFF_LEN FN_LEN -#endif -#endif my_string fn_format(my_string to, const char *name, const char *dsk, const char *form, int flag) { reg1 uint length; - char dev[FN_REFLEN], buff[BUFF_LEN], *pos, *startpos; + char dev[FN_REFLEN], buff[FN_REFLEN], *pos, *startpos; const char *ext; DBUG_ENTER("fn_format"); DBUG_PRINT("enter",("name: %s dsk: %s form: %s flag: %d", @@ -109,18 +96,14 @@ my_string fn_format(my_string to, const char *name, const char *dsk, #endif (void) strmov(pos,ext); /* Don't convert extension */ } - /* Purify gives a lot of UMR errors when using realpath */ -#if defined(HAVE_REALPATH) && !defined(HAVE_purify) && !defined(HAVE_BROKEN_REALPATH) if (flag & 16) { - struct stat stat_buff; - if (flag & 32 || (!lstat(to,&stat_buff) && S_ISLNK(stat_buff.st_mode))) - { - if (realpath(to,buff)) - strmake(to,buff,FN_REFLEN-1); - } + strmov(buff,to); + my_symlink(to, buff, MYF(flag & 32 ? 0 : MY_RESOLVE_LINK)); } -#endif + else if (flag & 32) + my_realpath(to, to, MYF(flag & 32 ? 0 : MY_RESOLVE_LINK)); + DBUG_RETURN (to); } /* fn_format */ diff --git a/mysys/mf_qsort.c b/mysys/mf_qsort.c index 7074abac96e..7ba32ea4fbd 100644 --- a/mysys/mf_qsort.c +++ b/mysys/mf_qsort.c @@ -1,248 +1,215 @@ -/* Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc. - This file is part of the GNU C Library. - Written by Douglas C. Schmidt (schmidt@ics.uci.edu). - - The GNU C 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. - - The GNU C Library is distributed in the hope that it will be useful, +/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult 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 the GNU C Library; see the file COPYING.LIB. If not, - write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ + License along with this library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + MA 02111-1307, USA */ /* - Modifications by monty: - - Uses mysys include files - - Small fixes to make the it a bit faster - - Can be compiled with a cmp function that takes one extra argument. + qsort implementation optimized for comparison of pointers + Inspired by the qsort implementations by Douglas C. Schmidt, + and Bentley & McIlroy's "Engineering a Sort Function". */ + #include "mysys_priv.h" -/* Envoke the comparison function, returns either 0, < 0, or > 0. */ +/* We need to use qsort with 2 different compare functions */ #ifdef QSORT_EXTRA_CMP_ARGUMENT #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B))) #else #define CMP(A,B) ((*cmp)((A),(B))) #endif -/* Byte-wise swap two items of size SIZE. */ -#define SWAP(a, b, size) \ - do \ - { \ - register size_t __size = (size); \ - register char *__a = (a), *__b = (b); \ - do \ - { \ - char __tmp = *__a; \ - *__a++ = *__b; \ - *__b++ = __tmp; \ - } while (--__size > 0); \ - } while (0) - -/* Discontinue quicksort algorithm when partition gets below this size. - This particular magic number was chosen to work best on a Sun 4/260. */ -#define MAX_THRESH 8 - -/* Stack node declarations used to store unfulfilled partition obligations. */ -typedef struct - { - char *lo; - char *hi; - } stack_node; - -/* The next 4 #defines implement a very fast in-line stack abstraction. */ -#define STACK_SIZE (8 * sizeof(unsigned long int)) -#define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0) -#define POP(LOW,HIGH) do {LOW = (--top)->lo;HIGH = top->hi;} while (0) -#define STACK_NOT_EMPTY (stack < top) - -/* Order size using quicksort. This implementation incorporates - four optimizations discussed in Sedgewick: - - 1. Non-recursive, using an explicit stack of pointer that store the - next array partition to sort. To save time, this maximum amount - of space required to store an array of MAX_INT is allocated on the - stack. Assuming a 32-bit integer, this needs only 32 * - sizeof (stack_node) == 136 bits. Pretty cheap, actually. +#define SWAP(A, B, size,swap_ptrs) \ +do { \ + if (swap_ptrs) \ + { \ + reg1 char **a = (char**) (A), **b = (char**) (B); \ + char *tmp = *a; *a++ = *b; *b++ = tmp; \ + } \ + else \ + { \ + reg1 char *a = (A), *b = (B); \ + reg3 char *end= a+size; \ + do \ + { \ + char tmp = *a; *a++ = *b; *b++ = tmp; \ + } while (a < end); \ + } \ +} while (0) + +/* Put the median in the middle argument */ +#define MEDIAN(low, mid, high) \ +{ \ + if (CMP(high,low) < 0) \ + SWAP(high, low, size, ptr_cmp); \ + if (CMP(mid, low) < 0) \ + SWAP(mid, low, size, ptr_cmp); \ + else if (CMP(high, mid) < 0) \ + SWAP(mid, high, size, ptr_cmp); \ +} - 2. Chose the pivot element using a median-of-three decision tree. - This reduces the probability of selecting a bad pivot value and - eliminates certain extraneous comparisons. +/* The following node is used to store ranges to avoid recursive calls */ - 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving - insertion sort to order the MAX_THRESH items within each partition. - This is a big win, since insertion sort is faster for small, mostly - sorted array segments. +typedef struct st_stack +{ + char *low,*high; +} STACK; - 4. The larger of the two sub-partitions is always pushed onto the - stack first, with the algorithm then concentrating on the - smaller partition. This *guarantees* no more than log (n) - stack size is needed (actually O(1) in this case)! */ +#define PUSH(LOW,HIGH) {stack_ptr->low = LOW; stack_ptr++->high = HIGH;} +#define POP(LOW,HIGH) {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;} +/* The following stack size is enough for ulong ~0 elements */ +#define STACK_SIZE (8 * sizeof(unsigned long int)) +#define THRESHOLD_FOR_INSERT_SORT 10 #if defined(QSORT_TYPE_IS_VOID) #define SORT_RETURN return #else #define SORT_RETURN return 0 #endif +/**************************************************************************** +** 'standard' quicksort with the following extensions: +** +** Can be compiled with the qsort2_cmp compare function +** Store ranges on stack to avoid recursion +** Use insert sort on small ranges +** Optimize for sorting of pointers (used often by MySQL) +** Use median comparison to find partition element +*****************************************************************************/ + #ifdef QSORT_EXTRA_CMP_ARGUMENT -qsort_t qsort2(void *base_ptr, size_t total_elems, size_t size, qsort2_cmp cmp, +qsort_t qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp, void *cmp_argument) #else -qsort_t qsort(void *base_ptr, size_t total_elems, size_t size, qsort_cmp cmp) +qsort_t qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp) #endif { - /* Allocating SIZE bytes for a pivot buffer facilitates a better - algorithm below since we can do comparisons directly on the pivot. - */ - size_t max_thresh = (size_t) (MAX_THRESH * size); - if (total_elems <= 1) - SORT_RETURN; /* Crashes on MSDOS if continues */ - - if (total_elems > MAX_THRESH) - { - char *lo = base_ptr; - char *hi = &lo[size * (total_elems - 1)]; - stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */ - stack_node *top = stack + 1; - char *pivot = (char *) my_alloca ((int) size); + char *low, *high, *pivot; + STACK stack[STACK_SIZE], *stack_ptr; + my_bool ptr_cmp; + /* Handle the simple case first */ + /* This will also make the rest of the code simpler */ + if (count <= 1) + SORT_RETURN; + + low = (char*) base_ptr; + high = low+ size * (count - 1); + stack_ptr = stack + 1; #ifdef HAVE_purify - stack[0].lo=stack[0].hi=0; + /* The first element in the stack will be accessed for the last POP */ + stack[0].lo=stack[0].hi=0; #endif + pivot = (char *) my_alloca((int) size); + ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1)); - do + /* The following loop sorts elements between high and low */ + do + { + char *low_ptr, *high_ptr, *mid; + + count=((size_t) (high - low) / size)+1; + /* If count is small, then an insert sort is faster than qsort */ + if (count < THRESHOLD_FOR_INSERT_SORT) { - char *left_ptr,*right_ptr; - - /* Select median value from among LO, MID, and HI. Rearrange - LO and HI so the three values are sorted. This lowers the - probability of picking a pathological pivot value and - skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ - - char *mid = lo + size * (((ulong) (hi - lo) / (ulong) size) >> 1); - - if (CMP(hi,lo) < 0) - SWAP (hi, lo, size); - if (CMP (mid, lo) < 0) - SWAP (mid, lo, size); - else if (CMP (hi, mid) < 0) - SWAP (mid, hi, size); - memcpy (pivot, mid, size); - - left_ptr = lo + size; - right_ptr = hi - size; - - /* Here's the famous ``collapse the walls'' section of quicksort. - Gotta like those tight inner loops! They are the main reason - that this algorithm runs much faster than others. */ - do + for (low_ptr = low + size; low_ptr <= high; low_ptr += size) { - while (CMP (left_ptr, pivot) < 0) - left_ptr += size; - - while (CMP (pivot, right_ptr) < 0) - right_ptr -= size; - - if (left_ptr < right_ptr) - { - SWAP (left_ptr, right_ptr, size); - left_ptr += size; - right_ptr -= size; - } - else if (left_ptr == right_ptr) - { - left_ptr += size; - right_ptr -= size; - break; - } - else - break; /* left_ptr > right_ptr */ + char *ptr; + for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0; + ptr -= size) + SWAP(ptr, ptr - size, size, ptr_cmp); } - while (left_ptr <= right_ptr); + POP(low, high); + continue; + } + /* Try to find a good middle element */ + mid= low + size * (count >> 1); + if (count > 40) /* Must be bigger than 24 */ + { + size_t step = size* (count / 8); + MEDIAN(low, low + step, low+step*2); + MEDIAN(mid - step, mid, mid+step); + MEDIAN(high - 2 * step, high-step, high); + /* Put best median in 'mid' */ + MEDIAN(low+step, mid, high-step); + low_ptr = low; + high_ptr = high; + } + else + { + MEDIAN(low, mid, high); + /* The low and high argument are already in sorted against 'pivot' */ + low_ptr = low + size; + high_ptr = high - size; + } + memcpy(pivot, mid, size); - /* Set up pointers for next iteration. First determine whether - left and right partitions are below the threshold size. If so, - ignore one or both. Otherwise, push the larger partition's - bounds on the stack and continue sorting the smaller one. */ + do + { + while (CMP(low_ptr, pivot) < 0) + low_ptr += size; + while (CMP(pivot, high_ptr) < 0) + high_ptr -= size; - if ((size_t) (right_ptr - lo) <= max_thresh) + if (low_ptr < high_ptr) { - if ((size_t) (hi - left_ptr) <= max_thresh) - POP (lo, hi); /* Ignore both small partitions. */ - else - lo = left_ptr; /* Ignore small left part. */ + SWAP(low_ptr, high_ptr, size, ptr_cmp); + low_ptr += size; + high_ptr -= size; } - else if ((size_t) (hi - left_ptr) <= max_thresh) - hi = right_ptr; /* Ignore small right partition. */ - else if ((right_ptr - lo) > (hi - left_ptr)) - { - PUSH (lo, right_ptr); /* Push larger left part */ - lo = left_ptr; - } - else + else { - PUSH (left_ptr, hi); /* Push larger right part */ - hi = right_ptr; + if (low_ptr == high_ptr) + { + low_ptr += size; + high_ptr -= size; + } + break; } - } while (STACK_NOT_EMPTY); - my_afree(pivot); - } - - /* Once the BASE_PTR array is partially sorted by quicksort the rest - is completely sorted using insertion sort, since this is efficient - for partitions below MAX_THRESH size. BASE_PTR points to the beginning - of the array to sort, and END_PTR points at the very last element in - the array (*not* one beyond it!). */ - - { - char *end_ptr = (char*) base_ptr + size * (total_elems - 1); - char *tmp_ptr = (char*) base_ptr; - char *thresh = min (end_ptr, (char*) base_ptr + max_thresh); - register char *run_ptr; - - /* Find smallest element in first threshold and place it at the - array's beginning. This is the smallest array element, - and the operation speeds up insertion sort's inner loop. */ - - for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) - if (CMP (run_ptr, tmp_ptr) < 0) - tmp_ptr = run_ptr; - - if (tmp_ptr != (char*) base_ptr) - SWAP (tmp_ptr, (char*) base_ptr, size); + } + while (low_ptr <= high_ptr); - /* Insertion sort, running from left-hand-side up to right-hand-side. */ + /* + Prepare for next iteration. + Skip partitions of size 1 as these doesn't have to be sorted + Push the larger partition and sort the smaller one first. + This ensures that the stack is keept small. + */ - for (run_ptr = (char*) base_ptr + size; - (run_ptr += size) <= end_ptr; ) + if ((int) (high_ptr - low) <= 0) { - if (CMP (run_ptr, (tmp_ptr = run_ptr-size)) < 0) + if ((int) (high - low_ptr) <= 0) { - char *trav; - while (CMP (run_ptr, tmp_ptr -= size) < 0) ; - tmp_ptr += size; - - /* Shift down all smaller elements, put found element in 'run_ptr' */ - for (trav = run_ptr + size; --trav >= run_ptr;) - { - char c = *trav; - char *hi, *lo; - - for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) - *hi = *lo; - *hi = c; - } + POP(low, high); /* Nothing more to sort */ } + else + low = low_ptr; /* Ignore small left part. */ + } + else if ((int) (high - low_ptr) <= 0) + high = high_ptr; /* Ignore small right part. */ + else if ((high_ptr - low) > (high - low_ptr)) + { + PUSH(low, high_ptr); /* Push larger left part */ + low = low_ptr; + } + else + { + PUSH(low_ptr, high); /* Push larger right part */ + high = high_ptr; } - } + } while (stack_ptr > stack); + my_afree(pivot); SORT_RETURN; } diff --git a/mysys/my_alloc.c b/mysys/my_alloc.c index db482454e69..ffbed381226 100644 --- a/mysys/my_alloc.c +++ b/mysys/my_alloc.c @@ -100,7 +100,34 @@ gptr alloc_root(MEM_ROOT *mem_root,unsigned int Size) #endif } - /* deallocate everything used by alloc_root */ +/* Mark all data in blocks free for reusage */ + +static inline void mark_blocks_free(MEM_ROOT* root) +{ + reg1 USED_MEM *next; + reg2 USED_MEM **last; + + /* iterate through (partially) free blocks, mark them free */ + last= &root->free; + for (next= root->free; next; next= *(last= &next->next)) + next->left= next->size - ALIGN_SIZE(sizeof(USED_MEM)); + + /* Combine the free and the used list */ + *last= next=root->used; + + /* now go through the used blocks and mark them free */ + for (; next; next= next->next) + next->left= next->size - ALIGN_SIZE(sizeof(USED_MEM)); + + /* Now everything is set; Indicate that nothing is used anymore */ + root->used= 0; +} + + +/* + Deallocate everything used by alloc_root or just move + used blocks to free list if called with MY_USED_TO_FREE +*/ void free_root(MEM_ROOT *root, myf MyFlags) { @@ -109,18 +136,23 @@ void free_root(MEM_ROOT *root, myf MyFlags) if (!root) DBUG_VOID_RETURN; /* purecov: inspected */ + if (MyFlags & MY_MARK_BLOCKS_FREE) + { + mark_blocks_free(root); + DBUG_VOID_RETURN; + } if (!(MyFlags & MY_KEEP_PREALLOC)) root->pre_alloc=0; - for ( next=root->used; next ;) + for (next=root->used; next ;) { old=next; next= next->next ; if (old != root->pre_alloc) my_free((gptr) old,MYF(0)); } - for (next= root->free ; next ; ) + for (next=root->free ; next ;) { - old=next; next= next->next ; + old=next; next= next->next; if (old != root->pre_alloc) my_free((gptr) old,MYF(0)); } diff --git a/mysys/ptr_cmp.c b/mysys/ptr_cmp.c index 65b2c51aafd..f9b3e34d702 100644 --- a/mysys/ptr_cmp.c +++ b/mysys/ptr_cmp.c @@ -19,9 +19,6 @@ get_ptr_compare(len) returns a pointer to a optimal byte-compare function for a array of stringpointer where all strings have size len. The bytes are compare as unsigned chars. - Because the size is saved in a static variable. - When using threads the program must have called my_init and the thread - my_init_thread() */ #include "mysys_priv.h" diff --git a/mysys/tree.c b/mysys/tree.c index a36fd06f3f1..af64be55d2f 100644 --- a/mysys/tree.c +++ b/mysys/tree.c @@ -63,7 +63,7 @@ static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent); /* The actuall code for handling binary trees */ void init_tree(TREE *tree, uint default_alloc_size, int size, - qsort_cmp compare, my_bool with_delete, + qsort_cmp2 compare, my_bool with_delete, void (*free_element) (void *)) { DBUG_ENTER("init_tree"); @@ -77,13 +77,14 @@ void init_tree(TREE *tree, uint default_alloc_size, int size, tree->size_of_element=size > 0 ? (uint) size : 0; tree->free=free_element; tree->elements_in_tree=0; + tree->cmp_arg = 0; tree->null_element.colour=BLACK; tree->null_element.left=tree->null_element.right=0; if (!free_element && size >= 0 && ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1)))) { tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */ - /* Fix allocation size so that we don't loose any memory */ + /* Fix allocation size so that we don't lose any memory */ default_alloc_size/=(sizeof(TREE_ELEMENT)+size); if (!default_alloc_size) default_alloc_size=1; @@ -102,9 +103,9 @@ void init_tree(TREE *tree, uint default_alloc_size, int size, DBUG_VOID_RETURN; } -void delete_tree(TREE *tree) +static void free_tree(TREE *tree, myf free_flags) { - DBUG_ENTER("delete_tree"); + DBUG_ENTER("free_tree"); DBUG_PRINT("enter",("tree: %lx",tree)); if (tree->root) /* If initialized */ @@ -115,7 +116,7 @@ void delete_tree(TREE *tree) { if (tree->free) delete_tree_element(tree,tree->root); - free_root(&tree->mem_root,MYF(0)); + free_root(&tree->mem_root, free_flags); } } tree->root= &tree->null_element; @@ -124,6 +125,18 @@ void delete_tree(TREE *tree) DBUG_VOID_RETURN; } +void delete_tree(TREE* tree) +{ + free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */ +} + +void reset_tree(TREE* tree) +{ + free_tree(tree, MYF(MY_MARK_BLOCKS_FREE)); + /* do not my_free() mem_root if applicable, just mark blocks as free */ +} + + static void delete_tree_element(TREE *tree, TREE_ELEMENT *element) { if (element != &tree->null_element) @@ -152,7 +165,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size) for (;;) { if (element == &tree->null_element || - (cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0) + (cmp=(*tree->compare)(tree->cmp_arg, + ELEMENT_KEY(tree,element),key)) == 0) break; if (cmp < 0) { @@ -212,7 +226,8 @@ int tree_delete(TREE *tree, void *key) { if (element == &tree->null_element) return 1; /* Was not in tree */ - if ((cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0) + if ((cmp=(*tree->compare)(tree->cmp_arg, + ELEMENT_KEY(tree,element),key)) == 0) break; if (cmp < 0) { @@ -266,7 +281,8 @@ void *tree_search(TREE *tree, void *key) { if (element == &tree->null_element) return (void*) 0; - if ((cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0) + if ((cmp=(*tree->compare)(tree->cmp_arg, + ELEMENT_KEY(tree,element),key)) == 0) return ELEMENT_KEY(tree,element); if (cmp < 0) element=element->right; |