Home | History | Annotate | Line # | Download | only in dist
dba_array.c revision 1.1 
      1 /*	Id: dba_array.c,v 1.1 2016/07/19 21:31:55 schwarze Exp  */
      2 /*
      3  * Copyright (c) 2016 Ingo Schwarze <schwarze (at) 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 *
     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
     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
     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
     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 *
    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
    111 dba_array_start(struct dba_array *array)
    112 {
    113 	array->ec = array->eu;
    114 }
    115 
    116 void *
    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
    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
    138 dba_array_undel(struct dba_array *array)
    139 {
    140 	memset(array->em, 0, sizeof(*array->em) * array->eu);
    141 }
    142 
    143 void
    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
    150 dba_array_getpos(struct dba_array *array)
    151 {
    152 	return array->pos;
    153 }
    154 
    155 void
    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
    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
    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
    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