blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 748 Projects 19 Wiki Activity

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

This commit is contained in:
Campbell Barton 2018-04-03 18:07:51 +02:00
parent 1f0f234b07
commit ab695c3297
1 changed files with 9 additions and 5 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

14
source/blender/blenkernel/intern/undo_system.c
View File

@ -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)