1/* $Id: dba_array.c,v 1.2 2020/06/22 19:20:40 schwarze Exp $ */
2/*
3 * Copyright (c) 2016 Ingo Schwarze <schwarze@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 *
17 * Allocation-based arrays for the mandoc database, for read-write access.
18 * The interface is defined in "dba_array.h".
19 */
20#include "config.h"
21
22#include <assert.h>
23#include <stdint.h>
24#include <stdlib.h>
25#include <string.h>
26
27#include "mandoc_aux.h"
28#include "dba_write.h"
29#include "dba_array.h"
30
31struct dba_array {
32	void	**ep;	/* Array of entries. */
33	int32_t	 *em;	/* Array of map positions. */
34	int	  flags;
35	int32_t	  ea;	/* Entries allocated. */
36	int32_t	  eu;	/* Entries used (including deleted). */
37	int32_t	  ed;	/* Entries deleted. */
38	int32_t	  ec;	/* Currently active entry. */
39	int32_t	  pos;  /* Map position of this array. */
40};
41
42
43struct dba_array *
44dba_array_new(int32_t ea, int flags)
45{
46	struct dba_array	*array;
47
48	assert(ea > 0);
49	array = mandoc_malloc(sizeof(*array));
50	array->ep = mandoc_reallocarray(NULL, ea, sizeof(*array->ep));
51	array->em = mandoc_reallocarray(NULL, ea, sizeof(*array->em));
52	array->ea = ea;
53	array->eu = 0;
54	array->ed = 0;
55	array->ec = 0;
56	array->flags = flags;
57	array->pos = 0;
58	return array;
59}
60
61void
62dba_array_free(struct dba_array *array)
63{
64	int32_t	 ie;
65
66	if (array == NULL)
67		return;
68	if (array->flags & DBA_STR)
69		for (ie = 0; ie < array->eu; ie++)
70			free(array->ep[ie]);
71	free(array->ep);
72	free(array->em);
73	free(array);
74}
75
76void
77dba_array_set(struct dba_array *array, int32_t ie, void *entry)
78{
79	assert(ie >= 0);
80	assert(ie < array->ea);
81	assert(ie <= array->eu);
82	if (ie == array->eu)
83		array->eu++;
84	if (array->flags & DBA_STR)
85		entry = mandoc_strdup(entry);
86	array->ep[ie] = entry;
87	array->em[ie] = 0;
88}
89
90void
91dba_array_add(struct dba_array *array, void *entry)
92{
93	if (array->eu == array->ea) {
94		assert(array->flags & DBA_GROW);
95		array->ep = mandoc_reallocarray(array->ep,
96		    2, sizeof(*array->ep) * array->ea);
97		array->em = mandoc_reallocarray(array->em,
98		    2, sizeof(*array->em) * array->ea);
99		array->ea *= 2;
100	}
101	dba_array_set(array, array->eu, entry);
102}
103
104void *
105dba_array_get(struct dba_array *array, int32_t ie)
106{
107	if (ie < 0 || ie >= array->eu || array->em[ie] == -1)
108		return NULL;
109	return array->ep[ie];
110}
111
112void
113dba_array_start(struct dba_array *array)
114{
115	array->ec = array->eu;
116}
117
118void *
119dba_array_next(struct dba_array *array)
120{
121	if (array->ec < array->eu)
122		array->ec++;
123	else
124		array->ec = 0;
125	while (array->ec < array->eu && array->em[array->ec] == -1)
126		array->ec++;
127	return array->ec < array->eu ? array->ep[array->ec] : NULL;
128}
129
130void
131dba_array_del(struct dba_array *array)
132{
133	if (array->ec < array->eu && array->em[array->ec] != -1) {
134		array->em[array->ec] = -1;
135		array->ed++;
136	}
137}
138
139void
140dba_array_undel(struct dba_array *array)
141{
142	memset(array->em, 0, sizeof(*array->em) * array->eu);
143}
144
145void
146dba_array_setpos(struct dba_array *array, int32_t ie, int32_t pos)
147{
148	array->em[ie] = pos;
149}
150
151int32_t
152dba_array_getpos(struct dba_array *array)
153{
154	return array->pos;
155}
156
157void
158dba_array_sort(struct dba_array *array, dba_compare_func func)
159{
160	assert(array->ed == 0);
161	qsort(array->ep, array->eu, sizeof(*array->ep), func);
162}
163
164int32_t
165dba_array_writelen(struct dba_array *array, int32_t nmemb)
166{
167	dba_int_write(array->eu - array->ed);
168	return dba_skip(nmemb, array->eu - array->ed);
169}
170
171void
172dba_array_writepos(struct dba_array *array)
173{
174	int32_t	 ie;
175
176	array->pos = dba_tell();
177	for (ie = 0; ie < array->eu; ie++)
178		if (array->em[ie] != -1)
179			dba_int_write(array->em[ie]);
180}
181
182void
183dba_array_writelst(struct dba_array *array)
184{
185	const char	*str;
186
187	dba_array_FOREACH(array, str)
188		dba_str_write(str);
189	dba_char_write('\0');
190}
191