Lines Matching +full:multi +full:- +full:attr
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
50 #define TINY_NODE(sl) ((sl)->tosort_num < 65)
51 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
56 /* sort sub-levels array size */
103 sort_left -= n; in sort_left_dec()
134 ls->next = g_ls; in _push_ls()
147 new_ls->sl = sl; in push_ls()
161 * Pop sort level from the stack (single-threaded style)
171 sl = g_ls->sl; in pop_ls_st()
173 g_ls = g_ls->next; in pop_ls_st()
184 * Pop sort level from the stack (multi-threaded style)
196 sl = g_ls->sl; in pop_ls_mt()
198 g_ls = g_ls->next; in pop_ls_mt()
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()
234 if (++(ssl->tosort_num) > ssl->tosort_sz) { in add_to_sublevel()
235 ssl->tosort_sz = ssl->tosort_num + 128; in add_to_sublevel()
236 ssl->tosort = sort_realloc(ssl->tosort, in add_to_sublevel()
237 sizeof(struct sort_list_item*) * (ssl->tosort_sz)); in add_to_sublevel()
240 ssl->tosort[ssl->tosort_num - 1] = item; in add_to_sublevel()
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()
262 kv = get_key_from_keys_array(&sli->ka, 0); in get_wc_index()
263 bws = kv->k; in get_wc_index()
273 /* Sort most-significant byte first. */ in get_wc_index()
274 if (level % wcfact < wcfact - 1) in get_wc_index()
275 res = (res >> (8 * (wcfact - 1 - (level % wcfact)))); in get_wc_index()
280 return (-1); in get_wc_index()
289 sli = sl->tosort[item]; in place_item()
290 c = get_wc_index(sli, sl->level); in place_item()
292 if (c == -1) in place_item()
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()
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()
373 * character-width, so we must divide the level (bytes) 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()
393 (int(*)(const void *, const void *)) func) == -1) 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()
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()
485 n = sln - i - 1; 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()
510 * Single-threaded sort cycle
529 * Multi-threaded sort cycle
545 * Sort cycle thread (in multi-threaded mode)
564 default_sort_mods->rflag; in run_top_sort_level()
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()
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()
641 pthread_attr_t attr; in run_top_sort_level() local
644 pthread_attr_init(&attr); in run_top_sort_level()
645 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED); in run_top_sort_level()
648 int res = pthread_create(&pth, &attr, in run_top_sort_level()
659 pthread_attr_destroy(&attr); in run_top_sort_level()
696 sl->tosort = base; in run_sort()
697 sl->tosort_num = nmemb; in run_sort()
698 sl->tosort_sz = nmemb; in run_sort()