1 /* Copyright (C) 2011-2022 by The D Language Foundation, All Rights Reserved
2 * written by Walter Bright
3 * https://www.digitalmars.com
4 * Distributed under the Boost Software License, Version 1.0.
5 * https://www.boost.org/LICENSE_1_0.txt
6 * https://github.com/dlang/dmd/blob/master/src/dmd/root/array.h
15 template <typename TYPE
>
22 #define SMALLARRAYCAP 1
23 TYPE smallarray
[SMALLARRAYCAP
]; // inline storage for small arrays
37 if (data
.ptr
!= &smallarray
[0])
43 const char **buf
= (const char **)mem
.xmalloc(length
* sizeof(const char *));
45 for (d_size_t u
= 0; u
< length
; u
++)
47 buf
[u
] = ((RootObject
*)data
.ptr
[u
])->toChars();
48 len
+= strlen(buf
[u
]) + 1;
50 char *str
= (char *)mem
.xmalloc(len
);
54 for (d_size_t u
= 0; u
< length
; u
++)
71 data
.ptr
[length
++] = ptr
;
79 void reserve(d_size_t nentries
)
81 //printf("Array::reserve: length = %d, data.length = %d, nentries = %d\n", (int)length, (int)data.length, (int)nentries);
82 if (data
.length
- length
< nentries
)
86 // Not properly initialized, someone memset it to zero
87 if (nentries
<= SMALLARRAYCAP
)
89 data
.length
= SMALLARRAYCAP
;
90 data
.ptr
= SMALLARRAYCAP
? &smallarray
[0] : NULL
;
94 data
.length
= nentries
;
95 data
.ptr
= (TYPE
*)mem
.xmalloc(data
.length
* sizeof(TYPE
));
98 else if (data
.length
== SMALLARRAYCAP
)
100 data
.length
= length
+ nentries
;
101 data
.ptr
= (TYPE
*)mem
.xmalloc(data
.length
* sizeof(TYPE
));
102 memcpy(data
.ptr
, &smallarray
[0], length
* sizeof(TYPE
));
106 /* Increase size by 1.5x to avoid excessive memory fragmentation
108 d_size_t increment
= length
/ 2;
109 if (nentries
> increment
) // if 1.5 is not enough
110 increment
= nentries
;
111 data
.length
= length
+ increment
;
112 data
.ptr
= (TYPE
*)mem
.xrealloc(data
.ptr
, data
.length
* sizeof(TYPE
));
117 void remove(d_size_t i
)
120 memmove(data
.ptr
+ i
, data
.ptr
+ i
+ 1, (length
- i
- 1) * sizeof(TYPE
));
124 void insert(d_size_t index
, Array
*a
)
128 d_size_t d
= a
->length
;
131 memmove(data
.ptr
+ index
+ d
, data
.ptr
+ index
, (length
- index
) * sizeof(TYPE
));
132 memcpy(data
.ptr
+ index
, a
->data
.ptr
, d
* sizeof(TYPE
));
137 void insert(d_size_t index
, TYPE ptr
)
140 memmove(data
.ptr
+ index
+ 1, data
.ptr
+ index
, (length
- index
) * sizeof(TYPE
));
141 data
.ptr
[index
] = ptr
;
145 void setDim(d_size_t newdim
)
149 reserve(newdim
- length
);
154 d_size_t
find(TYPE ptr
) const
156 for (d_size_t i
= 0; i
< length
; i
++)
158 if (data
.ptr
[i
] == ptr
)
164 bool contains(TYPE ptr
) const
166 return find(ptr
) != SIZE_MAX
;
169 TYPE
& operator[] (d_size_t index
)
172 assert(index
< length
);
174 return data
.ptr
[index
];
184 Array
*a
= new Array();
186 memcpy(a
->data
.ptr
, data
.ptr
, length
* sizeof(TYPE
));
193 memmove(data
.ptr
+ 1, data
.ptr
, length
* sizeof(TYPE
));
200 memset(data
.ptr
, 0, length
* sizeof(TYPE
));
205 return data
.ptr
[--length
];