[Bf-blender-cvs] [b1ef03f8ab7] temp-improve-id-sort-by-name: Use std::lower_bound.
Monique
noreply at git.blender.org
Tue Oct 4 19:56:03 CEST 2022
Commit: b1ef03f8ab7fe3a4b1bca56e4dab523ac38fa8f1
Author: Monique
Date: Mon Oct 3 22:20:02 2022 +0200
Branches: temp-improve-id-sort-by-name
https://developer.blender.org/rBb1ef03f8ab7fe3a4b1bca56e4dab523ac38fa8f1
Use std::lower_bound.
===================================================================
M source/blender/blenkernel/CMakeLists.txt
M source/blender/blenkernel/intern/lib_id.c
A source/blender/blenkernel/intern/lib_id_sort.cc
===================================================================
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 627e34be424..f55a7958a79 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -171,6 +171,7 @@ set(SRC
intern/lattice_deform.c
intern/layer.c
intern/layer_utils.c
+ intern/lib_id_sort.cc
intern/lib_id.c
intern/lib_id_delete.c
intern/lib_id_eval.c
diff --git a/source/blender/blenkernel/intern/lib_id.c b/source/blender/blenkernel/intern/lib_id.c
index 6c3e5bad430..7035fe387a2 100644
--- a/source/blender/blenkernel/intern/lib_id.c
+++ b/source/blender/blenkernel/intern/lib_id.c
@@ -1368,96 +1368,6 @@ struct ID *BKE_libblock_find_session_uuid(Main *bmain,
return NULL;
}
-void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint)
-{
- 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;
- }
- }
-
- /* Look for the last ID of the expected library.*/
- /* 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). */
- for (idtest = lb->last; (idtest != NULL) && (idtest->lib != id->lib); idtest = idtest->prev) {
- }
-
- /* idtest can be null, expected library is not found,
- * or can be on the last id of the expected library.
- *
- * If expected library not found and 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 (idtest == NULL) {
- if (ID_IS_LINKED(id)) {
- BLI_addtail(lb, id);
- }
- else {
- BLI_addhead(lb, id);
- }
- return;
- }
-
- /* In case idtest is on the last id of the expected library, walk to the first ID in
- * the list that is smaller than the newly to be inserted ID but still part of the same
- * library.*/
- for (; (idtest != lb->first) && (idtest->lib == id->lib); idtest = idtest->prev) {
- if (BLI_strcasecmp(idtest->name, id->name) < 0) {
- break;
- }
- }
-
- /* 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);
- }
-}
bool BKE_id_new_name_validate(
struct Main *bmain, ListBase *lb, ID *id, const char *tname, const bool do_linked_data)
diff --git a/source/blender/blenkernel/intern/lib_id_sort.cc b/source/blender/blenkernel/intern/lib_id_sort.cc
new file mode 100644
index 00000000000..298f8bb5248
--- /dev/null
+++ b/source/blender/blenkernel/intern/lib_id_sort.cc
@@ -0,0 +1,243 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include <algorithm>
+
+#include "BLI_listbase.h"
+#include "BLI_string.h"
+
+#include "DNA_ID.h"
+#include "DNA_listBase.h"
+
+#include "BKE_lib_id.h"
+
+extern "C" {
+
+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, nullptr, id) && id_sorting_hint->lib == id->lib) {
+ BLI_assert(BLI_findindex(lb, id_sorting_hint) >= 0);
+
+ ID *id_sorting_hint_next = static_cast<ID *>(id_sorting_hint->next);
+ if (BLI_strcasecmp(id_sorting_hint->name, id->name) < 0 &&
+ (id_sorting_hint_next == nullptr || 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 = static_cast<ID *>(id_sorting_hint->prev);
+ if (BLI_strcasecmp(id_sorting_hint->name, id->name) > 0 &&
+ (id_sorting_hint_prev == nullptr || 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;
+ }
+ }
+
+ /* Look for the last ID of the expected library.*/
+ /* 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). */
+ for (idtest = static_cast<ID *>(lb->last); (idtest != nullptr) && (idtest->lib != id->lib);
+ idtest = static_cast<ID *>(idtest->prev)) {
+ }
+
+ /* idtest can be null, expected library is not found,
+ * or can be on the last id of the expected library.
+ *
+ * If expected library not found and 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 (idtest == nullptr) {
+ if (ID_IS_LINKED(id)) {
+ BLI_addtail(lb, id);
+ }
+ else {
+ BLI_addhead(lb, id);
+ }
+ return;
+ }
+
+ /* In case idtest is on the last id of the expected library, walk to the first ID in
+ * the list that is smaller than the newly to be inserted ID but still part of the same
+ * library.*/
+ ID *item_array[ID_SORT_STEP_SIZE] = {nullptr};
+ int item_array_index = ID_SORT_STEP_SIZE - 1;
+ for (; (idtest) && (idtest->lib == id->lib); idtest = static_cast<ID *>(idtest->prev)) {
+ 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--;
+ }
+
+ ID **lower_bound = std::lower_bound(
+ &item_array[item_array_index + 1],
+ &item_array[ID_SORT_STEP_SIZE],
+ id,
+ [](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);
+ }
+ 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
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list