Revert "Fix T78296: Performance - Use Binary Search for MDeformWeight"

This reverts commit 39b525e0f07fa25dcda54226ade789959b642dec and
3121015dceb1d269d79690c8f15c8e1406c9b09f as tests are failing.

1 files changed, 16 insertions, 91 deletions

diff --git a/source/blender/blenkernel/intern/deform.c b/source/blender/blenkernel/intern/deform.c
index 7e924db5ae4..b97935d57f2 100644
--- a/source/blender/blenkernel/intern/deform.c
+++ b/source/blender/blenkernel/intern/deform.c
@@ -216,47 +216,6 @@ void BKE_defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, cons
   }
 }
 
-/* -------------------------------------------------------------------- */
-/** \name Deform Weights - Sorting
- *
- * \{ */
-
-/* Reorder the weights so they are sorted. It is required that all `MDeformVert` weights are sorted
- * so we can use binary search.
- */
-static int defweight_cmp(const void *a, const void *b)
-{
-  const MDeformWeight *dw1 = a;
-  const MDeformWeight *dw2 = b;
-  if (dw1->def_nr < dw2->def_nr) {
-    return -1;
-  }
-  else if (dw1->def_nr > dw2->def_nr) {
-    return 1;
-  }
-  else {
-    return 0;
-  }
-}
-
-static void defvert_sort_weights(struct MDeformVert *dvert)
-{
-  if (dvert->dw) {
-    qsort(dvert->dw, dvert->totweight, sizeof(MDeformWeight), defweight_cmp);
-  }
-}
-
-void BKE_defvert_array_sort_weights(struct MDeformVert *dvert, const int num_verts)
-{
-  if (!dvert) {
-    return;
-  }
-  for (int i = 0; i < num_verts; i++) {
-    defvert_sort_weights(&dvert[i]);
-  }
-}
-/* \} */
-
 /**
  * be sure all flip_map values are valid
  */
@@ -301,7 +260,6 @@ void BKE_defvert_remap(MDeformVert *dvert, int *map, const int map_len)
       dw->def_nr = map[dw->def_nr];
     }
   }
-  defvert_sort_weights(dvert);
 }
 
 /**
@@ -501,7 +459,6 @@ void BKE_defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_ma
       }
     }
   }
-  defvert_sort_weights(dvert);
 }
 
 void BKE_defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
@@ -708,40 +665,23 @@ float BKE_defvert_array_find_weight_safe(const struct MDeformVert *dvert,
   return BKE_defvert_find_weight(dvert + index, defgroup);
 }
 
-static int defvert_index_get(const MDeformVert *dvert, const int defgroup)
-{
-  int low = 0;
-  int high = dvert->totweight - 1;
-  int mid;
-  while (low < high) {
-    mid = (low + high) / 2;
-    MDeformWeight *dweight = &dvert->dw[mid];
-    const unsigned int dweight_def_nr = dweight->def_nr;
-    if (dweight_def_nr == defgroup) {
-      return mid;
-    }
-    if (dweight_def_nr < defgroup) {
-      low = mid + 1;
-    }
-    else {
-      high = mid - 1;
-    }
-  }
-  return -1;
-}
-
 MDeformWeight *BKE_defvert_find_index(const MDeformVert *dvert, const int defgroup)
 {
-  BLI_assert(dvert);
-  BLI_assert(defgroup >= 0);
+  if (dvert && defgroup >= 0) {
+    MDeformWeight *dw = dvert->dw;
+    unsigned int i;
 
-  int index = defvert_index_get(dvert, defgroup);
-  if (index == -1) {
-    return NULL;
+    for (i = dvert->totweight; i != 0; i--, dw++) {
+      if (dw->def_nr == defgroup) {
+        return dw;
+      }
+    }
   }
   else {
-    return &dvert->dw[index];
+    BLI_assert(0);
   }
+
+  return NULL;
 }
 
 /**
@@ -766,18 +706,17 @@ MDeformWeight *BKE_defvert_ensure_index(MDeformVert *dvert, const int defgroup)
 
   dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
   if (dvert->dw) {
-    memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+    memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
     MEM_freeN(dvert->dw);
   }
   dvert->dw = dw_new;
+  dw_new += dvert->totweight;
   dw_new->weight = 0.0f;
   dw_new->def_nr = defgroup;
   /* Group index */
 
   dvert->totweight++;
 
-  defvert_sort_weights(dvert);
-
   return dw_new;
 }
 
@@ -801,15 +740,14 @@ void BKE_defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float
   dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1),
                        "defvert_add_to group, new deformWeight");
   if (dvert->dw) {
-    memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+    memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
     MEM_freeN(dvert->dw);
   }
   dvert->dw = dw_new;
+  dw_new += dvert->totweight;
   dw_new->weight = weight;
   dw_new->def_nr = defgroup;
   dvert->totweight++;
-
-  defvert_sort_weights(dvert);
 }
 
 /**
@@ -835,7 +773,7 @@ void BKE_defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
       BLI_assert(dvert->dw != NULL);
 
       if (i != dvert->totweight) {
-        memmove(&dvert->dw[i], &dvert->dw[i + 1], sizeof(MDeformWeight) * dvert->totweight - i);
+        dvert->dw[i] = dvert->dw[dvert->totweight];
       }
 
       dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
@@ -1587,17 +1525,4 @@ void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight)
   }
 }
 
-#ifndef NDEBUG
-bool BKE_defvert_is_sorted_for_assert(const MDeformVert *dv)
-{
-  const MDeformWeight *dw = dv->dw;
-  for (int i = 1; i < dv->totweight; i++) {
-    if (dw[i - 1].def_nr > dw[i].def_nr) {
-      return false;
-    }
-  }
-  return true;
-}
-#endif
-
 /** \} */