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                         void grow(size_t newsize)
 150                         {
 151                                 if (newsize <= bufsize)
 152                                         return;
 153
 154                                 T *oldptr = ptr;
 155                                 T *newptr = new(Alloc()) T[newsize];
 156
 157                                 memcpy(newptr, ptr, count * sizeof(T));
 158
 159                                 ptr = newptr;
 160                                 ll_smp_membar_store_after_store();
 161                                 bufsize = newsize;
 162                                 ll_smp_membar_any_after_store();
 163
 164                                 Alloc::release(oldptr);
 165                         }
 166
 167                         // Caller must sync against all writers.
 168                         void append(T *newptr, size_t len, size_t max = ULONG_MAX)
 169                         {
 170                                 if (count + len < count)
 171                                         throw ArrayException();
 172
 173                                 if (count + len > max)
 174                                         throw ArrayException();
 175
 176                                 if (count + len > bufsize)
 177                                         grow(ll_get_order_round_up(count + len));
 178
 179                                 memcpy(ptr + count, newptr, len * sizeof(T));
 180                                 count += len;
 181                         }
 182                 };
 183
 184                 template<typename T, typename Alloc = ::System::RunTime::ORBMM> struct Array {
 185                         const T *ptr;
 186                         size_t count;
 187
 188                         bool valid_index(size_t index)
 189                         {
 190                                 return index >= 0 && index < count;
 191                         }
 192
 193                         const T &operator[](size_t index)
 194                         {
 195 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 196                                 if (!valid_index(index))
 197                                         throw ArrayException();
 198 #endif
 199
 200                                 return ptr[index];
 201                         }
 202
 203                         Array()
 204                         {
 205                                 ptr = NULL;
 206                                 count = 0;
 207                         }
 208
 209                         Array(NullArray na)
 210                         {
 211                                 ptr = NULL;
 212                                 count = 0;
 213                         }
 214
 215                         Array(const T *PTR, size_t COUNT)
 216                         {
 217                                 ptr = PTR;
 218                                 count = COUNT;
 219                         }
 220
 221                         Array(MutableArray<T, Alloc> ma)
 222                         {
 223                                 ptr = ma.ptr;
 224                                 count = ma.count;
 225                         }
 226
 227                         MutableArray<T, Alloc> constcast()
 228                         {
 229                                 MutableArray<T, Alloc> ma;
 230                                 ma.ptr = const_cast<T>(ptr);
 231                                 ma.count = count;
 232                                 return ma;
 233                         }
 234
 235                         Array &slice_nocheck(size_t first, size_t newcount)
 236                         {
 237                                 Array ret;
 238                                 ret.ptr = ptr + first;
 239                                 ret.count = newcount;
 240                                 return ret;
 241                         }
 242
 243                         Array &slice_nocheck(size_t first)
 244                         {
 245                                 Array ret;
 246                                 ret.ptr = ptr + first;
 247                                 ret.count = count - first;
 248                                 return ret;
 249                         }
 250
 251                         Array &slice(size_t first, size_t count)
 252                         {
 253 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 254                                 if (!valid_index(first) || !valid_index(first + count - 1))
 255                                         throw ArrayException();
 256 #endif
 257
 258                                 return slice_nocheck(first, count);
 259                         }
 260
 261                         Array &slice(size_t first)
 262                         {
 263 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
 264                                 if (!valid_index(first))
 265                                         throw ArrayException();
 266 #endif
 267
 268                                 return slice_nocheck(first);
 269                         }
 270
 271                         MutableArray<T, Alloc> copy()
 272                         {
 273                                 MutableArray<T, Alloc> new_arr;
 274                                 new_arr.ptr = new(Alloc()) T[count];
 275                                 new_arr.count = count;
 276                                 memcpy(new_arr.ptr, ptr, count);
 277                                 return new_arr;
 278                         }
 279                 };
 280
 281                 template<typename Alloc>
 282                 static inline Array<uint8_t, Alloc>
 283                 countarray(const char *ptr)
 284                 {
 285                         Array<uint8_t, Alloc> ret;
 286                         ret.ptr = reinterpret_cast<const uint8_t *>(ptr);
 287                         ret.count = strlen(ptr);
 288                         return ret;
 289                 }
 290
 291                 template<typename Alloc>
 292                 static inline MutableArray<uint8_t, Alloc>
 293                 countarray(char *ptr)
 294                 {
 295                         MutableArray<uint8_t, Alloc> ret;
 296                         ret.ptr = reinterpret_cast<uint8_t *>(ptr);
 297                         ret.count = strlen(ptr);
 298                         return ret;
 299                 }
 300         }
 301
 302         using namespace Arrays;
 303 }
 304
 305 #endif