diff options
author | Jeroen Bakker <j.bakker@atmind.nl> | 2022-10-04 22:27:13 +0300 |
---|---|---|
committer | Jeroen Bakker <j.bakker@atmind.nl> | 2022-10-04 22:27:13 +0300 |
commit | ae8ce434335746f7167d6f605406c29c10677263 (patch) | |
tree | 0354e38bf2a7f23b28df3e87fd8715aff890ec8c | |
parent | 7e141a01a44317abd802417151011cf78cb76b71 (diff) |
Fix issues using lower_bound.temp-improve-id-sort-by-name
-rw-r--r-- | source/blender/blenkernel/intern/lib_id_sort.cc | 141 |
1 files changed, 1 insertions, 140 deletions
diff --git a/source/blender/blenkernel/intern/lib_id_sort.cc b/source/blender/blenkernel/intern/lib_id_sort.cc index 298f8bb5248..8d42bb48cc4 100644 --- a/source/blender/blenkernel/intern/lib_id_sort.cc +++ b/source/blender/blenkernel/intern/lib_id_sort.cc @@ -94,150 +94,11 @@ void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint) [](ID *&a, ID *const &b) { return BLI_strcasecmp(a->name, b->name) <= 0; }); if (lower_bound == &item_array[ID_SORT_STEP_SIZE]) { - BLI_insertlinkbefore(lb, item_array[item_array_index + 1], id); + BLI_insertlinkafter(lb, item_array[ID_SORT_STEP_SIZE - 1], id); } else { BLI_insertlinkbefore(lb, *lower_bound, id); } - -#if 0 - /* idtest is either on the head of the list or on the tail of the list - * or on the first ID in the expected library that is smaller - * or it's the last item in another library. - * In case idtest is on the head or on the tail or on the first ID in the expected - * library, the new ID can be inserted before or after. Otherwise insert after.*/ - if (idtest == lb->first) { - if (BLI_strcasecmp(idtest->name, id->name) < 0) { - BLI_insertlinkafter(lb, idtest, id); - } - else { - BLI_addhead(lb, id); - } - } - else if (idtest == lb->last) { - if (BLI_strcasecmp(idtest->name, id->name) < 0) { - BLI_addtail(lb, id); - } - else { - BLI_insertlinkbefore(lb, idtest, id); - } - } - else { - BLI_insertlinkafter(lb, idtest, id); - } -#endif - #undef ID_SORT_STEP_SIZE } - -#if 0 - void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint) -{ -# define ID_SORT_STEP_SIZE 512 - - ID *idtest; - - /* insert alphabetically */ - if (lb->first == lb->last) { - return; - } - - BLI_remlink(lb, id); - - /* Check if we can actually insert id before or after id_sorting_hint, if given. */ - if (!ELEM(id_sorting_hint, NULL, id) && id_sorting_hint->lib == id->lib) { - BLI_assert(BLI_findindex(lb, id_sorting_hint) >= 0); - - ID *id_sorting_hint_next = id_sorting_hint->next; - if (BLI_strcasecmp(id_sorting_hint->name, id->name) < 0 && - (id_sorting_hint_next == NULL || id_sorting_hint_next->lib != id->lib || - BLI_strcasecmp(id_sorting_hint_next->name, id->name) > 0)) { - BLI_insertlinkafter(lb, id_sorting_hint, id); - return; - } - - ID *id_sorting_hint_prev = id_sorting_hint->prev; - if (BLI_strcasecmp(id_sorting_hint->name, id->name) > 0 && - (id_sorting_hint_prev == NULL || id_sorting_hint_prev->lib != id->lib || - BLI_strcasecmp(id_sorting_hint_prev->name, id->name) < 0)) { - BLI_insertlinkbefore(lb, id_sorting_hint, id); - return; - } - } - - void *item_array[ID_SORT_STEP_SIZE]; - int item_array_index; - - /* Step one: We go backward over a whole chunk of items at once, until we find a limit item - * that is lower than, or equal (should never happen!) to the one we want to insert. */ - /* NOTE: We start from the end, because in typical 'heavy' case (insertion of lots of IDs at - * once using the same base name), newly inserted items will generally be towards the end - * (higher extension numbers). */ - bool is_in_library = false; - item_array_index = ID_SORT_STEP_SIZE - 1; - for (idtest = lb->last; idtest != NULL; idtest = idtest->prev) { - if (is_in_library) { - if (idtest->lib != id->lib) { - /* We got out of expected library 'range' in the list, so we are done here and can move on - * to the next step. */ - break; - } - } - else if (idtest->lib == id->lib) { - /* We are entering the expected library 'range' of IDs in the list. */ - is_in_library = true; - } - - if (!is_in_library) { - continue; - } - - item_array[item_array_index] = idtest; - if (item_array_index == 0) { - if (BLI_strcasecmp(idtest->name, id->name) <= 0) { - break; - } - item_array_index = ID_SORT_STEP_SIZE; - } - item_array_index--; - } - - /* Step two: we go forward in the selected chunk of items and check all of them, as we know - * that our target is in there. */ - - /* If we reached start of the list, current item_array_index is off-by-one. - * Otherwise, we already know that it points to an item lower-or-equal-than the one we want to - * insert, no need to redo the check for that one. - * So we can increment that index in any case. */ - for (item_array_index++; item_array_index < ID_SORT_STEP_SIZE; item_array_index++) { - idtest = item_array[item_array_index]; - if (BLI_strcasecmp(idtest->name, id->name) > 0) { - BLI_insertlinkbefore(lb, idtest, id); - break; - } - } - if (item_array_index == ID_SORT_STEP_SIZE) { - if (idtest == NULL) { - /* If idtest is NULL here, it means that in the first loop, the last comparison was - * performed exactly on the first item of the list, and that it also failed. And that the - * second loop was not walked at all. - * - * In other words, if `id` is local, all the items in the list are greater than the inserted - * one, so we can put it at the start of the list. Or, if `id` is linked, it is the first one - * of its library, and we can put it at the very end of the list. */ - if (ID_IS_LINKED(id)) { - BLI_addtail(lb, id); - } - else { - BLI_addhead(lb, id); - } - } - else { - BLI_insertlinkafter(lb, idtest, id); - } - } - -# undef ID_SORT_STEP_SIZE -} -#endif }
\ No newline at end of file |