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