src/ngircd/array.c

   1 /*
   2  * This program is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License as published by
   4  * the Free Software Foundation; either version 2 of the License, or
   5  * (at your option) any later version.
   6  * Please read the file COPYING, README and AUTHORS for more information.
   7  *
   8  * functions to dynamically allocate arrays.
   9  * Copyright (c) 2005 Florian Westphal (westphal@foo.fh-furtwangen.de)
  10  *
  11  */
  12
  13 #include "array.h"
  14
  15 static char UNUSED id[] = "$Id: array.c,v 1.11 2006/07/01 22:11:48 fw Exp $";
  16
  17 #include <assert.h>
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "log.h"
  23
  24 /* Enable more Debug messages in alloc / append / memmove code. */
  25 /* #define DEBUG_ARRAY */
  26
  27
  28
  29 #define array_UNUSABLE(x)       ( !(x)->mem || (0 == (x)->allocated) )
  30
  31 #define ALIGN_32U(x)            (((x)+31U  ) & ~(31U))
  32 #define ALIGN_1024U(x)          (((x)+1023U) & ~(1023U))
  33 #define ALIGN_4096U(x)          (((x)+4095U) & ~(4095U))
  34
  35
  36 static bool
  37 safemult_sizet(size_t a, size_t b, size_t *res)
  38 {
  39         size_t tmp = a * b;
  40
  41         if (b && (tmp / b != a))
  42                 return false;
  43
  44         *res = tmp;
  45         return true;
  46 }
  47
  48
  49 void
  50 array_init(array *a)
  51 {
  52         assert(a != NULL);
  53         a->mem = NULL;
  54         a->allocated = 0;
  55         a->used = 0;
  56 }
  57
  58
  59 /* if realloc() fails, array_alloc return NULL. otherwise return pointer to elem pos in array */
  60 void *
  61 array_alloc(array * a, size_t size, size_t pos)
  62 {
  63         size_t alloc, pos_plus1 = pos + 1;
  64         size_t aligned = 0;
  65         char *tmp;
  66
  67         assert(size > 0);
  68
  69         if (pos_plus1 < pos)
  70                 return NULL;
  71
  72         if (!safemult_sizet(size, pos_plus1, &alloc))
  73                 return NULL;
  74
  75         if (a->allocated < alloc) {
  76                 if (alloc < 128) {
  77                         aligned = ALIGN_32U(alloc);
  78                 } else {
  79                         if (alloc < 4096) {
  80                                 aligned = ALIGN_1024U(alloc);
  81                         } else {
  82                                 aligned = ALIGN_4096U(alloc);
  83                         }
  84                 }
  85 #ifdef DEBUG_ARRAY
  86                 Log(LOG_DEBUG, "array_alloc(): rounded %u to %u bytes.", alloc, aligned);
  87 #endif
  88
  89                 assert(aligned >= alloc);
  90
  91                 if (aligned < alloc)    /* rounding overflow */
  92                         return NULL;
  93
  94                 alloc = aligned;
  95 #ifdef DEBUG_ARRAY
  96                 Log(LOG_DEBUG, "array_alloc(): changing size from %u to %u bytes.",
  97                     a->allocated, aligned);
  98 #endif
  99
 100                 tmp = realloc(a->mem, alloc);
 101                 if (!tmp)
 102                         return NULL;
 103
 104                 a->mem = tmp;
 105                 a->allocated = alloc;
 106
 107                 assert(a->allocated > a->used);
 108
 109                 memset(a->mem + a->used, 0, a->allocated - a->used);
 110
 111                 a->used = alloc;
 112         }
 113         return a->mem + (pos * size);
 114 }
 115
 116
 117 /*return number of initialized ELEMS in a. */
 118 size_t
 119 array_length(const array * const a, size_t membersize)
 120 {
 121         assert(a != NULL);
 122         assert(membersize > 0);
 123
 124         if (array_UNUSABLE(a))
 125                 return 0;
 126
 127         return membersize ? a->used / membersize : 0;
 128 }
 129
 130
 131 /* copy array src to array dest */
 132 bool
 133 array_copy(array * dest, const array * const src)
 134 {
 135         if (array_UNUSABLE(src))
 136                 return false;
 137
 138         return array_copyb(dest, src->mem, src->used);
 139 }
 140
 141
 142 /* return false on failure (realloc failure, invalid src/dest array) */
 143 bool
 144 array_copyb(array * dest, const char *src, size_t len)
 145 {
 146         assert(dest != NULL);
 147         assert(src != NULL );
 148
 149         if (!src || !dest)
 150                 return false;
 151
 152         array_trunc(dest);
 153         return array_catb(dest, src, len);
 154 }
 155
 156
 157 /* copy string to dest */
 158 bool
 159 array_copys(array * dest, const char *src)
 160 {
 161         return array_copyb(dest, src, strlen(src));
 162 }
 163
 164
 165 /* append len bytes from src to the array dest.
 166 return false if we could not append all bytes (realloc failure, invalid src/dest array) */
 167 bool
 168 array_catb(array * dest, const char *src, size_t len)
 169 {
 170         size_t tmp;
 171         size_t used;
 172         char *ptr;
 173
 174         assert(dest != NULL);
 175         assert(src != NULL);
 176
 177         if (!len)
 178                 return true;
 179
 180         if (!src || !dest)
 181                 return false;
 182
 183         used = dest->used;
 184         tmp = used + len;
 185
 186         if (tmp < used || tmp < len)    /* integer overflow */
 187                 return false;
 188
 189         if (!array_alloc(dest, 1, tmp))
 190                 return false;
 191
 192         ptr = dest->mem;
 193
 194         assert(ptr != NULL);
 195
 196 #ifdef DEBUG_ARRAY
 197         Log(LOG_DEBUG,
 198             "array_catb(): appending %u bytes to array (now %u bytes in array).",
 199             len, tmp);
 200 #endif
 201         memcpy(ptr + used, src, len);
 202         dest->used = tmp;
 203         return true;
 204 }
 205
 206
 207 /* append string to dest */
 208 bool
 209 array_cats(array * dest, const char *src)
 210 {
 211         return array_catb(dest, src, strlen(src));
 212 }
 213
 214
 215 /* append trailing NUL byte to array */
 216 bool
 217 array_cat0(array * a)
 218 {
 219         return array_catb(a, "", 1);
 220 }
 221
 222
 223 /* append trailing NUL byte to array, but do not count it. */
 224 bool
 225 array_cat0_temporary(array * a)
 226 {
 227         char *endpos = array_alloc(a, 1, array_bytes(a));
 228         if (!endpos)
 229                 return false;
 230
 231         *endpos = '\0';
 232         return true;
 233 }
 234
 235 /* add contents of array src to array dest. */
 236 bool
 237 array_cat(array * dest, const array * const src)
 238 {
 239         if (array_UNUSABLE(src))
 240                 return false;
 241
 242         return array_catb(dest, src->mem, src->used);
 243 }
 244
 245
 246 /* return pointer to the element at pos.
 247    return NULL if the array is unallocated, or if pos is larger than
 248    the number of elements stored int the array. */
 249 void *
 250 array_get(array * a, size_t membersize, size_t pos)
 251 {
 252         size_t totalsize;
 253
 254         assert(membersize > 0);
 255         assert(a != NULL);
 256
 257         if (array_UNUSABLE(a))
 258                 return NULL;
 259
 260         if (!safemult_sizet(pos, membersize, &totalsize))
 261                 return NULL;
 262
 263         if (a->allocated < totalsize)
 264                 return NULL;
 265
 266         return a->mem + pos * membersize;
 267 }
 268
 269
 270 void
 271 array_free(array * a)
 272 {
 273         assert(a != NULL);
 274 #ifdef DEBUG
 275         Log(LOG_DEBUG,
 276             "array_free(): %u bytes free'd (%u bytes still used at time of free()).",
 277             a->allocated, a->used);
 278 #endif
 279         free(a->mem);
 280         a->mem = NULL;
 281         a->allocated = 0;
 282         a->used = 0;
 283 }
 284
 285
 286 void
 287 array_free_wipe(array * a)
 288 {
 289         if (!array_UNUSABLE(a))
 290                 memset(a->mem, 0, a->allocated);
 291
 292         array_free(a);
 293 }
 294
 295
 296 void *
 297 array_start(const array * const a)
 298 {
 299         assert(a != NULL);
 300         return a->mem;
 301 }
 302
 303
 304 void
 305 array_trunc(array * a)
 306 {
 307         assert(a != NULL);
 308         a->used = 0;
 309 }
 310
 311
 312 void
 313 array_truncate(array * a, size_t membersize, size_t len)
 314 {
 315         size_t newlen;
 316         assert(a != NULL);
 317         if (!safemult_sizet(membersize, len, &newlen))
 318                 return;
 319
 320         if (newlen <= a->allocated)
 321                 a->used = newlen;
 322 }
 323
 324
 325 /* move elements starting at pos to beginning of array */
 326 void
 327 array_moveleft(array * a, size_t membersize, size_t pos)
 328 {
 329         size_t bytepos;
 330
 331         assert(a != NULL);
 332         assert(membersize > 0);
 333
 334         if (!pos)
 335                 return;
 336
 337         if (!safemult_sizet(membersize, pos, &bytepos)) {
 338                 a->used = 0;
 339                 return;
 340         }
 341
 342         if (!bytepos)
 343                 return; /* nothing to do */
 344
 345 #ifdef DEBUG_ARRAY
 346         Log(LOG_DEBUG,
 347             "array_moveleft(): %u bytes used in array, starting at position %u.",
 348             a->used, bytepos);
 349 #endif
 350         if (a->used <= bytepos) {
 351                 a->used = 0;
 352                 return;
 353         }
 354
 355         a->used -= bytepos;
 356         memmove(a->mem, a->mem + bytepos, a->used);
 357 }
 358
 359 /* -eof- */