blob: f7cb0c75184f2ca7077bce7874e30cbbccbaa315 [file] [log] [blame]
/* Copyright (C) 2011-2021 by The D Language Foundation, All Rights Reserved
* written by Walter Bright
* http://www.digitalmars.com
* Distributed under the Boost Software License, Version 1.0.
* http://www.boost.org/LICENSE_1_0.txt
* https://github.com/dlang/dmd/blob/master/src/dmd/root/array.h
*/
#pragma once
#include "dsystem.h"
#include "dcompat.h"
#include "object.h"
#include "rmem.h"
template <typename TYPE>
struct Array
{
size_t length;
private:
DArray<TYPE> data;
#define SMALLARRAYCAP 1
TYPE smallarray[SMALLARRAYCAP]; // inline storage for small arrays
Array(const Array&);
public:
Array()
{
data.ptr = NULL;
length = 0;
data.length = 0;
}
~Array()
{
if (data.ptr != &smallarray[0])
mem.xfree(data.ptr);
}
char *toChars() const
{
const char **buf = (const char **)mem.xmalloc(length * sizeof(const char *));
size_t len = 2;
for (size_t u = 0; u < length; u++)
{
buf[u] = ((RootObject *)data.ptr[u])->toChars();
len += strlen(buf[u]) + 1;
}
char *str = (char *)mem.xmalloc(len);
str[0] = '[';
char *p = str + 1;
for (size_t u = 0; u < length; u++)
{
if (u)
*p++ = ',';
len = strlen(buf[u]);
memcpy(p,buf[u],len);
p += len;
}
*p++ = ']';
*p = 0;
mem.xfree(buf);
return str;
}
void push(TYPE ptr)
{
reserve(1);
data.ptr[length++] = ptr;
}
void append(Array *a)
{
insert(length, a);
}
void reserve(size_t nentries)
{
//printf("Array::reserve: length = %d, data.length = %d, nentries = %d\n", (int)length, (int)data.length, (int)nentries);
if (data.length - length < nentries)
{
if (data.length == 0)
{
// Not properly initialized, someone memset it to zero
if (nentries <= SMALLARRAYCAP)
{
data.length = SMALLARRAYCAP;
data.ptr = SMALLARRAYCAP ? &smallarray[0] : NULL;
}
else
{
data.length = nentries;
data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
}
}
else if (data.length == SMALLARRAYCAP)
{
data.length = length + nentries;
data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
memcpy(data.ptr, &smallarray[0], length * sizeof(TYPE));
}
else
{
/* Increase size by 1.5x to avoid excessive memory fragmentation
*/
size_t increment = length / 2;
if (nentries > increment) // if 1.5 is not enough
increment = nentries;
data.length = length + increment;
data.ptr = (TYPE *)mem.xrealloc(data.ptr, data.length * sizeof(TYPE));
}
}
}
void remove(size_t i)
{
if (length - i - 1)
memmove(data.ptr + i, data.ptr + i + 1, (length - i - 1) * sizeof(TYPE));
length--;
}
void insert(size_t index, Array *a)
{
if (a)
{
size_t d = a->length;
reserve(d);
if (length != index)
memmove(data.ptr + index + d, data.ptr + index, (length - index) * sizeof(TYPE));
memcpy(data.ptr + index, a->data.ptr, d * sizeof(TYPE));
length += d;
}
}
void insert(size_t index, TYPE ptr)
{
reserve(1);
memmove(data.ptr + index + 1, data.ptr + index, (length - index) * sizeof(TYPE));
data.ptr[index] = ptr;
length++;
}
void setDim(size_t newdim)
{
if (length < newdim)
{
reserve(newdim - length);
}
length = newdim;
}
size_t find(TYPE ptr) const
{
for (size_t i = 0; i < length; i++)
{
if (data.ptr[i] == ptr)
return i;
}
return SIZE_MAX;
}
bool contains(TYPE ptr) const
{
return find(ptr) != SIZE_MAX;
}
TYPE& operator[] (size_t index)
{
#ifdef DEBUG
assert(index < length);
#endif
return data.ptr[index];
}
TYPE *tdata()
{
return data.ptr;
}
Array *copy()
{
Array *a = new Array();
a->setDim(length);
memcpy(a->data.ptr, data.ptr, length * sizeof(TYPE));
return a;
}
void shift(TYPE ptr)
{
reserve(1);
memmove(data.ptr + 1, data.ptr, length * sizeof(TYPE));
data.ptr[0] = ptr;
length++;
}
void zero()
{
memset(data.ptr, 0, length * sizeof(TYPE));
}
TYPE pop()
{
return data.ptr[--length];
}
void sort()
{
struct ArraySort
{
static int
#if _WIN32
__cdecl
#endif
Array_sort_compare(const void *x, const void *y)
{
RootObject *ox = *(RootObject **)const_cast<void *>(x);
RootObject *oy = *(RootObject **)const_cast<void *>(y);
return ox->compare(oy);
}
};
if (length)
{
qsort(data.ptr, length, sizeof(RootObject *), &ArraySort::Array_sort_compare);
}
}
};