diff options
Diffstat (limited to 'blist/blist.h')
-rw-r--r-- | blist/blist.h | 248 |
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 */ |