1 #ifndef Py_INTERNAL_OBJECT_STACK_H 2 #define Py_INTERNAL_OBJECT_STACK_H 3 4 #include "pycore_freelist.h" // _PyFreeListState 5 6 #ifdef __cplusplus 7 extern "C" { 8 #endif 9 10 #ifndef Py_BUILD_CORE 11 # error "this header requires Py_BUILD_CORE define" 12 #endif 13 14 // _PyObjectStack is a stack of Python objects implemented as a linked list of 15 // fixed size buffers. 16 17 // Chosen so that _PyObjectStackChunk is a power-of-two size. 18 #define _Py_OBJECT_STACK_CHUNK_SIZE 254 19 20 typedef struct _PyObjectStackChunk { 21 struct _PyObjectStackChunk *prev; 22 Py_ssize_t n; 23 PyObject *objs[_Py_OBJECT_STACK_CHUNK_SIZE]; 24 } _PyObjectStackChunk; 25 26 typedef struct _PyObjectStack { 27 _PyObjectStackChunk *head; 28 } _PyObjectStack; 29 30 31 extern _PyObjectStackChunk * 32 _PyObjectStackChunk_New(void); 33 34 extern void 35 _PyObjectStackChunk_Free(_PyObjectStackChunk *); 36 37 // Push an item onto the stack. Return -1 on allocation failure, 0 on success. 38 static inline int _PyObjectStack_Push(_PyObjectStack * stack,PyObject * obj)39_PyObjectStack_Push(_PyObjectStack *stack, PyObject *obj) 40 { 41 _PyObjectStackChunk *buf = stack->head; 42 if (buf == NULL || buf->n == _Py_OBJECT_STACK_CHUNK_SIZE) { 43 buf = _PyObjectStackChunk_New(); 44 if (buf == NULL) { 45 return -1; 46 } 47 buf->prev = stack->head; 48 buf->n = 0; 49 stack->head = buf; 50 } 51 52 assert(buf->n >= 0 && buf->n < _Py_OBJECT_STACK_CHUNK_SIZE); 53 buf->objs[buf->n] = obj; 54 buf->n++; 55 return 0; 56 } 57 58 // Pop the top item from the stack. Return NULL if the stack is empty. 59 static inline PyObject * _PyObjectStack_Pop(_PyObjectStack * stack)60_PyObjectStack_Pop(_PyObjectStack *stack) 61 { 62 _PyObjectStackChunk *buf = stack->head; 63 if (buf == NULL) { 64 return NULL; 65 } 66 assert(buf->n > 0 && buf->n <= _Py_OBJECT_STACK_CHUNK_SIZE); 67 buf->n--; 68 PyObject *obj = buf->objs[buf->n]; 69 if (buf->n == 0) { 70 stack->head = buf->prev; 71 _PyObjectStackChunk_Free(buf); 72 } 73 return obj; 74 } 75 76 static inline Py_ssize_t _PyObjectStack_Size(_PyObjectStack * stack)77_PyObjectStack_Size(_PyObjectStack *stack) 78 { 79 Py_ssize_t size = 0; 80 for (_PyObjectStackChunk *buf = stack->head; buf != NULL; buf = buf->prev) { 81 size += buf->n; 82 } 83 return size; 84 } 85 86 // Merge src into dst, leaving src empty 87 extern void 88 _PyObjectStack_Merge(_PyObjectStack *dst, _PyObjectStack *src); 89 90 // Remove all items from the stack 91 extern void 92 _PyObjectStack_Clear(_PyObjectStack *stack); 93 94 #ifdef __cplusplus 95 } 96 #endif 97 #endif // !Py_INTERNAL_OBJECT_STACK_H 98