diff options
author | Campbell Barton <ideasman42@gmail.com> | 2018-04-03 19:07:51 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2018-04-03 19:07:51 +0300 |
commit | ab695c32974fde8720c04dff47d240b7fa0f8151 (patch) | |
tree | 849712d66dd0d5907d1bbc0b302bc11fa613e087 /source/blender/blenkernel/intern/undo_system.c | |
parent | 1f0f234b07dda752492b8ebdafd5711b32e07df0 (diff) |
Undo: make id-map use binary search to keep sorted
Diffstat (limited to 'source/blender/blenkernel/intern/undo_system.c')
-rw-r--r-- | source/blender/blenkernel/intern/undo_system.c | 14 |
1 files changed, 9 insertions, 5 deletions
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) |