include/c++/util/array.h

   1 // util/array.h -- Dynamically sized arrays
   2 //
   3 // This software is copyright (c) 2007 Scott Wood <scott@buserror.net>.
   4 //
   5 // This software is provided 'as-is', without any express or implied warranty.
   6 // In no event will the authors or contributors be held liable for any damages
   7 // arising from the use of this software.
   8 //
   9 // Permission is hereby granted to everyone, free of charge, to use, copy,
  10 // modify, prepare derivative works of, publish, distribute, perform,
  11 // sublicense, and/or sell copies of the Software, provided that the above
  12 // copyright notice and disclaimer of warranty be included in all copies or
  13 // substantial portions of this software.
  14
  15 #ifndef _UTIL_ARRAY_H
  16 #define _UTIL_ARRAY_H
  17
  18 namespace System {
  19 namespace RunTime {
  20         class ORBMM;
  21 }}
  22
  23 namespace Util {
  24         namespace Arrays {
  25                 struct ArrayException
  26                 {
  27                 };
  28
  29                 class NullArray {
  30                 };
  31
  32                 static const NullArray nullarray = {};
  33
  34                 template<typename T, typename Alloc = ::System::RunTime::ORBMM> struct MutableArray {
  35                         T *ptr;
  36                         size_t count;
  37
  38                         bool valid_index(size_t index)
  39                         {
  40                                 return index >= 0 && index < count;
  41                         }
  42
  43                         T &operator[](size_t index)
  44                         {
  45 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
  46                                 if (!valid_index(index))
  47                                         throw ArrayException();
  48 #endif
  49
  50                                 return ptr[index];
  51                         }
  52
  53                         MutableArray()
  54                         {
  55                                 ptr = NULL;
  56                                 count = 0;
  57                         }
  58
  59                         MutableArray(NullArray na)
  60                         {
  61                                 ptr = NULL;
  62                                 count = 0;
  63                         }
  64
  65                         MutableArray(T *PTR, size_t COUNT)
  66                         {
  67                                 ptr = PTR;
  68                                 count = COUNT;
  69                         }
  70
  71                         MutableArray &slice_nocheck(size_t first, size_t newcount)
  72                         {
  73                                 MutableArray ret;
  74                                 ret.ptr = ptr + first;
  75                                 ret.count = newcount;
  76                                 return ret;
  77                         }
  78
  79                         MutableArray &slice_nocheck(size_t first)
  80                         {
  81                                 MutableArray ret;
  82                                 ret.ptr = ptr + first;
  83                                 ret.count = count - first;
  84                                 return ret;
  85                         }
  86
  87                         MutableArray &slice(size_t first, size_t count)
  88                         {
  89 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
  90                                 if (!valid_index(first) || !valid_index(first + count - 1))
  91                                         throw ArrayException();
  92 #endif
  93
  94                                 return slice_nocheck(first, count);
  95                         }
  96
  97                         MutableArray &slice(size_t first)
  98                         {
  99 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 100                                 if (!valid_index(first))
 101                                         throw ArrayException();
 102 #endif
 103
 104                                 return slice_nocheck(first);
 105                         }
 106
 107                         MutableArray copy()
 108                         {
 109                                 MutableArray new_arr;
 110                                 new_arr.ptr = new(Alloc()) T[count];
 111                                 new_arr.count = count;
 112                                 memcpy(new_arr.ptr, ptr, count);
 113                                 return new_arr;
 114                         }
 115                 };
 116
 117                 template<typename T, typename Alloc = ::System::RunTime::ORBMM>
 118                 struct GrowableArray : public MutableArray<T, Alloc> {
 119                         using MutableArray<T, Alloc>::ptr;
 120                         using MutableArray<T, Alloc>::count;
 121                         size_t bufsize;
 122
 123                         GrowableArray()
 124                         {
 125                                 bufsize = 0;
 126                         }
 127
 128                         GrowableArray(NullArray na) : MutableArray<T, Alloc>(na)
 129                         {
 130                                 bufsize = 0;
 131                         }
 132
 133                         GrowableArray(T *PTR, size_t COUNT) : MutableArray<T, Alloc>(PTR, COUNT)
 134                         {
 135                                 bufsize = COUNT;
 136                         }
 137
 138                         GrowableArray(T *PTR, size_t COUNT, size_t BUFSIZE) :
 139                         MutableArray<T, Alloc>(PTR, COUNT)
 140                         {
 141                                 bufsize = BUFSIZE;
 142                         }
 143
 144                         GrowableArray(MutableArray<T, Alloc> &ma) : MutableArray<T, Alloc>(ma)
 145                         {
 146                                 bufsize = count;
 147                         }
 148
 149                         // FIXME: use realloc
 150                         void grow(size_t newsize)
 151                         {
 152                                 if (newsize <= bufsize)
 153                                         return;
 154
 155                                 T *oldptr = ptr;
 156                                 T *newptr = new(Alloc()) T[newsize];
 157
 158                                 memcpy(newptr, ptr, count * sizeof(T));
 159                                 memset(newptr + count, 0, (newsize - count) * sizeof(T));
 160
 161                                 ptr = newptr;
 162                                 ll_smp_membar_store_after_store();
 163                                 bufsize = newsize;
 164                                 ll_smp_membar_any_after_store();
 165
 166                                 Alloc::release(oldptr);
 167                         }
 168
 169                         T *grow_by(size_t len, size_t max = ULONG_MAX)
 170                         {
 171                                 size_t oldcount = count;
 172
 173                                 if (count + len < count)
 174                                         throw ArrayException();
 175
 176                                 if (count + len > max)
 177                                         throw ArrayException();
 178
 179                                 if (count + len > bufsize)
 180                                         grow(ll_get_order_round_up(count + len));
 181
 182                                 return ptr + oldcount;
 183                         }
 184
 185                         // align must be power-of-two
 186                         void align_to(size_t align, size_t max = ULONG_MAX)
 187                         {
 188                                 size_t newcount = (count + align - 1) & ~(align - 1);
 189
 190                                 if (newcount < count)
 191                                         throw ArrayException();
 192
 193                                 if (newcount > max)
 194                                         throw ArrayException();
 195
 196                                 if (newcount > bufsize)
 197                                         grow(ll_get_order_round_up(newcount));
 198                         }
 199
 200                         // Caller must sync against all writers.
 201                         void append(T *newptr, size_t len, size_t max = ULONG_MAX)
 202                         {
 203                                 memcpy(ptr + grow_by(len, max), newptr, len * sizeof(T));
 204                                 count += len;
 205                         }
 206                 };
 207
 208                 template<typename T, typename Alloc = ::System::RunTime::ORBMM> struct Array {
 209                         const T *ptr;
 210                         size_t count;
 211
 212                         bool valid_index(size_t index)
 213                         {
 214                                 return index >= 0 && index < count;
 215                         }
 216
 217                         const T &operator[](size_t index)
 218                         {
 219 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 220                                 if (!valid_index(index))
 221                                         throw ArrayException();
 222 #endif
 223
 224                                 return ptr[index];
 225                         }
 226
 227                         Array()
 228                         {
 229                                 ptr = NULL;
 230                                 count = 0;
 231                         }
 232
 233                         Array(NullArray na)
 234                         {
 235                                 ptr = NULL;
 236                                 count = 0;
 237                         }
 238
 239                         Array(const T *PTR, size_t COUNT)
 240                         {
 241                                 ptr = PTR;
 242                                 count = COUNT;
 243                         }
 244
 245                         Array(MutableArray<T, Alloc> ma)
 246                         {
 247                                 ptr = ma.ptr;
 248                                 count = ma.count;
 249                         }
 250
 251                         MutableArray<T, Alloc> constcast()
 252                         {
 253                                 MutableArray<T, Alloc> ma;
 254                                 ma.ptr = const_cast<T>(ptr);
 255                                 ma.count = count;
 256                                 return ma;
 257                         }
 258
 259                         Array &slice_nocheck(size_t first, size_t newcount)
 260                         {
 261                                 Array ret;
 262                                 ret.ptr = ptr + first;
 263                                 ret.count = newcount;
 264                                 return ret;
 265                         }
 266
 267                         Array &slice_nocheck(size_t first)
 268                         {
 269                                 Array ret;
 270                                 ret.ptr = ptr + first;
 271                                 ret.count = count - first;
 272                                 return ret;
 273                         }
 274
 275                         Array &slice(size_t first, size_t count)
 276                         {
 277 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 278                                 if (!valid_index(first) || !valid_index(first + count - 1))
 279                                         throw ArrayException();
 280 #endif
 281
 282                                 return slice_nocheck(first, count);
 283                         }
 284
 285                         Array &slice(size_t first)
 286                         {
 287 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 288                                 if (!valid_index(first))
 289                                         throw ArrayException();
 290 #endif
 291
 292                                 return slice_nocheck(first);
 293                         }
 294
 295                         MutableArray<T, Alloc> copy()
 296                         {
 297                                 MutableArray<T, Alloc> new_arr;
 298                                 new_arr.ptr = new(Alloc()) T[count];
 299                                 new_arr.count = count;
 300                                 memcpy(new_arr.ptr, ptr, count);
 301                                 return new_arr;
 302                         }
 303                 };
 304
 305                 template<typename Alloc>
 306                 static inline Array<uint8_t, Alloc>
 307                 countarray(const char *ptr)
 308                 {
 309                         Array<uint8_t, Alloc> ret;
 310                         ret.ptr = reinterpret_cast<const uint8_t *>(ptr);
 311                         ret.count = strlen(ptr);
 312                         return ret;
 313                 }
 314
 315                 template<typename Alloc>
 316                 static inline MutableArray<uint8_t, Alloc>
 317                 countarray(char *ptr)
 318                 {
 319                         MutableArray<uint8_t, Alloc> ret;
 320                         ret.ptr = reinterpret_cast<uint8_t *>(ptr);
 321                         ret.count = strlen(ptr);
 322                         return ret;
 323                 }
 324         }
 325
 326         using namespace Arrays;
 327 }
 328
 329 #endif