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