diff options
Diffstat (limited to 'src/nvim/eval')
-rw-r--r-- | src/nvim/eval/typval.c | 42 | ||||
-rw-r--r-- | src/nvim/eval/typval.h | 22 |
2 files changed, 50 insertions, 14 deletions
diff --git a/src/nvim/eval/typval.c b/src/nvim/eval/typval.c index fba9e9c843..21bb84a945 100644 --- a/src/nvim/eval/typval.c +++ b/src/nvim/eval/typval.c @@ -3,6 +3,7 @@ #include <stdio.h> #include <stddef.h> +#include <stdlib.h> #include <string.h> #include <assert.h> #include <stdbool.h> @@ -757,6 +758,47 @@ void tv_list_reverse(list_T *const l) l->lv_idx = l->lv_len - l->lv_idx - 1; } +// FIXME Add unit tests for tv_list_item_sort(). + +/// Sort list using libc qsort +/// +/// @param[in,out] l List to sort, will be sorted in-place. +/// @param ptrs Preallocated array of items to sort, must have at least +/// tv_list_len(l) entries. Should not be initialized. +/// @param[in] item_compare_func Function used to compare list items. +/// @param errp Location where information about whether error occurred is +/// saved by item_compare_func. If boolean there appears to be +/// true list will not be modified. Must be initialized to false +/// by the caller. +void tv_list_item_sort(list_T *const l, ListSortItem *const ptrs, + const ListSorter item_compare_func, + bool *errp) + FUNC_ATTR_NONNULL_ARG(3, 4) +{ + const int len = tv_list_len(l); + if (len <= 1) { + return; + } + int i = 0; + TV_LIST_ITER(l, li, { + ptrs[i].item = li; + ptrs[i].idx = i; + i++; + }); + // Sort the array with item pointers. + qsort(ptrs, (size_t)len, sizeof(ListSortItem), item_compare_func); + if (!(*errp)) { + // Clear the list and append the items in the sorted order. + l->lv_first = NULL; + l->lv_last = NULL; + l->lv_idx_item = NULL; + l->lv_len = 0; + for (i = 0; i < len; i++) { + tv_list_append(l, ptrs[i].item); + } + } +} + //{{{2 Indexing/searching /// Locate item with a given index in a list and return it diff --git a/src/nvim/eval/typval.h b/src/nvim/eval/typval.h index 2bce7bd6b2..c9a9a3e7e8 100644 --- a/src/nvim/eval/typval.h +++ b/src/nvim/eval/typval.h @@ -296,6 +296,14 @@ typedef struct list_stack_S { struct list_stack_S *prev; } list_stack_T; +/// Structure representing one list item, used for sort array. +typedef struct { + listitem_T *item; ///< Sorted list item. + int idx; ///< Sorted list item index. +} ListSortItem; + +typedef int (*ListSorter)(const void *, const void *); + // In a hashtab item "hi_key" points to "di_key" in a dictitem. // This avoids adding a pointer to the hashtab item. @@ -403,20 +411,6 @@ static inline list_T *tv_list_latest_copy(const list_T *const l) return l->lv_copylist; } -/// Clear the list without freeing anything at all -/// -/// For use in sort() which saves items to a separate array and readds them back -/// after sorting via a number of tv_list_append() calls. -/// -/// @param[out] l List to clear. -static inline void tv_list_clear(list_T *const l) -{ - l->lv_first = NULL; - l->lv_last = NULL; - l->lv_idx_item = NULL; - l->lv_len = 0; -} - static inline int tv_list_uidx(const list_T *const l, int n) REAL_FATTR_PURE REAL_FATTR_WARN_UNUSED_RESULT; |