1 /* Id: dba_array.c,v 1.1 2016/07/19 21:31:55 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 <assert.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #include "mandoc_aux.h"
26 #include "dba_write.h"
27 #include "dba_array.h"
28
29 struct dba_array {
30 void **ep; /* Array of entries. */
31 int32_t *em; /* Array of map positions. */
32 int flags;
33 int32_t ea; /* Entries allocated. */
34 int32_t eu; /* Entries used (including deleted). */
35 int32_t ed; /* Entries deleted. */
36 int32_t ec; /* Currently active entry. */
37 int32_t pos; /* Map position of this array. */
38 };
39
40
41 struct dba_array *
dba_array_new(int32_t ea,int flags)42 dba_array_new(int32_t ea, int flags)
43 {
44 struct dba_array *array;
45
46 assert(ea > 0);
47 array = mandoc_malloc(sizeof(*array));
48 array->ep = mandoc_reallocarray(NULL, ea, sizeof(*array->ep));
49 array->em = mandoc_reallocarray(NULL, ea, sizeof(*array->em));
50 array->ea = ea;
51 array->eu = 0;
52 array->ed = 0;
53 array->ec = 0;
54 array->flags = flags;
55 array->pos = 0;
56 return array;
57 }
58
59 void
dba_array_free(struct dba_array * array)60 dba_array_free(struct dba_array *array)
61 {
62 int32_t ie;
63
64 if (array == NULL)
65 return;
66 if (array->flags & DBA_STR)
67 for (ie = 0; ie < array->eu; ie++)
68 free(array->ep[ie]);
69 free(array->ep);
70 free(array->em);
71 free(array);
72 }
73
74 void
dba_array_set(struct dba_array * array,int32_t ie,void * entry)75 dba_array_set(struct dba_array *array, int32_t ie, void *entry)
76 {
77 assert(ie >= 0);
78 assert(ie < array->ea);
79 assert(ie <= array->eu);
80 if (ie == array->eu)
81 array->eu++;
82 if (array->flags & DBA_STR)
83 entry = mandoc_strdup(entry);
84 array->ep[ie] = entry;
85 array->em[ie] = 0;
86 }
87
88 void
dba_array_add(struct dba_array * array,void * entry)89 dba_array_add(struct dba_array *array, void *entry)
90 {
91 if (array->eu == array->ea) {
92 assert(array->flags & DBA_GROW);
93 array->ep = mandoc_reallocarray(array->ep,
94 2, sizeof(*array->ep) * array->ea);
95 array->em = mandoc_reallocarray(array->em,
96 2, sizeof(*array->em) * array->ea);
97 array->ea *= 2;
98 }
99 dba_array_set(array, array->eu, entry);
100 }
101
102 void *
dba_array_get(struct dba_array * array,int32_t ie)103 dba_array_get(struct dba_array *array, int32_t ie)
104 {
105 if (ie < 0 || ie >= array->eu || array->em[ie] == -1)
106 return NULL;
107 return array->ep[ie];
108 }
109
110 void
dba_array_start(struct dba_array * array)111 dba_array_start(struct dba_array *array)
112 {
113 array->ec = array->eu;
114 }
115
116 void *
dba_array_next(struct dba_array * array)117 dba_array_next(struct dba_array *array)
118 {
119 if (array->ec < array->eu)
120 array->ec++;
121 else
122 array->ec = 0;
123 while (array->ec < array->eu && array->em[array->ec] == -1)
124 array->ec++;
125 return array->ec < array->eu ? array->ep[array->ec] : NULL;
126 }
127
128 void
dba_array_del(struct dba_array * array)129 dba_array_del(struct dba_array *array)
130 {
131 if (array->ec < array->eu && array->em[array->ec] != -1) {
132 array->em[array->ec] = -1;
133 array->ed++;
134 }
135 }
136
137 void
dba_array_undel(struct dba_array * array)138 dba_array_undel(struct dba_array *array)
139 {
140 memset(array->em, 0, sizeof(*array->em) * array->eu);
141 }
142
143 void
dba_array_setpos(struct dba_array * array,int32_t ie,int32_t pos)144 dba_array_setpos(struct dba_array *array, int32_t ie, int32_t pos)
145 {
146 array->em[ie] = pos;
147 }
148
149 int32_t
dba_array_getpos(struct dba_array * array)150 dba_array_getpos(struct dba_array *array)
151 {
152 return array->pos;
153 }
154
155 void
dba_array_sort(struct dba_array * array,dba_compare_func func)156 dba_array_sort(struct dba_array *array, dba_compare_func func)
157 {
158 assert(array->ed == 0);
159 qsort(array->ep, array->eu, sizeof(*array->ep), func);
160 }
161
162 int32_t
dba_array_writelen(struct dba_array * array,int32_t nmemb)163 dba_array_writelen(struct dba_array *array, int32_t nmemb)
164 {
165 dba_int_write(array->eu - array->ed);
166 return dba_skip(nmemb, array->eu - array->ed);
167 }
168
169 void
dba_array_writepos(struct dba_array * array)170 dba_array_writepos(struct dba_array *array)
171 {
172 int32_t ie;
173
174 array->pos = dba_tell();
175 for (ie = 0; ie < array->eu; ie++)
176 if (array->em[ie] != -1)
177 dba_int_write(array->em[ie]);
178 }
179
180 void
dba_array_writelst(struct dba_array * array)181 dba_array_writelst(struct dba_array *array)
182 {
183 const char *str;
184
185 dba_array_FOREACH(array, str)
186 dba_str_write(str);
187 dba_char_write('\0');
188 }
189