Merge branch 'master' into temp-ghash-experimentstemp-ghash-experiments

Note that 'store hash' feature was removed for now - to complex to maintain (conflicts)
and relatively easy to re-add if we ever really want this one day.

Conflicts:
	source/blender/blenlib/BLI_ghash.h
	source/blender/blenlib/intern/BLI_ghash.c
	source/blender/blenlib/intern/hash_mm2a.c
	source/blender/bmesh/tools/bmesh_region_match.c
	tests/gtests/blenlib/BLI_ghash_performance_test.cc
	tests/gtests/blenlib/BLI_ghash_test.cc
	tests/gtests/blenlib/CMakeLists.txt

1 files changed, 39 insertions, 34 deletions

diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c
index d52c09790f9..ebee2c7941c 100644
--- a/source/blender/blenlib/intern/listbase.c
+++ b/source/blender/blenlib/intern/listbase.c
@@ -42,6 +42,8 @@
 
 #include "BLI_listbase.h"
 
+#include "BLI_strict_flags.h"
+
 /* implementation */
 
 /**
@@ -205,53 +207,56 @@ void BLI_freelinkN(ListBase *listbase, void *vlink)
 	MEM_freeN(link);
 }
 
+/**
+ * Assigns all #Link.prev pointers from #Link.next
+ */
+static void listbase_double_from_single(Link *iter, ListBase *listbase)
+{
+	Link *prev = NULL;
+	listbase->first = iter;
+	do {
+		iter->prev = prev;
+		prev = iter;
+	} while ((iter = iter->next));
+	listbase->last = prev;
+}
+
+#define SORT_IMPL_LINKTYPE Link
+
+/* regular call */
+#define SORT_IMPL_FUNC listbase_sort_fn
+#include "list_sort_impl.h"
+#undef SORT_IMPL_FUNC
+
+/* reentrant call */
+#define SORT_IMPL_USE_THUNK
+#define SORT_IMPL_FUNC listbase_sort_fn_r
+#include "list_sort_impl.h"
+#undef SORT_IMPL_FUNC
+#undef SORT_IMPL_USE_THUNK
+
+#undef SORT_IMPL_LINKTYPE
 
 /**
  * Sorts the elements of listbase into the order defined by cmp
- * (which should return 1 iff its first arg should come after its second arg).
+ * (which should return 1 if its first arg should come after its second arg).
  * This uses insertion sort, so NOT ok for large list.
  */
 void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *))
 {
-	Link *current = NULL;
-	Link *previous = NULL;
-	Link *next = NULL;
-
 	if (listbase->first != listbase->last) {
-		for (previous = listbase->first, current = previous->next; current; current = next) {
-			next = current->next;
-			previous = current->prev;
-			
-			BLI_remlink(listbase, current);
-			
-			while (previous && cmp(previous, current) == 1) {
-				previous = previous->prev;
-			}
-			
-			BLI_insertlinkafter(listbase, previous, current);
-		}
+		Link *head = listbase->first;
+		head = listbase_sort_fn(head, cmp);
+		listbase_double_from_single(head, listbase);
 	}
 }
 
-void BLI_listbase_sort_r(ListBase *listbase, void *thunk, int (*cmp)(void *, const void *, const void *))
+void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk)
 {
-	Link *current = NULL;
-	Link *previous = NULL;
-	Link *next = NULL;
-
 	if (listbase->first != listbase->last) {
-		for (previous = listbase->first, current = previous->next; current; current = next) {
-			next = current->next;
-			previous = current->prev;
-
-			BLI_remlink(listbase, current);
-
-			while (previous && cmp(thunk, previous, current) == 1) {
-				previous = previous->prev;
-			}
-
-			BLI_insertlinkafter(listbase, previous, current);
-		}
+		Link *head = listbase->first;
+		head = listbase_sort_fn_r(head, cmp, thunk);
+		listbase_double_from_single(head, listbase);
 	}
 }