Copying void-pointer element into void-pointer array causes multiple copies of element in array

Question

I'm trying to code a TreeSort function in C89 for practice with a qsort parameters i.e. (void* base, size_t num, size_t size, int (*compare)(const void*, const void*)). I've implemented sort function, BST and I just can't do one thing: move data from BST to original array base.

I have this kind of tree node:

struct TreeNode {
    void* val;
    struct TreeNode* left;
    struct TreeNode* right;
};

This tree insert function:

struct TreeNode* Insert(struct TreeNode* root, void* val,
                        int (*compare)(const void*, const void*)) {
    if (root == 0) {
        root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        root->val = val;
        root->left = 0;
        root->right = 0;
        return root;
    }

    if ((*compare) ((void*) val, (void*) root->val) <= 0) {
        root->left = Insert(root->left, val, compare);
    } else if ((*compare) ((void*) val, (void*) root->val) > 0) {
        root->right = Insert(root->right, val, compare);
    }

    return root;
}

This sort function:

int16_t CEcoLab1_TreeSort(/* in */ void* base,
                          /* in */ size_t num,
                          /* in */ size_t size,
                          /* in */ int (*compare)(const void*, const void*)) {
    struct TreeNode* bst = 0;
    int ptr = 0;
    int i = 0;

    if (me == 0 || base == 0 || compare == 0) {
        return -1;
    }

    for (i = 0; i < num; ++i) {
        bst = Insert(bst, (char_t*) base + (size * i), compare);
    }

    Write_Inorder(bst, base, num, size, &ptr);

    Destroy(bst);

    return 0;
}

And trying to write data in base array like this. ptr points to current index in which we have to write number.

void Write_Inorder(struct TreeNode* root,
                   void* target,
                   size_t num,
                   size_t size,
                   int* ptr) {
    if (root != 0) {
        Write_Inorder(root->left, target, num, size, ptr);

        memcpy((char_t*) target + (size * (*ptr)++), root->val, size);

        Write_Inorder(root->right, target, num, size, ptr);
    }
}

And this causes behaviour like this.

I have no idea why it happens, but it is probably connected with ptr increment, because when index is hardcoded all problems are gone. BST is also works correctly and I even can print numbers from it with printf("%d ", *(int32_t*) root->val);

Hope someone read this post and will help... Thanks in advance.

Reprex is here (compiled in VS 2022)

Answer 1

Rather than

// weak
if ((*compare) ((void*) val, (void*) root->val) <= 0) {
    root->left = Insert(root->left, val, compare);
} else if ((*compare) ((void*) val, (void*) root->val) > 0) {
    root->right = Insert(root->right, val, compare);
}

Simplify and detect equality that BST disallow two nodes having the same value

// replacement
int cmp = compare(val, root->val);
if (cmp < 0) {
    root->left = Insert(root->left, val, compare);
} else if (cmp > 0) {
    root->right = Insert(root->right, val, compare);
} else {
    TBD code;
}