summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorGravatar Nikias Bassen2023-02-05 13:42:23 +0100
committerGravatar Nikias Bassen2023-02-05 13:42:23 +0100
commit52826a6c229ed3e353d4dae711a6c52a96d99764 (patch)
treebbff0a7bbea4e62f7646174ee245e5950b4b0d30 /src
parent706771e357570d1bee268fc7c2233506da967bcd (diff)
downloadlibplist-52826a6c229ed3e353d4dae711a6c52a96d99764.tar.gz
libplist-52826a6c229ed3e353d4dae711a6c52a96d99764.tar.bz2
Fix plist_sort() by swapping the nodes in the tree instead of their data
The problem was that we swapped potential child node data between nodes, but their parents would not be updated that way, leading to double frees or segmentation faults when freeing a plist. This commit instead fixes this by swapping the actual nodes in the tree.
Diffstat (limited to 'src')
-rw-r--r--src/plist.c62
1 files changed, 33 insertions, 29 deletions
diff --git a/src/plist.c b/src/plist.c
index 72c3e98..0fcd926 100644
--- a/src/plist.c
+++ b/src/plist.c
@@ -43,6 +43,7 @@
#endif
#include <node.h>
+#include <node_list.h>
#include <hashtable.h>
#include <ptrarray.h>
@@ -1515,44 +1516,47 @@ PLIST_API void plist_sort(plist_t plist)
plist_sort((plist_t)ch);
}
#define KEY_DATA(x) (x->data)
- #define VAL_DATA(x) (x->next->data)
- #define VAL_COUNT(x) (x->next->count)
- #define VAL_CHDN(x) (x->next->children)
#define NEXT_KEY(x) (x->next->next)
- #define NEXT_VAL(x) (NEXT_KEY(x)->next)
- #define NEXT_KEY_DATA(x) (NEXT_KEY(x)->data)
- #define NEXT_VAL_DATA(x) (NEXT_VAL(x)->data)
- #define NEXT_VAL_CHDN(x) (NEXT_VAL(x)->children)
- #define NEXT_VAL_COUNT(x) (NEXT_VAL(x)->count)
#define KEY_STRVAL(x) ((plist_data_t)(KEY_DATA(x)))->strval
- #define NEXT_KEY_STRVAL(x) ((plist_data_t)(NEXT_KEY_DATA(x)))->strval
int swapped = 0;
do {
swapped = 0;
node_t *lptr = NULL;
- node_t *ptr_key = node_first_child((node_t*)plist);
- while (NEXT_KEY(ptr_key) != lptr) {
- if (strcmp(KEY_STRVAL(ptr_key), NEXT_KEY_STRVAL(ptr_key)) > 0) {
- // backup old values
- void* key_data_tmp = KEY_DATA(ptr_key);
- void* val_data_tmp = VAL_DATA(ptr_key);
- struct node_list_t *val_chdn_tmp = VAL_CHDN(ptr_key);
- unsigned int val_count_tmp = VAL_COUNT(ptr_key);
- // replace current with next
- KEY_DATA(ptr_key) = NEXT_KEY_DATA(ptr_key);
- VAL_DATA(ptr_key) = NEXT_VAL_DATA(ptr_key);
- VAL_CHDN(ptr_key) = NEXT_VAL_CHDN(ptr_key);
- VAL_COUNT(ptr_key) = NEXT_VAL_COUNT(ptr_key);
- // replace next with old
- NEXT_KEY_DATA(ptr_key) = key_data_tmp;
- NEXT_VAL_DATA(ptr_key) = val_data_tmp;
- NEXT_VAL_CHDN(ptr_key) = val_chdn_tmp;
- NEXT_VAL_COUNT(ptr_key) = val_count_tmp;
+ node_t *cur_key = node_first_child((node_t*)plist);
+
+ while (NEXT_KEY(cur_key) != lptr) {
+ node_t *next_key = NEXT_KEY(cur_key);
+ if (strcmp(KEY_STRVAL(cur_key), KEY_STRVAL(next_key)) > 0) {
+ node_t *cur_val = cur_key->next;
+ node_t *next_val = next_key->next;
+ // we need to swap 2 consecutive nodes with the 2 after them
+ // a -> b -> [c] -> [d] -> [e] -> [f] -> g -> h
+ // cur next
+ // swapped:
+ // a -> b -> [e] -> [f] -> [c] -> [d] -> g -> h
+ // next cur
+ node_t *tmp_prev = cur_key->prev;
+ node_t *tmp_next = next_val->next;
+ cur_key->prev = next_val;
+ cur_val->next = tmp_next;
+ next_val->next = cur_key;
+ next_key->prev = tmp_prev;
+ if (tmp_prev) {
+ tmp_prev->next = next_key;
+ } else {
+ ((node_t*)plist)->children->begin = next_key;
+ }
+ if (tmp_next) {
+ tmp_next->prev = cur_val;
+ } else {
+ ((node_t*)plist)->children->end = cur_val;
+ }
+ cur_key = next_key;
swapped = 1;
}
- ptr_key = NEXT_KEY(ptr_key);
+ cur_key = NEXT_KEY(cur_key);
}
- lptr = ptr_key;
+ lptr = cur_key;
} while (swapped);
}
}