cgit.sxemacs.org Git - sxemacs/blob - src/dynarr.c

   1 /* Simple 'n' stupid dynamic-array module.
   2    Copyright (C) 1993 Sun Microsystems, Inc.
   3
   4 This file is part of SXEmacs
   5
   6 SXEmacs is free software: you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation, either version 3 of the License, or
   9 (at your option) any later version.
  10
  11 SXEmacs is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  18
  19
  20 /* Synched up with:  Not in FSF. */
  21
  22 /* Written by Ben Wing, December 1993. */
  23
  24 /*
  25
  26 A "dynamic array" is a contiguous array of fixed-size elements where there
  27 is no upper limit (except available memory) on the number of elements in the
  28 array.  Because the elements are maintained contiguously, space is used
  29 efficiently (no per-element pointers necessary) and random access to a
  30 particular element is in constant time.  At any one point, the block of memory
  31 that holds the array has an upper limit; if this limit is exceeded, the
  32 memory is realloc()ed into a new array that is twice as big.  Assuming that
  33 the time to grow the array is on the order of the new size of the array
  34 block, this scheme has a provably constant amortized time (i.e. average
  35 time over all additions).
  36
  37 When you add elements or retrieve elements, pointers are used.  Note that
  38 the element itself (of whatever size it is), and not the pointer to it,
  39 is stored in the array; thus you do not have to allocate any heap memory
  40 on your own.  Also, returned pointers are only guaranteed to be valid
  41 until the next operation that changes the length of the array.
  42
  43 This is a container object.  Declare a dynamic array of a specific type
  44 as follows:
  45
  46 typedef struct
  47 {
  48   Dynarr_declare (mytype);
  49 } mytype_dynarr;
  50
  51 Use the following functions/macros:
  52
  53    void *Dynarr_new(type)
  54       [MACRO] Create a new dynamic-array object, with each element of the
  55       specified type.  The return value is cast to (type##_dynarr).
  56       This requires following the convention that types are declared in
  57       such a way that this type concatenation works.  In particular, TYPE
  58       must be a symbol, not an arbitrary C type.
  59
  60    Dynarr_add(d, el)
  61       [MACRO] Add an element to the end of a dynamic array.  EL is a pointer
  62       to the element; the element itself is stored in the array, however.
  63       No function call is performed unless the array needs to be resized.
  64
  65    Dynarr_add_many(d, base, len)
  66       [MACRO] Add LEN elements to the end of the dynamic array.  The elements
  67       should be contiguous in memory, starting at BASE.
  68
  69    Dynarr_insert_many_at_start(d, base, len)
  70       [MACRO] Append LEN elements to the beginning of the dynamic array.
  71       The elements should be contiguous in memory, starting at BASE.
  72
  73    Dynarr_insert_many(d, base, len, start)
  74       Insert LEN elements to the dynamic array starting at position
  75       START.  The elements should be contiguous in memory, starting at BASE.
  76
  77    int Dynarr_length(d)
  78       [MACRO] Return the number of elements currently in a dynamic array.
  79
  80    int Dynarr_largest(d)
  81       [MACRO] Return the maximum value that Dynarr_length(d) would
  82       ever have returned.
  83
  84    type Dynarr_at(d, i)
  85       [MACRO] Return the element at the specified index (no bounds checking
  86       done on the index).  The element itself is returned, not a pointer
  87       to it.
  88
  89    type *Dynarr_atp(d, i)
  90       [MACRO] Return a pointer to the element at the specified index (no
  91       bounds checking done on the index).  The pointer may not be valid
  92       after an element is added to or removed from the array.
  93
  94    Dynarr_reset(d)
  95       [MACRO] Reset the length of a dynamic array to 0.
  96
  97    Dynarr_free(d)
  98       Destroy a dynamic array and the memory allocated to it.
  99
 100 Use the following global variable:
 101
 102    Dynarr_min_size
 103       Minimum allowable size for a dynamic array when it is resized.
 104
 105 */
 106
 107 #include <config.h>
 108 #include "lisp.h"
 109
 110 static int Dynarr_min_size = 8;
 111
 112 static void Dynarr_realloc(Dynarr * dy, int new_size)
 113 {
 114         if (DUMPEDP(dy->base)) {
 115                 void *new_base = dy->elsize >= (signed int)sizeof(void*)
 116                         ? xmalloc(new_size)
 117                         : xmalloc_atomic(new_size);
 118                 int max_bytes = dy->max * dy->elsize;
 119                 memcpy(new_base, dy->base,
 120                        max_bytes > new_size ? new_size : max_bytes);
 121                 dy->base = new_base;
 122         } else {
 123                 dy->base = xrealloc(dy->base, new_size);
 124         }
 125 }
 126
 127 void *Dynarr_newf(int elsize)
 128 {
 129         Dynarr *d = xnew_and_zero(Dynarr);
 130         d->elsize = elsize;
 131
 132         return d;
 133 }
 134
 135 void Dynarr_resize(void *d, int size)
 136 {
 137        Dynarr *dy = (Dynarr *) d;
 138        int newsize = max(Dynarr_min_size,dy->max);
 139
 140
 141        if (dy->max <= 16)
 142                while(newsize < size)
 143                        /* newsize *= 2 */
 144                        newsize <<= 1;
 145        else
 146                while(newsize < size)
 147                        /* newsize *= 1.5 */
 148                        newsize += (newsize>>1);
 149
 150
 151         /* Don't do anything if the array is already big enough. */
 152         if (newsize > dy->max) {
 153                 Dynarr_realloc(dy, newsize * dy->elsize);
 154                 dy->max = newsize;
 155         }
 156 }
 157
 158 /* Add a number of contiguous elements to the array starting at START. */
 159 void Dynarr_insert_many(void *d, const void *el, int len, int start)
 160 {
 161         Dynarr *dy = (Dynarr *) d;
 162
 163         Dynarr_resize(dy, dy->cur + len);
 164         /* Silently adjust start to be valid. */
 165         if (start > dy->cur)
 166                 start = dy->cur;
 167         else if (start < 0)
 168                 start = 0;
 169
 170         if (start != dy->cur) {
 171                 memmove((char *)dy->base + (start + len) * dy->elsize,
 172                         (char *)dy->base + start * dy->elsize,
 173                         (dy->cur - start) * dy->elsize);
 174         }
 175         memcpy((char *)dy->base + start * dy->elsize, el, len * dy->elsize);
 176         dy->cur += len;
 177
 178         if (dy->cur > dy->largest)
 179                 dy->largest = dy->cur;
 180 }
 181
 182 void Dynarr_delete_many(void *d, int start, int len)
 183 {
 184         Dynarr *dy = (Dynarr *) d;
 185
 186         assert(start >= 0 && len >= 0 && start + len <= dy->cur);
 187         memmove((char *)dy->base + start * dy->elsize,
 188                 (char *)dy->base + (start + len) * dy->elsize,
 189                 (dy->cur - start - len) * dy->elsize);
 190         dy->cur -= len;
 191 }
 192
 193 void Dynarr_free(void *d)
 194 {
 195         Dynarr *dy = (Dynarr *) d;
 196
 197         if (dy->base && !DUMPEDP(dy->base))
 198                 xfree(dy->base);
 199         if (!DUMPEDP(dy))
 200                 xfree(dy);
 201 }
 202
 203 #if defined MEMORY_USAGE_STATS && !(defined HAVE_BDWGC && defined EF_USE_BDWGC)
 204
 205 /* Return memory usage for Dynarr D.  The returned value is the total
 206    amount of bytes actually being used for the Dynarr, including all
 207    overhead.  The extra amount of space in the Dynarr that is
 208    allocated beyond what was requested is returned in DYNARR_OVERHEAD
 209    in STATS.  The extra amount of space that malloc() allocates beyond
 210    what was requested of it is returned in MALLOC_OVERHEAD in STATS.
 211    See the comment above the definition of this structure. */
 212
 213 size_t Dynarr_memory_usage(void *d, struct overhead_stats *stats)
 214 {
 215         size_t total = 0;
 216         Dynarr *dy = (Dynarr *) d;
 217
 218         /* We have to be a bit tricky here because not all of the
 219            memory that malloc() will claim as "requested" was actually
 220            requested. */
 221
 222         if (dy->base) {
 223                 size_t malloc_used = malloced_storage_size(dy->base,
 224                                                            dy->elsize * dy->max,
 225                                                            0);
 226                 /* #### This may or may not be correct.  Some Dynarrs would
 227                    prefer that we use dy->cur instead of dy->largest here. */
 228                 int was_requested = dy->elsize * dy->largest;
 229                 int dynarr_overhead = dy->elsize * (dy->max - dy->largest);
 230
 231                 total += malloc_used;
 232                 stats->was_requested += was_requested;
 233                 stats->dynarr_overhead += dynarr_overhead;
 234                 /* And the remainder must be malloc overhead. */
 235                 stats->malloc_overhead +=
 236                         malloc_used - was_requested - dynarr_overhead;
 237         }
 238
 239         total += malloced_storage_size(d, sizeof(*dy), stats);
 240
 241         return total;
 242 }
 243
 244 #endif                          /* MEMORY_USAGE_STATS */