/**************************************************************************** ** ** This file is part of GAP, a system for computational discrete algebra. ** ** Copyright of GAP belongs to its developers, whose names are too numerous ** to list here. Please refer to the COPYRIGHT file for details. ** ** SPDX-License-Identifier: GPL-2.0-or-later ** ** This file declares the functions that deal with plain lists. ** ** A plain list is a list that may have holes and may contain elements of ** arbitrary types. A plain list may also have room for elements beyond its ** current logical length. The last position to which an element can be ** assigned without resizing the plain list is called the physical length. ** ** This representation is encoded by the functions 'NEW_PLIST', 'GROW_PLIST', ** 'SHRINK_PLIST', 'SET_LEN_PLIST', 'LEN_PLIST', 'SET_ELM_PLIST', and ** 'ELM_PLIST', which are used by the functions in this package and the rest ** of the {\GAP} kernel to access plain lists. ** ** This package also contains the list functions for plain lists, which are ** installed in the appropriate tables by 'InitPlist'.
*/
#ifndef GAP_PLIST_H #define GAP_PLIST_H
#include"objects.h"
#include <string.h> // for memcpy
/**************************************************************************** ** *F NEW_PLIST(<type>,<plen>) . . . . . . . . . . . allocate a new plain list ** ** 'NEW_PLIST' allocates a new plain list of type <type> that has room for ** at least <plen> elements. **
*/
EXPORT_INLINE Obj NEW_PLIST(UInt type, Int plen)
{
GAP_ASSERT(plen >= 0);
GAP_ASSERT(plen <= INT_INTOBJ_MAX);
GAP_ASSERT(FIRST_PLIST_TNUM <= type && type <= LAST_PLIST_TNUM);
Obj bag = NewBag(type, (plen + 1) * sizeof(Obj));
ADDR_OBJ(bag)[0] = INTOBJ_INT(0); return bag;
}
EXPORT_INLINE Obj NEW_PLIST_WITH_MUTABILITY(Int mut, UInt type, Int plen)
{ if (!mut)
type |= IMMUTABLE; return NEW_PLIST(type, plen);
}
/**************************************************************************** ** *F IS_PLIST( <list> ) . . . . . . . . . . . check if <list> is a plain list
*/
EXPORT_INLINE BOOL IS_PLIST(Obj list)
{ return FIRST_PLIST_TNUM <= TNUM_OBJ(list) &&
TNUM_OBJ(list) <= LAST_PLIST_TNUM;
}
/**************************************************************************** ** *F IS_PLIST_OR_POSOBJ( <list> ) . . . . . . . . . . . . check type of <list> ** ** Checks if this is 'PLIST'-like. ** This function is used in a GAP_ASSERT checking if calling functions like ** SET_ELM_PLIST is acceptable on an Obj. ** ** Unlike IS_PLIST, this function also accepts positional objects ** (which have the same memory layout as plists), as the plist APIs using it ** for assertion checks are in practice invoked on such objects, too.
*/
EXPORT_INLINE BOOL IS_PLIST_OR_POSOBJ(Obj list)
{
UInt tnum = TNUM_OBJ(list); return (FIRST_PLIST_TNUM <= tnum && tnum <= LAST_PLIST_TNUM) ||
tnum == T_POSOBJ;
}
/**************************************************************************** ** *F CAPACITY_PLIST(<list>) . . . . . . . . . . . capacity of a plain list ** ** 'CAPACITY_PLIST' returns the maximum capacity of a PLIST. **
*/
EXPORT_INLINE Int CAPACITY_PLIST(Obj list)
{ return SIZE_OBJ(list) / sizeof(Obj) - 1;
}
void GrowPlist(Obj list, UInt need);
/**************************************************************************** ** *F GROW_PLIST(<list>,<plen>) . . . . make sure a plain list is large enough ** ** 'GROW_PLIST' grows the plain list <list> if necessary to ensure that it ** has room for at least <plen> elements. **
*/
EXPORT_INLINE void GROW_PLIST(Obj list, Int plen)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
GAP_ASSERT(plen >= 0); if (plen > CAPACITY_PLIST(list)) {
GrowPlist(list, plen);
}
}
/**************************************************************************** ** *F SHRINK_PLIST(<list>,<plen>) . . . . . . . . . . . . . shrink a plain list ** ** 'SHRINK_PLIST' shrinks the plain list <list> if possible so that it has ** still room for at least <plen> elements. **
*/
EXPORT_INLINE void SHRINK_PLIST(Obj list, Int plen)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
GAP_ASSERT(plen >= 0);
GAP_ASSERT(plen <= CAPACITY_PLIST(list));
ResizeBag(list, (plen + 1) * sizeof(Obj));
}
/**************************************************************************** ** *F SET_LEN_PLIST(<list>,<len>) . . . . . . . set the length of a plain list ** ** 'SET_LEN_PLIST' sets the length of the plain list <list> to <len>. **
*/
EXPORT_INLINE void SET_LEN_PLIST(Obj list, Int len)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
GAP_ASSERT(len >= 0);
GAP_ASSERT(len <= CAPACITY_PLIST(list));
ADDR_OBJ(list)[0] = INTOBJ_INT(len);
}
/**************************************************************************** ** *F LEN_PLIST(<list>) . . . . . . . . . . . . . . . . length of a plain list ** ** 'LEN_PLIST' returns the logical length of the list <list> as a C integer. **
*/
EXPORT_INLINE Int LEN_PLIST(Obj list)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list)); return INT_INTOBJ(CONST_ADDR_OBJ(list)[0]);
}
/**************************************************************************** ** *F SET_ELM_PLIST(<list>,<pos>,<val>) . . . assign an element to a plain list ** ** 'SET_ELM_PLIST' assigns the value <val> to the plain list <list> at the ** position <pos>. <pos> must be a positive integer less than or equal to ** the length of <list>. **
*/
EXPORT_INLINE void SET_ELM_PLIST(Obj list, Int pos, Obj val)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
GAP_ASSERT(pos >= 1);
GAP_ASSERT(pos <= CAPACITY_PLIST(list));
ADDR_OBJ(list)[pos] = val;
}
/**************************************************************************** ** *F ELM_PLIST(<list>,<pos>) . . . . . . . . . . . . . element of a plain list ** ** 'ELM_PLIST' return the <pos>-th element of the list <list>. <pos> must ** be a positive integer less than or equal to the physical length of ** <list>. If <list> has no assigned element at position <pos>, 'ELM_PLIST' ** returns 0.
*/
EXPORT_INLINE Obj ELM_PLIST(Obj list, Int pos)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list));
GAP_ASSERT(pos >= 1);
GAP_ASSERT(pos <= CAPACITY_PLIST(list)); return CONST_ADDR_OBJ(list)[pos];
}
/**************************************************************************** ** *F BASE_PTR_PLIST(<list>) . . . . . . . . . . . . . element of a plain list ** ** 'BASE_PTR_PLIST' returns a point to the first element of the plist <list> ** ** This point will be invalidated whenever a garbage collection occurs.
*/
EXPORT_INLINE Obj * BASE_PTR_PLIST(Obj list)
{
GAP_ASSERT(IS_PLIST_OR_POSOBJ(list)); return ADDR_OBJ(list) + 1;
}
/**************************************************************************** ** *F IS_DENSE_PLIST( <list> ) . . . . . check if <list> is a dense plain list ** ** Note that this only checks for plists that are known to be dense. This is ** very fast. If you want to also handle plists for which it is now known ** whether they are dense or not (i.e. of type 'T_PLIST'), ** use 'IS_DENSE_LIST' instead.
*/
EXPORT_INLINE BOOL IS_DENSE_PLIST(Obj list)
{ return T_PLIST_DENSE <= TNUM_OBJ(list) &&
TNUM_OBJ(list) <= LAST_PLIST_TNUM;
}
/**************************************************************************** ** *F AssPlist( <list>, <pos>, <val>) . . . . . . . . . assign to a plain list
*/ void AssPlist(Obj list, Int pos, Obj val);
/**************************************************************************** ** *F PushPlist( <list>, <val> ) . . . . . . . . assign to end of a plain list ** ** Note that this function does not adjust the TNUM of the list object. It ** also does not attempt to convert the list to a different representation, ** such as a string or blist. If your need that, use AddList or AddPlist ** instead. **
*/
EXPORT_INLINE UInt PushPlist(Obj list, Obj val)
{ const UInt pos = LEN_PLIST(list) + 1;
GROW_PLIST(list, pos);
SET_LEN_PLIST(list, pos);
SET_ELM_PLIST(list, pos, val); if (IS_BAG_REF(val))
CHANGED_BAG(list); return pos;
}
/**************************************************************************** ** *F PopPlist( <list> ) . . . . . . . . . remove last element of a plain list ** ** Also returns the removed element. Caller is responsible for ensuring that ** the list is non-empty. Otherwise an assertion may be raised or the plist ** be left in an invalid state. ** ** Also clear the slot used by the pop'ed object, to avoid stale references ** preventing the garbage collector from collecting the pop'ed object. **
*/
EXPORT_INLINE Obj PopPlist(Obj list)
{ const UInt pos = LEN_PLIST(list);
Obj val = ELM_PLIST(list, pos);
SET_LEN_PLIST(list, pos - 1);
SET_ELM_PLIST(list, pos, 0); return val;
}
/**************************************************************************** ** *F NewEmptyPlist() . . . . . . . . . . create a new mutable empty plain list
*/
EXPORT_INLINE Obj NewEmptyPlist(void)
{ return NEW_PLIST(T_PLIST_EMPTY, 0);
}
/**************************************************************************** ** *F NewImmutableEmptyPlist() . . . . . create a new immutable empty plain list
*/
EXPORT_INLINE Obj NewImmutableEmptyPlist(void)
{ return NEW_PLIST_IMM(T_PLIST_EMPTY, 0);
}
/**************************************************************************** ** *F NewPlistFromArray(<list>,<length>) . . create a plain list from a C array
*/
EXPORT_INLINE Obj NewPlistFromArray(const Obj * list, Int length)
{ if (length == 0) { return NewEmptyPlist();
}
/**************************************************************************** ** *F NewPlistFromArgs(<args...>) . create a plain list from list of arguments ** ** NewPlistFromArgs turns a variable-length list of arguments into ** an array, which is then passed to NewPlistFromArray. ** ** There is no (nice) single implementation of NewPlistFromArgs that works ** in both C and C++, so there are two separate implementations.
*/ #ifdef __cplusplus
// For C++, we use a variadic template function (requires C++11) extern"C++"template <typename... Ts>
Obj NewPlistFromArgs(Ts... args)
{ constint size = sizeof...(args);
Obj res[size] = { args... }; return NewPlistFromArray(res, size);
} #else
// For C, we use a variadic macro: __VA_ARGS__ contains the list of // arguments given to this macro. (Obj[]){ __VA_ARGS__ } creates an // array of Obj containing the elements of __VA_ARGS__. #define NewPlistFromArgs(...) \
NewPlistFromArray((Obj[]){ __VA_ARGS__ }, \
ARRAY_SIZE(((Obj[]){ __VA_ARGS__ }))) #endif
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
