contrib/mandoc/dba_array.c

   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 }