diff options
Diffstat (limited to 'myisam/rt_key.c')
| -rw-r--r-- | myisam/rt_key.c | 154 |
1 files changed, 154 insertions, 0 deletions
diff --git a/myisam/rt_key.c b/myisam/rt_key.c new file mode 100644 index 00000000000..c08e918c6db --- /dev/null +++ b/myisam/rt_key.c @@ -0,0 +1,154 @@ +/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB + & TCX DataKonsult 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 */ + +#include "myisamdef.h" + +#include "rt_index.h" +#include "rt_key.h" +#include "rt_mbr.h" + +/* +Add key to the page +Result values: +-1 - error + 0 - not split + 1 - split +*/ +int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, + uint key_length, uchar *page_buf, my_off_t *new_page) +{ + uint page_size = mi_getint(page_buf); + uint nod_flag = mi_test_if_nod(page_buf); + + if (page_size + key_length + nod_flag <= keyinfo->block_length) + { + /* split won't be necessary */ + if (nod_flag) + { + /* save key */ + memcpy(rt_PAGE_END(page_buf), key - nod_flag, key_length + nod_flag); + page_size += key_length + nod_flag; + } + else + { + /* save key */ + memcpy(rt_PAGE_END(page_buf), key, key_length + + info->s->base.rec_reflength); + page_size += key_length + info->s->base.rec_reflength; + } + mi_putint(page_buf, page_size, nod_flag); + return 0; + } + else + { + if (rtree_split_page(info, keyinfo, page_buf, key, key_length, new_page)) + return -1; + else + return 1; + } +} + +/* +Delete key from the page +*/ +int rtree_delete_key(MI_INFO *info, uchar *page_buf, uchar *key, + uint key_length, uint nod_flag) +{ + uint16 page_size = mi_getint(page_buf); + uchar *key_start; + + if (nod_flag) + { + key_start = key - nod_flag; + } + else + { + key_start = key; + key_length += info->s->base.rec_reflength; + } + memmove(key_start, key + key_length, page_size - key_length - + (key - page_buf)); + page_size -= key_length + nod_flag; + + mi_putint(page_buf, page_size, nod_flag); + + return 0; +} + +/* +Calculate and store key MBR +*/ +int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, + uint key_length, my_off_t child_page) +{ + uchar *k; + uchar *last; + uint nod_flag; + + if (!_mi_fetch_keypage(info, keyinfo, child_page, info->buff, 0)) + goto err1; + nod_flag = mi_test_if_nod(info->buff); + + k = rt_PAGE_FIRST_KEY(info->buff, nod_flag); + last = rt_PAGE_END(info->buff); + + rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length); + + return 0; + +err1: + return -1; +} + +/* +Choose non-leaf better key for insertion +*/ +uchar *rtree_choose_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, + uint key_length, uchar *page_buf, uint nod_flag) +{ + double increase; + double best_incr = DBL_MAX; + double area; + double best_area; + uchar *best_key; + + uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag); + uchar *last = rt_PAGE_END(page_buf); + + for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag)) + { + if ((increase = rtree_area_increase(keyinfo->seg, key, k, key_length, + &area)) == -1) + return NULL; + if (increase < best_incr) + { + best_key = k; + best_area = area; + best_incr = increase; + } + else + { + if ((increase == best_incr) && (area < best_area)) + { + best_key = k; + best_area = area; + best_incr = increase; + } + } + } + return best_key; +} |