vect.c

   1 /*
   2  * This file is part of ltrace.
   3  * Copyright (C) 2011,2012,2013 Petr Machata, Red Hat Inc.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation; either version 2 of the
   8  * License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
  18  * 02110-1301 USA
  19  */
  20
  21 #include <stdlib.h>
  22 #include <assert.h>
  23 #include <string.h>
  24 #include "vect.h"
  25
  26 static void *
  27 slot(struct vect *vec, size_t i)
  28 {
  29         return ((unsigned char *)vec->data) + vec->elt_size * i;
  30 }
  31
  32 static const void *
  33 cslot(const struct vect *vec, size_t i)
  34 {
  35         return ((const unsigned char *)vec->data) + vec->elt_size * i;
  36 }
  37
  38 void
  39 vect_init(struct vect *vec, size_t elt_size)
  40 {
  41         *vec = (struct vect){ NULL, 0, 0, elt_size };
  42 }
  43
  44 static int
  45 copy_elt(void *tgt, const void *src, void *data)
  46 {
  47         struct vect *target = data;
  48         memcpy(tgt, src, target->elt_size);
  49         return 0;
  50 }
  51
  52 int
  53 vect_clone(struct vect *target, const struct vect *source,
  54            int (*clone)(void *tgt, const void *src, void *data),
  55            void (*dtor)(void *elt, void *data),
  56            void *data)
  57 {
  58         vect_init(target, source->elt_size);
  59         if (vect_reserve(target, source->size) < 0)
  60                 return -1;
  61
  62         if (clone == NULL) {
  63                 assert(dtor == NULL);
  64                 clone = copy_elt;
  65                 data = target;
  66         } else {
  67                 assert(dtor != NULL);
  68         }
  69
  70         size_t i;
  71         for (i = 0; i < source->size; ++i)
  72                 if (clone(slot(target, i), cslot(source, i), data) < 0)
  73                         goto fail;
  74
  75         target->size = source->size;
  76         return 0;
  77
  78 fail:
  79         /* N.B. destroy the elements in opposite order.  */
  80         if (dtor != NULL)
  81                 while (i-- != 0)
  82                         dtor(slot(target, i), data);
  83         vect_destroy(target, NULL, NULL);
  84         return -1;
  85 }
  86
  87 int
  88 vect_reserve(struct vect *vec, size_t count)
  89 {
  90         if (count > vec->allocated) {
  91                 size_t na = vec->allocated != 0 ? 2 * vec->allocated : 4;
  92                 while (na < count)
  93                         na *= 2;
  94                 void *n = realloc(vec->data, na * vec->elt_size);
  95                 if (n == NULL)
  96                         return -1;
  97                 vec->data = n;
  98                 vec->allocated = na;
  99         }
 100         assert(count <= vec->allocated);
 101         return 0;
 102 }
 103
 104 size_t
 105 vect_size(const struct vect *vec)
 106 {
 107         return vec->size;
 108 }
 109
 110 int
 111 vect_empty(const struct vect *vec)
 112 {
 113         return vec->size == 0;
 114 }
 115
 116 int
 117 vect_reserve_additional(struct vect *vec, size_t count)
 118 {
 119         return vect_reserve(vec, vect_size(vec) + count);
 120 }
 121
 122 int
 123 vect_pushback(struct vect *vec, void *eltp)
 124 {
 125         if (vect_reserve_additional(vec, 1) < 0)
 126                 return -1;
 127         memcpy(slot(vec, vec->size++), eltp, vec->elt_size);
 128         return 0;
 129 }
 130
 131 void
 132 vect_erase(struct vect *vec, size_t start, size_t end,
 133            void (*dtor)(void *emt, void *data), void *data)
 134 {
 135         assert(start < vect_size(vec) || start == 0);
 136         assert(end <= vect_size(vec));
 137
 138         /* First, destroy the elements that are to be erased.  */
 139         if (dtor != NULL) {
 140                 size_t i;
 141                 for (i = start; i < end; ++i)
 142                         dtor(slot(vec, i), data);
 143         }
 144
 145         /* Now move the tail forward and adjust size.  */
 146         memmove(slot(vec, start), slot(vec, end),
 147                 slot(vec, vec->size) - slot(vec, end));
 148         vec->size -= end - start;
 149 }
 150
 151 void
 152 vect_popback(struct vect *vec,
 153              void (*dtor)(void *emt, void *data), void *data)
 154 {
 155         assert(vect_size(vec) > 0);
 156         vect_erase(vec, vect_size(vec)-1, vect_size(vec), dtor, data);
 157 }
 158
 159 void
 160 vect_destroy(struct vect *vec, void (*dtor)(void *emt, void *data), void *data)
 161 {
 162         if (vec == NULL)
 163                 return;
 164
 165         vect_erase(vec, 0, vect_size(vec), dtor, data);
 166         assert(vect_size(vec) == 0);
 167         free(vec->data);
 168 }
 169
 170 void *
 171 vect_each(struct vect *vec, void *start_after,
 172           enum callback_status (*cb)(void *, void *), void *data)
 173 {
 174         size_t i = start_after == NULL ? 0
 175                 : ((start_after - vec->data) / vec->elt_size) + 1;
 176
 177         for (; i < vec->size; ++i) {
 178                 void *slt = slot(vec, i);
 179                 switch ((*cb)(slt, data)) {
 180                 case CBS_FAIL:
 181                         /* XXX handle me */
 182                 case CBS_STOP:
 183                         return slt;
 184                 case CBS_CONT:
 185                         break;
 186                 }
 187         }
 188
 189         return NULL;
 190 }
 191
 192 void
 193 vect_qsort(struct vect *vec, int (*compar)(const void *, const void *))
 194 {
 195         qsort(vec->data, vec->size, vec->elt_size, compar);
 196 }
 197
 198 const void *
 199 vect_each_cst(const struct vect *vec, const void *start_after,
 200               enum callback_status (*cb)(const void *, void *), void *data)
 201 {
 202         return vect_each((struct vect *)vec, (void *)start_after,
 203                          (void *)cb, data);
 204 }
 205
 206 void
 207 vect_dtor_string(char **key, void *data)
 208 {
 209         free(*key);
 210 }