Untitled

/*
 * CS107 Assignment 4
 * Code by Brent Ju
 *
 * This program takes in an array and a key with generic typing
 * through void* and either returns the pointer to which the key's
 * value was found in the array, or the pointer to where the value
 * was correctly inserted into the array if it didn't already exist.
 *
 * */

#include <string.h>
#include "samples/prototypes.h"

void *binsert(const void *key, void *base, size_t *p_nelem, size_t width,
              int (*compar)(const void *, const void *)) {
    // using a void* to track where to insert my element
    void* insertion = base;
    // tracking end of array helps to calculate how many bytes to shift
    // later in memmove
    char* arr_end = (char*)base + (*p_nelem * width);
    for (size_t nremain = *p_nelem; nremain != 0; nremain >>= 1) {
        void* p = (char *)base + (nremain >> 1) * width;
        int sign = compar(key, p);
        if (sign == 0) {
            return p;
        }
        if (sign > 0) {  /* key > p: move right */
            base = (char *)p + width;
            // if this is the last search, base now holds the correct
            // insertion point for our key, update value
            insertion = base;
            nremain--;
        } else {
            // if key < p, then p is the current correct insertion position
            // if we have performed all possible binary searches.
            insertion = p;
        }     /* else move left */
    }
    // shift all elements right by one
    // pointer arithmetic using char* and subtraction gives
    // us the number of bytes to copy over
    memmove((char*)insertion + width, (char*)insertion,
            ((arr_end - (char*)insertion)));
    memcpy(insertion, key, width);
    *p_nelem += 1;
    return insertion;
}