1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 **
10 ** This file declares the functions that deal with plain lists.
11 **
12 ** A plain list is a list that may have holes and may contain elements of
13 ** arbitrary types. A plain list may also have room for elements beyond its
14 ** current logical length. The last position to which an element can be
15 ** assigned without resizing the plain list is called the physical length.
16 **
17 ** This representation is encoded by the functions 'NEW_PLIST', 'GROW_PLIST',
18 ** 'SHRINK_PLIST', 'SET_LEN_PLIST', 'LEN_PLIST', 'SET_ELM_PLIST', and
19 ** 'ELM_PLIST', which are used by the functions in this package and the rest
20 ** of the {\GAP} kernel to access plain lists.
21 **
22 ** This package also contains the list functions for plain lists, which are
23 ** installed in the appropriate tables by 'InitPlist'.
24 */
25
26 #ifndef GAP_PLIST_H
27 #define GAP_PLIST_H
28
29 #include "objects.h"
30
31 /****************************************************************************
32 **
33 *F NEW_PLIST(<type>,<plen>) . . . . . . . . . . . allocate a new plain list
34 **
35 ** 'NEW_PLIST' allocates a new plain list of type <type> that has room for
36 ** at least <plen> elements.
37 **
38 */
NEW_PLIST(UInt type,Int plen)39 EXPORT_INLINE Obj NEW_PLIST(UInt type, Int plen)
40 {
41 GAP_ASSERT(plen >= 0);
42 GAP_ASSERT(plen <= INT_INTOBJ_MAX);
43 GAP_ASSERT(FIRST_PLIST_TNUM <= type && type <= LAST_PLIST_TNUM);
44 Obj bag = NewBag(type, (plen + 1) * sizeof(Obj));
45 ADDR_OBJ(bag)[0] = INTOBJ_INT(0);
46 return bag;
47 }
48
NEW_PLIST_IMM(UInt type,Int plen)49 EXPORT_INLINE Obj NEW_PLIST_IMM(UInt type, Int plen)
50 {
51 return NEW_PLIST(type | IMMUTABLE, plen);
52 }
53
NEW_PLIST_WITH_MUTABILITY(Int mut,UInt type,Int plen)54 EXPORT_INLINE Obj NEW_PLIST_WITH_MUTABILITY(Int mut, UInt type, Int plen)
55 {
56 if (!mut)
57 type |= IMMUTABLE;
58 return NEW_PLIST(type, plen);
59 }
60
61 /****************************************************************************
62 **
63 *F IS_PLIST( <list> ) . . . . . . . . . . . check if <list> is a plain list
64 */
IS_PLIST(Obj list)65 EXPORT_INLINE Int IS_PLIST(Obj list)
66 {
67 return FIRST_PLIST_TNUM <= TNUM_OBJ(list) &&
68 TNUM_OBJ(list) <= LAST_PLIST_TNUM;
69 }
70
71 /****************************************************************************
72 **
73 *F IS_PLIST_OR_POSOBJ( <list> ) . . . . . . . . . . . . check type of <list>
74 **
75 ** Checks if this is 'PLIST'-like.
76 ** This function is used in a GAP_ASSERT checking if calling functions like
77 ** SET_ELM_PLIST is acceptable on an Obj.
78 **
79 ** Unlike IS_PLIST, this function also accepts positional objects
80 ** (which have the same memory layout as plists), as the plist APIs using it
81 ** for assertion checks are in practice invoked on such objects, too.
82 */
IS_PLIST_OR_POSOBJ(Obj list)83 EXPORT_INLINE Int IS_PLIST_OR_POSOBJ(Obj list)
84 {
85 UInt tnum = TNUM_OBJ(list);
86 return (FIRST_PLIST_TNUM <= tnum && tnum <= LAST_PLIST_TNUM) ||
87 tnum == T_POSOBJ;
88 }
89
90
91 /****************************************************************************
92 **
93 *F CAPACITY_PLIST(<list>) . . . . . . . . . . . capacity of a plain list
94 **
95 ** 'CAPACITY_PLIST' returns the maximum capacity of a PLIST.
96 **
97 */
CAPACITY_PLIST(Obj list)98 EXPORT_INLINE Int CAPACITY_PLIST(Obj list)
99 {
100 return SIZE_OBJ(list) / sizeof(Obj) - 1;
101 }
102
103 void GrowPlist(Obj list, UInt need);
104
105 /****************************************************************************
106 **
107 *F GROW_PLIST(<list>,<plen>) . . . . make sure a plain list is large enough
108 **
109 ** 'GROW_PLIST' grows the plain list <list> if necessary to ensure that it
110 ** has room for at least <plen> elements.
111 **
112 */
GROW_PLIST(Obj list,Int plen)113 EXPORT_INLINE void GROW_PLIST(Obj list, Int plen)
114 {
115 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
116 GAP_ASSERT(plen >= 0);
117 if (plen > CAPACITY_PLIST(list)) {
118 GrowPlist(list, plen);
119 }
120 }
121
122
123 /****************************************************************************
124 **
125 *F SHRINK_PLIST(<list>,<plen>) . . . . . . . . . . . . . shrink a plain list
126 **
127 ** 'SHRINK_PLIST' shrinks the plain list <list> if possible so that it has
128 ** still room for at least <plen> elements.
129 **
130 */
SHRINK_PLIST(Obj list,Int plen)131 EXPORT_INLINE void SHRINK_PLIST(Obj list, Int plen)
132 {
133 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
134 GAP_ASSERT(plen >= 0);
135 GAP_ASSERT(plen <= CAPACITY_PLIST(list));
136 ResizeBag(list, (plen + 1) * sizeof(Obj));
137 }
138
139
140 /****************************************************************************
141 **
142 *F SET_LEN_PLIST(<list>,<len>) . . . . . . . set the length of a plain list
143 **
144 ** 'SET_LEN_PLIST' sets the length of the plain list <list> to <len>.
145 **
146 */
SET_LEN_PLIST(Obj list,Int len)147 EXPORT_INLINE void SET_LEN_PLIST(Obj list, Int len)
148 {
149 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
150 GAP_ASSERT(len >= 0);
151 GAP_ASSERT(len <= CAPACITY_PLIST(list));
152 ADDR_OBJ(list)[0] = INTOBJ_INT(len);
153 }
154
155
156 /****************************************************************************
157 **
158 *F LEN_PLIST(<list>) . . . . . . . . . . . . . . . . length of a plain list
159 **
160 ** 'LEN_PLIST' returns the logical length of the list <list> as a C integer.
161 **
162 */
LEN_PLIST(Obj list)163 EXPORT_INLINE Int LEN_PLIST(Obj list)
164 {
165 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
166 return INT_INTOBJ(CONST_ADDR_OBJ(list)[0]);
167 }
168
169
170 /****************************************************************************
171 **
172 *F SET_ELM_PLIST(<list>,<pos>,<val>) . . . assign an element to a plain list
173 **
174 ** 'SET_ELM_PLIST' assigns the value <val> to the plain list <list> at the
175 ** position <pos>. <pos> must be a positive integer less than or equal to
176 ** the length of <list>.
177 **
178 */
SET_ELM_PLIST(Obj list,Int pos,Obj val)179 EXPORT_INLINE void SET_ELM_PLIST(Obj list, Int pos, Obj val)
180 {
181 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
182 GAP_ASSERT(pos >= 1);
183 GAP_ASSERT(pos <= CAPACITY_PLIST(list));
184 ADDR_OBJ(list)[pos] = val;
185 }
186
187 /****************************************************************************
188 **
189 *F ELM_PLIST(<list>,<pos>) . . . . . . . . . . . . . element of a plain list
190 **
191 ** 'ELM_PLIST' return the <pos>-th element of the list <list>. <pos> must
192 ** be a positive integer less than or equal to the physical length of
193 ** <list>. If <list> has no assigned element at position <pos>, 'ELM_PLIST'
194 ** returns 0.
195 */
ELM_PLIST(Obj list,Int pos)196 EXPORT_INLINE Obj ELM_PLIST(Obj list, Int pos)
197 {
198 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
199 GAP_ASSERT(pos >= 1);
200 GAP_ASSERT(pos <= CAPACITY_PLIST(list));
201 return CONST_ADDR_OBJ(list)[pos];
202 }
203
204 /****************************************************************************
205 **
206 *F BASE_PTR_PLIST(<list>) . . . . . . . . . . . . . element of a plain list
207 **
208 ** 'BASE_PTR_PLIST' returns a point to the first element of the plist <list>
209 **
210 ** This point will be invalidated whenever a garbage collection occurs.
211 */
BASE_PTR_PLIST(Obj list)212 EXPORT_INLINE Obj * BASE_PTR_PLIST(Obj list)
213 {
214 GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
215 return ADDR_OBJ(list) + 1;
216 }
217
218 /****************************************************************************
219 **
220 *F IS_DENSE_PLIST( <list> ) . . . . . check if <list> is a dense plain list
221 **
222 ** Note that this only checks for plists that are known to be dense. This is
223 ** very fast. If you want to also handle plists for which it is now known
224 ** whether they are dense or not (i.e. of type 'T_PLIST'),
225 ** use 'IS_DENSE_LIST' instead.
226 */
IS_DENSE_PLIST(Obj list)227 EXPORT_INLINE Int IS_DENSE_PLIST(Obj list)
228 {
229 return T_PLIST_DENSE <= TNUM_OBJ(list) &&
230 TNUM_OBJ(list) <= LAST_PLIST_TNUM;
231 }
232
233 /****************************************************************************
234 **
235 *F IS_PLIST_MUTABLE( <list> ) . . . . . . . . . . . is a plain list mutable
236 */
IS_PLIST_MUTABLE(Obj list)237 EXPORT_INLINE Int IS_PLIST_MUTABLE(Obj list)
238 {
239 GAP_ASSERT(IS_PLIST(list));
240 return !((TNUM_OBJ(list) - T_PLIST) % 2);
241 }
242
243 /****************************************************************************
244 **
245 *F AssPlist( <list>, <pos>, <val>) . . . . . . . . . assign to a plain list
246 */
247 void AssPlist(Obj list, Int pos, Obj val);
248
249 /****************************************************************************
250 **
251 *F PushPlist( <list>, <val> ) . . . . . . . . assign to end of a plain list
252 **
253 ** Note that this function does not adjust the TNUM of the list object. It
254 ** also does not attempt to convert the list to a different representation,
255 ** such as a string or blist. If your need that, use AddList or AddPlist
256 ** instead.
257 **
258 */
PushPlist(Obj list,Obj val)259 EXPORT_INLINE UInt PushPlist(Obj list, Obj val)
260 {
261 const UInt pos = LEN_PLIST(list) + 1;
262 GROW_PLIST(list, pos);
263 SET_LEN_PLIST(list, pos);
264 SET_ELM_PLIST(list, pos, val);
265 if (IS_BAG_REF(val))
266 CHANGED_BAG(list);
267 return pos;
268 }
269
270 /****************************************************************************
271 **
272 *F PopPlist( <list> ) . . . . . . . . . remove last element of a plain list
273 **
274 ** Also returns the removed element. Caller is responsible for ensuring that
275 ** the list is non-empty. Otherwise an assertion may be raised or the plist
276 ** be left in an invalid state.
277 **
278 ** Also clear the slot used by the pop'ed object, to avoid stale references
279 ** preventing the garbage collector from collecting the pop'ed object.
280 **
281 */
PopPlist(Obj list)282 EXPORT_INLINE Obj PopPlist(Obj list)
283 {
284 const UInt pos = LEN_PLIST(list);
285 Obj val = ELM_PLIST(list, pos);
286 SET_LEN_PLIST(list, pos - 1);
287 SET_ELM_PLIST(list, pos, 0);
288 return val;
289 }
290
291
292 /****************************************************************************
293 **
294 *F NewEmptyPlist() . . . . . . . . . . create a new mutable empty plain list
295 */
NewEmptyPlist(void)296 EXPORT_INLINE Obj NewEmptyPlist(void)
297 {
298 return NEW_PLIST(T_PLIST_EMPTY, 0);
299 }
300
301
302 /****************************************************************************
303 **
304 *F NewImmutableEmptyPlist() . . . . . create a new immutable empty plain list
305 */
NewImmutableEmptyPlist(void)306 EXPORT_INLINE Obj NewImmutableEmptyPlist(void)
307 {
308 return NEW_PLIST_IMM(T_PLIST_EMPTY, 0);
309 }
310
311
312 /****************************************************************************
313 **
314 *F NewPlistFromArray(<list>,<length>) . . create a plain list from a C array
315 */
NewPlistFromArray(const Obj * list,Int length)316 EXPORT_INLINE Obj NewPlistFromArray(const Obj * list, Int length)
317 {
318 if (length == 0) {
319 return NewEmptyPlist();
320 }
321
322 Obj o = NEW_PLIST(T_PLIST, length);
323 SET_LEN_PLIST(o, length);
324 memcpy(BASE_PTR_PLIST(o), list, length * sizeof(Obj));
325 CHANGED_BAG(o);
326 return o;
327 }
328
329 /****************************************************************************
330 **
331 *F NewPlistFromArgs(<args...>) . create a plain list from list of arguments
332 **
333 ** This macro turns a variable-length list of macro arguments into an array,
334 ** which is then passed to NewPlistFromArray.
335 **
336 ** __VA_ARGS__ contains the list of arguments given to this macro.
337 ** (Obj[]){ __VA_ARGS__ } creates an array of Obj containing the elements
338 ** of __VA_ARGS__.
339 */
340 #define NewPlistFromArgs(...) \
341 NewPlistFromArray((Obj[]){ __VA_ARGS__ }, \
342 ARRAY_SIZE(((Obj[]){ __VA_ARGS__ })))
343
344
345 /****************************************************************************
346 **
347 *F ShallowCopyPlist( <list>> )
348 */
349 Obj ShallowCopyPlist(Obj list);
350
351
352 /****************************************************************************
353 **
354 *F AssPlistEmpty( <list>, <pos>, <val> ) . . . . . assignment to empty list
355 */
356 void AssPlistEmpty(Obj list, Int pos, Obj val);
357
358 void AssPlistFfe(Obj list, Int pos, Obj val);
359
360 /****************************************************************************
361 **
362 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
363 */
364
365
366 /****************************************************************************
367 **
368 *F InitInfoPlist() . . . . . . . . . . . . . . . . . table of init functions
369 */
370 StructInitInfo * InitInfoPlist ( void );
371
372
373 #endif // GAP_PLIST_H
374