summaryrefslogtreecommitdiff
path: root/blist/blist.h
diff options
context:
space:
mode:
Diffstat (limited to 'blist/blist.h')
-rw-r--r--blist/blist.h248
1 files changed, 248 insertions, 0 deletions
diff --git a/blist/blist.h b/blist/blist.h
new file mode 100644
index 0000000..7476fe1
--- /dev/null
+++ b/blist/blist.h
@@ -0,0 +1,248 @@
+
+/* List object interface */
+
+/*
+Another generally useful object type is an list of object pointers.
+This is a mutable type: the list items can be changed, and items can be
+added or removed. Out-of-range indices or non-list objects are ignored.
+
+*** WARNING *** PyList_SetItem does not increment the new item's reference
+count, but does decrement the reference count of the item it replaces,
+if not nil. It does *decrement* the reference count if it is *not*
+inserted in the list. Similarly, PyList_GetItem does not increment the
+returned item's reference count.
+*/
+
+/**********************************************************************
+ * *
+ * PLEASE READ blist.rst BEFORE MODIFYING THIS CODE *
+ * *
+ **********************************************************************/
+
+#ifndef Py_BLISTOBJECT_H
+#define Py_BLISTOBJECT_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#if 0
+#define BLIST_IN_PYTHON /* Define if building BList into Python */
+#endif
+
+/* pyport.h includes similar defines, but they're broken and never use
+ * "inline" except on Windows :-( */
+#if defined(_MSC_VER)
+/* ignore warnings if the compiler decides not to inline a function */
+#pragma warning(disable: 4710)
+/* fastest possible local call under MSVC */
+#define BLIST_LOCAL(type) static type __fastcall
+#define BLIST_LOCAL_INLINE(type) static __inline type __fastcall
+#elif defined(__GNUC__)
+#if defined(__i386__)
+#define BLIST_LOCAL(type) static type __attribute__((fastcall))
+#define BLIST_LOCAL_INLINE(type) static inline __attribute__((fastcall)) type
+#else
+#define BLIST_LOCAL(type) static type
+#define BLIST_LOCAL_INLINE(type) static inline type
+#endif
+#else
+#define BLIST_LOCAL(type) static type
+#define BLIST_LOCAL_INLINE(type) static type
+#endif
+
+#ifndef LIMIT
+#define LIMIT (128) /* Good performance value */
+#if 0
+#define LIMIT (8) /* Maximum size, currently low (for test purposes) */
+#endif
+#endif
+#define HALF (LIMIT/2) /* Minimum size */
+#define MAX_HEIGHT (16) /* ceil(log(PY_SSIZE_T_MAX)/log(HALF)); */
+#if LIMIT & 1
+#error LIMIT must be divisible by 2
+#endif
+#if LIMIT < 8
+#error LIMIT must be at least 8
+#endif
+#define INDEX_FACTOR (HALF)
+
+typedef struct PyBList {
+ PyObject_HEAD
+ Py_ssize_t n; /* Total # of user-object descendents */
+ int num_children; /* Number of immediate children */
+ int leaf; /* Boolean value */
+ PyObject **children; /* Immediate children */
+} PyBList;
+
+typedef struct PyBListRoot {
+ PyObject_HEAD
+#define BLIST_FIRST_FIELD n
+ Py_ssize_t n; /* Total # of user-object descendents */
+ int num_children; /* Number of immediate children */
+ int leaf; /* Boolean value */
+ PyObject **children; /* Immediate children */
+
+ PyBList **index_list;
+ Py_ssize_t *offset_list;
+ unsigned *setclean_list; /* contains index_allocated _bits_ */
+ Py_ssize_t index_allocated;
+ Py_ssize_t *dirty;
+ Py_ssize_t dirty_length;
+ Py_ssize_t dirty_root;
+ Py_ssize_t free_root;
+
+#ifdef Py_DEBUG
+ Py_ssize_t last_n; /* For debug */
+#endif
+} PyBListRoot;
+
+#define PyBList_GET_ITEM(op, i) (((PyBList *)(op))->leaf ? (((PyBList *)(op))->children[(i)]) : _PyBList_GET_ITEM_FAST2((PyBListRoot*) (op), (i)))
+
+/************************************************************************
+ * Code used when building BList into the interpreter
+ */
+
+#ifdef BLIST_IN_PYTHON
+int PyList_Init1(void);
+int PyList_Init2(void);
+typedef PyBListRoot PyListObject;
+
+//PyAPI_DATA(PyTypeObject) PyList_Type;
+
+PyAPI_DATA(PyTypeObject) PyBList_Type;
+PyAPI_DATA(PyTypeObject) PyRootBList_Type;
+#define PyList_Type PyRootBList_Type
+
+#define PyList_Check(op) \
+ PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LIST_SUBCLASS)
+#define PyList_CheckExact(op) ((op)->ob_type == &PyRootBList_Type)
+
+PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);
+PyAPI_FUNC(Py_ssize_t) PyList_Size(PyObject *);
+PyAPI_FUNC(PyObject *) PyList_GetItem(PyObject *, Py_ssize_t);
+PyAPI_FUNC(int) PyList_SetItem(PyObject *, Py_ssize_t, PyObject *);
+PyAPI_FUNC(int) PyList_Insert(PyObject *, Py_ssize_t, PyObject *);
+PyAPI_FUNC(int) PyList_Append(PyObject *, PyObject *);
+PyAPI_FUNC(PyObject *) PyList_GetSlice(PyObject *, Py_ssize_t, Py_ssize_t);
+PyAPI_FUNC(int) PyList_SetSlice(PyObject *, Py_ssize_t, Py_ssize_t, PyObject *);
+PyAPI_FUNC(int) PyList_Sort(PyObject *);
+PyAPI_FUNC(int) PyList_Reverse(PyObject *);
+PyAPI_FUNC(PyObject *) PyList_AsTuple(PyObject *);
+PyAPI_FUNC(PyObject *) _PyList_Extend(PyBListRoot *, PyObject *);
+
+PyAPI_FUNC(void) _PyList_SetItemFast(PyObject *, Py_ssize_t, PyObject *);
+
+/* Macro, trading safety for speed */
+#define PyList_GET_ITEM(op, i) (PyBList_GET_ITEM((op), (i)))
+//#define PyList_SET_ITEM(op, i, v) (((PyBList *)(op))->leaf ? (void) (((PyBList *)(op))->children[(i)] = (v)) : (void) _PyList_SetItemFast((PyObject *) (op), (i), (v)))
+#define PyList_SET_ITEM(self, i, v) (((PyBList *)self)->leaf ? (void) (((PyBList*)self)->children[(i)] = (v)) : (void) blist_ass_item_return2((PyBListRoot*)(self), (i), (v)))
+
+//#define PyList_GET_ITEM(op, i) PyList_GetItem((PyObject*) (op), (i))
+//#define PyList_SET_ITEM(op, i, v) _PyList_SetItemFast((PyObject *) (op), (i), (v))
+#define PyList_GET_SIZE(op) ({ assert(PyList_Check(op)); (((PyBList *)(op))->n); })
+
+#define PyList_IS_LEAF(op) ({ assert(PyList_Check(op)); (((PyBList *) (op))->leaf); })
+
+PyAPI_FUNC(PyObject *) _PyBList_GetItemFast3(PyBListRoot *, Py_ssize_t);
+
+PyAPI_FUNC(PyObject *) blist_ass_item_return_slow(PyBListRoot *root, Py_ssize_t i, PyObject *v);
+PyAPI_FUNC(PyObject *) ext_make_clean_set(PyBListRoot *root, Py_ssize_t i, PyObject *v);
+#else
+PyObject *_PyBList_GetItemFast3(PyBListRoot *, Py_ssize_t);
+PyObject *blist_ass_item_return_slow(PyBListRoot *root, Py_ssize_t i, PyObject *v);
+PyObject *ext_make_clean_set(PyBListRoot *root, Py_ssize_t i, PyObject *v);
+#endif
+
+#define INDEX_FACTOR (HALF)
+
+/* This should only be called if we know the root is not a leaf */
+/* inlining a common case for speed */
+BLIST_LOCAL_INLINE(PyObject *)
+_PyBList_GET_ITEM_FAST2(PyBListRoot *root, Py_ssize_t i)
+{
+ Py_ssize_t ioffset;
+ Py_ssize_t offset;
+ PyBList *p;
+
+ assert(!root->leaf);
+ assert(i >= 0);
+ assert(i < root->n);
+
+ if (root->dirty_root >= -1 /* DIRTY */)
+ return _PyBList_GetItemFast3(root, i);
+
+ ioffset = i / INDEX_FACTOR;
+ offset = root->offset_list[ioffset];
+ p = root->index_list[ioffset];
+
+ if (i < offset + p->n)
+ return p->children[i - offset];
+ ioffset++;
+ offset = root->offset_list[ioffset];
+ p = root->index_list[ioffset];
+ return p->children[i - offset];
+}
+
+#define SETCLEAN_LEN(index_allocated) ((((index_allocated)-1) >> SETCLEAN_SHIFT)+1)
+#if SIZEOF_INT == 4
+#define SETCLEAN_SHIFT (5u)
+#define SETCLEAN_MASK (0x1fu)
+#elif SIZEOF_INT == 8
+#define SETCLEAN_SHIFT (6u)
+#define SETCLEAN_MASK (0x3fu)
+#else
+#error Unknown sizeof(unsigned)
+#endif
+
+#define SET_BIT(setclean_list, i) (setclean_list[(i) >> SETCLEAN_SHIFT] |= (1u << ((i) & SETCLEAN_MASK)))
+#define CLEAR_BIT(setclean_list, i) (setclean_list[(i) >> SETCLEAN_SHIFT] &= ~(1u << ((i) & SETCLEAN_MASK)))
+#define GET_BIT(setclean_list, i) (setclean_list[(i) >> SETCLEAN_SHIFT] & (1u << ((i) & SETCLEAN_MASK)))
+
+BLIST_LOCAL_INLINE(PyObject *)
+blist_ass_item_return2(PyBListRoot *root, Py_ssize_t i, PyObject *v)
+{
+ PyObject *rv;
+ Py_ssize_t offset;
+ PyBList *p;
+ Py_ssize_t ioffset = i / INDEX_FACTOR;
+
+ assert(i >= 0);
+ assert(i < root->n);
+ assert(!root->leaf);
+
+ if (root->dirty_root >= -1 /* DIRTY */
+ || !GET_BIT(root->setclean_list, ioffset))
+ return blist_ass_item_return_slow(root, i, v);
+
+ offset = root->offset_list[ioffset];
+ p = root->index_list[ioffset];
+ assert(i >= offset);
+ assert(p);
+ assert(p->leaf);
+ if (i < offset + p->n) {
+ good:
+ /* Py_REFCNT(p) == 1, generally, but see comment in
+ * blist_ass_item_return_slow for caveats */
+ rv = p->children[i - offset];
+ p->children[i - offset] = v;
+ } else if (!GET_BIT(root->setclean_list, ioffset+1)) {
+ return ext_make_clean_set(root, i, v);
+ } else {
+ ioffset++;
+ assert(ioffset < root->index_allocated);
+ offset = root->offset_list[ioffset];
+ p = root->index_list[ioffset];
+ assert(p);
+ assert(p->leaf);
+ assert(i < offset + p->n);
+
+ goto good;
+ }
+
+ return rv;
+}
+
+#ifdef __cplusplus
+}
+#endif
+#endif /* !Py_BLISTOBJECT_H */
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-18 09:54:27 +0000