OAuth2Lib/util/sorted_str_set.c

#include "sorted_str_set.h"

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#define SORTED_STR_SET_INITIAL_CAPACITY 8
#define SORTED_STR_SET_GROWTH_FACTOR 1.5

static ssize_t _get(const sorted_str_set* set, const char* key, int* out_res) {
	ssize_t index = 0;
	ssize_t low = 0;
	ssize_t upp = set->size - 1;
	int res = 0;

	while (low <= upp) {
		index = low + (upp-low)/2;
		
		res = strcmp(key, set->data[index].key);
		if (res == 0) {
			if (out_res) *out_res = res;
			return index;
		}

		if (res < 0) {
			upp = index - 1;
		} else {
			low = index + 1;
		}
	}

	if (res > 0) {
		++index;
	}

	return -1;
}


sorted_str_set* sorted_str_set_new(size_t element_size) {
	
	sorted_str_set* set = malloc(sizeof(sorted_str_set));
	if (!set) { return NULL; }

	struct sorted_str_set_pair* data = malloc(SORTED_STR_SET_INITIAL_CAPACITY * sizeof(struct sorted_str_set_pair));
	if (!data) { 
		free(set);
		return NULL;
	}

	*set = (sorted_str_set) {
		.element_size = element_size,
		.size = 0,
		.capacity = SORTED_STR_SET_INITIAL_CAPACITY,
		.data = data,
	};
	return set;
}

void sorted_str_set_free(sorted_str_set* set) {
	assert(set); //, "set must not be NULL.");
	for (int i = 0; i < set->size; ++i) {
		free(set->data[i].key);
		free(set->data[i].element);
	}
	free(set->data);
	free(set);
}

void* sorted_str_set_get(const sorted_str_set* set, const char* key) {
	
	assert(set); //, "set must not be null");
	assert(key); //, "key must not be null");

	if (set->size == 0) {
		return NULL;
	}

	ssize_t i = _get(set, key, NULL);

	if (i == -1) {
		return NULL;
	} else {
		return set->data[i].element;
	}
}

void* sorted_str_set_insert(sorted_str_set* set, const char* key, const void* element) {

	assert(set); //, "set must not be NULL");
	assert(key); //, "key must not be NULL");
	assert(element); //, "element must not be NULL");

	size_t index = 0;

	if (set->size != 0) {
		ssize_t low = 0;
		ssize_t upp = set->size - 1;
		int res = 0;

		while (low <= upp) {
			index = low + (upp-low)/2;
			
			res = strcmp(key, set->data[index].key);
			if (res == 0) {
				return set->data[index].element;
			}

			if (res < 0) {
				upp = index - 1;
			} else {
				low = index + 1;
			}
		}

		if (res > 0) {
			++index;
		}
	}

	if (set->size == set->capacity) {
		size_t new_cap = set->capacity * SORTED_STR_SET_GROWTH_FACTOR;
		struct sorted_str_set_pair* tmp = reallocarray(set->data, new_cap, sizeof(struct sorted_str_set_pair));
		if (!tmp) {
			return NULL;
		}

		set->data = tmp;
		set->capacity = new_cap;
	}
	
	struct sorted_str_set_pair pair = {
		.key = malloc(strlen(key) + 1),
		.element = malloc(set->element_size),
	};
	if (!pair.key || !pair.element) {
		free(pair.key);
		free(pair.element);
		return NULL;
	}
	strcpy(pair.key, key);
	memcpy(pair.element, element, set->element_size);
	
	if (set->size - index) {
		memmove(&set->data[index + 1], &set->data[index], (set->size - index) * sizeof(struct sorted_str_set_pair));
	}

	set->data[index] = pair;
	set->size++;

	return set->data[index].element;
}

void sorted_str_set_remove(sorted_str_set* set, const char* key) {

	assert(set);//, "set must not be NULL");
	assert(key);//, "key must not be NULL");
	
	ssize_t index = _get(set, key, NULL);
	if (index == -1) {
		return;
	}

	struct sorted_str_set_pair* loc = &set->data[index];

	free(loc->key);
	free(loc->element);

	set->size--;
	
	memmove(loc, loc+1, (set->size - index) * sizeof(struct sorted_str_set_pair));

}