1/*
2 * Copyright 2013-2015 Samy Al Bahra
3 * Copyright 2013-2014 AppNexus, Inc.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27
28#include <ck_array.h>
29#include <ck_cc.h>
30#include <ck_pr.h>
31#include <ck_stdbool.h>
32#include <ck_string.h>
33
34static struct _ck_array *
35ck_array_create(struct ck_malloc *allocator, unsigned int length)
36{
37	struct _ck_array *active;
38
39	active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length);
40	if (active == NULL)
41		return NULL;
42
43	active->n_committed = 0;
44	active->length = length;
45
46	return active;
47}
48
49bool
50ck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length)
51{
52	struct _ck_array *active;
53
54	(void)mode;
55
56	if (allocator->realloc == NULL ||
57	    allocator->malloc == NULL ||
58	    allocator->free == NULL ||
59	    length == 0)
60		return false;
61
62	active = ck_array_create(allocator, length);
63	if (active == NULL)
64		return false;
65
66	array->n_entries = 0;
67	array->allocator = allocator;
68	array->active = active;
69	array->transaction = NULL;
70	return true;
71}
72
73bool
74ck_array_put(struct ck_array *array, void *value)
75{
76	struct _ck_array *target;
77	unsigned int size;
78
79	/*
80	 * If no transaction copy has been necessary, attempt to do in-place
81	 * modification of the array.
82	 */
83	if (array->transaction == NULL) {
84		target = array->active;
85
86		if (array->n_entries == target->length) {
87			size = target->length << 1;
88
89			target = array->allocator->realloc(target,
90			    sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
91			    sizeof(struct _ck_array) + sizeof(void *) * size,
92			    true);
93
94			if (target == NULL)
95				return false;
96
97			ck_pr_store_uint(&target->length, size);
98
99			/* Serialize with respect to contents. */
100			ck_pr_fence_store();
101			ck_pr_store_ptr(&array->active, target);
102		}
103
104		target->values[array->n_entries++] = value;
105		return true;
106	}
107
108	target = array->transaction;
109	if (array->n_entries == target->length) {
110		size = target->length << 1;
111
112		target = array->allocator->realloc(target,
113		    sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
114		    sizeof(struct _ck_array) + sizeof(void *) * size,
115		    true);
116
117		if (target == NULL)
118			return false;
119
120		target->length = size;
121		array->transaction = target;
122	}
123
124	target->values[array->n_entries++] = value;
125	return false;
126}
127
128int
129ck_array_put_unique(struct ck_array *array, void *value)
130{
131	unsigned int i, limit;
132	void **v;
133
134	limit = array->n_entries;
135	if (array->transaction != NULL) {
136		v = array->transaction->values;
137	} else {
138		v = array->active->values;
139	}
140
141	for (i = 0; i < limit; i++) {
142		if (v[i] == value)
143			return 1;
144	}
145
146	return -!ck_array_put(array, value);
147}
148
149bool
150ck_array_remove(struct ck_array *array, void *value)
151{
152	struct _ck_array *target;
153	unsigned int i;
154
155	if (array->transaction != NULL) {
156		target = array->transaction;
157
158		for (i = 0; i < array->n_entries; i++) {
159			if (target->values[i] == value) {
160				target->values[i] = target->values[--array->n_entries];
161				return true;
162			}
163		}
164
165		return false;
166	}
167
168	target = array->active;
169
170	for (i = 0; i < array->n_entries; i++) {
171		if (target->values[i] == value)
172			break;
173	}
174
175	if (i == array->n_entries)
176		return false;
177
178	/* If there are pending additions, immediately eliminate the operation. */
179	if (target->n_committed != array->n_entries) {
180		ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]);
181		return true;
182	}
183
184	/*
185	 * The assumption is that these allocations are small to begin with.
186	 * If there is no immediate opportunity for transaction, allocate a
187	 * transactional array which will be applied upon commit time.
188	 */
189	target = ck_array_create(array->allocator, array->n_entries);
190	if (target == NULL)
191		return false;
192
193	memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries);
194	target->length = array->n_entries;
195	target->n_committed = array->n_entries;
196	target->values[i] = target->values[--array->n_entries];
197
198	array->transaction = target;
199	return true;
200}
201
202bool
203ck_array_commit(ck_array_t *array)
204{
205	struct _ck_array *m = array->transaction;
206
207	if (m != NULL) {
208		struct _ck_array *p;
209
210		m->n_committed = array->n_entries;
211		ck_pr_fence_store();
212		p = array->active;
213		ck_pr_store_ptr(&array->active, m);
214		array->allocator->free(p, sizeof(struct _ck_array) +
215		    p->length * sizeof(void *), true);
216		array->transaction = NULL;
217
218		return true;
219	}
220
221	ck_pr_fence_store();
222	ck_pr_store_uint(&array->active->n_committed, array->n_entries);
223	return true;
224}
225
226void
227ck_array_deinit(struct ck_array *array, bool defer)
228{
229
230	array->allocator->free(array->active,
231	    sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer);
232
233	if (array->transaction != NULL) {
234		array->allocator->free(array->transaction,
235		    sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer);
236	}
237
238	array->transaction = array->active = NULL;
239	return;
240}
241