[Bf-blender-cvs] [ab695c32974] master: Undo: make id-map use binary search to keep sorted

[Campbell Barton]

Commit: ab695c32974fde8720c04dff47d240b7fa0f8151
Author: Campbell Barton
Date:   Tue Apr 3 18:07:51 2018 +0200
Branches: master
https://developer.blender.org/rBab695c32974fde8720c04dff47d240b7fa0f8151

Undo: make id-map use binary search to keep sorted

===================================================================

M	source/blender/blenkernel/intern/undo_system.c

===================================================================

diff --git a/source/blender/blenkernel/intern/undo_system.c b/source/blender/blenkernel/intern/undo_system.c
index 17d01bf1fcb..2de7dd96867 100644
--- a/source/blender/blenkernel/intern/undo_system.c
+++ b/source/blender/blenkernel/intern/undo_system.c
@@ -720,6 +720,9 @@ static bool undosys_ID_map_lookup_index(const UndoIDPtrMap *map, const void *key
 			max = mid - 1;
 		}
 	}
+	if (r_index) {
+		*r_index = min;
+	}
 	return false;
 }
 
@@ -772,12 +775,13 @@ void BKE_undosys_ID_map_add(UndoIDPtrMap *map, ID *id)
 #endif
 	map->refs[len_src].ptr = id;
 
-	map->pmap[len_src].ptr = id;
-	map->pmap[len_src].index = len_src;
-	map->len = len_dst;
+	if (len_src != 0 && index != len_src) {
+		memmove(&map->pmap[index + 1], &map->pmap[index], sizeof(*map->pmap) * (len_src - index));
+	}
+	map->pmap[index].ptr = id;
+	map->pmap[index].index = len_src;
 
-	/* TODO(campbell): use binary search result and memmove instread of full-sort. */
-	qsort(map->pmap, map->len, sizeof(*map->pmap), BLI_sortutil_cmp_ptr);
+	map->len = len_dst;
 }
 
 ID *BKE_undosys_ID_map_lookup(const UndoIDPtrMap *map, const ID *id_src)