forked from python/cpython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdynarray.c
More file actions
150 lines (132 loc) · 3.38 KB
/
dynarray.c
File metadata and controls
150 lines (132 loc) · 3.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
* Dynamic array implementation.
*/
#include "pycore_dynarray.h"
#include "pycore_pymem.h" // _PyMem_RawStrdup
static inline void
call_deallocator_maybe(_PyDynArray *array, Py_ssize_t index)
{
if (array->deallocator != NULL && array->items[index] != NULL)
{
array->deallocator(array->items[index]);
}
}
int
_PyDynArray_InitWithSize(_PyDynArray *array,
_PyDynArray_Deallocator deallocator,
Py_ssize_t initial)
{
assert(array != NULL);
assert(initial > 0);
void **items = PyMem_RawCalloc(sizeof(void *), initial);
if (items == NULL)
{
return -1;
}
array->capacity = initial;
array->items = items;
array->length = 0;
array->deallocator = deallocator;
return 0;
}
static int
resize_if_needed(_PyDynArray *array)
{
if (array->length == array->capacity)
{
// Need to resize
array->capacity *= 2;
void **new_items = PyMem_RawRealloc(
array->items,
sizeof(void *) * array->capacity);
if (new_items == NULL)
{
return -1;
}
array->items = new_items;
}
return 0;
}
int
_PyDynArray_Append(_PyDynArray *array, void *item)
{
_PyDynArray_ASSERT_VALID(array);
array->items[array->length++] = item;
if (resize_if_needed(array) < 0)
{
array->items[--array->length] = NULL;
return -1;
}
return 0;
}
int
_PyDynArray_Insert(_PyDynArray *array, Py_ssize_t index, void *item)
{
_PyDynArray_ASSERT_VALID(array);
_PyDynArray_ASSERT_INDEX(array, index);
++array->length;
if (resize_if_needed(array) < 0)
{
// Grow the array beforehand, otherwise it's
// going to be a mess putting it back together if
// allocation fails.
--array->length;
return -1;
}
for (Py_ssize_t i = array->length - 1; i > index; --i)
{
array->items[i] = array->items[i - 1];
}
array->items[index] = item;
return 0;
}
void
_PyDynArray_Set(_PyDynArray *array, Py_ssize_t index, void *item)
{
_PyDynArray_ASSERT_VALID(array);
_PyDynArray_ASSERT_INDEX(array, index);
call_deallocator_maybe(array, index);
array->items[index] = item;
}
static void
remove_no_dealloc(_PyDynArray *array, Py_ssize_t index)
{
for (Py_ssize_t i = index; i < array->length - 1; ++i)
{
array->items[i] = array->items[i + 1];
}
--array->length;
}
void
_PyDynArray_Remove(_PyDynArray *array, Py_ssize_t index)
{
_PyDynArray_ASSERT_VALID(array);
_PyDynArray_ASSERT_INDEX(array, index);
call_deallocator_maybe(array, index);
remove_no_dealloc(array, index);
}
void *
_PyDynArray_Pop(_PyDynArray *array, Py_ssize_t index)
{
_PyDynArray_ASSERT_VALID(array);
_PyDynArray_ASSERT_INDEX(array, index);
void *item = array->items[index];
remove_no_dealloc(array, index);
return item;
}
void
_PyDynArray_Clear(_PyDynArray *array)
{
_PyDynArray_ASSERT_VALID(array);
for (Py_ssize_t i = 0; i < array->length; ++i)
{
call_deallocator_maybe(array, i);
}
PyMem_RawFree(array->items);
// It would be nice if others could reuse the allocation for another
// dynarray later, so clear all the fields.
array->items = NULL;
array->length = 0;
array->capacity = 0;
array->deallocator = NULL;
}