~drizzle-trunk/drizzle/development : contents of plugin/myisam/mi

~drizzle-trunk/drizzle/development : (revision 2239.1.1)

1 by brian clean slate	1	/* Copyright (C) 2000-2006 MySQL AB
	2
	3	This program is free software; you can redistribute it and/or modify
	4	it under the terms of the GNU General Public License as published by
	5	the Free Software Foundation; version 2 of the License.
	6
	7	This program is distributed in the hope that it will be useful,
	8	but WITHOUT ANY WARRANTY; without even the implied warranty of
	9	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	10	GNU General Public License for more details.
	11
	12	You should have received a copy of the GNU General Public License
	13	along with this program; if not, write to the Free Software
1802.10.2 by Monty Taylor Update all of the copyright headers to include the correct address.	14	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
1 by brian clean slate	15
	16	/* key handling functions */
	17
1130.3.28 by Monty Taylor Moved heapdef.h and myisamdef.h to *_priv.h for easier filtering for include guard check.	18	#include "myisam_priv.h"
2173.2.1 by Monty Taylor Fixes incorrect usage of include	19	#include <drizzled/charset_info.h>
2173.2.1 by Monty Taylor Fixes incorrect usage of include	20	#include <drizzled/internal/m_string.h>
492.1.7 by Monty Taylor Moved test() to its own file.	21	#include <drizzled/util/test.h>
1 by brian clean slate	22
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	23	using namespace drizzled;
	24
481 by Brian Aker Remove all of uchar.	25	static bool _mi_get_prev_key(MI_INFO info, MI_KEYDEF keyinfo, unsigned char *page,
481 by Brian Aker Remove all of uchar.	26	unsigned char key, unsigned char keypos,
482 by Brian Aker Remove uint.	27	uint32_t *return_key_length);
1 by brian clean slate	28
	29	/* Check index */
	30
	31	int _mi_check_index(MI_INFO *info, int inx)
	32	{
	33	if (inx == -1) /* Use last index */
	34	inx=info->lastinx;
	35	if (inx < 0 \|\| ! mi_is_key_active(info->s->state.key_map, inx))
	36	{
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	37	errno=HA_ERR_WRONG_INDEX;
1 by brian clean slate	38	return -1;
	39	}
	40	if (info->lastinx != inx) /* Index changed */
	41	{
	42	info->lastinx = inx;
	43	info->page_changed=1;
	44	info->update= ((info->update & (HA_STATE_CHANGED \| HA_STATE_ROW_CHANGED)) \|
	45	HA_STATE_NEXT_FOUND \| HA_STATE_PREV_FOUND);
	46	}
	47	if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
	48	return(-1);
	49	return(inx);
	50	} /* mi_check_index */
	51
	52
	53	/*
	54	** Search after row by a key
	55	** Position to row is stored in info->lastpos
	56	** Return: -1 if not found
	57	** 1 if one should continue search on higher level
	58	*/
	59
	60	int _mi_search(register MI_INFO info, register MI_KEYDEF keyinfo,
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	61	unsigned char *key, uint32_t key_len, uint32_t nextflag, register internal::my_off_t pos)
1 by brian clean slate	62	{
281 by Brian Aker Converted myisam away from my_bool	63	bool last_key;
1 by brian clean slate	64	int error,flag;
482 by Brian Aker Remove uint.	65	uint32_t nod_flag;
481 by Brian Aker Remove all of uchar.	66	unsigned char keypos,maxpos;
481 by Brian Aker Remove all of uchar.	67	unsigned char lastkey[MI_MAX_KEY_BUFF],*buff;
1 by brian clean slate	68
	69	if (pos == HA_OFFSET_ERROR)
	70	{
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	71	errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1 by brian clean slate	72	info->lastpos= HA_OFFSET_ERROR;
1 by brian clean slate	73	if (!(nextflag & (SEARCH_SMALLER \| SEARCH_BIGGER \| SEARCH_LAST)))
51.1.111 by Jay Pipes Removed DBUG symbols	74	return(-1); /* Not found ; return error */
51.1.111 by Jay Pipes Removed DBUG symbols	75	return(1); /* Search at upper levels */
1 by brian clean slate	76	}
	77
	78	if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
	79	test(!(nextflag & SEARCH_SAVE_BUFF)))))
	80	goto err;
	81
	82	flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
	83	&keypos,lastkey, &last_key);
	84	if (flag == MI_FOUND_WRONG_KEY)
51.1.111 by Jay Pipes Removed DBUG symbols	85	return(-1);
1 by brian clean slate	86	nod_flag=mi_test_if_nod(buff);
	87	maxpos=buff+mi_getint(buff)-1;
	88
	89	if (flag)
	90	{
	91	if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
	92	_mi_kpos(nod_flag,keypos))) <= 0)
51.1.111 by Jay Pipes Removed DBUG symbols	93	return(error);
1 by brian clean slate	94
	95	if (flag >0)
	96	{
	97	if (nextflag & (SEARCH_SMALLER \| SEARCH_LAST) &&
	98	keypos == buff+2+nod_flag)
51.1.111 by Jay Pipes Removed DBUG symbols	99	return(1); /* Bigger than key */
1 by brian clean slate	100	}
1 by brian clean slate	101	else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
51.1.111 by Jay Pipes Removed DBUG symbols	102	return(1); /* Smaller than key */
1 by brian clean slate	103	}
	104	else
	105	{
	106	if ((nextflag & SEARCH_FIND) && nod_flag &&
	107	((keyinfo->flag & (HA_NOSAME \| HA_NULL_PART)) != HA_NOSAME \|\|
	108	key_len != USE_WHOLE_KEY))
	109	{
	110	if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
	111	_mi_kpos(nod_flag,keypos))) >= 0 \|\|
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	112	errno != HA_ERR_KEY_NOT_FOUND)
51.1.111 by Jay Pipes Removed DBUG symbols	113	return(error);
1 by brian clean slate	114	info->last_keypage= HA_OFFSET_ERROR; /* Buffer not in mem */
	115	}
	116	}
	117	if (pos != info->last_keypage)
	118	{
481 by Brian Aker Remove all of uchar.	119	unsigned char *old_buff=buff;
1 by brian clean slate	120	if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
	121	test(!(nextflag & SEARCH_SAVE_BUFF)))))
	122	goto err;
	123	keypos=buff+(keypos-old_buff);
	124	maxpos=buff+(maxpos-old_buff);
	125	}
	126
	127	if ((nextflag & (SEARCH_SMALLER \| SEARCH_LAST)) && flag != 0)
	128	{
482 by Brian Aker Remove uint.	129	uint32_t not_used[2];
1 by brian clean slate	130	if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
	131	&info->lastkey_length))
	132	goto err;
	133	if (!(nextflag & SEARCH_SMALLER) &&
	134	ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
	135	not_used))
	136	{
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	137	errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1 by brian clean slate	138	goto err;
	139	}
	140	}
	141	else
	142	{
	143	info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
	144	if (!info->lastkey_length)
	145	goto err;
	146	memcpy(info->lastkey,lastkey,info->lastkey_length);
	147	}
	148	info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
	149	/* Save position for a possible read next / previous */
	150	info->int_keypos=info->buff+ (keypos-buff);
	151	info->int_maxpos=info->buff+ (maxpos-buff);
	152	info->int_nod_flag=nod_flag;
	153	info->int_keytree_version=keyinfo->version;
	154	info->last_search_keypage=info->last_keypage;
	155	info->page_changed=0;
	156	info->buff_used= (info->buff != buff); /* If we have to reread buff */
	157
51.1.111 by Jay Pipes Removed DBUG symbols	158	return(0);
1 by brian clean slate	159
	160	err:
	161	info->lastpos= HA_OFFSET_ERROR;
	162	info->page_changed=1;
51.1.111 by Jay Pipes Removed DBUG symbols	163	return (-1);
1 by brian clean slate	164	} /* _mi_search */
	165
	166
	167	/* Search after key in page-block */
	168	/* If packed key puts smaller or identical key in buff */
	169	/* ret_pos point to where find or bigger key starts */
	170	/* ARGSUSED */
	171
481 by Brian Aker Remove all of uchar.	172	int _mi_bin_search(MI_INFO info, register MI_KEYDEF keyinfo, unsigned char *page,
482 by Brian Aker Remove uint.	173	unsigned char key, uint32_t key_len, uint32_t comp_flag, unsigned char *ret_pos,
779.3.1 by Monty Taylor More cleanup.	174	unsigned char buff, bool last_key)
1 by brian clean slate	175	{
779.3.1 by Monty Taylor More cleanup.	176	(void)buff;
1 by brian clean slate	177	register int start,mid,end,save_end;
1405.2.3 by jobin modified for the coding standard	178	int flag= 0;
482 by Brian Aker Remove uint.	179	uint32_t totlength,nod_flag,not_used[2];
1 by brian clean slate	180
	181	totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
	182	start=0; mid=1;
	183	save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
	184	page+=2+nod_flag;
	185
	186	while (start != end)
	187	{
	188	mid= (start+end)/2;
	189	if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
	190	comp_flag, not_used))
	191	>= 0)
	192	end=mid;
	193	else
	194	start=mid+1;
	195	}
	196	if (mid != start)
	197	flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
	198	comp_flag, not_used);
	199	if (flag < 0)
	200	start++; /* point at next, bigger key */
	201	ret_pos=page+(uint) starttotlength;
	202	*last_key= end == save_end;
51.1.111 by Jay Pipes Removed DBUG symbols	203	return(flag);
1 by brian clean slate	204	} /* _mi_bin_search */
	205
	206
	207	/*
	208	Locate a packed key in a key page.
	209
	210	SYNOPSIS
	211	_mi_seq_search()
	212	info Open table information.
	213	keyinfo Key definition information.
	214	page Key page (beginning).
	215	key Search key.
	216	key_len Length to use from search key or USE_WHOLE_KEY
	217	comp_flag Search flags like SEARCH_SAME etc.
	218	ret_pos RETURN Position in key page behind this key.
	219	buff RETURN Copy of previous or identical unpacked key.
	220	last_key RETURN If key is last in page.
	221
	222	DESCRIPTION
	223	Used instead of _mi_bin_search() when key is packed.
	224	Puts smaller or identical key in buff.
	225	Key is searched sequentially.
	226
	227	RETURN
	228	> 0 Key in 'buff' is smaller than search key.
	229	0 Key in 'buff' is identical to search key.
	230	< 0 Not found.
	231	*/
	232
481 by Brian Aker Remove all of uchar.	233	int _mi_seq_search(MI_INFO info, register MI_KEYDEF keyinfo, unsigned char *page,
482 by Brian Aker Remove uint.	234	unsigned char key, uint32_t key_len, uint32_t comp_flag, unsigned char *ret_pos,
481 by Brian Aker Remove all of uchar.	235	unsigned char buff, bool last_key)
1 by brian clean slate	236	{
1405.2.2 by jobin correcting for the coding standard for the ealier fix	237	int flag= 0;
482 by Brian Aker Remove uint.	238	uint32_t nod_flag,length=0,not_used[2];
481 by Brian Aker Remove all of uchar.	239	unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
1 by brian clean slate	240
	241	end= page+mi_getint(page);
	242	nod_flag=mi_test_if_nod(page);
	243	page+=2+nod_flag;
	244	*ret_pos=page;
	245	t_buff[0]=0; /* Avoid bugs */
	246	while (page < end)
	247	{
	248	length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
	249	if (length == 0 \|\| page > end)
	250	{
	251	mi_print_error(info->s, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	252	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	253	return(MI_FOUND_WRONG_KEY);
1 by brian clean slate	254	}
	255	if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
	256	not_used)) >= 0)
	257	break;
	258	memcpy(buff,t_buff,length);
	259	*ret_pos=page;
	260	}
	261	if (flag == 0)
	262	memcpy(buff,t_buff,length); /* Result is first key */
	263	*last_key= page == end;
51.1.111 by Jay Pipes Removed DBUG symbols	264	return(flag);
1 by brian clean slate	265	} /* _mi_seq_search */
	266
	267
481 by Brian Aker Remove all of uchar.	268	int _mi_prefix_search(MI_INFO info, register MI_KEYDEF keyinfo, unsigned char *page,
482 by Brian Aker Remove uint.	269	unsigned char key, uint32_t key_len, uint32_t nextflag, unsigned char *ret_pos,
481 by Brian Aker Remove all of uchar.	270	unsigned char buff, bool last_key)
1 by brian clean slate	271	{
	272	/*
	273	my_flag is raw comparison result to be changed according to
	274	SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
	275	flag is the value returned by ha_key_cmp and as treated as final
	276	*/
	277	int flag=0, my_flag=-1;
482 by Brian Aker Remove uint.	278	uint32_t nod_flag, length=0, len, matched, cmplen, kseg_len;
482 by Brian Aker Remove uint.	279	uint32_t prefix_len=0,suffix_len;
171.1.1 by Patrick Galbraith Dar, I forgot to commit this earlier.	280	int key_len_skip, seg_len_pack=0, key_len_left;
481 by Brian Aker Remove all of uchar.	281	unsigned char end, kseg, *vseg;
	282	unsigned char *sort_order=keyinfo->seg->charset->sort_order;
	283	unsigned char tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
	284	unsigned char saved_from=NULL, saved_to=NULL, *saved_vseg=NULL;
482 by Brian Aker Remove uint.	285	uint32_t saved_length=0, saved_prefix_len=0;
482 by Brian Aker Remove uint.	286	uint32_t length_pack;
1 by brian clean slate	287
171.1.1 by Patrick Galbraith Dar, I forgot to commit this earlier.	288
1 by brian clean slate	289	t_buff[0]=0; /* Avoid bugs */
	290	end= page+mi_getint(page);
	291	nod_flag=mi_test_if_nod(page);
	292	page+=2+nod_flag;
	293	*ret_pos=page;
	294	kseg=key;
	295
	296	get_key_pack_length(kseg_len,length_pack,kseg);
	297	key_len_skip=length_pack+kseg_len;
	298	key_len_left=(int) key_len- (int) key_len_skip;
	299	/* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
	300	cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
	301
	302	/*
	303	Keys are compressed the following way:
	304
	305	If the max length of first key segment <= 127 bytes the prefix is
	306	1 byte else it's 2 byte
	307
	308	(prefix) length The high bit is set if this is a prefix for the prev key.
	309	[suffix length] Packed length of suffix if the previous was a prefix.
	310	(suffix) data Key data bytes (past the common prefix or whole segment).
	311	[next-key-seg] Next key segments (([packed length], data), ...)
	312	pointer Reference to the data file (last_keyseg->length).
	313	*/
	314
	315	matched=0; /* how many char's from prefix were alredy matched */
	316	len=0; /* length of previous key unpacked */
	317
	318	while (page < end)
	319	{
482 by Brian Aker Remove uint.	320	uint32_t packed= *page & 128;
1 by brian clean slate	321
	322	vseg=page;
	323	if (keyinfo->seg->length >= 127)
	324	{
	325	suffix_len=mi_uint2korr(vseg) & 32767;
	326	vseg+=2;
	327	}
	328	else
	329	suffix_len= *vseg++ & 127;
	330
	331	if (packed)
	332	{
	333	if (suffix_len == 0)
	334	{
	335	/* == 0x80 or 0x8000, same key, prefix length == old key length. */
	336	prefix_len=len;
	337	}
	338	else
	339	{
	340	/* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
	341	prefix_len=suffix_len;
	342	get_key_length(suffix_len,vseg);
	343	}
	344	}
	345	else
	346	{
	347	/* Not packed. No prefix used from last key. */
	348	prefix_len=0;
	349	}
	350
	351	len=prefix_len+suffix_len;
	352	seg_len_pack=get_pack_length(len);
	353	t_buff=tt_buff+3-seg_len_pack;
	354	store_key_length(t_buff,len);
	355
	356	if (prefix_len > saved_prefix_len)
	357	memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
	358	prefix_len-saved_prefix_len);
	359	saved_vseg=vseg;
	360	saved_prefix_len=prefix_len;
	361
	362	{
481 by Brian Aker Remove all of uchar.	363	unsigned char *from=vseg+suffix_len;
1 by brian clean slate	364	HA_KEYSEG *keyseg;
482 by Brian Aker Remove uint.	365	uint32_t l;
1 by brian clean slate	366
	367	for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
	368	{
	369
	370	if (keyseg->flag & HA_NULL_PART)
	371	{
	372	if (!(*from++))
	373	continue;
	374	}
	375	if (keyseg->flag & (HA_VAR_LENGTH_PART \| HA_BLOB_PART \| HA_SPACE_PACK))
	376	{
	377	get_key_length(l,from);
	378	}
	379	else
	380	l=keyseg->length;
	381
	382	from+=l;
	383	}
	384	from+=keyseg->length;
	385	page=from+nod_flag;
	386	length=from-vseg;
	387	}
	388
	389	if (page > end)
	390	{
	391	mi_print_error(info->s, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	392	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	393	return(MI_FOUND_WRONG_KEY);
1 by brian clean slate	394	}
	395
	396	if (matched >= prefix_len)
	397	{
	398	/* We have to compare. But we can still skip part of the key */
482 by Brian Aker Remove uint.	399	uint32_t left;
481 by Brian Aker Remove all of uchar.	400	unsigned char *k=kseg+prefix_len;
1 by brian clean slate	401
	402	/*
	403	If prefix_len > cmplen then we are in the end-space comparison
	404	phase. Do not try to acces the key any more ==> left= 0.
	405	*/
	406	left= ((len <= cmplen) ? suffix_len :
	407	((prefix_len < cmplen) ? cmplen - prefix_len : 0));
	408
	409	matched=prefix_len+left;
	410
	411	if (sort_order)
	412	{
	413	for (my_flag=0;left;left--)
	414	if ((my_flag= (int) sort_order[vseg++] - (int) sort_order[k++]))
	415	break;
	416	}
	417	else
	418	{
	419	for (my_flag=0;left;left--)
	420	if ((my_flag= (int) vseg++ - (int) k++))
	421	break;
	422	}
	423
	424	if (my_flag>0) /* mismatch */
	425	break;
	426	if (my_flag==0) /* match */
	427	{
	428	/*
	429	** len cmplen seg_left_len more_segs
	430	** < matched=len; continue search
	431	** > = prefix ? found : (matched=len; continue search)
	432	** > < - ok, found
	433	** = < - ok, found
	434	** = = - ok, found
	435	** = = + next seg
	436	*/
	437	if (len < cmplen)
	438	{
	439	if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
	440	keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
	441	keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
	442	my_flag= -1;
	443	else
	444	{
	445	/* We have to compare k and vseg as if they were space extended */
481 by Brian Aker Remove all of uchar.	446	unsigned char *k_end= k+ (cmplen - len);
1 by brian clean slate	447	for ( ; k < k_end && *k == ' '; k++) ;
	448	if (k == k_end)
	449	goto cmp_rest; /* should never happen */
481 by Brian Aker Remove all of uchar.	450	if (*k < (unsigned char) ' ')
1 by brian clean slate	451	{
	452	my_flag= 1; /* Compared string is smaller */
	453	break;
	454	}
	455	my_flag= -1; /* Continue searching */
	456	}
	457	}
	458	else if (len > cmplen)
	459	{
481 by Brian Aker Remove all of uchar.	460	unsigned char *vseg_end;
1 by brian clean slate	461	if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
	462	goto fix_flag;
	463
	464	/* We have to compare k and vseg as if they were space extended */
	465	for (vseg_end= vseg + (len-cmplen) ;
481 by Brian Aker Remove all of uchar.	466	vseg < vseg_end && *vseg == (unsigned char) ' ';
1 by brian clean slate	467	vseg++, matched++) ;
51.1.111 by Jay Pipes Removed DBUG symbols	468	assert(vseg < vseg_end);
1 by brian clean slate	469
481 by Brian Aker Remove all of uchar.	470	if (*vseg > (unsigned char) ' ')
1 by brian clean slate	471	{
	472	my_flag= 1; /* Compared string is smaller */
	473	break;
	474	}
	475	my_flag= -1; /* Continue searching */
	476	}
	477	else
	478	{
	479	cmp_rest:
	480	if (key_len_left>0)
	481	{
482 by Brian Aker Remove uint.	482	uint32_t not_used[2];
1 by brian clean slate	483	if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
	484	k, key_len_left, nextflag, not_used)) >= 0)
	485	break;
	486	}
	487	else
	488	{
	489	/*
	490	at this line flag==-1 if the following lines were already
	491	visited and 0 otherwise, i.e. flag <=0 here always !!!
	492	*/
	493	fix_flag:
51.1.111 by Jay Pipes Removed DBUG symbols	494	assert(flag <= 0);
1 by brian clean slate	495	if (nextflag & (SEARCH_NO_FIND \| SEARCH_LAST))
	496	flag=(nextflag & (SEARCH_BIGGER \| SEARCH_LAST)) ? -1 : 1;
	497	if (flag>=0)
	498	break;
	499	}
	500	}
	501	}
	502	matched-=left;
	503	}
	504	/* else (matched < prefix_len) ---> do nothing. */
	505
	506	memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
	507	saved_to=buff+saved_length;
	508	saved_from=saved_vseg;
	509	saved_length=length;
	510	*ret_pos=page;
	511	}
	512	if (my_flag)
	513	flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
	514	if (flag == 0)
	515	{
	516	memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
	517	saved_to=buff+saved_length;
	518	saved_from=saved_vseg;
	519	saved_length=length;
	520	}
	521	if (saved_length)
	522	memcpy(saved_to,saved_from,saved_length);
	523
	524	*last_key= page == end;
	525
51.1.111 by Jay Pipes Removed DBUG symbols	526	return(flag);
1 by brian clean slate	527	} /* _mi_prefix_search */
	528
	529
	530	/* Get pos to a key_block */
	531
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	532	internal::my_off_t _mi_kpos(uint32_t nod_flag, unsigned char *after_key)
1 by brian clean slate	533	{
	534	after_key-=nod_flag;
	535	switch (nod_flag) {
	536	#if SIZEOF_OFF_T > 4
	537	case 7:
	538	return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
	539	case 6:
	540	return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
	541	case 5:
	542	return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
	543	#else
	544	case 7:
	545	after_key++;
	546	case 6:
	547	after_key++;
	548	case 5:
	549	after_key++;
	550	#endif
	551	case 4:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	552	return ((internal::my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
1 by brian clean slate	553	case 3:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	554	return ((internal::my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
1 by brian clean slate	555	case 2:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	556	return (internal::my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
1 by brian clean slate	557	case 1:
	558	return (uint) (after_key)MI_MIN_KEY_BLOCK_LENGTH;
	559	case 0: /* At leaf page */
	560	default: /* Impossible */
	561	return(HA_OFFSET_ERROR);
	562	}
	563	} /* _kpos */
	564
	565
	566	/* Save pos to a key_block */
	567
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	568	void _mi_kpointer(register MI_INFO info, register unsigned char buff, internal::my_off_t pos)
1 by brian clean slate	569	{
	570	pos/=MI_MIN_KEY_BLOCK_LENGTH;
	571	switch (info->s->base.key_reflength) {
	572	#if SIZEOF_OFF_T > 4
	573	case 7: mi_int7store(buff,pos); break;
	574	case 6: mi_int6store(buff,pos); break;
	575	case 5: mi_int5store(buff,pos); break;
	576	#else
	577	case 7: *buff++=0;
	578	/* fall trough */
	579	case 6: *buff++=0;
	580	/* fall trough */
	581	case 5: *buff++=0;
	582	/* fall trough */
	583	#endif
	584	case 4: mi_int4store(buff,pos); break;
	585	case 3: mi_int3store(buff,pos); break;
	586	case 2: mi_int2store(buff,(uint) pos); break;
481 by Brian Aker Remove all of uchar.	587	case 1: buff[0]= (unsigned char) pos; break;
1 by brian clean slate	588	default: abort(); /* impossible */
	589	}
	590	} /* _mi_kpointer */
	591
	592
	593	/* Calc pos to a data-record from a key */
	594
	595
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	596	internal::my_off_t _mi_dpos(MI_INFO info, uint32_t nod_flag, unsigned char after_key)
1 by brian clean slate	597	{
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	598	internal::my_off_t pos;
1 by brian clean slate	599	after_key-=(nod_flag + info->s->rec_reflength);
	600	switch (info->s->rec_reflength) {
	601	#if SIZEOF_OFF_T > 4
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	602	case 8: pos= (internal::my_off_t) mi_uint8korr(after_key); break;
	603	case 7: pos= (internal::my_off_t) mi_uint7korr(after_key); break;
	604	case 6: pos= (internal::my_off_t) mi_uint6korr(after_key); break;
	605	case 5: pos= (internal::my_off_t) mi_uint5korr(after_key); break;
1 by brian clean slate	606	#else
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	607	case 8: pos= (internal::my_off_t) mi_uint4korr(after_key+4); break;
	608	case 7: pos= (internal::my_off_t) mi_uint4korr(after_key+3); break;
	609	case 6: pos= (internal::my_off_t) mi_uint4korr(after_key+2); break;
	610	case 5: pos= (internal::my_off_t) mi_uint4korr(after_key+1); break;
1 by brian clean slate	611	#endif
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	612	case 4: pos= (internal::my_off_t) mi_uint4korr(after_key); break;
	613	case 3: pos= (internal::my_off_t) mi_uint3korr(after_key); break;
	614	case 2: pos= (internal::my_off_t) mi_uint2korr(after_key); break;
1 by brian clean slate	615	default:
	616	pos=0L; /* Shut compiler up */
	617	}
	618	return (info->s->options &
	619	(HA_OPTION_PACK_RECORD \| HA_OPTION_COMPRESS_RECORD)) ? pos :
	620	pos*info->s->base.pack_reclength;
	621	}
	622
	623
	624	/* Calc position from a record pointer ( in delete link chain ) */
	625
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	626	internal::my_off_t _mi_rec_pos(MYISAM_SHARE s, unsigned char ptr)
1 by brian clean slate	627	{
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	628	internal::my_off_t pos;
1 by brian clean slate	629	switch (s->rec_reflength) {
	630	#if SIZEOF_OFF_T > 4
	631	case 8:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	632	pos= (internal::my_off_t) mi_uint8korr(ptr);
1 by brian clean slate	633	if (pos == HA_OFFSET_ERROR)
	634	return HA_OFFSET_ERROR; /* end of list */
	635	break;
	636	case 7:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	637	pos= (internal::my_off_t) mi_uint7korr(ptr);
	638	if (pos == (((internal::my_off_t) 1) << 56) -1)
1 by brian clean slate	639	return HA_OFFSET_ERROR; /* end of list */
	640	break;
	641	case 6:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	642	pos= (internal::my_off_t) mi_uint6korr(ptr);
	643	if (pos == (((internal::my_off_t) 1) << 48) -1)
1 by brian clean slate	644	return HA_OFFSET_ERROR; /* end of list */
	645	break;
	646	case 5:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	647	pos= (internal::my_off_t) mi_uint5korr(ptr);
	648	if (pos == (((internal::my_off_t) 1) << 40) -1)
1 by brian clean slate	649	return HA_OFFSET_ERROR; /* end of list */
	650	break;
	651	#else
	652	case 8:
	653	case 7:
	654	case 6:
	655	case 5:
	656	ptr+= (s->rec_reflength-4);
	657	/* fall through */
	658	#endif
	659	case 4:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	660	pos= (internal::my_off_t) mi_uint4korr(ptr);
	661	if (pos == (internal::my_off_t) UINT32_MAX)
1 by brian clean slate	662	return HA_OFFSET_ERROR;
	663	break;
	664	case 3:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	665	pos= (internal::my_off_t) mi_uint3korr(ptr);
	666	if (pos == (internal::my_off_t) (1 << 24) -1)
1 by brian clean slate	667	return HA_OFFSET_ERROR;
	668	break;
	669	case 2:
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	670	pos= (internal::my_off_t) mi_uint2korr(ptr);
	671	if (pos == (internal::my_off_t) (1 << 16) -1)
1 by brian clean slate	672	return HA_OFFSET_ERROR;
	673	break;
	674	default: abort(); /* Impossible */
	675	}
	676	return ((s->options &
	677	(HA_OPTION_PACK_RECORD \| HA_OPTION_COMPRESS_RECORD)) ? pos :
	678	pos*s->base.pack_reclength);
	679	}
	680
	681
	682	/* save position to record */
	683
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	684	void _mi_dpointer(MI_INFO info, unsigned char buff, internal::my_off_t pos)
1 by brian clean slate	685	{
	686	if (!(info->s->options &
	687	(HA_OPTION_PACK_RECORD \| HA_OPTION_COMPRESS_RECORD)) &&
	688	pos != HA_OFFSET_ERROR)
	689	pos/=info->s->base.pack_reclength;
	690
	691	switch (info->s->rec_reflength) {
	692	#if SIZEOF_OFF_T > 4
	693	case 8: mi_int8store(buff,pos); break;
	694	case 7: mi_int7store(buff,pos); break;
	695	case 6: mi_int6store(buff,pos); break;
	696	case 5: mi_int5store(buff,pos); break;
	697	#else
	698	case 8: *buff++=0;
	699	/* fall trough */
	700	case 7: *buff++=0;
	701	/* fall trough */
	702	case 6: *buff++=0;
	703	/* fall trough */
	704	case 5: *buff++=0;
	705	/* fall trough */
	706	#endif
	707	case 4: mi_int4store(buff,pos); break;
	708	case 3: mi_int3store(buff,pos); break;
	709	case 2: mi_int2store(buff,(uint) pos); break;
	710	default: abort(); /* Impossible */
	711	}
	712	} /* _mi_dpointer */
	713
	714
	715	/* Get key from key-block */
	716	/* page points at previous key; its advanced to point at next key */
	717	/* key should contain previous key */
	718	/* Returns length of found key + pointers */
	719	/* nod_flag is a flag if we are on nod */
	720
	721	/* same as _mi_get_key but used with fixed length keys */
	722
482 by Brian Aker Remove uint.	723	uint32_t _mi_get_static_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
481 by Brian Aker Remove all of uchar.	724	register unsigned char *page, register unsigned char key)
1 by brian clean slate	725	{
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	726	memcpy(key, *page, keyinfo->keylength+nod_flag);
1 by brian clean slate	727	*page+=keyinfo->keylength+nod_flag;
	728	return(keyinfo->keylength);
	729	} /* _mi_get_static_key */
	730
	731
	732	/*
	733	get key witch is packed against previous key or key with a NULL column.
	734
	735	SYNOPSIS
	736	_mi_get_pack_key()
	737	keyinfo key definition information.
	738	nod_flag If nod: Length of node pointer, else zero.
	739	page_pos RETURN position in key page behind this key.
	740	key IN/OUT in: prev key, out: unpacked key.
	741
	742	RETURN
	743	key_length + length of data pointer
	744	*/
	745
482 by Brian Aker Remove uint.	746	uint32_t _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
481 by Brian Aker Remove all of uchar.	747	register unsigned char *page_pos, register unsigned char key)
1 by brian clean slate	748	{
1 by brian clean slate	749	register HA_KEYSEG *keyseg;
481 by Brian Aker Remove all of uchar.	750	unsigned char start_key,page=*page_pos;
482 by Brian Aker Remove uint.	751	uint32_t length;
1 by brian clean slate	752
	753	start_key=key;
	754	for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
	755	{
	756	if (keyseg->flag & HA_PACK_KEY)
	757	{
	758	/* key with length, packed to previous key */
481 by Brian Aker Remove all of uchar.	759	unsigned char *start=key;
482 by Brian Aker Remove uint.	760	uint32_t packed= *page & 128,tot_length,rest_length;
1 by brian clean slate	761	if (keyseg->length >= 127)
	762	{
	763	length=mi_uint2korr(page) & 32767;
	764	page+=2;
	765	}
	766	else
	767	length= *page++ & 127;
	768
	769	if (packed)
	770	{
	771	if (length > (uint) keyseg->length)
	772	{
	773	mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	774	errno=HA_ERR_CRASHED;
1 by brian clean slate	775	return 0; /* Error */
	776	}
	777	if (length == 0) /* Same key */
	778	{
	779	if (keyseg->flag & HA_NULL_PART)
	780	key++=1; / Can't be NULL */
	781	get_key_length(length,key);
	782	key+= length; /* Same diff_key as prev */
	783	if (length > keyseg->length)
	784	{
	785	mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	786	errno=HA_ERR_CRASHED;
1 by brian clean slate	787	return 0;
	788	}
	789	continue;
	790	}
	791	if (keyseg->flag & HA_NULL_PART)
	792	{
	793	key++; /* Skip null marker*/
	794	start++;
	795	}
	796
	797	get_key_length(rest_length,page);
	798	tot_length=rest_length+length;
	799
	800	/* If the stored length has changed, we must move the key */
	801	if (tot_length >= 255 && *start != 255)
	802	{
	803	/* length prefix changed from a length of one to a length of 3 */
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	804	internal::bmove_upp(key+length+3, key+length+1, length);
1 by brian clean slate	805	*key=255;
	806	mi_int2store(key+1,tot_length);
	807	key+=3+length;
	808	}
	809	else if (tot_length < 255 && *start == 255)
	810	{
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	811	memmove(key+1,key+3,length);
1 by brian clean slate	812	*key=tot_length;
	813	key+=1+length;
	814	}
	815	else
	816	{
	817	store_key_length_inc(key,tot_length);
	818	key+=length;
	819	}
	820	memcpy(key,page,rest_length);
	821	page+=rest_length;
	822	key+=rest_length;
	823	continue;
	824	}
	825	else
	826	{
	827	if (keyseg->flag & HA_NULL_PART)
	828	{
	829	if (!length--) /* Null part */
	830	{
	831	*key++=0;
	832	continue;
	833	}
	834	key++=1; / Not null */
	835	}
	836	}
	837	if (length > (uint) keyseg->length)
	838	{
	839	mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	840	errno=HA_ERR_CRASHED;
1 by brian clean slate	841	return 0; /* Error */
	842	}
	843	store_key_length_inc(key,length);
	844	}
	845	else
	846	{
	847	if (keyseg->flag & HA_NULL_PART)
	848	{
	849	if (!(key++ = page++))
	850	continue;
	851	}
	852	if (keyseg->flag &
	853	(HA_VAR_LENGTH_PART \| HA_BLOB_PART \| HA_SPACE_PACK))
	854	{
481 by Brian Aker Remove all of uchar.	855	unsigned char *tmp=page;
1 by brian clean slate	856	get_key_length(length,tmp);
	857	length+=(uint) (tmp-page);
	858	}
	859	else
	860	length=keyseg->length;
	861	}
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	862	memcpy(key, page, length);
1 by brian clean slate	863	key+=length;
	864	page+=length;
	865	}
	866	length=keyseg->length+nod_flag;
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	867	memmove(key,page,length);
1 by brian clean slate	868	*page_pos= page+length;
	869	return ((uint) (key-start_key)+keyseg->length);
	870	} /* _mi_get_pack_key */
	871
	872
	873
	874	/* key that is packed relatively to previous */
	875
482 by Brian Aker Remove uint.	876	uint32_t _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
481 by Brian Aker Remove all of uchar.	877	register unsigned char *page_pos, register unsigned char key)
1 by brian clean slate	878	{
1 by brian clean slate	879	register HA_KEYSEG *keyseg;
481 by Brian Aker Remove all of uchar.	880	unsigned char start_key,page,page_end,from,*from_end;
482 by Brian Aker Remove uint.	881	uint32_t length,tmp;
1 by brian clean slate	882
	883	page= *page_pos;
	884	page_end=page+MI_MAX_KEY_BUFF+1;
	885	start_key=key;
	886
	887	/*
	888	Keys are compressed the following way:
	889
	890	prefix length Packed length of prefix common with prev key (1 or 3 bytes)
	891	for each key segment:
	892	[is null] Null indicator if can be null (1 byte, zero means null)
	893	[length] Packed length if varlength (1 or 3 bytes)
	894	key segment 'length' bytes of key segment value
	895	pointer Reference to the data file (last_keyseg->length).
	896
	897	get_key_length() is a macro. It gets the prefix length from 'page'
	898	and puts it into 'length'. It increments 'page' by 1 or 3, depending
	899	on the packed length of the prefix length.
	900	*/
	901	get_key_length(length,page);
	902	if (length)
	903	{
	904	if (length > keyinfo->maxlength)
	905	{
	906	mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	907	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	908	return(0); /* Wrong key */
1 by brian clean slate	909	}
	910	/* Key is packed against prev key, take prefix from prev key. */
	911	from= key;
	912	from_end= key + length;
	913	}
	914	else
	915	{
	916	/* Key is not packed against prev key, take all from page buffer. */
	917	from= page;
	918	from_end= page_end;
	919	}
	920
	921	/*
	922	The trouble is that key can be split in two parts:
	923	The first part (prefix) is in from .. from_end - 1.
	924	The second part starts at page.
	925	The split can be at every byte position. So we need to check for
	926	the end of the first part before using every byte.
	927	*/
	928	for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
	929	{
	930	if (keyseg->flag & HA_NULL_PART)
	931	{
	932	/* If prefix is used up, switch to rest. */
	933	if (from == from_end) { from=page; from_end=page_end; }
	934	if (!(key++ = from++))
	935	continue; /* Null part */
	936	}
	937	if (keyseg->flag & (HA_VAR_LENGTH_PART \| HA_BLOB_PART \| HA_SPACE_PACK))
	938	{
	939	/* If prefix is used up, switch to rest. */
	940	if (from == from_end) { from=page; from_end=page_end; }
	941	/* Get length of dynamic length key part */
	942	if ((length= (key++ = from++)) == 255)
	943	{
	944	/* If prefix is used up, switch to rest. */
	945	if (from == from_end) { from=page; from_end=page_end; }
	946	length= (uint) ((key++ = from++)) << 8;
	947	/* If prefix is used up, switch to rest. */
	948	if (from == from_end) { from=page; from_end=page_end; }
	949	length+= (uint) ((key++ = from++));
	950	}
	951	}
	952	else
	953	length=keyseg->length;
	954
	955	if ((tmp=(uint) (from_end-from)) <= length)
	956	{
	957	key+=tmp; /* Use old key */
	958	length-=tmp;
	959	from=page; from_end=page_end;
	960	}
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	961	memmove(key, from, length);
1 by brian clean slate	962	key+=length;
	963	from+=length;
	964	}
	965	/*
	966	Last segment (type == 0) contains length of data pointer.
	967	If we have mixed key blocks with data pointer and key block pointer,
	968	we have to copy both.
	969	*/
	970	length=keyseg->length+nod_flag;
	971	if ((tmp=(uint) (from_end-from)) <= length)
	972	{
	973	/* Remaining length is less or equal max possible length. */
	974	memcpy(key+tmp,page,length-tmp); /* Get last part of key */
	975	*page_pos= page+length-tmp;
	976	}
	977	else
	978	{
	979	/*
	980	Remaining length is greater than max possible length.
	981	This can happen only if we switched to the new key bytes already.
	982	'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
	983	behind the real end of the key.
	984	*/
	985	if (from_end != page_end)
	986	{
	987	mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	988	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	989	return(0); /* Error */
1 by brian clean slate	990	}
1 by brian clean slate	991	/* Copy data pointer and, if appropriate, key block pointer. */
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	992	memcpy(key, from, length);
1 by brian clean slate	993	*page_pos= from+length;
1 by brian clean slate	994	}
51.1.111 by Jay Pipes Removed DBUG symbols	995	return((uint) (key-start_key)+keyseg->length);
1 by brian clean slate	996	}
	997
	998
	999	/* Get key at position without knowledge of previous key */
	1000	/* Returns pointer to next key */
	1001
481 by Brian Aker Remove all of uchar.	1002	unsigned char _mi_get_key(MI_INFO info, MI_KEYDEF keyinfo, unsigned char page,
482 by Brian Aker Remove uint.	1003	unsigned char key, unsigned char keypos, uint32_t *return_key_length)
1 by brian clean slate	1004	{
482 by Brian Aker Remove uint.	1005	uint32_t nod_flag;
1 by brian clean slate	1006
	1007	nod_flag=mi_test_if_nod(page);
	1008	if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY \| HA_BINARY_PACK_KEY)))
	1009	{
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	1010	memmove(key,keypos,keyinfo->keylength+nod_flag);
51.1.111 by Jay Pipes Removed DBUG symbols	1011	return(keypos+keyinfo->keylength+nod_flag);
1 by brian clean slate	1012	}
	1013	else
	1014	{
	1015	page+=2+nod_flag;
	1016	key[0]=0; /* safety */
	1017	while (page <= keypos)
	1018	{
	1019	return_key_length=(keyinfo->get_key)(keyinfo,nod_flag,&page,key);
	1020	if (*return_key_length == 0)
	1021	{
	1022	mi_print_error(info->s, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	1023	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	1024	return(0);
1 by brian clean slate	1025	}
	1026	}
	1027	}
51.1.111 by Jay Pipes Removed DBUG symbols	1028	return(page);
1 by brian clean slate	1029	} /* _mi_get_key */
	1030
	1031
	1032	/* Get key at position without knowledge of previous key */
	1033	/* Returns 0 if ok */
	1034
481 by Brian Aker Remove all of uchar.	1035	static bool _mi_get_prev_key(MI_INFO info, MI_KEYDEF keyinfo, unsigned char *page,
481 by Brian Aker Remove all of uchar.	1036	unsigned char key, unsigned char keypos,
482 by Brian Aker Remove uint.	1037	uint32_t *return_key_length)
1 by brian clean slate	1038	{
482 by Brian Aker Remove uint.	1039	uint32_t nod_flag;
1 by brian clean slate	1040
	1041	nod_flag=mi_test_if_nod(page);
	1042	if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY \| HA_BINARY_PACK_KEY)))
	1043	{
	1044	*return_key_length=keyinfo->keylength;
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	1045	memmove(key, keypos - return_key_length-nod_flag, return_key_length);
51.1.111 by Jay Pipes Removed DBUG symbols	1046	return(0);
1 by brian clean slate	1047	}
	1048	else
	1049	{
	1050	page+=2+nod_flag;
	1051	key[0]=0; /* safety */
	1052	while (page < keypos)
	1053	{
	1054	return_key_length=(keyinfo->get_key)(keyinfo,nod_flag,&page,key);
	1055	if (*return_key_length == 0)
	1056	{
	1057	mi_print_error(info->s, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	1058	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	1059	return(1);
1 by brian clean slate	1060	}
	1061	}
	1062	}
51.1.111 by Jay Pipes Removed DBUG symbols	1063	return(0);
1 by brian clean slate	1064	} /* _mi_get_key */
	1065
	1066
	1067
	1068	/* Get last key from key-page */
	1069	/* Return pointer to where key starts */
	1070
481 by Brian Aker Remove all of uchar.	1071	unsigned char _mi_get_last_key(MI_INFO info, MI_KEYDEF keyinfo, unsigned char page,
482 by Brian Aker Remove uint.	1072	unsigned char lastkey, unsigned char endpos, uint32_t *return_key_length)
1 by brian clean slate	1073	{
482 by Brian Aker Remove uint.	1074	uint32_t nod_flag;
481 by Brian Aker Remove all of uchar.	1075	unsigned char *lastpos;
1 by brian clean slate	1076
	1077	nod_flag=mi_test_if_nod(page);
	1078	if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY \| HA_BINARY_PACK_KEY)))
	1079	{
	1080	lastpos=endpos-keyinfo->keylength-nod_flag;
	1081	*return_key_length=keyinfo->keylength;
	1082	if (lastpos > page)
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	1083	memmove(lastkey,lastpos,keyinfo->keylength+nod_flag);
1 by brian clean slate	1084	}
	1085	else
	1086	{
	1087	lastpos=(page+=2+nod_flag);
	1088	lastkey[0]=0;
	1089	while (page < endpos)
	1090	{
	1091	lastpos=page;
	1092	return_key_length=(keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
	1093	if (*return_key_length == 0)
	1094	{
	1095	mi_print_error(info->s, HA_ERR_CRASHED);
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	1096	errno=HA_ERR_CRASHED;
51.1.111 by Jay Pipes Removed DBUG symbols	1097	return(0);
1 by brian clean slate	1098	}
	1099	}
	1100	}
51.1.111 by Jay Pipes Removed DBUG symbols	1101	return(lastpos);
1 by brian clean slate	1102	} /* _mi_get_last_key */
	1103
	1104
	1105	/* Calculate length of key */
	1106
482 by Brian Aker Remove uint.	1107	uint32_t _mi_keylength(MI_KEYDEF keyinfo, register unsigned char key)
1 by brian clean slate	1108	{
1 by brian clean slate	1109	register HA_KEYSEG *keyseg;
481 by Brian Aker Remove all of uchar.	1110	unsigned char *start;
1 by brian clean slate	1111
	1112	if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY \| HA_BINARY_PACK_KEY)))
	1113	return (keyinfo->keylength);
	1114
	1115	start=key;
	1116	for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
	1117	{
	1118	if (keyseg->flag & HA_NULL_PART)
	1119	if (!*key++)
	1120	continue;
	1121	if (keyseg->flag & (HA_SPACE_PACK \| HA_BLOB_PART \| HA_VAR_LENGTH_PART))
	1122	{
482 by Brian Aker Remove uint.	1123	uint32_t length;
1 by brian clean slate	1124	get_key_length(length,key);
	1125	key+=length;
	1126	}
	1127	else
	1128	key+= keyseg->length;
	1129	}
	1130	return((uint) (key-start)+keyseg->length);
	1131	} /* _mi_keylength */
	1132
	1133
	1134	/*
	1135	Calculate length of part key.
	1136
	1137	Used in mi_rkey() to find the key found for the key-part that was used.
	1138	This is needed in case of multi-byte character sets where we may search
	1139	after '0xDF' but find 'ss'
	1140	*/
	1141
482 by Brian Aker Remove uint.	1142	uint32_t _mi_keylength_part(MI_KEYDEF keyinfo, register unsigned char key,
1 by brian clean slate	1143	HA_KEYSEG *end)
	1144	{
	1145	register HA_KEYSEG *keyseg;
481 by Brian Aker Remove all of uchar.	1146	unsigned char *start= key;
1 by brian clean slate	1147
	1148	for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
	1149	{
	1150	if (keyseg->flag & HA_NULL_PART)
	1151	if (!*key++)
	1152	continue;
	1153	if (keyseg->flag & (HA_SPACE_PACK \| HA_BLOB_PART \| HA_VAR_LENGTH_PART))
	1154	{
482 by Brian Aker Remove uint.	1155	uint32_t length;
1 by brian clean slate	1156	get_key_length(length,key);
	1157	key+=length;
	1158	}
	1159	else
	1160	key+= keyseg->length;
	1161	}
	1162	return (uint) (key-start);
	1163	}
	1164
	1165	/* Move a key */
	1166
481 by Brian Aker Remove all of uchar.	1167	unsigned char _mi_move_key(MI_KEYDEF keyinfo, unsigned char to, unsigned char from)
1 by brian clean slate	1168	{
482 by Brian Aker Remove uint.	1169	register uint32_t length;
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	1170	length= _mi_keylength(keyinfo, from);
	1171	memcpy(to, from, length);
1 by brian clean slate	1172	return to+length;
	1173	}
	1174
	1175	/* Find next/previous record with same key */
	1176	/* This can't be used when database is touched after last read */
	1177
	1178	int _mi_search_next(register MI_INFO info, register MI_KEYDEF keyinfo,
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	1179	unsigned char *key, uint32_t key_length, uint32_t nextflag, internal::my_off_t pos)
1 by brian clean slate	1180	{
1 by brian clean slate	1181	int error;
482 by Brian Aker Remove uint.	1182	uint32_t nod_flag;
481 by Brian Aker Remove all of uchar.	1183	unsigned char lastkey[MI_MAX_KEY_BUFF];
1 by brian clean slate	1184
	1185	/* Force full read if we are at last key or if we are not on a leaf
	1186	and the key tree has changed since we used it last time
	1187	Note that even if the key tree has changed since last read, we can use
	1188	the last read data from the leaf if we haven't used the buffer for
	1189	something else.
	1190	*/
	1191
	1192	if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) \|\|
	1193	info->page_changed \|\|
	1194	(info->int_keytree_version != keyinfo->version &&
	1195	(info->int_nod_flag \|\| info->buff_used)))
51.1.111 by Jay Pipes Removed DBUG symbols	1196	return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1 by brian clean slate	1197	nextflag \| SEARCH_SAVE_BUFF, pos));
	1198
	1199	if (info->buff_used)
	1200	{
	1201	if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
	1202	DFLT_INIT_HITS,info->buff,0))
51.1.111 by Jay Pipes Removed DBUG symbols	1203	return(-1);
1 by brian clean slate	1204	info->buff_used=0;
	1205	}
	1206
	1207	/* Last used buffer is in info->buff */
	1208	nod_flag=mi_test_if_nod(info->buff);
	1209
	1210	if (nextflag & SEARCH_BIGGER) /* Next key */
	1211	{
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	1212	internal::my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
1 by brian clean slate	1213	if (tmp_pos != HA_OFFSET_ERROR)
	1214	{
	1215	if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
	1216	nextflag \| SEARCH_SAVE_BUFF, tmp_pos)) <=0)
51.1.111 by Jay Pipes Removed DBUG symbols	1217	return(error);
1 by brian clean slate	1218	}
	1219	memcpy(lastkey,key,key_length);
	1220	if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
	1221	&info->int_keypos,lastkey)))
51.1.111 by Jay Pipes Removed DBUG symbols	1222	return(-1);
1 by brian clean slate	1223	}
	1224	else /* Previous key */
	1225	{
482 by Brian Aker Remove uint.	1226	uint32_t length;
1 by brian clean slate	1227	/* Find start of previous key */
	1228	info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
	1229	info->int_keypos, &length);
	1230	if (!info->int_keypos)
51.1.111 by Jay Pipes Removed DBUG symbols	1231	return(-1);
1 by brian clean slate	1232	if (info->int_keypos == info->buff+2)
51.1.111 by Jay Pipes Removed DBUG symbols	1233	return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1 by brian clean slate	1234	nextflag \| SEARCH_SAVE_BUFF, pos));
	1235	if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
	1236	nextflag \| SEARCH_SAVE_BUFF,
	1237	_mi_kpos(nod_flag,info->int_keypos))) <= 0)
51.1.111 by Jay Pipes Removed DBUG symbols	1238	return(error);
1 by brian clean slate	1239
	1240	/* QQ: We should be able to optimize away the following call */
	1241	if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
	1242	info->int_keypos,&info->lastkey_length))
51.1.111 by Jay Pipes Removed DBUG symbols	1243	return(-1);
1 by brian clean slate	1244	}
	1245	memcpy(info->lastkey,lastkey,info->lastkey_length);
	1246	info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
51.1.111 by Jay Pipes Removed DBUG symbols	1247	return(0);
1 by brian clean slate	1248	} /* _mi_search_next */
	1249
	1250
	1251	/* Search after position for the first row in an index */
	1252	/* This is stored in info->lastpos */
	1253
	1254	int _mi_search_first(register MI_INFO info, register MI_KEYDEF keyinfo,
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	1255	register internal::my_off_t pos)
1 by brian clean slate	1256	{
482 by Brian Aker Remove uint.	1257	uint32_t nod_flag;
481 by Brian Aker Remove all of uchar.	1258	unsigned char *page;
1 by brian clean slate	1259
	1260	if (pos == HA_OFFSET_ERROR)
	1261	{
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	1262	errno=HA_ERR_KEY_NOT_FOUND;
1 by brian clean slate	1263	info->lastpos= HA_OFFSET_ERROR;
51.1.111 by Jay Pipes Removed DBUG symbols	1264	return(-1);
1 by brian clean slate	1265	}
	1266
	1267	do
	1268	{
	1269	if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
	1270	{
	1271	info->lastpos= HA_OFFSET_ERROR;
51.1.111 by Jay Pipes Removed DBUG symbols	1272	return(-1);
1 by brian clean slate	1273	}
	1274	nod_flag=mi_test_if_nod(info->buff);
	1275	page=info->buff+2+nod_flag;
	1276	} while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
	1277
	1278	if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
	1279	info->lastkey)))
51.1.111 by Jay Pipes Removed DBUG symbols	1280	return(-1); /* Crashed */
1 by brian clean slate	1281
	1282	info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
	1283	info->int_nod_flag=nod_flag;
	1284	info->int_keytree_version=keyinfo->version;
	1285	info->last_search_keypage=info->last_keypage;
	1286	info->page_changed=info->buff_used=0;
	1287	info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
	1288
51.1.111 by Jay Pipes Removed DBUG symbols	1289	return(0);
1 by brian clean slate	1290	} /* _mi_search_first */
	1291
	1292
	1293	/* Search after position for the last row in an index */
	1294	/* This is stored in info->lastpos */
	1295
	1296	int _mi_search_last(register MI_INFO info, register MI_KEYDEF keyinfo,
1280.1.10 by Monty Taylor Put everything in drizzled into drizzled namespace.	1297	register internal::my_off_t pos)
1 by brian clean slate	1298	{
482 by Brian Aker Remove uint.	1299	uint32_t nod_flag;
481 by Brian Aker Remove all of uchar.	1300	unsigned char buff,page;
1 by brian clean slate	1301
	1302	if (pos == HA_OFFSET_ERROR)
	1303	{
1241.9.57 by Monty Taylor Oy. Bigger change than I normally like - but this stuff is all intertwined.	1304	errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1 by brian clean slate	1305	info->lastpos= HA_OFFSET_ERROR;
51.1.111 by Jay Pipes Removed DBUG symbols	1306	return(-1);
1 by brian clean slate	1307	}
	1308
	1309	buff=info->buff;
	1310	do
	1311	{
	1312	if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
	1313	{
	1314	info->lastpos= HA_OFFSET_ERROR;
51.1.111 by Jay Pipes Removed DBUG symbols	1315	return(-1);
1 by brian clean slate	1316	}
	1317	page= buff+mi_getint(buff);
	1318	nod_flag=mi_test_if_nod(buff);
	1319	} while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
	1320
	1321	if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
	1322	&info->lastkey_length))
51.1.111 by Jay Pipes Removed DBUG symbols	1323	return(-1);
1 by brian clean slate	1324	info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
	1325	info->int_keypos=info->int_maxpos=page;
	1326	info->int_nod_flag=nod_flag;
	1327	info->int_keytree_version=keyinfo->version;
	1328	info->last_search_keypage=info->last_keypage;
	1329	info->page_changed=info->buff_used=0;
	1330
51.1.111 by Jay Pipes Removed DBUG symbols	1331	return(0);
1 by brian clean slate	1332	} /* _mi_search_last */
	1333
	1334
	1335
	1336	/****************************************************************************
	1337	**
	1338	** Functions to store and pack a key in a page
	1339	**
	1340	** mi_calc_xx_key_length takes the following arguments:
	1341	** nod_flag If nod: Length of nod-pointer
	1342	** next_key Position to pos after the new key in buffer
	1343	** org_key Key that was before the next key in buffer
	1344	** prev_key Last key before current key
	1345	** key Key that will be stored
	1346	** s_temp Information how next key will be packed
	1347	****************************************************************************/
	1348
	1349	/* Static length key */
	1350
	1351	int
482 by Brian Aker Remove uint.	1352	_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
779.3.1 by Monty Taylor More cleanup.	1353	unsigned char *next_pos,
	1354	unsigned char *org_key,
	1355	unsigned char *prev_key,
481 by Brian Aker Remove all of uchar.	1356	unsigned char key, MI_KEY_PARAM s_temp)
1 by brian clean slate	1357	{
779.3.1 by Monty Taylor More cleanup.	1358	(void)next_pos;
	1359	(void)org_key;
	1360	(void)prev_key;
1 by brian clean slate	1361	s_temp->key=key;
	1362	return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
	1363	}
	1364
	1365	/* Variable length key */
	1366
	1367	int
482 by Brian Aker Remove uint.	1368	_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
779.3.1 by Monty Taylor More cleanup.	1369	unsigned char *next_pos,
	1370	unsigned char *org_key,
	1371	unsigned char *prev_key,
481 by Brian Aker Remove all of uchar.	1372	unsigned char key, MI_KEY_PARAM s_temp)
1 by brian clean slate	1373	{
779.3.1 by Monty Taylor More cleanup.	1374	(void)next_pos;
	1375	(void)org_key;
	1376	(void)prev_key;
1 by brian clean slate	1377	s_temp->key=key;
	1378	return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
	1379	}
	1380
	1381	/*
	1382	length of key with a variable length first segment which is prefix
	1383	compressed (myisamchk reports 'packed + stripped')
	1384
	1385	Keys are compressed the following way:
	1386
	1387	If the max length of first key segment <= 127 bytes the prefix is
	1388	1 byte else it's 2 byte
	1389
	1390	prefix byte(s) The high bit is set if this is a prefix for the prev key
	1391	length Packed length if the previous was a prefix byte
	1392	[length] data bytes ('length' bytes)
	1393	next-key-seg Next key segments
	1394
	1395	If the first segment can have NULL:
	1396	The length is 0 for NULLS and 1+length for not null columns.
	1397
	1398	*/
	1399
	1400	int
779.3.1 by Monty Taylor More cleanup.	1401	_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
	1402	unsigned char *next_key,
	1403	unsigned char *org_key,
	1404	unsigned char *prev_key,
	1405	unsigned char *key,
1 by brian clean slate	1406	MI_KEY_PARAM *s_temp)
	1407	{
	1408	register HA_KEYSEG *keyseg;
	1409	int length;
482 by Brian Aker Remove uint.	1410	uint32_t key_length,ref_length,org_key_length=0,
1 by brian clean slate	1411	length_pack,new_key_length,diff_flag,pack_marker;
481 by Brian Aker Remove all of uchar.	1412	unsigned char start,end,key_end,sort_order;
281 by Brian Aker Converted myisam away from my_bool	1413	bool same_length;
1 by brian clean slate	1414
	1415	length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
	1416	same_length=0; keyseg=keyinfo->seg;
	1417	key_length=_mi_keylength(keyinfo,key)+nod_flag;
	1418
	1419	sort_order=0;
	1420
	1421	/* diff flag contains how many bytes is needed to pack key */
	1422	if (keyseg->length >= 127)
	1423	{
	1424	diff_flag=2;
	1425	pack_marker=32768;
	1426	}
	1427	else
	1428	{
	1429	diff_flag= 1;
	1430	pack_marker=128;
	1431	}
	1432	s_temp->pack_marker=pack_marker;
	1433
	1434	/* Handle the case that the first part have NULL values */
	1435	if (keyseg->flag & HA_NULL_PART)
	1436	{
	1437	if (!*key++)
	1438	{
	1439	s_temp->key=key;
	1440	s_temp->key_length= 0;
	1441	s_temp->totlength=key_length-1+diff_flag;
	1442	s_temp->next_key_pos=0; /* No next key */
	1443	return (s_temp->totlength);
	1444	}
	1445	s_temp->store_not_null=1;
	1446	key_length--; /* We don't store NULL */
	1447	if (prev_key && !*prev_key++)
	1448	org_key=prev_key=0; /* Can't pack against prev */
	1449	else if (org_key)
	1450	org_key++; /* Skip NULL */
	1451	}
	1452	else
	1453	s_temp->store_not_null=0;
	1454	s_temp->prev_key=org_key;
	1455
	1456	/* The key part will start with a packed length */
	1457
	1458	get_key_pack_length(new_key_length,length_pack,key);
	1459	end=key_end= key+ new_key_length;
	1460	start=key;
	1461
	1462	/* Calc how many characters are identical between this and the prev. key */
	1463	if (prev_key)
	1464	{
	1465	get_key_length(org_key_length,prev_key);
	1466	s_temp->prev_key=prev_key; /* Pointer at data */
	1467	/* Don't use key-pack if length == 0 */
	1468	if (new_key_length && new_key_length == org_key_length)
	1469	same_length=1;
	1470	else if (new_key_length > org_key_length)
	1471	end=key + org_key_length;
	1472
	1473	if (sort_order) /* SerG */
	1474	{
	1475	while (key < end && sort_order[key] == sort_order[prev_key])
	1476	{
	1477	key++; prev_key++;
1478	}
1479	}
1480	else
1481	{
1482	while (key < end && key == prev_key)
1483	{
1484	key++; prev_key++;
1485	}
1486	}
1487	}
1488
1489	s_temp->key=key;
1490	s_temp->key_length= (uint) (key_end-key);
1491
1492	if (same_length && key == key_end)
1493	{
1494	/* identical variable length key */
1495	s_temp->ref_length= pack_marker;
1496	length=(int) key_length-(int) (key_end-start)-length_pack;
1497	length+= diff_flag;
1498	if (next_key)
1499	{ /* Can't combine with next */
1500	s_temp->n_length= next_key; / Needed by _mi_store_key */
1501	next_key=0;
1502	}
1503	}
1504	else
1505	{
1506	if (start != key)
1507	{ /* Starts as prev key */
1508	ref_length= (uint) (key-start);
1509	s_temp->ref_length= ref_length + pack_marker;
1510	length= (int) (key_length - ref_length);
1511
1512	length-= length_pack;
1513	length+= diff_flag;
1514	length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
1515	}
1516	else
1517	{
1518	s_temp->key_length+=s_temp->store_not_null; /* If null */
1519	length= key_length - length_pack+ diff_flag;
1520	}
1521	}
1522	s_temp->totlength=(uint) length;
1523	s_temp->prev_length=0;
1524
1525	/* If something after that hasn't length=0, test if we can combine */
1526	if ((s_temp->next_key_pos=next_key))
1527	{
482 by Brian Aker Remove uint.	1528	uint32_t packed,n_length;
1 by brian clean slate	1529
	1530	packed = *next_key & 128;
	1531	if (diff_flag == 2)
	1532	{
	1533	n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
	1534	next_key+=2;
	1535	}
	1536	else
	1537	n_length= *next_key++ & 127;
	1538	if (!packed)
	1539	n_length-= s_temp->store_not_null;
	1540
	1541	if (n_length \|\| packed) /* Don't pack 0 length keys */
	1542	{
482 by Brian Aker Remove uint.	1543	uint32_t next_length_pack, new_ref_length=s_temp->ref_length;
1 by brian clean slate	1544
	1545	if (packed)
	1546	{
	1547	/* If first key and next key is packed (only on delete) */
	1548	if (!prev_key && org_key)
	1549	{
	1550	get_key_length(org_key_length,org_key);
	1551	key=start;
	1552	if (sort_order) /* SerG */
	1553	{
	1554	while (key < end && sort_order[key] == sort_order[org_key])
	1555	{
	1556	key++; org_key++;
	1557	}
	1558	}
	1559	else
	1560	{
	1561	while (key < end && key == org_key)
	1562	{
	1563	key++; org_key++;
	1564	}
	1565	}
	1566	if ((new_ref_length= (uint) (key - start)))
	1567	new_ref_length+=pack_marker;
	1568	}
	1569
	1570	if (!n_length)
	1571	{
	1572	/*
	1573	We put a different key between two identical variable length keys
	1574	Extend next key to have same prefix as this key
	1575	*/
	1576	if (new_ref_length) /* prefix of previus key */
	1577	{ /* make next key longer */
	1578	s_temp->part_of_prev_key= new_ref_length;
	1579	s_temp->prev_length= org_key_length -
	1580	(new_ref_length-pack_marker);
	1581	s_temp->n_ref_length= s_temp->part_of_prev_key;
	1582	s_temp->n_length= s_temp->prev_length;
	1583	n_length= get_pack_length(s_temp->prev_length);
	1584	s_temp->prev_key+= (new_ref_length - pack_marker);
	1585	length+= s_temp->prev_length + n_length;
	1586	}
	1587	else
	1588	{ /* Can't use prev key */
	1589	s_temp->part_of_prev_key=0;
	1590	s_temp->prev_length= org_key_length;
	1591	s_temp->n_ref_length=s_temp->n_length= org_key_length;
	1592	length+= org_key_length;
	1593	}
	1594	return (int) length;
	1595	}
	1596
	1597	ref_length=n_length;
	1598	/* Get information about not packed key suffix */
	1599	get_key_pack_length(n_length,next_length_pack,next_key);
	1600
	1601	/* Test if new keys has fewer characters that match the previous key */
	1602	if (!new_ref_length)
	1603	{ /* Can't use prev key */
	1604	s_temp->part_of_prev_key= 0;
	1605	s_temp->prev_length= ref_length;
	1606	s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
	1607	return (int) length+ref_length-next_length_pack;
1608	}
1609	if (ref_length+pack_marker > new_ref_length)
1610	{
482 by Brian Aker Remove uint.	1611	uint32_t new_pack_length=new_ref_length-pack_marker;
1 by brian clean slate	1612	/* We must copy characters from the original key to the next key */
	1613	s_temp->part_of_prev_key= new_ref_length;
	1614	s_temp->prev_length= ref_length - new_pack_length;
	1615	s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
	1616	s_temp->prev_key+= new_pack_length;
	1617	length-= (next_length_pack - get_pack_length(s_temp->n_length));
	1618	return (int) length + s_temp->prev_length;
	1619	}
	1620	}
	1621	else
	1622	{
	1623	/* Next key wasn't a prefix of previous key */
	1624	ref_length=0;
	1625	next_length_pack=0;
	1626	}
	1627
	1628	{
482 by Brian Aker Remove uint.	1629	uint32_t tmp_length;
1 by brian clean slate	1630	key=(start+=ref_length);
	1631	if (key+n_length < key_end) /* Normalize length based */
	1632	key_end=key+n_length;
	1633	if (sort_order) /* SerG */
	1634	{
	1635	while (key < key_end && sort_order[*key] ==
	1636	sort_order[*next_key])
	1637	{
	1638	key++; next_key++;
	1639	}
	1640	}
	1641	else
	1642	{
	1643	while (key < key_end && key == next_key)
	1644	{
	1645	key++; next_key++;
	1646	}
	1647	}
	1648	if (!(tmp_length=(uint) (key-start)))
	1649	{ /* Key can't be re-packed */
	1650	s_temp->next_key_pos=0;
	1651	return length;
	1652	}
	1653	ref_length+=tmp_length;
	1654	n_length-=tmp_length;
	1655	length-=tmp_length+next_length_pack; /* We gained these chars */
	1656	}
	1657	if (n_length == 0 && ref_length == new_key_length)
	1658	{
	1659	s_temp->n_ref_length=pack_marker; /* Same as prev key */
	1660	}
	1661	else
	1662	{
	1663	s_temp->n_ref_length=ref_length \| pack_marker;
	1664	length+= get_pack_length(n_length);
	1665	s_temp->n_length=n_length;
	1666	}
	1667	}
	1668	}
	1669	return length;
	1670	}
	1671
	1672
	1673	/* Length of key which is prefix compressed */
	1674
	1675	int
482 by Brian Aker Remove uint.	1676	_mi_calc_bin_pack_key_length(MI_KEYDEF keyinfo,uint32_t nod_flag,unsigned char next_key,
481 by Brian Aker Remove all of uchar.	1677	unsigned char org_key, unsigned char prev_key, unsigned char *key,
1 by brian clean slate	1678	MI_KEY_PARAM *s_temp)
1 by brian clean slate	1679	{
482 by Brian Aker Remove uint.	1680	uint32_t length,key_length,ref_length;
1 by brian clean slate	1681
1 by brian clean slate	1682	s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
1859.2.14 by Brian Aker Add support for --with-valgrind	1683	#ifdef HAVE_VALGRIND
1 by brian clean slate	1684	s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
	1685	#endif
	1686	s_temp->key=key;
	1687	s_temp->prev_key=org_key;
	1688	if (prev_key) /* If not first key in block */
	1689	{
	1690	/* pack key against previous key */
	1691	/*
	1692	As keys may be identical when running a sort in myisamchk, we
	1693	have to guard against the case where keys may be identical
	1694	*/
481 by Brian Aker Remove all of uchar.	1695	unsigned char *end;
1 by brian clean slate	1696	end=key+key_length;
	1697	for ( ; key == prev_key && key < end; key++,prev_key++) ;
	1698	s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
	1699	length=key_length - ref_length + get_pack_length(ref_length);
	1700	}
	1701	else
	1702	{
	1703	/* No previous key */
	1704	s_temp->ref_length=ref_length=0;
	1705	length=key_length+1;
	1706	}
	1707	if ((s_temp->next_key_pos=next_key)) /* If another key after */
	1708	{
	1709	/* pack key against next key */
482 by Brian Aker Remove uint.	1710	uint32_t next_length,next_length_pack;
1 by brian clean slate	1711	get_key_pack_length(next_length,next_length_pack,next_key);
	1712
	1713	/* If first key and next key is packed (only on delete) */
	1714	if (!prev_key && org_key && next_length)
	1715	{
481 by Brian Aker Remove all of uchar.	1716	unsigned char *end;
1 by brian clean slate	1717	for (key= s_temp->key, end=key+next_length ;
	1718	key == org_key && key < end;
	1719	key++,org_key++) ;
	1720	ref_length= (uint) (key - s_temp->key);
	1721	}
	1722
	1723	if (next_length > ref_length)
	1724	{
	1725	/* We put a key with different case between two keys with the same prefix
	1726	Extend next key to have same prefix as
	1727	this key */
	1728	s_temp->n_ref_length= ref_length;
	1729	s_temp->prev_length= next_length-ref_length;
	1730	s_temp->prev_key+= ref_length;
	1731	return (int) (length+ s_temp->prev_length - next_length_pack +
	1732	get_pack_length(ref_length));
	1733	}
	1734	/* Check how many characters are identical to next key */
	1735	key= s_temp->key+next_length;
	1736	while (key++ == next_key++) ;
	1737	if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
	1738	{
	1739	s_temp->next_key_pos=0;
	1740	return length; /* can't pack next key */
	1741	}
	1742	s_temp->prev_length=0;
	1743	s_temp->n_ref_length=ref_length;
	1744	return (int) (length-(ref_length - next_length) - next_length_pack +
	1745	get_pack_length(ref_length));
	1746	}
	1747	return (int) length;
	1748	}
	1749
	1750
	1751	/*
	1752	** store a key packed with _mi_calc_xxx_key_length in page-buffert
	1753	*/
	1754
	1755	/* store key without compression */
	1756
779.3.1 by Monty Taylor More cleanup.	1757	void _mi_store_static_key(MI_KEYDEF *keyinfo,
481 by Brian Aker Remove all of uchar.	1758	register unsigned char *key_pos,
1 by brian clean slate	1759	register MI_KEY_PARAM *s_temp)
1 by brian clean slate	1760	{
779.3.1 by Monty Taylor More cleanup.	1761	(void)keyinfo;
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	1762	memcpy(key_pos, s_temp->key, s_temp->totlength);
1 by brian clean slate	1763	}
	1764
	1765
	1766	/* store variable length key with prefix compression */
	1767
	1768	#define store_pack_length(test,pos,length) { \
481 by Brian Aker Remove all of uchar.	1769	if (test) { *((pos)++) = (unsigned char) (length); } else \
481 by Brian Aker Remove all of uchar.	1770	{ ((pos)++) = (unsigned char) ((length) >> 8); ((pos)++) = (unsigned char) (length); } }
1 by brian clean slate	1771
1 by brian clean slate	1772
779.3.1 by Monty Taylor More cleanup.	1773	void _mi_store_var_pack_key(MI_KEYDEF *keyinfo,
481 by Brian Aker Remove all of uchar.	1774	register unsigned char *key_pos,
1 by brian clean slate	1775	register MI_KEY_PARAM *s_temp)
1 by brian clean slate	1776	{
779.3.1 by Monty Taylor More cleanup.	1777	(void)keyinfo;
482 by Brian Aker Remove uint.	1778	uint32_t length;
481 by Brian Aker Remove all of uchar.	1779	unsigned char *start;
1 by brian clean slate	1780
	1781	start=key_pos;
	1782
	1783	if (s_temp->ref_length)
	1784	{
	1785	/* Packed against previous key */
	1786	store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
	1787	/* If not same key after */
	1788	if (s_temp->ref_length != s_temp->pack_marker)
	1789	store_key_length_inc(key_pos,s_temp->key_length);
	1790	}
	1791	else
	1792	{
	1793	/* Not packed against previous key */
	1794	store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
	1795	}
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	1796	assert(key_pos >= start);
	1797	length= s_temp->totlength - (key_pos - start);
629.3.4 by Kristian Nielsen Take Mats'es changes from bmove()->memcpy(), and fix all of them to be	1798	memmove(key_pos, s_temp->key, length);
1 by brian clean slate	1799
	1800	if (!s_temp->next_key_pos) /* No following key */
	1801	return;
	1802	key_pos+=length;
	1803
	1804	if (s_temp->prev_length)
	1805	{
	1806	/* Extend next key because new key didn't have same prefix as prev key */
	1807	if (s_temp->part_of_prev_key)
	1808	{
	1809	store_pack_length(s_temp->pack_marker == 128,key_pos,
	1810	s_temp->part_of_prev_key);
	1811	store_key_length_inc(key_pos,s_temp->n_length);
	1812	}
	1813	else
	1814	{
	1815	s_temp->n_length+= s_temp->store_not_null;
	1816	store_pack_length(s_temp->pack_marker == 128,key_pos,
	1817	s_temp->n_length);
	1818	}
	1819	memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
	1820	}
	1821	else if (s_temp->n_ref_length)
	1822	{
	1823	store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
	1824	if (s_temp->n_ref_length == s_temp->pack_marker)
	1825	return; /* Identical key */
	1826	store_key_length(key_pos,s_temp->n_length);
	1827	}
	1828	else
	1829	{
	1830	s_temp->n_length+= s_temp->store_not_null;
	1831	store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
	1832	}
	1833	}
	1834
	1835
	1836	/* variable length key with prefix compression */
	1837
779.3.1 by Monty Taylor More cleanup.	1838	void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo,
481 by Brian Aker Remove all of uchar.	1839	register unsigned char *key_pos,
1 by brian clean slate	1840	register MI_KEY_PARAM *s_temp)
1 by brian clean slate	1841	{
779.3.1 by Monty Taylor More cleanup.	1842	(void)keyinfo;
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	1843	assert(s_temp->totlength >= s_temp->ref_length);
1 by brian clean slate	1844	store_key_length_inc(key_pos,s_temp->ref_length);
212.6.12 by Mats Kindahl Removing redundant use of casts in MyISAM storage for memcmp(), memcpy(), memset(), and memmove().	1845	memcpy(key_pos,s_temp->key+s_temp->ref_length,
	1846	s_temp->totlength - s_temp->ref_length);
1 by brian clean slate	1847
	1848	if (s_temp->next_key_pos)
	1849	{
	1850	key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
	1851	store_key_length_inc(key_pos,s_temp->n_ref_length);
	1852	if (s_temp->prev_length) /* If we must extend key */
	1853	{
	1854	memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
	1855	}
	1856	}
	1857	}