xref: /freebsd/sys/contrib/ck/src/ck_array.c (revision 4f9d94bf6491250b649f5bc931b6d93e68373005)

/*
 * Copyright 2013-2015 Samy Al Bahra
 * Copyright 2013-2014 AppNexus, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <ck_array.h>
#include <ck_cc.h>
#include <ck_pr.h>
#include <ck_stdbool.h>
#include <ck_string.h>

static struct _ck_array *
ck_array_create(struct ck_malloc *allocator, unsigned int length)
{
	struct _ck_array *active;

	active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length);
	if (active == NULL)
		return NULL;

	active->n_committed = 0;
	active->length = length;

	return active;
}

bool
ck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length)
{
	struct _ck_array *active;

	(void)mode;

	if (allocator->realloc == NULL ||
	    allocator->malloc == NULL ||
	    allocator->free == NULL ||
	    length == 0)
		return false;

	active = ck_array_create(allocator, length);
	if (active == NULL)
		return false;

	array->n_entries = 0;
	array->allocator = allocator;
	array->active = active;
	array->transaction = NULL;
	return true;
}

bool
ck_array_put(struct ck_array *array, void *value)
{
	struct _ck_array *target;
	unsigned int size;

	/*
	 * If no transaction copy has been necessary, attempt to do in-place
	 * modification of the array.
	 */
	if (array->transaction == NULL) {
		target = array->active;

		if (array->n_entries == target->length) {
			size = target->length << 1;

			target = array->allocator->realloc(target,
			    sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
			    sizeof(struct _ck_array) + sizeof(void *) * size,
			    true);

			if (target == NULL)
				return false;

			ck_pr_store_uint(&target->length, size);

			/* Serialize with respect to contents. */
			ck_pr_fence_store();
			ck_pr_store_ptr(&array->active, target);
		}

		target->values[array->n_entries++] = value;
		return true;
	}

	target = array->transaction;
	if (array->n_entries == target->length) {
		size = target->length << 1;

		target = array->allocator->realloc(target,
		    sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
		    sizeof(struct _ck_array) + sizeof(void *) * size,
		    true);

		if (target == NULL)
			return false;

		target->length = size;
		array->transaction = target;
	}

	target->values[array->n_entries++] = value;
	return false;
}

int
ck_array_put_unique(struct ck_array *array, void *value)
{
	unsigned int i, limit;
	void **v;

	limit = array->n_entries;
	if (array->transaction != NULL) {
		v = array->transaction->values;
	} else {
		v = array->active->values;
	}

	for (i = 0; i < limit; i++) {
		if (v[i] == value)
			return 1;
	}

	return -!ck_array_put(array, value);
}

bool
ck_array_remove(struct ck_array *array, void *value)
{
	struct _ck_array *target;
	unsigned int i;

	if (array->transaction != NULL) {
		target = array->transaction;

		for (i = 0; i < array->n_entries; i++) {
			if (target->values[i] == value) {
				target->values[i] = target->values[--array->n_entries];
				return true;
			}
		}

		return false;
	}

	target = array->active;

	for (i = 0; i < array->n_entries; i++) {
		if (target->values[i] == value)
			break;
	}

	if (i == array->n_entries)
		return false;

	/* If there are pending additions, immediately eliminate the operation. */
	if (target->n_committed != array->n_entries) {
		ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]);
		return true;
	}

	/*
	 * The assumption is that these allocations are small to begin with.
	 * If there is no immediate opportunity for transaction, allocate a
	 * transactional array which will be applied upon commit time.
	 */
	target = ck_array_create(array->allocator, array->n_entries);
	if (target == NULL)
		return false;

	memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries);
	target->length = array->n_entries;
	target->n_committed = array->n_entries;
	target->values[i] = target->values[--array->n_entries];

	array->transaction = target;
	return true;
}

bool
ck_array_commit(ck_array_t *array)
{
	struct _ck_array *m = array->transaction;

	if (m != NULL) {
		struct _ck_array *p;

		m->n_committed = array->n_entries;
		ck_pr_fence_store();
		p = array->active;
		ck_pr_store_ptr(&array->active, m);
		array->allocator->free(p, sizeof(struct _ck_array) +
		    p->length * sizeof(void *), true);
		array->transaction = NULL;

		return true;
	}

	ck_pr_fence_store();
	ck_pr_store_uint(&array->active->n_committed, array->n_entries);
	return true;
}

void
ck_array_deinit(struct ck_array *array, bool defer)
{

	array->allocator->free(array->active,
	    sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer);

	if (array->transaction != NULL) {
		array->allocator->free(array->transaction,
		    sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer);
	}

	array->transaction = array->active = NULL;
	return;
}