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