Optimize sort id by name

2 files changed, 44 insertions, 60 deletions

diff --git a/source/blender/blenkernel/BKE_lib_id.h b/source/blender/blenkernel/BKE_lib_id.h
index aa3bdb502f8..a157c58b133 100644
--- a/source/blender/blenkernel/BKE_lib_id.h
+++ b/source/blender/blenkernel/BKE_lib_id.h
@@ -479,6 +479,8 @@ void BKE_lib_id_swap_full(struct Main *bmain, struct ID *id_a, struct ID *id_b);
 
 /**
  * Sort given \a id into given \a lb list, using case-insensitive comparison of the id names.
+ * ID's belonging to the same library are placed together in alphabetical order.
+ * Order of the libraries depends on the order in which they are added.
  *
  * \note All other IDs beside given one are assumed already properly sorted in the list.
  *
diff --git a/source/blender/blenkernel/intern/lib_id.c b/source/blender/blenkernel/intern/lib_id.c
index 158aaa961ce..6c3e5bad430 100644
--- a/source/blender/blenkernel/intern/lib_id.c
+++ b/source/blender/blenkernel/intern/lib_id.c
@@ -1370,8 +1370,6 @@ struct ID *BKE_libblock_find_session_uuid(Main *bmain,
 
 void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint)
 {
-#define ID_SORT_STEP_SIZE 512
-
   ID *idtest;
 
   /* insert alphabetically */
@@ -1402,79 +1400,63 @@ void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint)
     }
   }
 
-  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. */
+  /* 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). */
-  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;
-    }
+  for (idtest = lb->last; (idtest != NULL) && (idtest->lib != id->lib); idtest = idtest->prev) {
+  }
 
-    if (!is_in_library) {
-      continue;
+  /* 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);
     }
-
-    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;
+    else {
+      BLI_addhead(lb, id);
     }
-    item_array_index--;
+    return;
   }
 
-  /* 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);
+  /* 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;
     }
   }
-  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);
-      }
+
+  /* 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_insertlinkafter(lb, idtest, id);
+      BLI_addhead(lb, id);
     }
   }
-
-#undef ID_SORT_STEP_SIZE
+  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(