xref: /lighttpd1.4/src/array.c (revision be121a63)

#include "array.h"
#include "buffer.h"

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#include <errno.h>
#include <assert.h>

array *array_init(void) {
	array *a;

	a = calloc(1, sizeof(*a));
	force_assert(a);

	a->next_power_of_2 = 1;

	return a;
}

array *array_init_array(array *src) {
	size_t i;
	array *a = array_init();

	if (0 == src->size) return a;

	a->used = src->used;
	a->size = src->size;
	a->next_power_of_2 = src->next_power_of_2;
	a->unique_ndx = src->unique_ndx;

	a->data = malloc(sizeof(*src->data) * src->size);
	force_assert(NULL != a->data);
	for (i = 0; i < src->size; i++) {
		if (src->data[i]) a->data[i] = src->data[i]->copy(src->data[i]);
		else a->data[i] = NULL;
	}

	a->sorted = malloc(sizeof(*src->sorted) * src->size);
	force_assert(NULL != a->sorted);
	memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size);
	return a;
}

void array_free(array *a) {
	size_t i;
	if (!a) return;

	if (!a->is_weakref) {
		for (i = 0; i < a->size; i++) {
			if (a->data[i]) a->data[i]->free(a->data[i]);
		}
	}

	if (a->data) free(a->data);
	if (a->sorted) free(a->sorted);

	free(a);
}

void array_reset(array *a) {
	size_t i;
	if (!a) return;

	if (!a->is_weakref) {
		for (i = 0; i < a->used; i++) {
			a->data[i]->reset(a->data[i]);
		}
	}

	a->used = 0;
	a->unique_ndx = 0;
}

data_unset *array_pop(array *a) {
	data_unset *du;

	force_assert(a->used != 0);

	a->used --;
	du = a->data[a->used];
	force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */
	a->data[a->used] = NULL;

	return du;
}

static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) {
	int ndx = -1;
	int i, pos = 0;

	if (key == NULL) return -1;

	/* try to find the string */
	for (i = pos = a->next_power_of_2 / 2; ; i >>= 1) {
		int cmp;

		if (pos < 0) {
			pos += i;
		} else if (pos >= (int)a->used) {
			pos -= i;
		} else {
			cmp = buffer_caseless_compare(key, keylen, CONST_BUF_LEN(a->data[a->sorted[pos]]->key));

			if (cmp == 0) {
				/* found */
				ndx = a->sorted[pos];
				break;
			} else if (cmp < 0) {
				pos -= i;
			} else {
				pos += i;
			}
		}
		if (i == 0) break;
	}

	if (rndx) *rndx = pos;

	return ndx;
}

data_unset *array_get_element(array *a, const char *key) {
	int ndx;

	if (-1 != (ndx = array_get_index(a, key, strlen(key), NULL))) {
		/* found, leave here */

		return a->data[ndx];
	}

	return NULL;
}

data_unset *array_get_unused_element(array *a, data_type_t t) {
	data_unset *ds = NULL;
	unsigned int i;

	for (i = a->used; i < a->size; i++) {
		if (a->data[i] && a->data[i]->type == t) {
			ds = a->data[i];

			/* make empty slot at a->used for next insert */
			a->data[i] = a->data[a->used];
			a->data[a->used] = NULL;

			return ds;
		}
	}

	return NULL;
}

void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
	data_string *ds_dst;

	if (NULL != (ds_dst = (data_string *)array_get_element(hdrs, key))) {
		buffer_copy_string_len(ds_dst->value, value, val_len);
		return;
	}

	if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
		ds_dst = data_string_init();
	}

	buffer_copy_string_len(ds_dst->key, key, key_len);
	buffer_copy_string_len(ds_dst->value, value, val_len);
	array_insert_unique(hdrs, (data_unset *)ds_dst);
}

/* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */
static data_unset **array_find_or_insert(array *a, data_unset *entry) {
	int ndx = -1;
	int pos = 0;
	size_t j;

	/* generate unique index if neccesary */
	if (buffer_is_empty(entry->key) || entry->is_index_key) {
		buffer_copy_int(entry->key, a->unique_ndx++);
		entry->is_index_key = 1;
		force_assert(0 != a->unique_ndx); /* must not wrap or we'll get problems */
	}

	/* try to find the entry */
	if (-1 != (ndx = array_get_index(a, CONST_BUF_LEN(entry->key), &pos))) {
		/* found collision, return it */
		return &a->data[ndx];
	}

	/* insert */

	/* there is no good error handling for hitting this limit
	 * (we can't handle more then INT_MAX entries: see array_get_index())
	 */
	force_assert(a->used + 1 <= INT_MAX);

	if (a->size == 0) {
		a->size   = 16;
		a->data   = malloc(sizeof(*a->data)     * a->size);
		a->sorted = malloc(sizeof(*a->sorted)   * a->size);
		force_assert(a->data);
		force_assert(a->sorted);
		for (j = a->used; j < a->size; j++) a->data[j] = NULL;
	} else if (a->size == a->used) {
		a->size  += 16;
		a->data   = realloc(a->data,   sizeof(*a->data)   * a->size);
		a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
		force_assert(a->data);
		force_assert(a->sorted);
		for (j = a->used; j < a->size; j++) a->data[j] = NULL;
	}

	ndx = (int) a->used;

	/* make sure there is nothing here */
	if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]);

	a->data[a->used++] = entry;

	if (pos != ndx &&
	    ((pos < 0) ||
	     buffer_caseless_compare(CONST_BUF_LEN(entry->key), CONST_BUF_LEN(a->data[a->sorted[pos]]->key)) > 0)) {
		pos++;
	}

	/* move everything one step to the right */
	if (pos != ndx) {
		memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
	}

	/* insert */
	a->sorted[pos] = ndx;

	if (a->next_power_of_2 == (size_t)ndx) a->next_power_of_2 <<= 1;

	return NULL;
}

/* replace or insert data (free existing entry) */
void array_replace(array *a, data_unset *entry) {
	data_unset **old;

	force_assert(NULL != entry);
	if (NULL != (old = array_find_or_insert(a, entry))) {
		force_assert(*old != entry);
		(*old)->free(*old);
		*old = entry;
	}
}

void array_insert_unique(array *a, data_unset *entry) {
	data_unset **old;

	force_assert(NULL != entry);
	if (NULL != (old = array_find_or_insert(a, entry))) {
		force_assert((*old)->type == entry->type);
		entry->insert_dup(*old, entry);
	}
}

void array_print_indent(int depth) {
	int i;
	for (i = 0; i < depth; i ++) {
		fprintf(stdout, "    ");
	}
}

size_t array_get_max_key_length(array *a) {
	size_t maxlen, i;

	maxlen = 0;
	for (i = 0; i < a->used; i ++) {
		data_unset *du = a->data[i];
		size_t len = strlen(du->key->ptr);

		if (len > maxlen) {
			maxlen = len;
		}
	}
	return maxlen;
}

int array_print(array *a, int depth) {
	size_t i;
	size_t maxlen;
	int oneline = 1;

	if (a->used > 5) {
		oneline = 0;
	}
	for (i = 0; i < a->used && oneline; i++) {
		data_unset *du = a->data[i];
		if (!du->is_index_key) {
			oneline = 0;
			break;
		}
		switch (du->type) {
			case TYPE_INTEGER:
			case TYPE_STRING:
			case TYPE_COUNT:
				break;
			default:
				oneline = 0;
				break;
		}
	}
	if (oneline) {
		fprintf(stdout, "(");
		for (i = 0; i < a->used; i++) {
			data_unset *du = a->data[i];
			if (i != 0) {
				fprintf(stdout, ", ");
			}
			du->print(du, depth + 1);
		}
		fprintf(stdout, ")");
		return 0;
	}

	maxlen = array_get_max_key_length(a);
	fprintf(stdout, "(\n");
	for (i = 0; i < a->used; i++) {
		data_unset *du = a->data[i];
		array_print_indent(depth + 1);
		if (!du->is_index_key) {
			int j;

			if (i && (i % 5) == 0) {
				fprintf(stdout, "# %zd\n", i);
				array_print_indent(depth + 1);
			}
			fprintf(stdout, "\"%s\"", du->key->ptr);
			for (j = maxlen - strlen(du->key->ptr); j > 0; j --) {
				fprintf(stdout, " ");
			}
			fprintf(stdout, " => ");
		}
		du->print(du, depth + 1);
		fprintf(stdout, ",\n");
	}
	if (!(i && (i - 1 % 5) == 0)) {
		array_print_indent(depth + 1);
		fprintf(stdout, "# %zd\n", i);
	}
	array_print_indent(depth);
	fprintf(stdout, ")");

	return 0;
}

#ifdef DEBUG_ARRAY
int main (int argc, char **argv) {
	array *a;
	data_string *ds;
	data_count *dc;

	UNUSED(argc);
	UNUSED(argv);

	a = array_init();

	ds = data_string_init();
	buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
	buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));

	array_insert_unique(a, (data_unset *)ds);

	ds = data_string_init();
	buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
	buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman"));

	array_insert_unique(a, (data_unset *)ds);

	ds = data_string_init();
	buffer_copy_string_len(ds->key, CONST_STR_LEN("123"));
	buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));

	array_insert_unique(a, (data_unset *)ds);

	dc = data_count_init();
	buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));

	array_insert_unique(a, (data_unset *)dc);

	dc = data_count_init();
	buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));

	array_insert_unique(a, (data_unset *)dc);

	array_print(a, 0);

	array_free(a);

	fprintf(stderr, "%d\n",
	       buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type")));

	return 0;
}
#endif