<commit_before>#include "ut0bh.h"
#include "ut0mem.h"

#include <string.h>


UNIV_INLINE ulint ib_bh_size(const ib_bh_t* ib_bh)
{
	return ib_bh->n_elems;
}

UNIV_INLINE ibool ib_bh_is_empty(const ib_bh_t* ib_bh)
{
	return ib_bh_size(ib_bh) == 0;
}


UNIV_INLINE ibool ib_bh_is_full(const ib_bh_t* ib_bh)
{
	return (ib_bh->n_elems >= ib_bh->max_elems);
}

UNIV_INLINE void* ib_bh_get(ib_bh_t* ib_bh, ulint i)
{
	byte* ptr = (byte*)(ib_bh + 1);

	ut_a(i < ib_bh_size(ib_bh));

	return (ptr + (ib_bh->sizeof_elem * i));
}

UNIV_INLINE void* ib_bh_set(ib_bh_t* ib_bh, ulint i, const void* elem)
{
	void* ptr = ib_bh_get(ib_bh, i);
	ut_memcpy(ptr, elem, ib_bh->sizeof_elem);

	return ptr;
}

UNIV_INLINE void* ib_bh_first(ib_bh_t* ib_bh)
{
	return (ib_bh_is_empty(ib_bh) ? NULL : ib_bh_get(ib_bh, 0));
}

UNIV_INLINE void* ib_bh_last(ib_bh_t* ib_bh)
{
	return (ib_bh_is_empty(ib_bh) ? NULL : ib_bh_get(ib_bh, ib_bh->n_elems - 1));
}

UNIV_INTERN ib_bh_t* ib_bh_create(ib_bh_cmp_t compare, ulint sizeof_elem, ulint max_elems)
{
	ulint sz;
	ib_bh_t* ib_bh;

	sz = sizeof(ib_bh_t) + (sizeof_elem * max_elems);
	/*һڴ棬ڴ洢*/
	ib_bh = ut_malloc(sz);
	/*ΪʲôڴֱӴڴڴ棿*/
	memset(ib_bh, 0x0, sz);

	ib_bh->compare = compare;
	ib_bh->max_elems = max_elems;
	ib_bh->n_elems = 0;
	ib_bh->sizeof_elem = sizeof_elem;

	return ib_bh;
}

UNIV_INTERN void ib_bh_free(ib_bh_t* ib_bh)
{
	ut_free(ib_bh);
}
/*õǶֲҷӶlogN,ֻѭĸӶȡĸӶȡcompareib_bh_setֵֵӶ*/
UNIV_INTERN void* ib_bh_push(ib_bh_t* ib_bh, const void* elem)
{
	void* ptr;

	if(ib_bh_is_full(ib_bh))
		return NULL;
	else if(ib_bh_is_empty(ib_bh)){
		ib_bh->n_elems ++;
		return ib_bh_set(ib_bh, 0, ptr);
	}
	else{
		ulint i;
		i = ib_bh->n_elems;
		++ib_bh->n_elems;

		for(ptr = ib_bh_get(ib_bh, i >> 1); i > 0 && ib_bh->compare(ptr, elem) > 0; i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)){
			ib_bh_set(ib_bh, i, ptr);
		}
		/*ѭӦõͬ´:
		ptr = ib_bh_get(ib_bh, i >> 1);
		while(i > 0 && ib_bh->compare(ptr, elem) > 0){
			ib_bh_set(ib_bh, i, ptr);
			i >>= 1;
			ptr = ib_bh_get(ib_bh, i >> 1);
		}
		*/
		ptr = ib_bh_set(ib_bh, i, elem);
	}
}


<commit_msg>add bin min heap's pop<commit_after>#include "ut0bh.h"
#include "ut0mem.h"

#include <string.h>


UNIV_INLINE ulint ib_bh_size(const ib_bh_t* ib_bh)
{
	return ib_bh->n_elems;
}

UNIV_INLINE ibool ib_bh_is_empty(const ib_bh_t* ib_bh)
{
	return ib_bh_size(ib_bh) == 0;
}


UNIV_INLINE ibool ib_bh_is_full(const ib_bh_t* ib_bh)
{
	return (ib_bh->n_elems >= ib_bh->max_elems);
}

UNIV_INLINE void* ib_bh_get(ib_bh_t* ib_bh, ulint i)
{
	byte* ptr = (byte*)(ib_bh + 1);

	ut_a(i < ib_bh_size(ib_bh));

	return (ptr + (ib_bh->sizeof_elem * i));
}

UNIV_INLINE void* ib_bh_set(ib_bh_t* ib_bh, ulint i, const void* elem)
{
	void* ptr = ib_bh_get(ib_bh, i);
	ut_memcpy(ptr, elem, ib_bh->sizeof_elem);

	return ptr;
}

UNIV_INLINE void* ib_bh_first(ib_bh_t* ib_bh)
{
	return (ib_bh_is_empty(ib_bh) ? NULL : ib_bh_get(ib_bh, 0));
}

UNIV_INLINE void* ib_bh_last(ib_bh_t* ib_bh)
{
	return (ib_bh_is_empty(ib_bh) ? NULL : ib_bh_get(ib_bh, ib_bh->n_elems - 1));
}

UNIV_INTERN ib_bh_t* ib_bh_create(ib_bh_cmp_t compare, ulint sizeof_elem, ulint max_elems)
{
	ulint sz;
	ib_bh_t* ib_bh;

	sz = sizeof(ib_bh_t) + (sizeof_elem * max_elems);
	/*һڴ棬ڴ洢*/
	ib_bh = ut_malloc(sz);
	/*ΪʲôڴֱӴڴڴ棿*/
	memset(ib_bh, 0x0, sz);

	ib_bh->compare = compare;
	ib_bh->max_elems = max_elems;
	ib_bh->n_elems = 0;
	ib_bh->sizeof_elem = sizeof_elem;

	return ib_bh;
}

UNIV_INTERN void ib_bh_free(ib_bh_t* ib_bh)
{
	ut_free(ib_bh);
}
/*õǶֲҷӶlogN,ֻѭĸӶȡĸӶȡcompareib_bh_setֵֵӶ*/
UNIV_INTERN void* ib_bh_push(ib_bh_t* ib_bh, const void* elem)
{
	void* ptr;

	if(ib_bh_is_full(ib_bh))
		return NULL;
	else if(ib_bh_is_empty(ib_bh)){
		ib_bh->n_elems ++;
		return ib_bh_set(ib_bh, 0, ptr);
	}
	else{
		ulint i;
		i = ib_bh->n_elems;
		++ib_bh->n_elems;

		for(ptr = ib_bh_get(ib_bh, i >> 1); i > 0 && ib_bh->compare(ptr, elem) > 0; i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)){
			ib_bh_set(ib_bh, i, ptr);
		}
		/*ѭӦõͬ´:
		ptr = ib_bh_get(ib_bh, i >> 1);
		while(i > 0 && ib_bh->compare(ptr, elem) > 0){
			ib_bh_set(ib_bh, i, ptr);
			i >>= 1;
			ptr = ib_bh_get(ib_bh, i >> 1);
		}
		*/
		ptr = ib_bh_set(ib_bh, i, elem);
	}
}

UNIV_INTERN void ib_bh_pop(ib_bh_t* ib_bh)
{
	byte* ptr;
	byte* last;
	ulint parent = 0;

	if(ib_bh_is_empty(ib_bh))
		return;
	else if(ib_bh_size(ib_bh) == 1){
		--ib_bh->n_elems;
		return;
	}

	last = (byte *)ib_bh_last(ib_bh);
	ptr = (byte*)ib_bh_get(ib_bh, 1);

	/*LASTλãСֵŵheapǰ,Ƚ1±λ0λãȻʣС1һ*/
	while(ptr < last){
		if(ib_bh->compare(ptr + ib_bh->sizeof_elem, ptr) < 0)
			ptr += ib_bh->sizeof_elem;

		if(ib_bh->compare(last, ptr) <= 0)
			break;

		ib_bh_set(ib_bh, parent, ptr);

		parent = (ptr - (byte*)ib_bh_first(ib_bh)) / ib_bh->sizeof_elem;

		if((parent << 1) >= ib_bh_size(ib_bh))
			break;
		/*һ*/
		ptr = (byte *)ib_bh_get(ib_bh, parent << 1);
	}

	--ib_bh->n_elems;
	ib_bh_set(ib_bh, parent, last);
}





{'fraction_non_alphanumeric': 0.16499488229273285, 'fraction_numerical': 0.01023541453428864, 'mean_word_length': 4.459217877094972, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 77, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6448633', 'n_tokens_mistral': 2707, 'n_tokens_neox': 2564, 'n_words': 436}