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 31 struct 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 43 struct dba_array * 44 dba_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 61 void 62 dba_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 76 void 77 dba_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 90 void 91 dba_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 104 void * 105 dba_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 112 void 113 dba_array_start(struct dba_array *array) 114 { 115 array->ec = array->eu; 116 } 117 118 void * 119 dba_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 130 void 131 dba_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 139 void 140 dba_array_undel(struct dba_array *array) 141 { 142 memset(array->em, 0, sizeof(*array->em) * array->eu); 143 } 144 145 void 146 dba_array_setpos(struct dba_array *array, int32_t ie, int32_t pos) 147 { 148 array->em[ie] = pos; 149 } 150 151 int32_t 152 dba_array_getpos(struct dba_array *array) 153 { 154 return array->pos; 155 } 156 157 void 158 dba_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 164 int32_t 165 dba_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 171 void 172 dba_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 182 void 183 dba_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