50 #define TINY_NODE(sl) ((sl)->tosort_num < 65)  argument
51 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)  argument
79 	struct sort_level	 *sl;  member
142 push_ls(struct sort_level *sl)  in push_ls()  argument
147 	new_ls->sl = sl;  in push_ls()
166 	struct sort_level *sl;  in pop_ls_st()  local
171 		sl = g_ls->sl;  in pop_ls_st()
176 		sl = NULL;  in pop_ls_st()
178 	return (sl);  in pop_ls_st()
190 	struct sort_level *sl;  in pop_ls_mt()  local
196 			sl = g_ls->sl;  in pop_ls_mt()
201 		sl = NULL;  in pop_ls_mt()
213 	return (sl);  in pop_ls_mt()
219 add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)  in add_to_sublevel()  argument
223 	ssl = sl->sublevels[indx];  in add_to_sublevel()
228 		ssl->level = sl->level + 1;  in add_to_sublevel()
229 		sl->sublevels[indx] = ssl;  in add_to_sublevel()
231 		++(sl->real_sln);  in add_to_sublevel()
244 add_leaf(struct sort_level *sl, struct sort_list_item *item)  in add_leaf()  argument
247 	if (++(sl->leaves_num) > sl->leaves_sz) {  in add_leaf()
248 		sl->leaves_sz = sl->leaves_num + 128;  in add_leaf()
249 		sl->leaves = sort_realloc(sl->leaves,  in add_leaf()
250 		    (sizeof(struct sort_list_item*) * (sl->leaves_sz)));  in add_leaf()
252 	sl->leaves[sl->leaves_num - 1] = item;  in add_leaf()
284 place_item(struct sort_level *sl, size_t item)  in place_item()  argument
289 	sli = sl->tosort[item];  in place_item()
290 	c = get_wc_index(sli, sl->level);  in place_item()
293 		add_leaf(sl, sli);  in place_item()
295 		add_to_sublevel(sl, sli, c);  in place_item()
299 free_sort_level(struct sort_level *sl)  in free_sort_level()  argument
302 	if (sl) {  in free_sort_level()
303 		if (sl->leaves)  in free_sort_level()
304 			sort_free(sl->leaves);  in free_sort_level()
306 		if (sl->level > 0)  in free_sort_level()
307 			sort_free(sl->tosort);  in free_sort_level()
309 		if (sl->sublevels) {  in free_sort_level()
313 			sln = sl->sln;  in free_sort_level()
316 				slc = sl->sublevels[i];  in free_sort_level()
321 			sort_free(sl->sublevels);  in free_sort_level()
324 		sort_free(sl);  in free_sort_level()
329 run_sort_level_next(struct sort_level *sl)  in run_sort_level_next()  argument
335 	if (sl->sublevels) {  in run_sort_level_next()
336 		sort_free(sl->sublevels);  in run_sort_level_next()
337 		sl->sublevels = NULL;  in run_sort_level_next()
340 	switch (sl->tosort_num) {  in run_sort_level_next()
344 		sl->sorted[sl->start_position] = sl->tosort[0];  in run_sort_level_next()
356 		if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),  in run_sort_level_next()
357 		    sl->level / wcfact) > 0) {  in run_sort_level_next()
358 			sl->sorted[sl->start_position++] = sl->tosort[1];  in run_sort_level_next()
359 			sl->sorted[sl->start_position] = sl->tosort[0];  in run_sort_level_next()
361 			sl->sorted[sl->start_position++] = sl->tosort[0];  in run_sort_level_next()
362 			sl->sorted[sl->start_position] = sl->tosort[1];  in run_sort_level_next()
368 		if (TINY_NODE(sl) || (sl->level > 15)) {  in run_sort_level_next()
377 			func = get_list_call_func(sl->level / wcfact);  in run_sort_level_next()
379 			sl->leaves = sl->tosort;  in run_sort_level_next()
380 			sl->leaves_num = sl->tosort_num;  in run_sort_level_next()
381 			sl->leaves_sz = sl->leaves_num;  in run_sort_level_next()
382 			sl->leaves = sort_realloc(sl->leaves,  in run_sort_level_next()
384 			    (sl->leaves_sz)));  in run_sort_level_next()
385 			sl->tosort = NULL;  in run_sort_level_next()
386 			sl->tosort_num = 0;  in run_sort_level_next()
387 			sl->tosort_sz = 0;  in run_sort_level_next()
388 			sl->sln = 0;  in run_sort_level_next()
389 			sl->real_sln = 0;  in run_sort_level_next()
391 				if (mergesort(sl->leaves, sl->leaves_num,  in run_sort_level_next()
397 				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,  in run_sort_level_next()
401 			memcpy(sl->sorted + sl->start_position,  in run_sort_level_next()
402 			    sl->leaves, sl->leaves_num *  in run_sort_level_next()
405 			sort_left_dec(sl->leaves_num);  in run_sort_level_next()
409 			sl->tosort_sz = sl->tosort_num;  in run_sort_level_next()
410 			sl->tosort = sort_realloc(sl->tosort,  in run_sort_level_next()
411 			    sizeof(struct sort_list_item*) * (sl->tosort_sz));  in run_sort_level_next()
415 	sl->sln = 256;  in run_sort_level_next()
416 	sl->sublevels = sort_calloc(1, slsz);  in run_sort_level_next()
418 	sl->real_sln = 0;  in run_sort_level_next()
420 	tosort_num = sl->tosort_num;  in run_sort_level_next()
422 		place_item(sl, i);  in run_sort_level_next()
424 	sort_free(sl->tosort);  in run_sort_level_next()
425 	sl->tosort = NULL;  in run_sort_level_next()
426 	sl->tosort_num = 0;  in run_sort_level_next()
427 	sl->tosort_sz = 0;  in run_sort_level_next()
429 	if (sl->leaves_num > 1) {  in run_sort_level_next()
432 				mergesort(sl->leaves, sl->leaves_num,  in run_sort_level_next()
436 				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,  in run_sort_level_next()
441 			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,  in run_sort_level_next()
447 	sl->leaves_sz = sl->leaves_num;  in run_sort_level_next()
448 	sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *  in run_sort_level_next()
449 	    (sl->leaves_sz)));  in run_sort_level_next()
452 		memcpy(sl->sorted + sl->start_position, sl->leaves,  in run_sort_level_next()
453 		    sl->leaves_num * sizeof(struct sort_list_item*));  in run_sort_level_next()
454 		sl->start_position += sl->leaves_num;  in run_sort_level_next()
455 		sort_left_dec(sl->leaves_num);  in run_sort_level_next()
457 		sort_free(sl->leaves);  in run_sort_level_next()
458 		sl->leaves = NULL;  in run_sort_level_next()
459 		sl->leaves_num = 0;  in run_sort_level_next()
460 		sl->leaves_sz = 0;  in run_sort_level_next()
462 		sln = sl->sln;  in run_sort_level_next()
465 			slc = sl->sublevels[i];  in run_sort_level_next()
468 				slc->sorted = sl->sorted;  in run_sort_level_next()
469 				slc->start_position = sl->start_position;  in run_sort_level_next()
470 				sl->start_position += slc->tosort_num;  in run_sort_level_next()
475 				sl->sublevels[i] = NULL;  in run_sort_level_next()
482 		sln = sl->sln;  in run_sort_level_next()
486 			slc = sl->sublevels[n];  in run_sort_level_next()
489 				slc->sorted = sl->sorted;  in run_sort_level_next()
490 				slc->start_position = sl->start_position;  in run_sort_level_next()
491 				sl->start_position += slc->tosort_num;  in run_sort_level_next()
496 				sl->sublevels[n] = NULL;  in run_sort_level_next()
500 		memcpy(sl->sorted + sl->start_position, sl->leaves,  in run_sort_level_next()
501 		    sl->leaves_num * sizeof(struct sort_list_item*));  in run_sort_level_next()
502 		sort_left_dec(sl->leaves_num);  in run_sort_level_next()
506 	free_sort_level(sl);  in run_sort_level_next()
559 run_top_sort_level(struct sort_level *sl)  in run_top_sort_level()  argument
566 	sl->start_position = 0;  in run_top_sort_level()
567 	sl->sln = 256;  in run_top_sort_level()
568 	sl->sublevels = sort_calloc(1, slsz);  in run_top_sort_level()
570 	for (size_t i = 0; i < sl->tosort_num; ++i)  in run_top_sort_level()
571 		place_item(sl, i);  in run_top_sort_level()
573 	if (sl->leaves_num > 1) {  in run_top_sort_level()
576 				mergesort(sl->leaves, sl->leaves_num,  in run_top_sort_level()
580 				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,  in run_top_sort_level()
585 			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,  in run_top_sort_level()
592 		memcpy(sl->tosort + sl->start_position, sl->leaves,  in run_top_sort_level()
593 		    sl->leaves_num * sizeof(struct sort_list_item*));  in run_top_sort_level()
594 		sl->start_position += sl->leaves_num;  in run_top_sort_level()
595 		sort_left_dec(sl->leaves_num);  in run_top_sort_level()
597 		for (size_t i = 0; i < sl->sln; ++i) {  in run_top_sort_level()
598 			slc = sl->sublevels[i];  in run_top_sort_level()
601 				slc->sorted = sl->tosort;  in run_top_sort_level()
602 				slc->start_position = sl->start_position;  in run_top_sort_level()
603 				sl->start_position += slc->tosort_num;  in run_top_sort_level()
605 				sl->sublevels[i] = NULL;  in run_top_sort_level()
612 		for (size_t i = 0; i < sl->sln; ++i) {  in run_top_sort_level()
614 			n = sl->sln - i - 1;  in run_top_sort_level()
615 			slc = sl->sublevels[n];  in run_top_sort_level()
618 				slc->sorted = sl->tosort;  in run_top_sort_level()
619 				slc->start_position = sl->start_position;  in run_top_sort_level()
620 				sl->start_position += slc->tosort_num;  in run_top_sort_level()
622 				sl->sublevels[n] = NULL;  in run_top_sort_level()
626 		memcpy(sl->tosort + sl->start_position, sl->leaves,  in run_top_sort_level()
627 		    sl->leaves_num * sizeof(struct sort_list_item*));  in run_top_sort_level()
629 		sort_left_dec(sl->leaves_num);  in run_top_sort_level()
671 	struct sort_level *sl;  in run_sort()  local
694 	sl = sort_calloc(1, sizeof(struct sort_level));  in run_sort()
696 	sl->tosort = base;  in run_sort()
697 	sl->tosort_num = nmemb;  in run_sort()
698 	sl->tosort_sz = nmemb;  in run_sort()
704 	run_top_sort_level(sl);  in run_sort()
706 	free_sort_level(sl);  in run_sort()