1/* Generated by Cython 0.17.4 on Sun Feb 24 19:48:34 2013 */ 2 3#define PY_SSIZE_T_CLEAN 4#include "Python.h" 5#ifndef Py_PYTHON_H 6 #error Python headers needed to compile C extensions, please install development version of Python. 7#elif PY_VERSION_HEX < 0x02040000 8 #error Cython requires Python 2.4+. 9#else 10#include <stddef.h> /* For offsetof */ 11#ifndef offsetof 12#define offsetof(type, member) ( (size_t) & ((type*)0) -> member ) 13#endif 14#if !defined(WIN32) && !defined(MS_WINDOWS) 15 #ifndef __stdcall 16 #define __stdcall 17 #endif 18 #ifndef __cdecl 19 #define __cdecl 20 #endif 21 #ifndef __fastcall 22 #define __fastcall 23 #endif 24#endif 25#ifndef DL_IMPORT 26 #define DL_IMPORT(t) t 27#endif 28#ifndef DL_EXPORT 29 #define DL_EXPORT(t) t 30#endif 31#ifndef PY_LONG_LONG 32 #define PY_LONG_LONG LONG_LONG 33#endif 34#ifndef Py_HUGE_VAL 35 #define Py_HUGE_VAL HUGE_VAL 36#endif 37#ifdef PYPY_VERSION 38#define CYTHON_COMPILING_IN_PYPY 1 39#define CYTHON_COMPILING_IN_CPYTHON 0 40#else 41#define CYTHON_COMPILING_IN_PYPY 0 42#define CYTHON_COMPILING_IN_CPYTHON 1 43#endif 44#if PY_VERSION_HEX < 0x02050000 45 typedef int Py_ssize_t; 46 #define PY_SSIZE_T_MAX INT_MAX 47 #define PY_SSIZE_T_MIN INT_MIN 48 #define PY_FORMAT_SIZE_T "" 49 #define CYTHON_FORMAT_SSIZE_T "" 50 #define PyInt_FromSsize_t(z) PyInt_FromLong(z) 51 #define PyInt_AsSsize_t(o) __Pyx_PyInt_AsInt(o) 52 #define PyNumber_Index(o) ((PyNumber_Check(o) && !PyFloat_Check(o)) ? PyNumber_Int(o) : \ 53 (PyErr_Format(PyExc_TypeError, \ 54 "expected index value, got %.200s", Py_TYPE(o)->tp_name), \ 55 (PyObject*)0)) 56 #define __Pyx_PyIndex_Check(o) (PyNumber_Check(o) && !PyFloat_Check(o) && \ 57 !PyComplex_Check(o)) 58 #define PyIndex_Check __Pyx_PyIndex_Check 59 #define PyErr_WarnEx(category, message, stacklevel) PyErr_Warn(category, message) 60 #define __PYX_BUILD_PY_SSIZE_T "i" 61#else 62 #define __PYX_BUILD_PY_SSIZE_T "n" 63 #define CYTHON_FORMAT_SSIZE_T "z" 64 #define __Pyx_PyIndex_Check PyIndex_Check 65#endif 66#if PY_VERSION_HEX < 0x02060000 67 #define Py_REFCNT(ob) (((PyObject*)(ob))->ob_refcnt) 68 #define Py_TYPE(ob) (((PyObject*)(ob))->ob_type) 69 #define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size) 70 #define PyVarObject_HEAD_INIT(type, size) \ 71 PyObject_HEAD_INIT(type) size, 72 #define PyType_Modified(t) 73 typedef struct { 74 void *buf; 75 PyObject *obj; 76 Py_ssize_t len; 77 Py_ssize_t itemsize; 78 int readonly; 79 int ndim; 80 char *format; 81 Py_ssize_t *shape; 82 Py_ssize_t *strides; 83 Py_ssize_t *suboffsets; 84 void *internal; 85 } Py_buffer; 86 #define PyBUF_SIMPLE 0 87 #define PyBUF_WRITABLE 0x0001 88 #define PyBUF_FORMAT 0x0004 89 #define PyBUF_ND 0x0008 90 #define PyBUF_STRIDES (0x0010 | PyBUF_ND) 91 #define PyBUF_C_CONTIGUOUS (0x0020 | PyBUF_STRIDES) 92 #define PyBUF_F_CONTIGUOUS (0x0040 | PyBUF_STRIDES) 93 #define PyBUF_ANY_CONTIGUOUS (0x0080 | PyBUF_STRIDES) 94 #define PyBUF_INDIRECT (0x0100 | PyBUF_STRIDES) 95 #define PyBUF_RECORDS (PyBUF_STRIDES | PyBUF_FORMAT | PyBUF_WRITABLE) 96 #define PyBUF_FULL (PyBUF_INDIRECT | PyBUF_FORMAT | PyBUF_WRITABLE) 97 typedef int (*getbufferproc)(PyObject *, Py_buffer *, int); 98 typedef void (*releasebufferproc)(PyObject *, Py_buffer *); 99#endif 100#if PY_MAJOR_VERSION < 3 101 #define __Pyx_BUILTIN_MODULE_NAME "__builtin__" 102 #define __Pyx_PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) \ 103 PyCode_New(a, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) 104#else 105 #define __Pyx_BUILTIN_MODULE_NAME "builtins" 106 #define __Pyx_PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) \ 107 PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) 108#endif 109#if PY_MAJOR_VERSION < 3 && PY_MINOR_VERSION < 6 110 #define PyUnicode_FromString(s) PyUnicode_Decode(s, strlen(s), "UTF-8", "strict") 111#endif 112#if PY_MAJOR_VERSION >= 3 113 #define Py_TPFLAGS_CHECKTYPES 0 114 #define Py_TPFLAGS_HAVE_INDEX 0 115#endif 116#if (PY_VERSION_HEX < 0x02060000) || (PY_MAJOR_VERSION >= 3) 117 #define Py_TPFLAGS_HAVE_NEWBUFFER 0 118#endif 119#if PY_VERSION_HEX > 0x03030000 && defined(PyUnicode_KIND) 120 #define CYTHON_PEP393_ENABLED 1 121 #define __Pyx_PyUnicode_READY(op) (likely(PyUnicode_IS_READY(op)) ? \ 122 0 : _PyUnicode_Ready((PyObject *)(op))) 123 #define __Pyx_PyUnicode_GET_LENGTH(u) PyUnicode_GET_LENGTH(u) 124 #define __Pyx_PyUnicode_READ_CHAR(u, i) PyUnicode_READ_CHAR(u, i) 125 #define __Pyx_PyUnicode_READ(k, d, i) PyUnicode_READ(k, d, i) 126#else 127 #define CYTHON_PEP393_ENABLED 0 128 #define __Pyx_PyUnicode_READY(op) (0) 129 #define __Pyx_PyUnicode_GET_LENGTH(u) PyUnicode_GET_SIZE(u) 130 #define __Pyx_PyUnicode_READ_CHAR(u, i) ((Py_UCS4)(PyUnicode_AS_UNICODE(u)[i])) 131 #define __Pyx_PyUnicode_READ(k, d, i) ((k=k), (Py_UCS4)(((Py_UNICODE*)d)[i])) 132#endif 133#if PY_MAJOR_VERSION >= 3 134 #define PyBaseString_Type PyUnicode_Type 135 #define PyStringObject PyUnicodeObject 136 #define PyString_Type PyUnicode_Type 137 #define PyString_Check PyUnicode_Check 138 #define PyString_CheckExact PyUnicode_CheckExact 139#endif 140#if PY_VERSION_HEX < 0x02060000 141 #define PyBytesObject PyStringObject 142 #define PyBytes_Type PyString_Type 143 #define PyBytes_Check PyString_Check 144 #define PyBytes_CheckExact PyString_CheckExact 145 #define PyBytes_FromString PyString_FromString 146 #define PyBytes_FromStringAndSize PyString_FromStringAndSize 147 #define PyBytes_FromFormat PyString_FromFormat 148 #define PyBytes_DecodeEscape PyString_DecodeEscape 149 #define PyBytes_AsString PyString_AsString 150 #define PyBytes_AsStringAndSize PyString_AsStringAndSize 151 #define PyBytes_Size PyString_Size 152 #define PyBytes_AS_STRING PyString_AS_STRING 153 #define PyBytes_GET_SIZE PyString_GET_SIZE 154 #define PyBytes_Repr PyString_Repr 155 #define PyBytes_Concat PyString_Concat 156 #define PyBytes_ConcatAndDel PyString_ConcatAndDel 157#endif 158#if PY_VERSION_HEX < 0x02060000 159 #define PySet_Check(obj) PyObject_TypeCheck(obj, &PySet_Type) 160 #define PyFrozenSet_Check(obj) PyObject_TypeCheck(obj, &PyFrozenSet_Type) 161#endif 162#ifndef PySet_CheckExact 163 #define PySet_CheckExact(obj) (Py_TYPE(obj) == &PySet_Type) 164#endif 165#define __Pyx_TypeCheck(obj, type) PyObject_TypeCheck(obj, (PyTypeObject *)type) 166#if PY_MAJOR_VERSION >= 3 167 #define PyIntObject PyLongObject 168 #define PyInt_Type PyLong_Type 169 #define PyInt_Check(op) PyLong_Check(op) 170 #define PyInt_CheckExact(op) PyLong_CheckExact(op) 171 #define PyInt_FromString PyLong_FromString 172 #define PyInt_FromUnicode PyLong_FromUnicode 173 #define PyInt_FromLong PyLong_FromLong 174 #define PyInt_FromSize_t PyLong_FromSize_t 175 #define PyInt_FromSsize_t PyLong_FromSsize_t 176 #define PyInt_AsLong PyLong_AsLong 177 #define PyInt_AS_LONG PyLong_AS_LONG 178 #define PyInt_AsSsize_t PyLong_AsSsize_t 179 #define PyInt_AsUnsignedLongMask PyLong_AsUnsignedLongMask 180 #define PyInt_AsUnsignedLongLongMask PyLong_AsUnsignedLongLongMask 181#endif 182#if PY_MAJOR_VERSION >= 3 183 #define PyBoolObject PyLongObject 184#endif 185#if PY_VERSION_HEX < 0x03020000 186 typedef long Py_hash_t; 187 #define __Pyx_PyInt_FromHash_t PyInt_FromLong 188 #define __Pyx_PyInt_AsHash_t PyInt_AsLong 189#else 190 #define __Pyx_PyInt_FromHash_t PyInt_FromSsize_t 191 #define __Pyx_PyInt_AsHash_t PyInt_AsSsize_t 192#endif 193#if (PY_MAJOR_VERSION < 3) || (PY_VERSION_HEX >= 0x03010300) 194 #define __Pyx_PySequence_GetSlice(obj, a, b) PySequence_GetSlice(obj, a, b) 195 #define __Pyx_PySequence_SetSlice(obj, a, b, value) PySequence_SetSlice(obj, a, b, value) 196 #define __Pyx_PySequence_DelSlice(obj, a, b) PySequence_DelSlice(obj, a, b) 197#else 198 #define __Pyx_PySequence_GetSlice(obj, a, b) (unlikely(!(obj)) ? \ 199 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), (PyObject*)0) : \ 200 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_GetSlice(obj, a, b)) : \ 201 (PyErr_Format(PyExc_TypeError, "'%.200s' object is unsliceable", (obj)->ob_type->tp_name), (PyObject*)0))) 202 #define __Pyx_PySequence_SetSlice(obj, a, b, value) (unlikely(!(obj)) ? \ 203 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), -1) : \ 204 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_SetSlice(obj, a, b, value)) : \ 205 (PyErr_Format(PyExc_TypeError, "'%.200s' object doesn't support slice assignment", (obj)->ob_type->tp_name), -1))) 206 #define __Pyx_PySequence_DelSlice(obj, a, b) (unlikely(!(obj)) ? \ 207 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), -1) : \ 208 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_DelSlice(obj, a, b)) : \ 209 (PyErr_Format(PyExc_TypeError, "'%.200s' object doesn't support slice deletion", (obj)->ob_type->tp_name), -1))) 210#endif 211#if PY_MAJOR_VERSION >= 3 212 #define PyMethod_New(func, self, klass) ((self) ? PyMethod_New(func, self) : PyInstanceMethod_New(func)) 213#endif 214#if PY_VERSION_HEX < 0x02050000 215 #define __Pyx_GetAttrString(o,n) PyObject_GetAttrString((o),((char *)(n))) 216 #define __Pyx_SetAttrString(o,n,a) PyObject_SetAttrString((o),((char *)(n)),(a)) 217 #define __Pyx_DelAttrString(o,n) PyObject_DelAttrString((o),((char *)(n))) 218#else 219 #define __Pyx_GetAttrString(o,n) PyObject_GetAttrString((o),(n)) 220 #define __Pyx_SetAttrString(o,n,a) PyObject_SetAttrString((o),(n),(a)) 221 #define __Pyx_DelAttrString(o,n) PyObject_DelAttrString((o),(n)) 222#endif 223#if PY_VERSION_HEX < 0x02050000 224 #define __Pyx_NAMESTR(n) ((char *)(n)) 225 #define __Pyx_DOCSTR(n) ((char *)(n)) 226#else 227 #define __Pyx_NAMESTR(n) (n) 228 #define __Pyx_DOCSTR(n) (n) 229#endif 230 231 232#if PY_MAJOR_VERSION >= 3 233 #define __Pyx_PyNumber_Divide(x,y) PyNumber_TrueDivide(x,y) 234 #define __Pyx_PyNumber_InPlaceDivide(x,y) PyNumber_InPlaceTrueDivide(x,y) 235#else 236 #define __Pyx_PyNumber_Divide(x,y) PyNumber_Divide(x,y) 237 #define __Pyx_PyNumber_InPlaceDivide(x,y) PyNumber_InPlaceDivide(x,y) 238#endif 239 240#ifndef __PYX_EXTERN_C 241 #ifdef __cplusplus 242 #define __PYX_EXTERN_C extern "C" 243 #else 244 #define __PYX_EXTERN_C extern 245 #endif 246#endif 247 248#if defined(WIN32) || defined(MS_WINDOWS) 249#define _USE_MATH_DEFINES 250#endif 251#include <math.h> 252#define __PYX_HAVE__bintrees__qrbtree 253#define __PYX_HAVE_API__bintrees__qrbtree 254#include "ctrees.h" 255#include "stack.h" 256#ifdef _OPENMP 257#include <omp.h> 258#endif /* _OPENMP */ 259 260#ifdef PYREX_WITHOUT_ASSERTIONS 261#define CYTHON_WITHOUT_ASSERTIONS 262#endif 263 264 265/* inline attribute */ 266#ifndef CYTHON_INLINE 267 #if defined(__GNUC__) 268 #define CYTHON_INLINE __inline__ 269 #elif defined(_MSC_VER) 270 #define CYTHON_INLINE __inline 271 #elif defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L 272 #define CYTHON_INLINE inline 273 #else 274 #define CYTHON_INLINE 275 #endif 276#endif 277 278/* unused attribute */ 279#ifndef CYTHON_UNUSED 280# if defined(__GNUC__) 281# if !(defined(__cplusplus)) || (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) 282# define CYTHON_UNUSED __attribute__ ((__unused__)) 283# else 284# define CYTHON_UNUSED 285# endif 286# elif defined(__ICC) || (defined(__INTEL_COMPILER) && !defined(_MSC_VER)) 287# define CYTHON_UNUSED __attribute__ ((__unused__)) 288# else 289# define CYTHON_UNUSED 290# endif 291#endif 292 293typedef struct {PyObject **p; char *s; const long n; const char* encoding; const char is_unicode; const char is_str; const char intern; } __Pyx_StringTabEntry; /*proto*/ 294 295 296/* Type Conversion Predeclarations */ 297 298#define __Pyx_PyBytes_FromUString(s) PyBytes_FromString((char*)s) 299#define __Pyx_PyBytes_AsUString(s) ((unsigned char*) PyBytes_AsString(s)) 300 301#define __Pyx_Owned_Py_None(b) (Py_INCREF(Py_None), Py_None) 302#define __Pyx_PyBool_FromLong(b) ((b) ? (Py_INCREF(Py_True), Py_True) : (Py_INCREF(Py_False), Py_False)) 303static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject*); 304static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x); 305 306static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject*); 307static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t); 308static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject*); 309 310#if CYTHON_COMPILING_IN_CPYTHON 311#define __pyx_PyFloat_AsDouble(x) (PyFloat_CheckExact(x) ? PyFloat_AS_DOUBLE(x) : PyFloat_AsDouble(x)) 312#else 313#define __pyx_PyFloat_AsDouble(x) PyFloat_AsDouble(x) 314#endif 315#define __pyx_PyFloat_AsFloat(x) ((float) __pyx_PyFloat_AsDouble(x)) 316 317#ifdef __GNUC__ 318 /* Test for GCC > 2.95 */ 319 #if __GNUC__ > 2 || (__GNUC__ == 2 && (__GNUC_MINOR__ > 95)) 320 #define likely(x) __builtin_expect(!!(x), 1) 321 #define unlikely(x) __builtin_expect(!!(x), 0) 322 #else /* __GNUC__ > 2 ... */ 323 #define likely(x) (x) 324 #define unlikely(x) (x) 325 #endif /* __GNUC__ > 2 ... */ 326#else /* __GNUC__ */ 327 #define likely(x) (x) 328 #define unlikely(x) (x) 329#endif /* __GNUC__ */ 330 331static PyObject *__pyx_m; 332static PyObject *__pyx_b; 333static PyObject *__pyx_empty_tuple; 334static PyObject *__pyx_empty_bytes; 335static int __pyx_lineno; 336static int __pyx_clineno = 0; 337static const char * __pyx_cfilenm= __FILE__; 338static const char *__pyx_filename; 339 340 341static const char *__pyx_f[] = { 342 "qrbtree.pyx", 343 "cwalker.pxd", 344}; 345 346/*--- Type declarations ---*/ 347struct __pyx_obj_8bintrees_7cwalker_cWalker; 348struct __pyx_obj_8bintrees_7qrbtree_cRBTree; 349 350/* "cwalker.pxd":11 351 * from stack cimport node_stack_t 352 * 353 * cdef class cWalker: # <<<<<<<<<<<<<< 354 * cdef node_t *node 355 * cdef node_t *root 356 */ 357struct __pyx_obj_8bintrees_7cwalker_cWalker { 358 PyObject_HEAD 359 struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtab; 360 node_t *node; 361 node_t *root; 362 node_stack_t *stack; 363}; 364 365 366/* "bintrees\qrbtree.pyx":16 367 * from ctrees cimport * 368 * 369 * cdef class cRBTree: # <<<<<<<<<<<<<< 370 * cdef node_t *_root 371 * cdef int _count 372 */ 373struct __pyx_obj_8bintrees_7qrbtree_cRBTree { 374 PyObject_HEAD 375 node_t *_root; 376 int _count; 377}; 378 379 380 381/* "cwalker.pxd":11 382 * from stack cimport node_stack_t 383 * 384 * cdef class cWalker: # <<<<<<<<<<<<<< 385 * cdef node_t *node 386 * cdef node_t *root 387 */ 388 389struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker { 390 void (*set_tree)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, node_t *); 391 PyObject *(*reset)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 392 PyObject *(*push)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 393 PyObject *(*pop)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 394}; 395static struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtabptr_8bintrees_7cwalker_cWalker; 396#ifndef CYTHON_REFNANNY 397 #define CYTHON_REFNANNY 0 398#endif 399#if CYTHON_REFNANNY 400 typedef struct { 401 void (*INCREF)(void*, PyObject*, int); 402 void (*DECREF)(void*, PyObject*, int); 403 void (*GOTREF)(void*, PyObject*, int); 404 void (*GIVEREF)(void*, PyObject*, int); 405 void* (*SetupContext)(const char*, int, const char*); 406 void (*FinishContext)(void**); 407 } __Pyx_RefNannyAPIStruct; 408 static __Pyx_RefNannyAPIStruct *__Pyx_RefNanny = NULL; 409 static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname); /*proto*/ 410 #define __Pyx_RefNannyDeclarations void *__pyx_refnanny = NULL; 411#ifdef WITH_THREAD 412 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 413 if (acquire_gil) { \ 414 PyGILState_STATE __pyx_gilstate_save = PyGILState_Ensure(); \ 415 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 416 PyGILState_Release(__pyx_gilstate_save); \ 417 } else { \ 418 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 419 } 420#else 421 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 422 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__) 423#endif 424 #define __Pyx_RefNannyFinishContext() \ 425 __Pyx_RefNanny->FinishContext(&__pyx_refnanny) 426 #define __Pyx_INCREF(r) __Pyx_RefNanny->INCREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 427 #define __Pyx_DECREF(r) __Pyx_RefNanny->DECREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 428 #define __Pyx_GOTREF(r) __Pyx_RefNanny->GOTREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 429 #define __Pyx_GIVEREF(r) __Pyx_RefNanny->GIVEREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 430 #define __Pyx_XINCREF(r) do { if((r) != NULL) {__Pyx_INCREF(r); }} while(0) 431 #define __Pyx_XDECREF(r) do { if((r) != NULL) {__Pyx_DECREF(r); }} while(0) 432 #define __Pyx_XGOTREF(r) do { if((r) != NULL) {__Pyx_GOTREF(r); }} while(0) 433 #define __Pyx_XGIVEREF(r) do { if((r) != NULL) {__Pyx_GIVEREF(r);}} while(0) 434#else 435 #define __Pyx_RefNannyDeclarations 436 #define __Pyx_RefNannySetupContext(name, acquire_gil) 437 #define __Pyx_RefNannyFinishContext() 438 #define __Pyx_INCREF(r) Py_INCREF(r) 439 #define __Pyx_DECREF(r) Py_DECREF(r) 440 #define __Pyx_GOTREF(r) 441 #define __Pyx_GIVEREF(r) 442 #define __Pyx_XINCREF(r) Py_XINCREF(r) 443 #define __Pyx_XDECREF(r) Py_XDECREF(r) 444 #define __Pyx_XGOTREF(r) 445 #define __Pyx_XGIVEREF(r) 446#endif /* CYTHON_REFNANNY */ 447#define __Pyx_CLEAR(r) do { PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);} while(0) 448#define __Pyx_XCLEAR(r) do { if((r) != NULL) {PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);}} while(0) 449 450static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name); /*proto*/ 451 452static void __Pyx_RaiseDoubleKeywordsError(const char* func_name, PyObject* kw_name); /*proto*/ 453 454static int __Pyx_ParseOptionalKeywords(PyObject *kwds, PyObject **argnames[], \ 455 PyObject *kwds2, PyObject *values[], Py_ssize_t num_pos_args, \ 456 const char* function_name); /*proto*/ 457 458static void __Pyx_RaiseArgtupleInvalid(const char* func_name, int exact, 459 Py_ssize_t num_min, Py_ssize_t num_max, Py_ssize_t num_found); /*proto*/ 460 461static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb); /*proto*/ 462static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb); /*proto*/ 463 464static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause); /*proto*/ 465 466static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Generic(PyObject *o, PyObject* j) { 467 PyObject *r; 468 if (!j) return NULL; 469 r = PyObject_GetItem(o, j); 470 Py_DECREF(j); 471 return r; 472} 473#define __Pyx_GetItemInt_List(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 474 __Pyx_GetItemInt_List_Fast(o, i) : \ 475 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 476static CYTHON_INLINE PyObject *__Pyx_GetItemInt_List_Fast(PyObject *o, Py_ssize_t i) { 477#if CYTHON_COMPILING_IN_CPYTHON 478 if (likely((0 <= i) & (i < PyList_GET_SIZE(o)))) { 479 PyObject *r = PyList_GET_ITEM(o, i); 480 Py_INCREF(r); 481 return r; 482 } 483 else if ((-PyList_GET_SIZE(o) <= i) & (i < 0)) { 484 PyObject *r = PyList_GET_ITEM(o, PyList_GET_SIZE(o) + i); 485 Py_INCREF(r); 486 return r; 487 } 488 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 489#else 490 return PySequence_GetItem(o, i); 491#endif 492} 493#define __Pyx_GetItemInt_Tuple(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 494 __Pyx_GetItemInt_Tuple_Fast(o, i) : \ 495 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 496static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Tuple_Fast(PyObject *o, Py_ssize_t i) { 497#if CYTHON_COMPILING_IN_CPYTHON 498 if (likely((0 <= i) & (i < PyTuple_GET_SIZE(o)))) { 499 PyObject *r = PyTuple_GET_ITEM(o, i); 500 Py_INCREF(r); 501 return r; 502 } 503 else if ((-PyTuple_GET_SIZE(o) <= i) & (i < 0)) { 504 PyObject *r = PyTuple_GET_ITEM(o, PyTuple_GET_SIZE(o) + i); 505 Py_INCREF(r); 506 return r; 507 } 508 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 509#else 510 return PySequence_GetItem(o, i); 511#endif 512} 513#define __Pyx_GetItemInt(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 514 __Pyx_GetItemInt_Fast(o, i) : \ 515 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 516static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Fast(PyObject *o, Py_ssize_t i) { 517#if CYTHON_COMPILING_IN_CPYTHON 518 if (PyList_CheckExact(o)) { 519 Py_ssize_t n = (likely(i >= 0)) ? i : i + PyList_GET_SIZE(o); 520 if (likely((n >= 0) & (n < PyList_GET_SIZE(o)))) { 521 PyObject *r = PyList_GET_ITEM(o, n); 522 Py_INCREF(r); 523 return r; 524 } 525 } 526 else if (PyTuple_CheckExact(o)) { 527 Py_ssize_t n = (likely(i >= 0)) ? i : i + PyTuple_GET_SIZE(o); 528 if (likely((n >= 0) & (n < PyTuple_GET_SIZE(o)))) { 529 PyObject *r = PyTuple_GET_ITEM(o, n); 530 Py_INCREF(r); 531 return r; 532 } 533 } else { /* inlined PySequence_GetItem() */ 534 PySequenceMethods *m = Py_TYPE(o)->tp_as_sequence; 535 if (likely(m && m->sq_item)) { 536 if (unlikely(i < 0) && likely(m->sq_length)) { 537 Py_ssize_t l = m->sq_length(o); 538 if (unlikely(l < 0)) return NULL; 539 i += l; 540 } 541 return m->sq_item(o, i); 542 } 543 } 544#else 545 if (PySequence_Check(o)) { 546 return PySequence_GetItem(o, i); 547 } 548#endif 549 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 550} 551 552static PyObject *__Pyx_Import(PyObject *name, PyObject *from_list, long level); /*proto*/ 553 554static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject *); 555 556static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject *); 557 558static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject *); 559 560static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject *); 561 562static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject *); 563 564static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject *); 565 566static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject *); 567 568static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject *); 569 570static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject *); 571 572static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject *); 573 574static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject *); 575 576static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject *); 577 578static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject *); 579 580static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject *); 581 582static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject *); 583 584static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject *); 585 586static int __Pyx_check_binary_version(void); 587 588#if !defined(__Pyx_PyIdentifier_FromString) 589#if PY_MAJOR_VERSION < 3 590 #define __Pyx_PyIdentifier_FromString(s) PyString_FromString(s) 591#else 592 #define __Pyx_PyIdentifier_FromString(s) PyUnicode_FromString(s) 593#endif 594#endif 595 596static PyObject *__Pyx_ImportModule(const char *name); /*proto*/ 597 598static PyTypeObject *__Pyx_ImportType(const char *module_name, const char *class_name, size_t size, int strict); /*proto*/ 599 600static void* __Pyx_GetVtable(PyObject *dict); /*proto*/ 601 602typedef struct { 603 int code_line; 604 PyCodeObject* code_object; 605} __Pyx_CodeObjectCacheEntry; 606struct __Pyx_CodeObjectCache { 607 int count; 608 int max_count; 609 __Pyx_CodeObjectCacheEntry* entries; 610}; 611static struct __Pyx_CodeObjectCache __pyx_code_cache = {0,0,NULL}; 612static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line); 613static PyCodeObject *__pyx_find_code_object(int code_line); 614static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object); 615 616static void __Pyx_AddTraceback(const char *funcname, int c_line, 617 int py_line, const char *filename); /*proto*/ 618 619static int __Pyx_InitStrings(__Pyx_StringTabEntry *t); /*proto*/ 620 621 622/* Module declarations from 'bintrees.ctrees' */ 623 624/* Module declarations from 'bintrees.stack' */ 625 626/* Module declarations from 'bintrees.cwalker' */ 627static PyTypeObject *__pyx_ptype_8bintrees_7cwalker_cWalker = 0; 628 629/* Module declarations from 'bintrees.qrbtree' */ 630static PyTypeObject *__pyx_ptype_8bintrees_7qrbtree_cRBTree = 0; 631#define __Pyx_MODULE_NAME "bintrees.qrbtree" 632int __pyx_module_is_main_bintrees__qrbtree = 0; 633 634/* Implementation of 'bintrees.qrbtree' */ 635static PyObject *__pyx_builtin_property; 636static PyObject *__pyx_builtin_KeyError; 637static PyObject *__pyx_builtin_MemoryError; 638static PyObject *__pyx_builtin_ValueError; 639static int __pyx_pf_8bintrees_7qrbtree_7cRBTree___cinit__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_items); /* proto */ 640static void __pyx_pf_8bintrees_7qrbtree_7cRBTree_2__dealloc__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 641static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_4count(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 642static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_6__getstate__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 643static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_8__setstate__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_state); /* proto */ 644static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_10clear(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 645static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_12get_value(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 646static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_14get_walker(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 647static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_16insert(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key, PyObject *__pyx_v_value); /* proto */ 648static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_18remove(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 649static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_20max_item(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 650static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_22min_item(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self); /* proto */ 651static char __pyx_k_1[] = "Can not allocate memory for node structure."; 652static char __pyx_k_3[] = "Tree is empty"; 653static char __pyx_k__key[] = "key"; 654static char __pyx_k__count[] = "count"; 655static char __pyx_k__items[] = "items"; 656static char __pyx_k__value[] = "value"; 657static char __pyx_k__update[] = "update"; 658static char __pyx_k____all__[] = "__all__"; 659static char __pyx_k__cRBTree[] = "cRBTree"; 660static char __pyx_k__cWalker[] = "cWalker"; 661static char __pyx_k__cwalker[] = "cwalker"; 662static char __pyx_k__KeyError[] = "KeyError"; 663static char __pyx_k____main__[] = "__main__"; 664static char __pyx_k____test__[] = "__test__"; 665static char __pyx_k__property[] = "property"; 666static char __pyx_k__ValueError[] = "ValueError"; 667static char __pyx_k__MemoryError[] = "MemoryError"; 668static PyObject *__pyx_kp_s_1; 669static PyObject *__pyx_kp_s_3; 670static PyObject *__pyx_n_s__KeyError; 671static PyObject *__pyx_n_s__MemoryError; 672static PyObject *__pyx_n_s__ValueError; 673static PyObject *__pyx_n_s____all__; 674static PyObject *__pyx_n_s____main__; 675static PyObject *__pyx_n_s____test__; 676static PyObject *__pyx_n_s__cRBTree; 677static PyObject *__pyx_n_s__cWalker; 678static PyObject *__pyx_n_s__count; 679static PyObject *__pyx_n_s__cwalker; 680static PyObject *__pyx_n_s__items; 681static PyObject *__pyx_n_s__key; 682static PyObject *__pyx_n_s__property; 683static PyObject *__pyx_n_s__update; 684static PyObject *__pyx_n_s__value; 685static PyObject *__pyx_int_0; 686static PyObject *__pyx_k_tuple_2; 687static PyObject *__pyx_k_tuple_4; 688static PyObject *__pyx_k_tuple_5; 689 690/* Python wrapper */ 691static int __pyx_pw_8bintrees_7qrbtree_7cRBTree_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/ 692static int __pyx_pw_8bintrees_7qrbtree_7cRBTree_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) { 693 PyObject *__pyx_v_items = 0; 694 int __pyx_r; 695 __Pyx_RefNannyDeclarations 696 __Pyx_RefNannySetupContext("__cinit__ (wrapper)", 0); 697 { 698 static PyObject **__pyx_pyargnames[] = {&__pyx_n_s__items,0}; 699 PyObject* values[1] = {0}; 700 701 /* "bintrees\qrbtree.pyx":20 702 * cdef int _count 703 * 704 * def __cinit__(self, items=None): # <<<<<<<<<<<<<< 705 * self._root = NULL 706 * self._count = 0 707 */ 708 values[0] = ((PyObject *)Py_None); 709 if (unlikely(__pyx_kwds)) { 710 Py_ssize_t kw_args; 711 const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args); 712 switch (pos_args) { 713 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 714 case 0: break; 715 default: goto __pyx_L5_argtuple_error; 716 } 717 kw_args = PyDict_Size(__pyx_kwds); 718 switch (pos_args) { 719 case 0: 720 if (kw_args > 0) { 721 PyObject* value = PyDict_GetItem(__pyx_kwds, __pyx_n_s__items); 722 if (value) { values[0] = value; kw_args--; } 723 } 724 } 725 if (unlikely(kw_args > 0)) { 726 if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "__cinit__") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 727 } 728 } else { 729 switch (PyTuple_GET_SIZE(__pyx_args)) { 730 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 731 case 0: break; 732 default: goto __pyx_L5_argtuple_error; 733 } 734 } 735 __pyx_v_items = values[0]; 736 } 737 goto __pyx_L4_argument_unpacking_done; 738 __pyx_L5_argtuple_error:; 739 __Pyx_RaiseArgtupleInvalid("__cinit__", 0, 0, 1, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 740 __pyx_L3_error:; 741 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.__cinit__", __pyx_clineno, __pyx_lineno, __pyx_filename); 742 __Pyx_RefNannyFinishContext(); 743 return -1; 744 __pyx_L4_argument_unpacking_done:; 745 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree___cinit__(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self), __pyx_v_items); 746 __Pyx_RefNannyFinishContext(); 747 return __pyx_r; 748} 749 750static int __pyx_pf_8bintrees_7qrbtree_7cRBTree___cinit__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_items) { 751 int __pyx_r; 752 __Pyx_RefNannyDeclarations 753 int __pyx_t_1; 754 PyObject *__pyx_t_2 = NULL; 755 PyObject *__pyx_t_3 = NULL; 756 PyObject *__pyx_t_4 = NULL; 757 int __pyx_lineno = 0; 758 const char *__pyx_filename = NULL; 759 int __pyx_clineno = 0; 760 __Pyx_RefNannySetupContext("__cinit__", 0); 761 762 /* "bintrees\qrbtree.pyx":21 763 * 764 * def __cinit__(self, items=None): 765 * self._root = NULL # <<<<<<<<<<<<<< 766 * self._count = 0 767 * if items: 768 */ 769 __pyx_v_self->_root = NULL; 770 771 /* "bintrees\qrbtree.pyx":22 772 * def __cinit__(self, items=None): 773 * self._root = NULL 774 * self._count = 0 # <<<<<<<<<<<<<< 775 * if items: 776 * self.update(items) 777 */ 778 __pyx_v_self->_count = 0; 779 780 /* "bintrees\qrbtree.pyx":23 781 * self._root = NULL 782 * self._count = 0 783 * if items: # <<<<<<<<<<<<<< 784 * self.update(items) 785 * 786 */ 787 __pyx_t_1 = __Pyx_PyObject_IsTrue(__pyx_v_items); if (unlikely(__pyx_t_1 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 788 if (__pyx_t_1) { 789 790 /* "bintrees\qrbtree.pyx":24 791 * self._count = 0 792 * if items: 793 * self.update(items) # <<<<<<<<<<<<<< 794 * 795 * def __dealloc__(self): 796 */ 797 __pyx_t_2 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__update); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 798 __Pyx_GOTREF(__pyx_t_2); 799 __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 800 __Pyx_GOTREF(__pyx_t_3); 801 __Pyx_INCREF(__pyx_v_items); 802 PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_v_items); 803 __Pyx_GIVEREF(__pyx_v_items); 804 __pyx_t_4 = PyObject_Call(__pyx_t_2, ((PyObject *)__pyx_t_3), NULL); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 805 __Pyx_GOTREF(__pyx_t_4); 806 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 807 __Pyx_DECREF(((PyObject *)__pyx_t_3)); __pyx_t_3 = 0; 808 __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; 809 goto __pyx_L3; 810 } 811 __pyx_L3:; 812 813 __pyx_r = 0; 814 goto __pyx_L0; 815 __pyx_L1_error:; 816 __Pyx_XDECREF(__pyx_t_2); 817 __Pyx_XDECREF(__pyx_t_3); 818 __Pyx_XDECREF(__pyx_t_4); 819 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.__cinit__", __pyx_clineno, __pyx_lineno, __pyx_filename); 820 __pyx_r = -1; 821 __pyx_L0:; 822 __Pyx_RefNannyFinishContext(); 823 return __pyx_r; 824} 825 826/* Python wrapper */ 827static void __pyx_pw_8bintrees_7qrbtree_7cRBTree_3__dealloc__(PyObject *__pyx_v_self); /*proto*/ 828static void __pyx_pw_8bintrees_7qrbtree_7cRBTree_3__dealloc__(PyObject *__pyx_v_self) { 829 __Pyx_RefNannyDeclarations 830 __Pyx_RefNannySetupContext("__dealloc__ (wrapper)", 0); 831 __pyx_pf_8bintrees_7qrbtree_7cRBTree_2__dealloc__(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 832 __Pyx_RefNannyFinishContext(); 833} 834 835/* "bintrees\qrbtree.pyx":26 836 * self.update(items) 837 * 838 * def __dealloc__(self): # <<<<<<<<<<<<<< 839 * ct_delete_tree(self._root) 840 * 841 */ 842 843static void __pyx_pf_8bintrees_7qrbtree_7cRBTree_2__dealloc__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 844 __Pyx_RefNannyDeclarations 845 __Pyx_RefNannySetupContext("__dealloc__", 0); 846 847 /* "bintrees\qrbtree.pyx":27 848 * 849 * def __dealloc__(self): 850 * ct_delete_tree(self._root) # <<<<<<<<<<<<<< 851 * 852 * @property 853 */ 854 ct_delete_tree(__pyx_v_self->_root); 855 856 __Pyx_RefNannyFinishContext(); 857} 858 859/* Python wrapper */ 860static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_5count(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 861static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_5count(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 862 PyObject *__pyx_r = 0; 863 __Pyx_RefNannyDeclarations 864 __Pyx_RefNannySetupContext("count (wrapper)", 0); 865 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_4count(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 866 __Pyx_RefNannyFinishContext(); 867 return __pyx_r; 868} 869 870/* "bintrees\qrbtree.pyx":30 871 * 872 * @property 873 * def count(self): # <<<<<<<<<<<<<< 874 * return self._count 875 * 876 */ 877 878static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_4count(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 879 PyObject *__pyx_r = NULL; 880 __Pyx_RefNannyDeclarations 881 PyObject *__pyx_t_1 = NULL; 882 int __pyx_lineno = 0; 883 const char *__pyx_filename = NULL; 884 int __pyx_clineno = 0; 885 __Pyx_RefNannySetupContext("count", 0); 886 887 /* "bintrees\qrbtree.pyx":31 888 * @property 889 * def count(self): 890 * return self._count # <<<<<<<<<<<<<< 891 * 892 * def __getstate__(self): 893 */ 894 __Pyx_XDECREF(__pyx_r); 895 __pyx_t_1 = PyInt_FromLong(__pyx_v_self->_count); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 31; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 896 __Pyx_GOTREF(__pyx_t_1); 897 __pyx_r = __pyx_t_1; 898 __pyx_t_1 = 0; 899 goto __pyx_L0; 900 901 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 902 goto __pyx_L0; 903 __pyx_L1_error:; 904 __Pyx_XDECREF(__pyx_t_1); 905 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.count", __pyx_clineno, __pyx_lineno, __pyx_filename); 906 __pyx_r = NULL; 907 __pyx_L0:; 908 __Pyx_XGIVEREF(__pyx_r); 909 __Pyx_RefNannyFinishContext(); 910 return __pyx_r; 911} 912 913/* Python wrapper */ 914static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_7__getstate__(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 915static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_7__getstate__(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 916 PyObject *__pyx_r = 0; 917 __Pyx_RefNannyDeclarations 918 __Pyx_RefNannySetupContext("__getstate__ (wrapper)", 0); 919 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_6__getstate__(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 920 __Pyx_RefNannyFinishContext(); 921 return __pyx_r; 922} 923 924/* "bintrees\qrbtree.pyx":33 925 * return self._count 926 * 927 * def __getstate__(self): # <<<<<<<<<<<<<< 928 * return dict(self.items()) 929 * 930 */ 931 932static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_6__getstate__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 933 PyObject *__pyx_r = NULL; 934 __Pyx_RefNannyDeclarations 935 PyObject *__pyx_t_1 = NULL; 936 PyObject *__pyx_t_2 = NULL; 937 int __pyx_lineno = 0; 938 const char *__pyx_filename = NULL; 939 int __pyx_clineno = 0; 940 __Pyx_RefNannySetupContext("__getstate__", 0); 941 942 /* "bintrees\qrbtree.pyx":34 943 * 944 * def __getstate__(self): 945 * return dict(self.items()) # <<<<<<<<<<<<<< 946 * 947 * def __setstate__(self, state): 948 */ 949 __Pyx_XDECREF(__pyx_r); 950 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__items); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 951 __Pyx_GOTREF(__pyx_t_1); 952 __pyx_t_2 = PyObject_Call(__pyx_t_1, ((PyObject *)__pyx_empty_tuple), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 953 __Pyx_GOTREF(__pyx_t_2); 954 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 955 __pyx_t_1 = PyTuple_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 956 __Pyx_GOTREF(__pyx_t_1); 957 PyTuple_SET_ITEM(__pyx_t_1, 0, __pyx_t_2); 958 __Pyx_GIVEREF(__pyx_t_2); 959 __pyx_t_2 = 0; 960 __pyx_t_2 = PyObject_Call(((PyObject *)((PyObject*)(&PyDict_Type))), ((PyObject *)__pyx_t_1), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 961 __Pyx_GOTREF(__pyx_t_2); 962 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 963 __pyx_r = __pyx_t_2; 964 __pyx_t_2 = 0; 965 goto __pyx_L0; 966 967 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 968 goto __pyx_L0; 969 __pyx_L1_error:; 970 __Pyx_XDECREF(__pyx_t_1); 971 __Pyx_XDECREF(__pyx_t_2); 972 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.__getstate__", __pyx_clineno, __pyx_lineno, __pyx_filename); 973 __pyx_r = NULL; 974 __pyx_L0:; 975 __Pyx_XGIVEREF(__pyx_r); 976 __Pyx_RefNannyFinishContext(); 977 return __pyx_r; 978} 979 980/* Python wrapper */ 981static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_9__setstate__(PyObject *__pyx_v_self, PyObject *__pyx_v_state); /*proto*/ 982static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_9__setstate__(PyObject *__pyx_v_self, PyObject *__pyx_v_state) { 983 PyObject *__pyx_r = 0; 984 __Pyx_RefNannyDeclarations 985 __Pyx_RefNannySetupContext("__setstate__ (wrapper)", 0); 986 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_8__setstate__(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self), ((PyObject *)__pyx_v_state)); 987 __Pyx_RefNannyFinishContext(); 988 return __pyx_r; 989} 990 991/* "bintrees\qrbtree.pyx":36 992 * return dict(self.items()) 993 * 994 * def __setstate__(self, state): # <<<<<<<<<<<<<< 995 * self.update(state) 996 * 997 */ 998 999static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_8__setstate__(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_state) { 1000 PyObject *__pyx_r = NULL; 1001 __Pyx_RefNannyDeclarations 1002 PyObject *__pyx_t_1 = NULL; 1003 PyObject *__pyx_t_2 = NULL; 1004 PyObject *__pyx_t_3 = NULL; 1005 int __pyx_lineno = 0; 1006 const char *__pyx_filename = NULL; 1007 int __pyx_clineno = 0; 1008 __Pyx_RefNannySetupContext("__setstate__", 0); 1009 1010 /* "bintrees\qrbtree.pyx":37 1011 * 1012 * def __setstate__(self, state): 1013 * self.update(state) # <<<<<<<<<<<<<< 1014 * 1015 * def clear(self): 1016 */ 1017 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__update); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1018 __Pyx_GOTREF(__pyx_t_1); 1019 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1020 __Pyx_GOTREF(__pyx_t_2); 1021 __Pyx_INCREF(__pyx_v_state); 1022 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_state); 1023 __Pyx_GIVEREF(__pyx_v_state); 1024 __pyx_t_3 = PyObject_Call(__pyx_t_1, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1025 __Pyx_GOTREF(__pyx_t_3); 1026 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1027 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1028 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1029 1030 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1031 goto __pyx_L0; 1032 __pyx_L1_error:; 1033 __Pyx_XDECREF(__pyx_t_1); 1034 __Pyx_XDECREF(__pyx_t_2); 1035 __Pyx_XDECREF(__pyx_t_3); 1036 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.__setstate__", __pyx_clineno, __pyx_lineno, __pyx_filename); 1037 __pyx_r = NULL; 1038 __pyx_L0:; 1039 __Pyx_XGIVEREF(__pyx_r); 1040 __Pyx_RefNannyFinishContext(); 1041 return __pyx_r; 1042} 1043 1044/* Python wrapper */ 1045static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_11clear(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1046static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_11clear(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1047 PyObject *__pyx_r = 0; 1048 __Pyx_RefNannyDeclarations 1049 __Pyx_RefNannySetupContext("clear (wrapper)", 0); 1050 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_10clear(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 1051 __Pyx_RefNannyFinishContext(); 1052 return __pyx_r; 1053} 1054 1055/* "bintrees\qrbtree.pyx":39 1056 * self.update(state) 1057 * 1058 * def clear(self): # <<<<<<<<<<<<<< 1059 * ct_delete_tree(self._root) 1060 * self._count = 0 1061 */ 1062 1063static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_10clear(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 1064 PyObject *__pyx_r = NULL; 1065 __Pyx_RefNannyDeclarations 1066 __Pyx_RefNannySetupContext("clear", 0); 1067 1068 /* "bintrees\qrbtree.pyx":40 1069 * 1070 * def clear(self): 1071 * ct_delete_tree(self._root) # <<<<<<<<<<<<<< 1072 * self._count = 0 1073 * self._root = NULL 1074 */ 1075 ct_delete_tree(__pyx_v_self->_root); 1076 1077 /* "bintrees\qrbtree.pyx":41 1078 * def clear(self): 1079 * ct_delete_tree(self._root) 1080 * self._count = 0 # <<<<<<<<<<<<<< 1081 * self._root = NULL 1082 * 1083 */ 1084 __pyx_v_self->_count = 0; 1085 1086 /* "bintrees\qrbtree.pyx":42 1087 * ct_delete_tree(self._root) 1088 * self._count = 0 1089 * self._root = NULL # <<<<<<<<<<<<<< 1090 * 1091 * def get_value(self, key): 1092 */ 1093 __pyx_v_self->_root = NULL; 1094 1095 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1096 __Pyx_XGIVEREF(__pyx_r); 1097 __Pyx_RefNannyFinishContext(); 1098 return __pyx_r; 1099} 1100 1101/* Python wrapper */ 1102static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_13get_value(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1103static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_13get_value(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1104 PyObject *__pyx_r = 0; 1105 __Pyx_RefNannyDeclarations 1106 __Pyx_RefNannySetupContext("get_value (wrapper)", 0); 1107 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_12get_value(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1108 __Pyx_RefNannyFinishContext(); 1109 return __pyx_r; 1110} 1111 1112/* "bintrees\qrbtree.pyx":44 1113 * self._root = NULL 1114 * 1115 * def get_value(self, key): # <<<<<<<<<<<<<< 1116 * result = <object> ct_get_item(self._root, key) 1117 * if result is None: 1118 */ 1119 1120static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_12get_value(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key) { 1121 PyObject *__pyx_v_result = NULL; 1122 PyObject *__pyx_r = NULL; 1123 __Pyx_RefNannyDeclarations 1124 PyObject *__pyx_t_1; 1125 int __pyx_t_2; 1126 PyObject *__pyx_t_3 = NULL; 1127 PyObject *__pyx_t_4 = NULL; 1128 int __pyx_lineno = 0; 1129 const char *__pyx_filename = NULL; 1130 int __pyx_clineno = 0; 1131 __Pyx_RefNannySetupContext("get_value", 0); 1132 1133 /* "bintrees\qrbtree.pyx":45 1134 * 1135 * def get_value(self, key): 1136 * result = <object> ct_get_item(self._root, key) # <<<<<<<<<<<<<< 1137 * if result is None: 1138 * raise KeyError(key) 1139 */ 1140 __pyx_t_1 = ct_get_item(__pyx_v_self->_root, __pyx_v_key); 1141 __Pyx_INCREF(((PyObject *)__pyx_t_1)); 1142 __pyx_v_result = ((PyObject *)__pyx_t_1); 1143 1144 /* "bintrees\qrbtree.pyx":46 1145 * def get_value(self, key): 1146 * result = <object> ct_get_item(self._root, key) 1147 * if result is None: # <<<<<<<<<<<<<< 1148 * raise KeyError(key) 1149 * else: 1150 */ 1151 __pyx_t_2 = (__pyx_v_result == Py_None); 1152 if (__pyx_t_2) { 1153 1154 /* "bintrees\qrbtree.pyx":47 1155 * result = <object> ct_get_item(self._root, key) 1156 * if result is None: 1157 * raise KeyError(key) # <<<<<<<<<<<<<< 1158 * else: 1159 * return result[1] 1160 */ 1161 __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1162 __Pyx_GOTREF(__pyx_t_3); 1163 __Pyx_INCREF(__pyx_v_key); 1164 PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_v_key); 1165 __Pyx_GIVEREF(__pyx_v_key); 1166 __pyx_t_4 = PyObject_Call(__pyx_builtin_KeyError, ((PyObject *)__pyx_t_3), NULL); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1167 __Pyx_GOTREF(__pyx_t_4); 1168 __Pyx_DECREF(((PyObject *)__pyx_t_3)); __pyx_t_3 = 0; 1169 __Pyx_Raise(__pyx_t_4, 0, 0, 0); 1170 __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; 1171 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1172 goto __pyx_L3; 1173 } 1174 /*else*/ { 1175 1176 /* "bintrees\qrbtree.pyx":49 1177 * raise KeyError(key) 1178 * else: 1179 * return result[1] # <<<<<<<<<<<<<< 1180 * 1181 * def get_walker(self): 1182 */ 1183 __Pyx_XDECREF(__pyx_r); 1184 __pyx_t_4 = __Pyx_GetItemInt(__pyx_v_result, 1, sizeof(long), PyInt_FromLong); if (!__pyx_t_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 49; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1185 __Pyx_GOTREF(__pyx_t_4); 1186 __pyx_r = __pyx_t_4; 1187 __pyx_t_4 = 0; 1188 goto __pyx_L0; 1189 } 1190 __pyx_L3:; 1191 1192 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1193 goto __pyx_L0; 1194 __pyx_L1_error:; 1195 __Pyx_XDECREF(__pyx_t_3); 1196 __Pyx_XDECREF(__pyx_t_4); 1197 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.get_value", __pyx_clineno, __pyx_lineno, __pyx_filename); 1198 __pyx_r = NULL; 1199 __pyx_L0:; 1200 __Pyx_XDECREF(__pyx_v_result); 1201 __Pyx_XGIVEREF(__pyx_r); 1202 __Pyx_RefNannyFinishContext(); 1203 return __pyx_r; 1204} 1205 1206/* Python wrapper */ 1207static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_15get_walker(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1208static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_15get_walker(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1209 PyObject *__pyx_r = 0; 1210 __Pyx_RefNannyDeclarations 1211 __Pyx_RefNannySetupContext("get_walker (wrapper)", 0); 1212 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_14get_walker(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 1213 __Pyx_RefNannyFinishContext(); 1214 return __pyx_r; 1215} 1216 1217/* "bintrees\qrbtree.pyx":51 1218 * return result[1] 1219 * 1220 * def get_walker(self): # <<<<<<<<<<<<<< 1221 * cdef cWalker walker 1222 * walker = cWalker() 1223 */ 1224 1225static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_14get_walker(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 1226 struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_walker = 0; 1227 PyObject *__pyx_r = NULL; 1228 __Pyx_RefNannyDeclarations 1229 PyObject *__pyx_t_1 = NULL; 1230 int __pyx_lineno = 0; 1231 const char *__pyx_filename = NULL; 1232 int __pyx_clineno = 0; 1233 __Pyx_RefNannySetupContext("get_walker", 0); 1234 1235 /* "bintrees\qrbtree.pyx":53 1236 * def get_walker(self): 1237 * cdef cWalker walker 1238 * walker = cWalker() # <<<<<<<<<<<<<< 1239 * walker.set_tree(self._root) 1240 * return walker 1241 */ 1242 __pyx_t_1 = PyObject_Call(((PyObject *)((PyObject*)__pyx_ptype_8bintrees_7cwalker_cWalker)), ((PyObject *)__pyx_empty_tuple), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 53; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1243 __Pyx_GOTREF(__pyx_t_1); 1244 __pyx_v_walker = ((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_t_1); 1245 __pyx_t_1 = 0; 1246 1247 /* "bintrees\qrbtree.pyx":54 1248 * cdef cWalker walker 1249 * walker = cWalker() 1250 * walker.set_tree(self._root) # <<<<<<<<<<<<<< 1251 * return walker 1252 * 1253 */ 1254 ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_walker->__pyx_vtab)->set_tree(__pyx_v_walker, __pyx_v_self->_root); 1255 1256 /* "bintrees\qrbtree.pyx":55 1257 * walker = cWalker() 1258 * walker.set_tree(self._root) 1259 * return walker # <<<<<<<<<<<<<< 1260 * 1261 * def insert(self, key, value): 1262 */ 1263 __Pyx_XDECREF(__pyx_r); 1264 __Pyx_INCREF(((PyObject *)__pyx_v_walker)); 1265 __pyx_r = ((PyObject *)__pyx_v_walker); 1266 goto __pyx_L0; 1267 1268 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1269 goto __pyx_L0; 1270 __pyx_L1_error:; 1271 __Pyx_XDECREF(__pyx_t_1); 1272 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.get_walker", __pyx_clineno, __pyx_lineno, __pyx_filename); 1273 __pyx_r = NULL; 1274 __pyx_L0:; 1275 __Pyx_XDECREF((PyObject *)__pyx_v_walker); 1276 __Pyx_XGIVEREF(__pyx_r); 1277 __Pyx_RefNannyFinishContext(); 1278 return __pyx_r; 1279} 1280 1281/* Python wrapper */ 1282static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_17insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/ 1283static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_17insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) { 1284 PyObject *__pyx_v_key = 0; 1285 PyObject *__pyx_v_value = 0; 1286 PyObject *__pyx_r = 0; 1287 __Pyx_RefNannyDeclarations 1288 __Pyx_RefNannySetupContext("insert (wrapper)", 0); 1289 { 1290 static PyObject **__pyx_pyargnames[] = {&__pyx_n_s__key,&__pyx_n_s__value,0}; 1291 PyObject* values[2] = {0,0}; 1292 if (unlikely(__pyx_kwds)) { 1293 Py_ssize_t kw_args; 1294 const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args); 1295 switch (pos_args) { 1296 case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1); 1297 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 1298 case 0: break; 1299 default: goto __pyx_L5_argtuple_error; 1300 } 1301 kw_args = PyDict_Size(__pyx_kwds); 1302 switch (pos_args) { 1303 case 0: 1304 if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s__key)) != 0)) kw_args--; 1305 else goto __pyx_L5_argtuple_error; 1306 case 1: 1307 if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s__value)) != 0)) kw_args--; 1308 else { 1309 __Pyx_RaiseArgtupleInvalid("insert", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1310 } 1311 } 1312 if (unlikely(kw_args > 0)) { 1313 if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "insert") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1314 } 1315 } else if (PyTuple_GET_SIZE(__pyx_args) != 2) { 1316 goto __pyx_L5_argtuple_error; 1317 } else { 1318 values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 1319 values[1] = PyTuple_GET_ITEM(__pyx_args, 1); 1320 } 1321 __pyx_v_key = values[0]; 1322 __pyx_v_value = values[1]; 1323 } 1324 goto __pyx_L4_argument_unpacking_done; 1325 __pyx_L5_argtuple_error:; 1326 __Pyx_RaiseArgtupleInvalid("insert", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1327 __pyx_L3_error:; 1328 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.insert", __pyx_clineno, __pyx_lineno, __pyx_filename); 1329 __Pyx_RefNannyFinishContext(); 1330 return NULL; 1331 __pyx_L4_argument_unpacking_done:; 1332 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_16insert(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self), __pyx_v_key, __pyx_v_value); 1333 __Pyx_RefNannyFinishContext(); 1334 return __pyx_r; 1335} 1336 1337/* "bintrees\qrbtree.pyx":57 1338 * return walker 1339 * 1340 * def insert(self, key, value): # <<<<<<<<<<<<<< 1341 * res = rb_insert(&self._root, key, value) 1342 * if res < 0: 1343 */ 1344 1345static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_16insert(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key, PyObject *__pyx_v_value) { 1346 PyObject *__pyx_v_res = NULL; 1347 PyObject *__pyx_r = NULL; 1348 __Pyx_RefNannyDeclarations 1349 PyObject *__pyx_t_1 = NULL; 1350 int __pyx_t_2; 1351 PyObject *__pyx_t_3 = NULL; 1352 int __pyx_t_4; 1353 int __pyx_lineno = 0; 1354 const char *__pyx_filename = NULL; 1355 int __pyx_clineno = 0; 1356 __Pyx_RefNannySetupContext("insert", 0); 1357 1358 /* "bintrees\qrbtree.pyx":58 1359 * 1360 * def insert(self, key, value): 1361 * res = rb_insert(&self._root, key, value) # <<<<<<<<<<<<<< 1362 * if res < 0: 1363 * raise MemoryError('Can not allocate memory for node structure.') 1364 */ 1365 __pyx_t_1 = PyInt_FromLong(rb_insert((&__pyx_v_self->_root), __pyx_v_key, __pyx_v_value)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 58; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1366 __Pyx_GOTREF(__pyx_t_1); 1367 __pyx_v_res = __pyx_t_1; 1368 __pyx_t_1 = 0; 1369 1370 /* "bintrees\qrbtree.pyx":59 1371 * def insert(self, key, value): 1372 * res = rb_insert(&self._root, key, value) 1373 * if res < 0: # <<<<<<<<<<<<<< 1374 * raise MemoryError('Can not allocate memory for node structure.') 1375 * else: 1376 */ 1377 __pyx_t_1 = PyObject_RichCompare(__pyx_v_res, __pyx_int_0, Py_LT); __Pyx_XGOTREF(__pyx_t_1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 59; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1378 __pyx_t_2 = __Pyx_PyObject_IsTrue(__pyx_t_1); if (unlikely(__pyx_t_2 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 59; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1379 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1380 if (__pyx_t_2) { 1381 1382 /* "bintrees\qrbtree.pyx":60 1383 * res = rb_insert(&self._root, key, value) 1384 * if res < 0: 1385 * raise MemoryError('Can not allocate memory for node structure.') # <<<<<<<<<<<<<< 1386 * else: 1387 * self._count += res 1388 */ 1389 __pyx_t_1 = PyObject_Call(__pyx_builtin_MemoryError, ((PyObject *)__pyx_k_tuple_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1390 __Pyx_GOTREF(__pyx_t_1); 1391 __Pyx_Raise(__pyx_t_1, 0, 0, 0); 1392 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1393 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1394 goto __pyx_L3; 1395 } 1396 /*else*/ { 1397 1398 /* "bintrees\qrbtree.pyx":62 1399 * raise MemoryError('Can not allocate memory for node structure.') 1400 * else: 1401 * self._count += res # <<<<<<<<<<<<<< 1402 * 1403 * def remove(self, key): 1404 */ 1405 __pyx_t_1 = PyInt_FromLong(__pyx_v_self->_count); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1406 __Pyx_GOTREF(__pyx_t_1); 1407 __pyx_t_3 = PyNumber_InPlaceAdd(__pyx_t_1, __pyx_v_res); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1408 __Pyx_GOTREF(__pyx_t_3); 1409 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1410 __pyx_t_4 = __Pyx_PyInt_AsInt(__pyx_t_3); if (unlikely((__pyx_t_4 == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1411 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1412 __pyx_v_self->_count = __pyx_t_4; 1413 } 1414 __pyx_L3:; 1415 1416 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1417 goto __pyx_L0; 1418 __pyx_L1_error:; 1419 __Pyx_XDECREF(__pyx_t_1); 1420 __Pyx_XDECREF(__pyx_t_3); 1421 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.insert", __pyx_clineno, __pyx_lineno, __pyx_filename); 1422 __pyx_r = NULL; 1423 __pyx_L0:; 1424 __Pyx_XDECREF(__pyx_v_res); 1425 __Pyx_XGIVEREF(__pyx_r); 1426 __Pyx_RefNannyFinishContext(); 1427 return __pyx_r; 1428} 1429 1430/* Python wrapper */ 1431static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_19remove(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1432static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_19remove(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1433 PyObject *__pyx_r = 0; 1434 __Pyx_RefNannyDeclarations 1435 __Pyx_RefNannySetupContext("remove (wrapper)", 0); 1436 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_18remove(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1437 __Pyx_RefNannyFinishContext(); 1438 return __pyx_r; 1439} 1440 1441/* "bintrees\qrbtree.pyx":64 1442 * self._count += res 1443 * 1444 * def remove(self, key): # <<<<<<<<<<<<<< 1445 * cdef int result 1446 * result = rb_remove(&self._root, key) 1447 */ 1448 1449static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_18remove(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self, PyObject *__pyx_v_key) { 1450 int __pyx_v_result; 1451 PyObject *__pyx_r = NULL; 1452 __Pyx_RefNannyDeclarations 1453 int __pyx_t_1; 1454 PyObject *__pyx_t_2 = NULL; 1455 PyObject *__pyx_t_3 = NULL; 1456 int __pyx_lineno = 0; 1457 const char *__pyx_filename = NULL; 1458 int __pyx_clineno = 0; 1459 __Pyx_RefNannySetupContext("remove", 0); 1460 1461 /* "bintrees\qrbtree.pyx":66 1462 * def remove(self, key): 1463 * cdef int result 1464 * result = rb_remove(&self._root, key) # <<<<<<<<<<<<<< 1465 * if result == 0: 1466 * raise KeyError(str(key)) 1467 */ 1468 __pyx_v_result = rb_remove((&__pyx_v_self->_root), __pyx_v_key); 1469 1470 /* "bintrees\qrbtree.pyx":67 1471 * cdef int result 1472 * result = rb_remove(&self._root, key) 1473 * if result == 0: # <<<<<<<<<<<<<< 1474 * raise KeyError(str(key)) 1475 * else: 1476 */ 1477 __pyx_t_1 = (__pyx_v_result == 0); 1478 if (__pyx_t_1) { 1479 1480 /* "bintrees\qrbtree.pyx":68 1481 * result = rb_remove(&self._root, key) 1482 * if result == 0: 1483 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 1484 * else: 1485 * self._count -= 1 1486 */ 1487 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1488 __Pyx_GOTREF(__pyx_t_2); 1489 __Pyx_INCREF(__pyx_v_key); 1490 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 1491 __Pyx_GIVEREF(__pyx_v_key); 1492 __pyx_t_3 = PyObject_Call(((PyObject *)((PyObject*)(&PyString_Type))), ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1493 __Pyx_GOTREF(__pyx_t_3); 1494 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1495 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1496 __Pyx_GOTREF(__pyx_t_2); 1497 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 1498 __Pyx_GIVEREF(__pyx_t_3); 1499 __pyx_t_3 = 0; 1500 __pyx_t_3 = PyObject_Call(__pyx_builtin_KeyError, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1501 __Pyx_GOTREF(__pyx_t_3); 1502 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1503 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 1504 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1505 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1506 goto __pyx_L3; 1507 } 1508 /*else*/ { 1509 1510 /* "bintrees\qrbtree.pyx":70 1511 * raise KeyError(str(key)) 1512 * else: 1513 * self._count -= 1 # <<<<<<<<<<<<<< 1514 * 1515 * def max_item(self): 1516 */ 1517 __pyx_v_self->_count = (__pyx_v_self->_count - 1); 1518 } 1519 __pyx_L3:; 1520 1521 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1522 goto __pyx_L0; 1523 __pyx_L1_error:; 1524 __Pyx_XDECREF(__pyx_t_2); 1525 __Pyx_XDECREF(__pyx_t_3); 1526 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.remove", __pyx_clineno, __pyx_lineno, __pyx_filename); 1527 __pyx_r = NULL; 1528 __pyx_L0:; 1529 __Pyx_XGIVEREF(__pyx_r); 1530 __Pyx_RefNannyFinishContext(); 1531 return __pyx_r; 1532} 1533 1534/* Python wrapper */ 1535static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_21max_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1536static char __pyx_doc_8bintrees_7qrbtree_7cRBTree_20max_item[] = " Get item with max key of tree, raises ValueError if tree is empty. "; 1537static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_21max_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1538 PyObject *__pyx_r = 0; 1539 __Pyx_RefNannyDeclarations 1540 __Pyx_RefNannySetupContext("max_item (wrapper)", 0); 1541 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_20max_item(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 1542 __Pyx_RefNannyFinishContext(); 1543 return __pyx_r; 1544} 1545 1546/* "bintrees\qrbtree.pyx":72 1547 * self._count -= 1 1548 * 1549 * def max_item(self): # <<<<<<<<<<<<<< 1550 * """ Get item with max key of tree, raises ValueError if tree is empty. """ 1551 * cdef node_t *node 1552 */ 1553 1554static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_20max_item(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 1555 node_t *__pyx_v_node; 1556 PyObject *__pyx_r = NULL; 1557 __Pyx_RefNannyDeclarations 1558 int __pyx_t_1; 1559 PyObject *__pyx_t_2 = NULL; 1560 int __pyx_lineno = 0; 1561 const char *__pyx_filename = NULL; 1562 int __pyx_clineno = 0; 1563 __Pyx_RefNannySetupContext("max_item", 0); 1564 1565 /* "bintrees\qrbtree.pyx":75 1566 * """ Get item with max key of tree, raises ValueError if tree is empty. """ 1567 * cdef node_t *node 1568 * node = ct_max_node(self._root) # <<<<<<<<<<<<<< 1569 * if node == NULL: # root is None 1570 * raise ValueError("Tree is empty") 1571 */ 1572 __pyx_v_node = ct_max_node(__pyx_v_self->_root); 1573 1574 /* "bintrees\qrbtree.pyx":76 1575 * cdef node_t *node 1576 * node = ct_max_node(self._root) 1577 * if node == NULL: # root is None # <<<<<<<<<<<<<< 1578 * raise ValueError("Tree is empty") 1579 * return (<object>node.key, <object>node.value) 1580 */ 1581 __pyx_t_1 = (__pyx_v_node == NULL); 1582 if (__pyx_t_1) { 1583 1584 /* "bintrees\qrbtree.pyx":77 1585 * node = ct_max_node(self._root) 1586 * if node == NULL: # root is None 1587 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1588 * return (<object>node.key, <object>node.value) 1589 * 1590 */ 1591 __pyx_t_2 = PyObject_Call(__pyx_builtin_ValueError, ((PyObject *)__pyx_k_tuple_4), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1592 __Pyx_GOTREF(__pyx_t_2); 1593 __Pyx_Raise(__pyx_t_2, 0, 0, 0); 1594 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 1595 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1596 goto __pyx_L3; 1597 } 1598 __pyx_L3:; 1599 1600 /* "bintrees\qrbtree.pyx":78 1601 * if node == NULL: # root is None 1602 * raise ValueError("Tree is empty") 1603 * return (<object>node.key, <object>node.value) # <<<<<<<<<<<<<< 1604 * 1605 * def min_item(self): 1606 */ 1607 __Pyx_XDECREF(__pyx_r); 1608 __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 78; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1609 __Pyx_GOTREF(__pyx_t_2); 1610 __Pyx_INCREF(((PyObject *)__pyx_v_node->key)); 1611 PyTuple_SET_ITEM(__pyx_t_2, 0, ((PyObject *)__pyx_v_node->key)); 1612 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->key)); 1613 __Pyx_INCREF(((PyObject *)__pyx_v_node->value)); 1614 PyTuple_SET_ITEM(__pyx_t_2, 1, ((PyObject *)__pyx_v_node->value)); 1615 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->value)); 1616 __pyx_r = ((PyObject *)__pyx_t_2); 1617 __pyx_t_2 = 0; 1618 goto __pyx_L0; 1619 1620 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1621 goto __pyx_L0; 1622 __pyx_L1_error:; 1623 __Pyx_XDECREF(__pyx_t_2); 1624 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.max_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 1625 __pyx_r = NULL; 1626 __pyx_L0:; 1627 __Pyx_XGIVEREF(__pyx_r); 1628 __Pyx_RefNannyFinishContext(); 1629 return __pyx_r; 1630} 1631 1632/* Python wrapper */ 1633static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_23min_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1634static char __pyx_doc_8bintrees_7qrbtree_7cRBTree_22min_item[] = " Get item with min key of tree, raises ValueError if tree is empty. "; 1635static PyObject *__pyx_pw_8bintrees_7qrbtree_7cRBTree_23min_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1636 PyObject *__pyx_r = 0; 1637 __Pyx_RefNannyDeclarations 1638 __Pyx_RefNannySetupContext("min_item (wrapper)", 0); 1639 __pyx_r = __pyx_pf_8bintrees_7qrbtree_7cRBTree_22min_item(((struct __pyx_obj_8bintrees_7qrbtree_cRBTree *)__pyx_v_self)); 1640 __Pyx_RefNannyFinishContext(); 1641 return __pyx_r; 1642} 1643 1644/* "bintrees\qrbtree.pyx":80 1645 * return (<object>node.key, <object>node.value) 1646 * 1647 * def min_item(self): # <<<<<<<<<<<<<< 1648 * """ Get item with min key of tree, raises ValueError if tree is empty. """ 1649 * cdef node_t *node 1650 */ 1651 1652static PyObject *__pyx_pf_8bintrees_7qrbtree_7cRBTree_22min_item(struct __pyx_obj_8bintrees_7qrbtree_cRBTree *__pyx_v_self) { 1653 node_t *__pyx_v_node; 1654 PyObject *__pyx_r = NULL; 1655 __Pyx_RefNannyDeclarations 1656 int __pyx_t_1; 1657 PyObject *__pyx_t_2 = NULL; 1658 int __pyx_lineno = 0; 1659 const char *__pyx_filename = NULL; 1660 int __pyx_clineno = 0; 1661 __Pyx_RefNannySetupContext("min_item", 0); 1662 1663 /* "bintrees\qrbtree.pyx":83 1664 * """ Get item with min key of tree, raises ValueError if tree is empty. """ 1665 * cdef node_t *node 1666 * node = ct_min_node(self._root) # <<<<<<<<<<<<<< 1667 * if node == NULL: # root is None 1668 * raise ValueError("Tree is empty") 1669 */ 1670 __pyx_v_node = ct_min_node(__pyx_v_self->_root); 1671 1672 /* "bintrees\qrbtree.pyx":84 1673 * cdef node_t *node 1674 * node = ct_min_node(self._root) 1675 * if node == NULL: # root is None # <<<<<<<<<<<<<< 1676 * raise ValueError("Tree is empty") 1677 * return (<object>node.key, <object>node.value) 1678 */ 1679 __pyx_t_1 = (__pyx_v_node == NULL); 1680 if (__pyx_t_1) { 1681 1682 /* "bintrees\qrbtree.pyx":85 1683 * node = ct_min_node(self._root) 1684 * if node == NULL: # root is None 1685 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1686 * return (<object>node.key, <object>node.value) 1687 */ 1688 __pyx_t_2 = PyObject_Call(__pyx_builtin_ValueError, ((PyObject *)__pyx_k_tuple_5), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1689 __Pyx_GOTREF(__pyx_t_2); 1690 __Pyx_Raise(__pyx_t_2, 0, 0, 0); 1691 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 1692 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1693 goto __pyx_L3; 1694 } 1695 __pyx_L3:; 1696 1697 /* "bintrees\qrbtree.pyx":86 1698 * if node == NULL: # root is None 1699 * raise ValueError("Tree is empty") 1700 * return (<object>node.key, <object>node.value) # <<<<<<<<<<<<<< 1701 */ 1702 __Pyx_XDECREF(__pyx_r); 1703 __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 86; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1704 __Pyx_GOTREF(__pyx_t_2); 1705 __Pyx_INCREF(((PyObject *)__pyx_v_node->key)); 1706 PyTuple_SET_ITEM(__pyx_t_2, 0, ((PyObject *)__pyx_v_node->key)); 1707 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->key)); 1708 __Pyx_INCREF(((PyObject *)__pyx_v_node->value)); 1709 PyTuple_SET_ITEM(__pyx_t_2, 1, ((PyObject *)__pyx_v_node->value)); 1710 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->value)); 1711 __pyx_r = ((PyObject *)__pyx_t_2); 1712 __pyx_t_2 = 0; 1713 goto __pyx_L0; 1714 1715 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1716 goto __pyx_L0; 1717 __pyx_L1_error:; 1718 __Pyx_XDECREF(__pyx_t_2); 1719 __Pyx_AddTraceback("bintrees.qrbtree.cRBTree.min_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 1720 __pyx_r = NULL; 1721 __pyx_L0:; 1722 __Pyx_XGIVEREF(__pyx_r); 1723 __Pyx_RefNannyFinishContext(); 1724 return __pyx_r; 1725} 1726 1727static PyObject *__pyx_tp_new_8bintrees_7qrbtree_cRBTree(PyTypeObject *t, PyObject *a, PyObject *k) { 1728 PyObject *o = (*t->tp_alloc)(t, 0); 1729 if (!o) return 0; 1730 if (__pyx_pw_8bintrees_7qrbtree_7cRBTree_1__cinit__(o, a, k) < 0) { 1731 Py_DECREF(o); o = 0; 1732 } 1733 return o; 1734} 1735 1736static void __pyx_tp_dealloc_8bintrees_7qrbtree_cRBTree(PyObject *o) { 1737 { 1738 PyObject *etype, *eval, *etb; 1739 PyErr_Fetch(&etype, &eval, &etb); 1740 ++Py_REFCNT(o); 1741 __pyx_pw_8bintrees_7qrbtree_7cRBTree_3__dealloc__(o); 1742 if (PyErr_Occurred()) PyErr_WriteUnraisable(o); 1743 --Py_REFCNT(o); 1744 PyErr_Restore(etype, eval, etb); 1745 } 1746 (*Py_TYPE(o)->tp_free)(o); 1747} 1748 1749static PyMethodDef __pyx_methods_8bintrees_7qrbtree_cRBTree[] = { 1750 {__Pyx_NAMESTR("count"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_5count, METH_NOARGS, __Pyx_DOCSTR(0)}, 1751 {__Pyx_NAMESTR("__getstate__"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_7__getstate__, METH_NOARGS, __Pyx_DOCSTR(0)}, 1752 {__Pyx_NAMESTR("__setstate__"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_9__setstate__, METH_O, __Pyx_DOCSTR(0)}, 1753 {__Pyx_NAMESTR("clear"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_11clear, METH_NOARGS, __Pyx_DOCSTR(0)}, 1754 {__Pyx_NAMESTR("get_value"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_13get_value, METH_O, __Pyx_DOCSTR(0)}, 1755 {__Pyx_NAMESTR("get_walker"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_15get_walker, METH_NOARGS, __Pyx_DOCSTR(0)}, 1756 {__Pyx_NAMESTR("insert"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_17insert, METH_VARARGS|METH_KEYWORDS, __Pyx_DOCSTR(0)}, 1757 {__Pyx_NAMESTR("remove"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_19remove, METH_O, __Pyx_DOCSTR(0)}, 1758 {__Pyx_NAMESTR("max_item"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_21max_item, METH_NOARGS, __Pyx_DOCSTR(__pyx_doc_8bintrees_7qrbtree_7cRBTree_20max_item)}, 1759 {__Pyx_NAMESTR("min_item"), (PyCFunction)__pyx_pw_8bintrees_7qrbtree_7cRBTree_23min_item, METH_NOARGS, __Pyx_DOCSTR(__pyx_doc_8bintrees_7qrbtree_7cRBTree_22min_item)}, 1760 {0, 0, 0, 0} 1761}; 1762 1763static PyNumberMethods __pyx_tp_as_number_cRBTree = { 1764 0, /*nb_add*/ 1765 0, /*nb_subtract*/ 1766 0, /*nb_multiply*/ 1767 #if PY_MAJOR_VERSION < 3 1768 0, /*nb_divide*/ 1769 #endif 1770 0, /*nb_remainder*/ 1771 0, /*nb_divmod*/ 1772 0, /*nb_power*/ 1773 0, /*nb_negative*/ 1774 0, /*nb_positive*/ 1775 0, /*nb_absolute*/ 1776 0, /*nb_nonzero*/ 1777 0, /*nb_invert*/ 1778 0, /*nb_lshift*/ 1779 0, /*nb_rshift*/ 1780 0, /*nb_and*/ 1781 0, /*nb_xor*/ 1782 0, /*nb_or*/ 1783 #if PY_MAJOR_VERSION < 3 1784 0, /*nb_coerce*/ 1785 #endif 1786 0, /*nb_int*/ 1787 #if PY_MAJOR_VERSION < 3 1788 0, /*nb_long*/ 1789 #else 1790 0, /*reserved*/ 1791 #endif 1792 0, /*nb_float*/ 1793 #if PY_MAJOR_VERSION < 3 1794 0, /*nb_oct*/ 1795 #endif 1796 #if PY_MAJOR_VERSION < 3 1797 0, /*nb_hex*/ 1798 #endif 1799 0, /*nb_inplace_add*/ 1800 0, /*nb_inplace_subtract*/ 1801 0, /*nb_inplace_multiply*/ 1802 #if PY_MAJOR_VERSION < 3 1803 0, /*nb_inplace_divide*/ 1804 #endif 1805 0, /*nb_inplace_remainder*/ 1806 0, /*nb_inplace_power*/ 1807 0, /*nb_inplace_lshift*/ 1808 0, /*nb_inplace_rshift*/ 1809 0, /*nb_inplace_and*/ 1810 0, /*nb_inplace_xor*/ 1811 0, /*nb_inplace_or*/ 1812 0, /*nb_floor_divide*/ 1813 0, /*nb_true_divide*/ 1814 0, /*nb_inplace_floor_divide*/ 1815 0, /*nb_inplace_true_divide*/ 1816 #if PY_VERSION_HEX >= 0x02050000 1817 0, /*nb_index*/ 1818 #endif 1819}; 1820 1821static PySequenceMethods __pyx_tp_as_sequence_cRBTree = { 1822 0, /*sq_length*/ 1823 0, /*sq_concat*/ 1824 0, /*sq_repeat*/ 1825 0, /*sq_item*/ 1826 0, /*sq_slice*/ 1827 0, /*sq_ass_item*/ 1828 0, /*sq_ass_slice*/ 1829 0, /*sq_contains*/ 1830 0, /*sq_inplace_concat*/ 1831 0, /*sq_inplace_repeat*/ 1832}; 1833 1834static PyMappingMethods __pyx_tp_as_mapping_cRBTree = { 1835 0, /*mp_length*/ 1836 0, /*mp_subscript*/ 1837 0, /*mp_ass_subscript*/ 1838}; 1839 1840static PyBufferProcs __pyx_tp_as_buffer_cRBTree = { 1841 #if PY_MAJOR_VERSION < 3 1842 0, /*bf_getreadbuffer*/ 1843 #endif 1844 #if PY_MAJOR_VERSION < 3 1845 0, /*bf_getwritebuffer*/ 1846 #endif 1847 #if PY_MAJOR_VERSION < 3 1848 0, /*bf_getsegcount*/ 1849 #endif 1850 #if PY_MAJOR_VERSION < 3 1851 0, /*bf_getcharbuffer*/ 1852 #endif 1853 #if PY_VERSION_HEX >= 0x02060000 1854 0, /*bf_getbuffer*/ 1855 #endif 1856 #if PY_VERSION_HEX >= 0x02060000 1857 0, /*bf_releasebuffer*/ 1858 #endif 1859}; 1860 1861static PyTypeObject __pyx_type_8bintrees_7qrbtree_cRBTree = { 1862 PyVarObject_HEAD_INIT(0, 0) 1863 __Pyx_NAMESTR("bintrees.qrbtree.cRBTree"), /*tp_name*/ 1864 sizeof(struct __pyx_obj_8bintrees_7qrbtree_cRBTree), /*tp_basicsize*/ 1865 0, /*tp_itemsize*/ 1866 __pyx_tp_dealloc_8bintrees_7qrbtree_cRBTree, /*tp_dealloc*/ 1867 0, /*tp_print*/ 1868 0, /*tp_getattr*/ 1869 0, /*tp_setattr*/ 1870 #if PY_MAJOR_VERSION < 3 1871 0, /*tp_compare*/ 1872 #else 1873 0, /*reserved*/ 1874 #endif 1875 0, /*tp_repr*/ 1876 &__pyx_tp_as_number_cRBTree, /*tp_as_number*/ 1877 &__pyx_tp_as_sequence_cRBTree, /*tp_as_sequence*/ 1878 &__pyx_tp_as_mapping_cRBTree, /*tp_as_mapping*/ 1879 0, /*tp_hash*/ 1880 0, /*tp_call*/ 1881 0, /*tp_str*/ 1882 0, /*tp_getattro*/ 1883 0, /*tp_setattro*/ 1884 &__pyx_tp_as_buffer_cRBTree, /*tp_as_buffer*/ 1885 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_CHECKTYPES|Py_TPFLAGS_HAVE_NEWBUFFER|Py_TPFLAGS_BASETYPE, /*tp_flags*/ 1886 0, /*tp_doc*/ 1887 0, /*tp_traverse*/ 1888 0, /*tp_clear*/ 1889 0, /*tp_richcompare*/ 1890 0, /*tp_weaklistoffset*/ 1891 0, /*tp_iter*/ 1892 0, /*tp_iternext*/ 1893 __pyx_methods_8bintrees_7qrbtree_cRBTree, /*tp_methods*/ 1894 0, /*tp_members*/ 1895 0, /*tp_getset*/ 1896 0, /*tp_base*/ 1897 0, /*tp_dict*/ 1898 0, /*tp_descr_get*/ 1899 0, /*tp_descr_set*/ 1900 0, /*tp_dictoffset*/ 1901 0, /*tp_init*/ 1902 0, /*tp_alloc*/ 1903 __pyx_tp_new_8bintrees_7qrbtree_cRBTree, /*tp_new*/ 1904 0, /*tp_free*/ 1905 0, /*tp_is_gc*/ 1906 0, /*tp_bases*/ 1907 0, /*tp_mro*/ 1908 0, /*tp_cache*/ 1909 0, /*tp_subclasses*/ 1910 0, /*tp_weaklist*/ 1911 0, /*tp_del*/ 1912 #if PY_VERSION_HEX >= 0x02060000 1913 0, /*tp_version_tag*/ 1914 #endif 1915}; 1916 1917static PyMethodDef __pyx_methods[] = { 1918 {0, 0, 0, 0} 1919}; 1920 1921#if PY_MAJOR_VERSION >= 3 1922static struct PyModuleDef __pyx_moduledef = { 1923 PyModuleDef_HEAD_INIT, 1924 __Pyx_NAMESTR("qrbtree"), 1925 0, /* m_doc */ 1926 -1, /* m_size */ 1927 __pyx_methods /* m_methods */, 1928 NULL, /* m_reload */ 1929 NULL, /* m_traverse */ 1930 NULL, /* m_clear */ 1931 NULL /* m_free */ 1932}; 1933#endif 1934 1935static __Pyx_StringTabEntry __pyx_string_tab[] = { 1936 {&__pyx_kp_s_1, __pyx_k_1, sizeof(__pyx_k_1), 0, 0, 1, 0}, 1937 {&__pyx_kp_s_3, __pyx_k_3, sizeof(__pyx_k_3), 0, 0, 1, 0}, 1938 {&__pyx_n_s__KeyError, __pyx_k__KeyError, sizeof(__pyx_k__KeyError), 0, 0, 1, 1}, 1939 {&__pyx_n_s__MemoryError, __pyx_k__MemoryError, sizeof(__pyx_k__MemoryError), 0, 0, 1, 1}, 1940 {&__pyx_n_s__ValueError, __pyx_k__ValueError, sizeof(__pyx_k__ValueError), 0, 0, 1, 1}, 1941 {&__pyx_n_s____all__, __pyx_k____all__, sizeof(__pyx_k____all__), 0, 0, 1, 1}, 1942 {&__pyx_n_s____main__, __pyx_k____main__, sizeof(__pyx_k____main__), 0, 0, 1, 1}, 1943 {&__pyx_n_s____test__, __pyx_k____test__, sizeof(__pyx_k____test__), 0, 0, 1, 1}, 1944 {&__pyx_n_s__cRBTree, __pyx_k__cRBTree, sizeof(__pyx_k__cRBTree), 0, 0, 1, 1}, 1945 {&__pyx_n_s__cWalker, __pyx_k__cWalker, sizeof(__pyx_k__cWalker), 0, 0, 1, 1}, 1946 {&__pyx_n_s__count, __pyx_k__count, sizeof(__pyx_k__count), 0, 0, 1, 1}, 1947 {&__pyx_n_s__cwalker, __pyx_k__cwalker, sizeof(__pyx_k__cwalker), 0, 0, 1, 1}, 1948 {&__pyx_n_s__items, __pyx_k__items, sizeof(__pyx_k__items), 0, 0, 1, 1}, 1949 {&__pyx_n_s__key, __pyx_k__key, sizeof(__pyx_k__key), 0, 0, 1, 1}, 1950 {&__pyx_n_s__property, __pyx_k__property, sizeof(__pyx_k__property), 0, 0, 1, 1}, 1951 {&__pyx_n_s__update, __pyx_k__update, sizeof(__pyx_k__update), 0, 0, 1, 1}, 1952 {&__pyx_n_s__value, __pyx_k__value, sizeof(__pyx_k__value), 0, 0, 1, 1}, 1953 {0, 0, 0, 0, 0, 0, 0} 1954}; 1955static int __Pyx_InitCachedBuiltins(void) { 1956 __pyx_builtin_property = __Pyx_GetName(__pyx_b, __pyx_n_s__property); if (!__pyx_builtin_property) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1957 __pyx_builtin_KeyError = __Pyx_GetName(__pyx_b, __pyx_n_s__KeyError); if (!__pyx_builtin_KeyError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1958 __pyx_builtin_MemoryError = __Pyx_GetName(__pyx_b, __pyx_n_s__MemoryError); if (!__pyx_builtin_MemoryError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1959 __pyx_builtin_ValueError = __Pyx_GetName(__pyx_b, __pyx_n_s__ValueError); if (!__pyx_builtin_ValueError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1960 return 0; 1961 __pyx_L1_error:; 1962 return -1; 1963} 1964 1965static int __Pyx_InitCachedConstants(void) { 1966 __Pyx_RefNannyDeclarations 1967 __Pyx_RefNannySetupContext("__Pyx_InitCachedConstants", 0); 1968 1969 /* "bintrees\qrbtree.pyx":60 1970 * res = rb_insert(&self._root, key, value) 1971 * if res < 0: 1972 * raise MemoryError('Can not allocate memory for node structure.') # <<<<<<<<<<<<<< 1973 * else: 1974 * self._count += res 1975 */ 1976 __pyx_k_tuple_2 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1977 __Pyx_GOTREF(__pyx_k_tuple_2); 1978 __Pyx_INCREF(((PyObject *)__pyx_kp_s_1)); 1979 PyTuple_SET_ITEM(__pyx_k_tuple_2, 0, ((PyObject *)__pyx_kp_s_1)); 1980 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_1)); 1981 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_2)); 1982 1983 /* "bintrees\qrbtree.pyx":77 1984 * node = ct_max_node(self._root) 1985 * if node == NULL: # root is None 1986 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1987 * return (<object>node.key, <object>node.value) 1988 * 1989 */ 1990 __pyx_k_tuple_4 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1991 __Pyx_GOTREF(__pyx_k_tuple_4); 1992 __Pyx_INCREF(((PyObject *)__pyx_kp_s_3)); 1993 PyTuple_SET_ITEM(__pyx_k_tuple_4, 0, ((PyObject *)__pyx_kp_s_3)); 1994 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_3)); 1995 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_4)); 1996 1997 /* "bintrees\qrbtree.pyx":85 1998 * node = ct_min_node(self._root) 1999 * if node == NULL: # root is None 2000 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 2001 * return (<object>node.key, <object>node.value) 2002 */ 2003 __pyx_k_tuple_5 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2004 __Pyx_GOTREF(__pyx_k_tuple_5); 2005 __Pyx_INCREF(((PyObject *)__pyx_kp_s_3)); 2006 PyTuple_SET_ITEM(__pyx_k_tuple_5, 0, ((PyObject *)__pyx_kp_s_3)); 2007 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_3)); 2008 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_5)); 2009 __Pyx_RefNannyFinishContext(); 2010 return 0; 2011 __pyx_L1_error:; 2012 __Pyx_RefNannyFinishContext(); 2013 return -1; 2014} 2015 2016static int __Pyx_InitGlobals(void) { 2017 if (__Pyx_InitStrings(__pyx_string_tab) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2018 __pyx_int_0 = PyInt_FromLong(0); if (unlikely(!__pyx_int_0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2019 return 0; 2020 __pyx_L1_error:; 2021 return -1; 2022} 2023 2024#if PY_MAJOR_VERSION < 3 2025PyMODINIT_FUNC initqrbtree(void); /*proto*/ 2026PyMODINIT_FUNC initqrbtree(void) 2027#else 2028PyMODINIT_FUNC PyInit_qrbtree(void); /*proto*/ 2029PyMODINIT_FUNC PyInit_qrbtree(void) 2030#endif 2031{ 2032 PyObject *__pyx_t_1 = NULL; 2033 PyObject *__pyx_t_2 = NULL; 2034 __Pyx_RefNannyDeclarations 2035 #if CYTHON_REFNANNY 2036 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("refnanny"); 2037 if (!__Pyx_RefNanny) { 2038 PyErr_Clear(); 2039 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("Cython.Runtime.refnanny"); 2040 if (!__Pyx_RefNanny) 2041 Py_FatalError("failed to import 'refnanny' module"); 2042 } 2043 #endif 2044 __Pyx_RefNannySetupContext("PyMODINIT_FUNC PyInit_qrbtree(void)", 0); 2045 if ( __Pyx_check_binary_version() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2046 __pyx_empty_tuple = PyTuple_New(0); if (unlikely(!__pyx_empty_tuple)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2047 __pyx_empty_bytes = PyBytes_FromStringAndSize("", 0); if (unlikely(!__pyx_empty_bytes)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2048 #ifdef __Pyx_CyFunction_USED 2049 if (__Pyx_CyFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2050 #endif 2051 #ifdef __Pyx_FusedFunction_USED 2052 if (__pyx_FusedFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2053 #endif 2054 #ifdef __Pyx_Generator_USED 2055 if (__pyx_Generator_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2056 #endif 2057 /*--- Library function declarations ---*/ 2058 /*--- Threads initialization code ---*/ 2059 #if defined(__PYX_FORCE_INIT_THREADS) && __PYX_FORCE_INIT_THREADS 2060 #ifdef WITH_THREAD /* Python build with threading support? */ 2061 PyEval_InitThreads(); 2062 #endif 2063 #endif 2064 /*--- Module creation code ---*/ 2065 #if PY_MAJOR_VERSION < 3 2066 __pyx_m = Py_InitModule4(__Pyx_NAMESTR("qrbtree"), __pyx_methods, 0, 0, PYTHON_API_VERSION); Py_XINCREF(__pyx_m); 2067 #else 2068 __pyx_m = PyModule_Create(&__pyx_moduledef); 2069 #endif 2070 if (unlikely(!__pyx_m)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2071 #if PY_MAJOR_VERSION >= 3 2072 { 2073 PyObject *modules = PyImport_GetModuleDict(); if (unlikely(!modules)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2074 if (!PyDict_GetItemString(modules, "bintrees.qrbtree")) { 2075 if (unlikely(PyDict_SetItemString(modules, "bintrees.qrbtree", __pyx_m) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2076 } 2077 } 2078 #endif 2079 __pyx_b = PyImport_AddModule(__Pyx_NAMESTR(__Pyx_BUILTIN_MODULE_NAME)); if (unlikely(!__pyx_b)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2080 #if CYTHON_COMPILING_IN_PYPY 2081 Py_INCREF(__pyx_b); 2082 #endif 2083 if (__Pyx_SetAttrString(__pyx_m, "__builtins__", __pyx_b) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2084 /*--- Initialize various global constants etc. ---*/ 2085 if (unlikely(__Pyx_InitGlobals() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2086 if (__pyx_module_is_main_bintrees__qrbtree) { 2087 if (__Pyx_SetAttrString(__pyx_m, "__name__", __pyx_n_s____main__) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2088 } 2089 /*--- Builtin init code ---*/ 2090 if (unlikely(__Pyx_InitCachedBuiltins() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2091 /*--- Constants init code ---*/ 2092 if (unlikely(__Pyx_InitCachedConstants() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2093 /*--- Global init code ---*/ 2094 /*--- Variable export code ---*/ 2095 /*--- Function export code ---*/ 2096 /*--- Type init code ---*/ 2097 if (PyType_Ready(&__pyx_type_8bintrees_7qrbtree_cRBTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2098 if (__Pyx_SetAttrString(__pyx_m, "cRBTree", (PyObject *)&__pyx_type_8bintrees_7qrbtree_cRBTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2099 __pyx_ptype_8bintrees_7qrbtree_cRBTree = &__pyx_type_8bintrees_7qrbtree_cRBTree; 2100 /*--- Type import code ---*/ 2101 __pyx_ptype_8bintrees_7cwalker_cWalker = __Pyx_ImportType("bintrees.cwalker", "cWalker", sizeof(struct __pyx_obj_8bintrees_7cwalker_cWalker), 1); if (unlikely(!__pyx_ptype_8bintrees_7cwalker_cWalker)) {__pyx_filename = __pyx_f[1]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2102 __pyx_vtabptr_8bintrees_7cwalker_cWalker = (struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker*)__Pyx_GetVtable(__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict); if (unlikely(!__pyx_vtabptr_8bintrees_7cwalker_cWalker)) {__pyx_filename = __pyx_f[1]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2103 /*--- Variable import code ---*/ 2104 /*--- Function import code ---*/ 2105 /*--- Execution code ---*/ 2106 2107 /* "bintrees\qrbtree.pyx":9 2108 * # License: MIT License 2109 * 2110 * __all__ = ['cRBTree'] # <<<<<<<<<<<<<< 2111 * 2112 * from cwalker import cWalker 2113 */ 2114 __pyx_t_1 = PyList_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 9; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2115 __Pyx_GOTREF(__pyx_t_1); 2116 __Pyx_INCREF(((PyObject *)__pyx_n_s__cRBTree)); 2117 PyList_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_n_s__cRBTree)); 2118 __Pyx_GIVEREF(((PyObject *)__pyx_n_s__cRBTree)); 2119 if (PyObject_SetAttr(__pyx_m, __pyx_n_s____all__, ((PyObject *)__pyx_t_1)) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 9; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2120 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2121 2122 /* "bintrees\qrbtree.pyx":11 2123 * __all__ = ['cRBTree'] 2124 * 2125 * from cwalker import cWalker # <<<<<<<<<<<<<< 2126 * 2127 * from cwalker cimport * 2128 */ 2129 __pyx_t_1 = PyList_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2130 __Pyx_GOTREF(__pyx_t_1); 2131 __Pyx_INCREF(((PyObject *)__pyx_n_s__cWalker)); 2132 PyList_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_n_s__cWalker)); 2133 __Pyx_GIVEREF(((PyObject *)__pyx_n_s__cWalker)); 2134 __pyx_t_2 = __Pyx_Import(((PyObject *)__pyx_n_s__cwalker), ((PyObject *)__pyx_t_1), -1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2135 __Pyx_GOTREF(__pyx_t_2); 2136 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2137 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 2138 2139 /* "bintrees\qrbtree.pyx":30 2140 * 2141 * @property 2142 * def count(self): # <<<<<<<<<<<<<< 2143 * return self._count 2144 * 2145 */ 2146 __pyx_t_2 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_7qrbtree_cRBTree, __pyx_n_s__count); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 30; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2147 __Pyx_GOTREF(__pyx_t_2); 2148 __pyx_t_1 = PyTuple_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2149 __Pyx_GOTREF(__pyx_t_1); 2150 PyTuple_SET_ITEM(__pyx_t_1, 0, __pyx_t_2); 2151 __Pyx_GIVEREF(__pyx_t_2); 2152 __pyx_t_2 = 0; 2153 __pyx_t_2 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_1), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2154 __Pyx_GOTREF(__pyx_t_2); 2155 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2156 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_7qrbtree_cRBTree->tp_dict, __pyx_n_s__count, __pyx_t_2) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 30; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2157 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 2158 PyType_Modified(__pyx_ptype_8bintrees_7qrbtree_cRBTree); 2159 2160 /* "bintrees\qrbtree.pyx":1 2161 * #!/usr/bin/env python # <<<<<<<<<<<<<< 2162 * #coding:utf-8 2163 * # Author: mozman 2164 */ 2165 __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2166 __Pyx_GOTREF(((PyObject *)__pyx_t_2)); 2167 if (PyObject_SetAttr(__pyx_m, __pyx_n_s____test__, ((PyObject *)__pyx_t_2)) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2168 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2169 goto __pyx_L0; 2170 __pyx_L1_error:; 2171 __Pyx_XDECREF(__pyx_t_1); 2172 __Pyx_XDECREF(__pyx_t_2); 2173 if (__pyx_m) { 2174 __Pyx_AddTraceback("init bintrees.qrbtree", __pyx_clineno, __pyx_lineno, __pyx_filename); 2175 Py_DECREF(__pyx_m); __pyx_m = 0; 2176 } else if (!PyErr_Occurred()) { 2177 PyErr_SetString(PyExc_ImportError, "init bintrees.qrbtree"); 2178 } 2179 __pyx_L0:; 2180 __Pyx_RefNannyFinishContext(); 2181 #if PY_MAJOR_VERSION < 3 2182 return; 2183 #else 2184 return __pyx_m; 2185 #endif 2186} 2187 2188/* Runtime support code */ 2189#if CYTHON_REFNANNY 2190static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname) { 2191 PyObject *m = NULL, *p = NULL; 2192 void *r = NULL; 2193 m = PyImport_ImportModule((char *)modname); 2194 if (!m) goto end; 2195 p = PyObject_GetAttrString(m, (char *)"RefNannyAPI"); 2196 if (!p) goto end; 2197 r = PyLong_AsVoidPtr(p); 2198end: 2199 Py_XDECREF(p); 2200 Py_XDECREF(m); 2201 return (__Pyx_RefNannyAPIStruct *)r; 2202} 2203#endif /* CYTHON_REFNANNY */ 2204 2205static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name) { 2206 PyObject *result; 2207 result = PyObject_GetAttr(dict, name); 2208 if (!result) { 2209 if (dict != __pyx_b) { 2210 PyErr_Clear(); 2211 result = PyObject_GetAttr(__pyx_b, name); 2212 } 2213 if (!result) { 2214 PyErr_SetObject(PyExc_NameError, name); 2215 } 2216 } 2217 return result; 2218} 2219 2220static void __Pyx_RaiseDoubleKeywordsError( 2221 const char* func_name, 2222 PyObject* kw_name) 2223{ 2224 PyErr_Format(PyExc_TypeError, 2225 #if PY_MAJOR_VERSION >= 3 2226 "%s() got multiple values for keyword argument '%U'", func_name, kw_name); 2227 #else 2228 "%s() got multiple values for keyword argument '%s'", func_name, 2229 PyString_AsString(kw_name)); 2230 #endif 2231} 2232 2233static int __Pyx_ParseOptionalKeywords( 2234 PyObject *kwds, 2235 PyObject **argnames[], 2236 PyObject *kwds2, 2237 PyObject *values[], 2238 Py_ssize_t num_pos_args, 2239 const char* function_name) 2240{ 2241 PyObject *key = 0, *value = 0; 2242 Py_ssize_t pos = 0; 2243 PyObject*** name; 2244 PyObject*** first_kw_arg = argnames + num_pos_args; 2245 while (PyDict_Next(kwds, &pos, &key, &value)) { 2246 name = first_kw_arg; 2247 while (*name && (**name != key)) name++; 2248 if (*name) { 2249 values[name-argnames] = value; 2250 continue; 2251 } 2252 name = first_kw_arg; 2253 #if PY_MAJOR_VERSION < 3 2254 if (likely(PyString_CheckExact(key)) || likely(PyString_Check(key))) { 2255 while (*name) { 2256 if ((CYTHON_COMPILING_IN_PYPY || PyString_GET_SIZE(**name) == PyString_GET_SIZE(key)) 2257 && _PyString_Eq(**name, key)) { 2258 values[name-argnames] = value; 2259 break; 2260 } 2261 name++; 2262 } 2263 if (*name) continue; 2264 else { 2265 PyObject*** argname = argnames; 2266 while (argname != first_kw_arg) { 2267 if ((**argname == key) || ( 2268 (CYTHON_COMPILING_IN_PYPY || PyString_GET_SIZE(**argname) == PyString_GET_SIZE(key)) 2269 && _PyString_Eq(**argname, key))) { 2270 goto arg_passed_twice; 2271 } 2272 argname++; 2273 } 2274 } 2275 } else 2276 #endif 2277 if (likely(PyUnicode_Check(key))) { 2278 while (*name) { 2279 int cmp = (**name == key) ? 0 : 2280 #if !CYTHON_COMPILING_IN_PYPY && PY_MAJOR_VERSION >= 3 2281 (PyUnicode_GET_SIZE(**name) != PyUnicode_GET_SIZE(key)) ? 1 : 2282 #endif 2283 PyUnicode_Compare(**name, key); 2284 if (cmp < 0 && unlikely(PyErr_Occurred())) goto bad; 2285 if (cmp == 0) { 2286 values[name-argnames] = value; 2287 break; 2288 } 2289 name++; 2290 } 2291 if (*name) continue; 2292 else { 2293 PyObject*** argname = argnames; 2294 while (argname != first_kw_arg) { 2295 int cmp = (**argname == key) ? 0 : 2296 #if !CYTHON_COMPILING_IN_PYPY && PY_MAJOR_VERSION >= 3 2297 (PyUnicode_GET_SIZE(**argname) != PyUnicode_GET_SIZE(key)) ? 1 : 2298 #endif 2299 PyUnicode_Compare(**argname, key); 2300 if (cmp < 0 && unlikely(PyErr_Occurred())) goto bad; 2301 if (cmp == 0) goto arg_passed_twice; 2302 argname++; 2303 } 2304 } 2305 } else 2306 goto invalid_keyword_type; 2307 if (kwds2) { 2308 if (unlikely(PyDict_SetItem(kwds2, key, value))) goto bad; 2309 } else { 2310 goto invalid_keyword; 2311 } 2312 } 2313 return 0; 2314arg_passed_twice: 2315 __Pyx_RaiseDoubleKeywordsError(function_name, key); 2316 goto bad; 2317invalid_keyword_type: 2318 PyErr_Format(PyExc_TypeError, 2319 "%s() keywords must be strings", function_name); 2320 goto bad; 2321invalid_keyword: 2322 PyErr_Format(PyExc_TypeError, 2323 #if PY_MAJOR_VERSION < 3 2324 "%s() got an unexpected keyword argument '%s'", 2325 function_name, PyString_AsString(key)); 2326 #else 2327 "%s() got an unexpected keyword argument '%U'", 2328 function_name, key); 2329 #endif 2330bad: 2331 return -1; 2332} 2333 2334static void __Pyx_RaiseArgtupleInvalid( 2335 const char* func_name, 2336 int exact, 2337 Py_ssize_t num_min, 2338 Py_ssize_t num_max, 2339 Py_ssize_t num_found) 2340{ 2341 Py_ssize_t num_expected; 2342 const char *more_or_less; 2343 if (num_found < num_min) { 2344 num_expected = num_min; 2345 more_or_less = "at least"; 2346 } else { 2347 num_expected = num_max; 2348 more_or_less = "at most"; 2349 } 2350 if (exact) { 2351 more_or_less = "exactly"; 2352 } 2353 PyErr_Format(PyExc_TypeError, 2354 "%s() takes %s %" CYTHON_FORMAT_SSIZE_T "d positional argument%s (%" CYTHON_FORMAT_SSIZE_T "d given)", 2355 func_name, more_or_less, num_expected, 2356 (num_expected == 1) ? "" : "s", num_found); 2357} 2358 2359static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb) { 2360#if CYTHON_COMPILING_IN_CPYTHON 2361 PyObject *tmp_type, *tmp_value, *tmp_tb; 2362 PyThreadState *tstate = PyThreadState_GET(); 2363 tmp_type = tstate->curexc_type; 2364 tmp_value = tstate->curexc_value; 2365 tmp_tb = tstate->curexc_traceback; 2366 tstate->curexc_type = type; 2367 tstate->curexc_value = value; 2368 tstate->curexc_traceback = tb; 2369 Py_XDECREF(tmp_type); 2370 Py_XDECREF(tmp_value); 2371 Py_XDECREF(tmp_tb); 2372#else 2373 PyErr_Restore(type, value, tb); 2374#endif 2375} 2376static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb) { 2377#if CYTHON_COMPILING_IN_CPYTHON 2378 PyThreadState *tstate = PyThreadState_GET(); 2379 *type = tstate->curexc_type; 2380 *value = tstate->curexc_value; 2381 *tb = tstate->curexc_traceback; 2382 tstate->curexc_type = 0; 2383 tstate->curexc_value = 0; 2384 tstate->curexc_traceback = 0; 2385#else 2386 PyErr_Fetch(type, value, tb); 2387#endif 2388} 2389 2390#if PY_MAJOR_VERSION < 3 2391static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, 2392 CYTHON_UNUSED PyObject *cause) { 2393 Py_XINCREF(type); 2394 if (!value || value == Py_None) 2395 value = NULL; 2396 else 2397 Py_INCREF(value); 2398 if (!tb || tb == Py_None) 2399 tb = NULL; 2400 else { 2401 Py_INCREF(tb); 2402 if (!PyTraceBack_Check(tb)) { 2403 PyErr_SetString(PyExc_TypeError, 2404 "raise: arg 3 must be a traceback or None"); 2405 goto raise_error; 2406 } 2407 } 2408 #if PY_VERSION_HEX < 0x02050000 2409 if (PyClass_Check(type)) { 2410 #else 2411 if (PyType_Check(type)) { 2412 #endif 2413#if CYTHON_COMPILING_IN_PYPY 2414 if (!value) { 2415 Py_INCREF(Py_None); 2416 value = Py_None; 2417 } 2418#endif 2419 PyErr_NormalizeException(&type, &value, &tb); 2420 } else { 2421 if (value) { 2422 PyErr_SetString(PyExc_TypeError, 2423 "instance exception may not have a separate value"); 2424 goto raise_error; 2425 } 2426 value = type; 2427 #if PY_VERSION_HEX < 0x02050000 2428 if (PyInstance_Check(type)) { 2429 type = (PyObject*) ((PyInstanceObject*)type)->in_class; 2430 Py_INCREF(type); 2431 } 2432 else { 2433 type = 0; 2434 PyErr_SetString(PyExc_TypeError, 2435 "raise: exception must be an old-style class or instance"); 2436 goto raise_error; 2437 } 2438 #else 2439 type = (PyObject*) Py_TYPE(type); 2440 Py_INCREF(type); 2441 if (!PyType_IsSubtype((PyTypeObject *)type, (PyTypeObject *)PyExc_BaseException)) { 2442 PyErr_SetString(PyExc_TypeError, 2443 "raise: exception class must be a subclass of BaseException"); 2444 goto raise_error; 2445 } 2446 #endif 2447 } 2448 __Pyx_ErrRestore(type, value, tb); 2449 return; 2450raise_error: 2451 Py_XDECREF(value); 2452 Py_XDECREF(type); 2453 Py_XDECREF(tb); 2454 return; 2455} 2456#else /* Python 3+ */ 2457static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause) { 2458 PyObject* owned_instance = NULL; 2459 if (tb == Py_None) { 2460 tb = 0; 2461 } else if (tb && !PyTraceBack_Check(tb)) { 2462 PyErr_SetString(PyExc_TypeError, 2463 "raise: arg 3 must be a traceback or None"); 2464 goto bad; 2465 } 2466 if (value == Py_None) 2467 value = 0; 2468 if (PyExceptionInstance_Check(type)) { 2469 if (value) { 2470 PyErr_SetString(PyExc_TypeError, 2471 "instance exception may not have a separate value"); 2472 goto bad; 2473 } 2474 value = type; 2475 type = (PyObject*) Py_TYPE(value); 2476 } else if (PyExceptionClass_Check(type)) { 2477 PyObject *args; 2478 if (!value) 2479 args = PyTuple_New(0); 2480 else if (PyTuple_Check(value)) { 2481 Py_INCREF(value); 2482 args = value; 2483 } 2484 else 2485 args = PyTuple_Pack(1, value); 2486 if (!args) 2487 goto bad; 2488 owned_instance = PyEval_CallObject(type, args); 2489 Py_DECREF(args); 2490 if (!owned_instance) 2491 goto bad; 2492 value = owned_instance; 2493 if (!PyExceptionInstance_Check(value)) { 2494 PyErr_Format(PyExc_TypeError, 2495 "calling %R should have returned an instance of " 2496 "BaseException, not %R", 2497 type, Py_TYPE(value)); 2498 goto bad; 2499 } 2500 } else { 2501 PyErr_SetString(PyExc_TypeError, 2502 "raise: exception class must be a subclass of BaseException"); 2503 goto bad; 2504 } 2505 if (cause && cause != Py_None) { 2506 PyObject *fixed_cause; 2507 if (PyExceptionClass_Check(cause)) { 2508 fixed_cause = PyObject_CallObject(cause, NULL); 2509 if (fixed_cause == NULL) 2510 goto bad; 2511 } 2512 else if (PyExceptionInstance_Check(cause)) { 2513 fixed_cause = cause; 2514 Py_INCREF(fixed_cause); 2515 } 2516 else { 2517 PyErr_SetString(PyExc_TypeError, 2518 "exception causes must derive from " 2519 "BaseException"); 2520 goto bad; 2521 } 2522 PyException_SetCause(value, fixed_cause); 2523 } 2524 PyErr_SetObject(type, value); 2525 if (tb) { 2526 PyThreadState *tstate = PyThreadState_GET(); 2527 PyObject* tmp_tb = tstate->curexc_traceback; 2528 if (tb != tmp_tb) { 2529 Py_INCREF(tb); 2530 tstate->curexc_traceback = tb; 2531 Py_XDECREF(tmp_tb); 2532 } 2533 } 2534bad: 2535 Py_XDECREF(owned_instance); 2536 return; 2537} 2538#endif 2539 2540static PyObject *__Pyx_Import(PyObject *name, PyObject *from_list, long level) { 2541 PyObject *py_import = 0; 2542 PyObject *empty_list = 0; 2543 PyObject *module = 0; 2544 PyObject *global_dict = 0; 2545 PyObject *empty_dict = 0; 2546 PyObject *list; 2547 py_import = __Pyx_GetAttrString(__pyx_b, "__import__"); 2548 if (!py_import) 2549 goto bad; 2550 if (from_list) 2551 list = from_list; 2552 else { 2553 empty_list = PyList_New(0); 2554 if (!empty_list) 2555 goto bad; 2556 list = empty_list; 2557 } 2558 global_dict = PyModule_GetDict(__pyx_m); 2559 if (!global_dict) 2560 goto bad; 2561 empty_dict = PyDict_New(); 2562 if (!empty_dict) 2563 goto bad; 2564 #if PY_VERSION_HEX >= 0x02050000 2565 { 2566 #if PY_MAJOR_VERSION >= 3 2567 if (level == -1) { 2568 if (strchr(__Pyx_MODULE_NAME, '.')) { 2569 /* try package relative import first */ 2570 PyObject *py_level = PyInt_FromLong(1); 2571 if (!py_level) 2572 goto bad; 2573 module = PyObject_CallFunctionObjArgs(py_import, 2574 name, global_dict, empty_dict, list, py_level, NULL); 2575 Py_DECREF(py_level); 2576 if (!module) { 2577 if (!PyErr_ExceptionMatches(PyExc_ImportError)) 2578 goto bad; 2579 PyErr_Clear(); 2580 } 2581 } 2582 level = 0; /* try absolute import on failure */ 2583 } 2584 #endif 2585 if (!module) { 2586 PyObject *py_level = PyInt_FromLong(level); 2587 if (!py_level) 2588 goto bad; 2589 module = PyObject_CallFunctionObjArgs(py_import, 2590 name, global_dict, empty_dict, list, py_level, NULL); 2591 Py_DECREF(py_level); 2592 } 2593 } 2594 #else 2595 if (level>0) { 2596 PyErr_SetString(PyExc_RuntimeError, "Relative import is not supported for Python <=2.4."); 2597 goto bad; 2598 } 2599 module = PyObject_CallFunctionObjArgs(py_import, 2600 name, global_dict, empty_dict, list, NULL); 2601 #endif 2602bad: 2603 Py_XDECREF(empty_list); 2604 Py_XDECREF(py_import); 2605 Py_XDECREF(empty_dict); 2606 return module; 2607} 2608 2609static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject* x) { 2610 const unsigned char neg_one = (unsigned char)-1, const_zero = 0; 2611 const int is_unsigned = neg_one > const_zero; 2612 if (sizeof(unsigned char) < sizeof(long)) { 2613 long val = __Pyx_PyInt_AsLong(x); 2614 if (unlikely(val != (long)(unsigned char)val)) { 2615 if (!unlikely(val == -1 && PyErr_Occurred())) { 2616 PyErr_SetString(PyExc_OverflowError, 2617 (is_unsigned && unlikely(val < 0)) ? 2618 "can't convert negative value to unsigned char" : 2619 "value too large to convert to unsigned char"); 2620 } 2621 return (unsigned char)-1; 2622 } 2623 return (unsigned char)val; 2624 } 2625 return (unsigned char)__Pyx_PyInt_AsUnsignedLong(x); 2626} 2627 2628static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject* x) { 2629 const unsigned short neg_one = (unsigned short)-1, const_zero = 0; 2630 const int is_unsigned = neg_one > const_zero; 2631 if (sizeof(unsigned short) < sizeof(long)) { 2632 long val = __Pyx_PyInt_AsLong(x); 2633 if (unlikely(val != (long)(unsigned short)val)) { 2634 if (!unlikely(val == -1 && PyErr_Occurred())) { 2635 PyErr_SetString(PyExc_OverflowError, 2636 (is_unsigned && unlikely(val < 0)) ? 2637 "can't convert negative value to unsigned short" : 2638 "value too large to convert to unsigned short"); 2639 } 2640 return (unsigned short)-1; 2641 } 2642 return (unsigned short)val; 2643 } 2644 return (unsigned short)__Pyx_PyInt_AsUnsignedLong(x); 2645} 2646 2647static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject* x) { 2648 const unsigned int neg_one = (unsigned int)-1, const_zero = 0; 2649 const int is_unsigned = neg_one > const_zero; 2650 if (sizeof(unsigned int) < sizeof(long)) { 2651 long val = __Pyx_PyInt_AsLong(x); 2652 if (unlikely(val != (long)(unsigned int)val)) { 2653 if (!unlikely(val == -1 && PyErr_Occurred())) { 2654 PyErr_SetString(PyExc_OverflowError, 2655 (is_unsigned && unlikely(val < 0)) ? 2656 "can't convert negative value to unsigned int" : 2657 "value too large to convert to unsigned int"); 2658 } 2659 return (unsigned int)-1; 2660 } 2661 return (unsigned int)val; 2662 } 2663 return (unsigned int)__Pyx_PyInt_AsUnsignedLong(x); 2664} 2665 2666static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject* x) { 2667 const char neg_one = (char)-1, const_zero = 0; 2668 const int is_unsigned = neg_one > const_zero; 2669 if (sizeof(char) < sizeof(long)) { 2670 long val = __Pyx_PyInt_AsLong(x); 2671 if (unlikely(val != (long)(char)val)) { 2672 if (!unlikely(val == -1 && PyErr_Occurred())) { 2673 PyErr_SetString(PyExc_OverflowError, 2674 (is_unsigned && unlikely(val < 0)) ? 2675 "can't convert negative value to char" : 2676 "value too large to convert to char"); 2677 } 2678 return (char)-1; 2679 } 2680 return (char)val; 2681 } 2682 return (char)__Pyx_PyInt_AsLong(x); 2683} 2684 2685static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject* x) { 2686 const short neg_one = (short)-1, const_zero = 0; 2687 const int is_unsigned = neg_one > const_zero; 2688 if (sizeof(short) < sizeof(long)) { 2689 long val = __Pyx_PyInt_AsLong(x); 2690 if (unlikely(val != (long)(short)val)) { 2691 if (!unlikely(val == -1 && PyErr_Occurred())) { 2692 PyErr_SetString(PyExc_OverflowError, 2693 (is_unsigned && unlikely(val < 0)) ? 2694 "can't convert negative value to short" : 2695 "value too large to convert to short"); 2696 } 2697 return (short)-1; 2698 } 2699 return (short)val; 2700 } 2701 return (short)__Pyx_PyInt_AsLong(x); 2702} 2703 2704static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject* x) { 2705 const int neg_one = (int)-1, const_zero = 0; 2706 const int is_unsigned = neg_one > const_zero; 2707 if (sizeof(int) < sizeof(long)) { 2708 long val = __Pyx_PyInt_AsLong(x); 2709 if (unlikely(val != (long)(int)val)) { 2710 if (!unlikely(val == -1 && PyErr_Occurred())) { 2711 PyErr_SetString(PyExc_OverflowError, 2712 (is_unsigned && unlikely(val < 0)) ? 2713 "can't convert negative value to int" : 2714 "value too large to convert to int"); 2715 } 2716 return (int)-1; 2717 } 2718 return (int)val; 2719 } 2720 return (int)__Pyx_PyInt_AsLong(x); 2721} 2722 2723static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject* x) { 2724 const signed char neg_one = (signed char)-1, const_zero = 0; 2725 const int is_unsigned = neg_one > const_zero; 2726 if (sizeof(signed char) < sizeof(long)) { 2727 long val = __Pyx_PyInt_AsLong(x); 2728 if (unlikely(val != (long)(signed char)val)) { 2729 if (!unlikely(val == -1 && PyErr_Occurred())) { 2730 PyErr_SetString(PyExc_OverflowError, 2731 (is_unsigned && unlikely(val < 0)) ? 2732 "can't convert negative value to signed char" : 2733 "value too large to convert to signed char"); 2734 } 2735 return (signed char)-1; 2736 } 2737 return (signed char)val; 2738 } 2739 return (signed char)__Pyx_PyInt_AsSignedLong(x); 2740} 2741 2742static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject* x) { 2743 const signed short neg_one = (signed short)-1, const_zero = 0; 2744 const int is_unsigned = neg_one > const_zero; 2745 if (sizeof(signed short) < sizeof(long)) { 2746 long val = __Pyx_PyInt_AsLong(x); 2747 if (unlikely(val != (long)(signed short)val)) { 2748 if (!unlikely(val == -1 && PyErr_Occurred())) { 2749 PyErr_SetString(PyExc_OverflowError, 2750 (is_unsigned && unlikely(val < 0)) ? 2751 "can't convert negative value to signed short" : 2752 "value too large to convert to signed short"); 2753 } 2754 return (signed short)-1; 2755 } 2756 return (signed short)val; 2757 } 2758 return (signed short)__Pyx_PyInt_AsSignedLong(x); 2759} 2760 2761static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject* x) { 2762 const signed int neg_one = (signed int)-1, const_zero = 0; 2763 const int is_unsigned = neg_one > const_zero; 2764 if (sizeof(signed int) < sizeof(long)) { 2765 long val = __Pyx_PyInt_AsLong(x); 2766 if (unlikely(val != (long)(signed int)val)) { 2767 if (!unlikely(val == -1 && PyErr_Occurred())) { 2768 PyErr_SetString(PyExc_OverflowError, 2769 (is_unsigned && unlikely(val < 0)) ? 2770 "can't convert negative value to signed int" : 2771 "value too large to convert to signed int"); 2772 } 2773 return (signed int)-1; 2774 } 2775 return (signed int)val; 2776 } 2777 return (signed int)__Pyx_PyInt_AsSignedLong(x); 2778} 2779 2780static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject* x) { 2781 const int neg_one = (int)-1, const_zero = 0; 2782 const int is_unsigned = neg_one > const_zero; 2783 if (sizeof(int) < sizeof(long)) { 2784 long val = __Pyx_PyInt_AsLong(x); 2785 if (unlikely(val != (long)(int)val)) { 2786 if (!unlikely(val == -1 && PyErr_Occurred())) { 2787 PyErr_SetString(PyExc_OverflowError, 2788 (is_unsigned && unlikely(val < 0)) ? 2789 "can't convert negative value to int" : 2790 "value too large to convert to int"); 2791 } 2792 return (int)-1; 2793 } 2794 return (int)val; 2795 } 2796 return (int)__Pyx_PyInt_AsLong(x); 2797} 2798 2799static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject* x) { 2800 const unsigned long neg_one = (unsigned long)-1, const_zero = 0; 2801 const int is_unsigned = neg_one > const_zero; 2802#if PY_VERSION_HEX < 0x03000000 2803 if (likely(PyInt_Check(x))) { 2804 long val = PyInt_AS_LONG(x); 2805 if (is_unsigned && unlikely(val < 0)) { 2806 PyErr_SetString(PyExc_OverflowError, 2807 "can't convert negative value to unsigned long"); 2808 return (unsigned long)-1; 2809 } 2810 return (unsigned long)val; 2811 } else 2812#endif 2813 if (likely(PyLong_Check(x))) { 2814 if (is_unsigned) { 2815 if (unlikely(Py_SIZE(x) < 0)) { 2816 PyErr_SetString(PyExc_OverflowError, 2817 "can't convert negative value to unsigned long"); 2818 return (unsigned long)-1; 2819 } 2820 return (unsigned long)PyLong_AsUnsignedLong(x); 2821 } else { 2822 return (unsigned long)PyLong_AsLong(x); 2823 } 2824 } else { 2825 unsigned long val; 2826 PyObject *tmp = __Pyx_PyNumber_Int(x); 2827 if (!tmp) return (unsigned long)-1; 2828 val = __Pyx_PyInt_AsUnsignedLong(tmp); 2829 Py_DECREF(tmp); 2830 return val; 2831 } 2832} 2833 2834static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject* x) { 2835 const unsigned PY_LONG_LONG neg_one = (unsigned PY_LONG_LONG)-1, const_zero = 0; 2836 const int is_unsigned = neg_one > const_zero; 2837#if PY_VERSION_HEX < 0x03000000 2838 if (likely(PyInt_Check(x))) { 2839 long val = PyInt_AS_LONG(x); 2840 if (is_unsigned && unlikely(val < 0)) { 2841 PyErr_SetString(PyExc_OverflowError, 2842 "can't convert negative value to unsigned PY_LONG_LONG"); 2843 return (unsigned PY_LONG_LONG)-1; 2844 } 2845 return (unsigned PY_LONG_LONG)val; 2846 } else 2847#endif 2848 if (likely(PyLong_Check(x))) { 2849 if (is_unsigned) { 2850 if (unlikely(Py_SIZE(x) < 0)) { 2851 PyErr_SetString(PyExc_OverflowError, 2852 "can't convert negative value to unsigned PY_LONG_LONG"); 2853 return (unsigned PY_LONG_LONG)-1; 2854 } 2855 return (unsigned PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2856 } else { 2857 return (unsigned PY_LONG_LONG)PyLong_AsLongLong(x); 2858 } 2859 } else { 2860 unsigned PY_LONG_LONG val; 2861 PyObject *tmp = __Pyx_PyNumber_Int(x); 2862 if (!tmp) return (unsigned PY_LONG_LONG)-1; 2863 val = __Pyx_PyInt_AsUnsignedLongLong(tmp); 2864 Py_DECREF(tmp); 2865 return val; 2866 } 2867} 2868 2869static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject* x) { 2870 const long neg_one = (long)-1, const_zero = 0; 2871 const int is_unsigned = neg_one > const_zero; 2872#if PY_VERSION_HEX < 0x03000000 2873 if (likely(PyInt_Check(x))) { 2874 long val = PyInt_AS_LONG(x); 2875 if (is_unsigned && unlikely(val < 0)) { 2876 PyErr_SetString(PyExc_OverflowError, 2877 "can't convert negative value to long"); 2878 return (long)-1; 2879 } 2880 return (long)val; 2881 } else 2882#endif 2883 if (likely(PyLong_Check(x))) { 2884 if (is_unsigned) { 2885 if (unlikely(Py_SIZE(x) < 0)) { 2886 PyErr_SetString(PyExc_OverflowError, 2887 "can't convert negative value to long"); 2888 return (long)-1; 2889 } 2890 return (long)PyLong_AsUnsignedLong(x); 2891 } else { 2892 return (long)PyLong_AsLong(x); 2893 } 2894 } else { 2895 long val; 2896 PyObject *tmp = __Pyx_PyNumber_Int(x); 2897 if (!tmp) return (long)-1; 2898 val = __Pyx_PyInt_AsLong(tmp); 2899 Py_DECREF(tmp); 2900 return val; 2901 } 2902} 2903 2904static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject* x) { 2905 const PY_LONG_LONG neg_one = (PY_LONG_LONG)-1, const_zero = 0; 2906 const int is_unsigned = neg_one > const_zero; 2907#if PY_VERSION_HEX < 0x03000000 2908 if (likely(PyInt_Check(x))) { 2909 long val = PyInt_AS_LONG(x); 2910 if (is_unsigned && unlikely(val < 0)) { 2911 PyErr_SetString(PyExc_OverflowError, 2912 "can't convert negative value to PY_LONG_LONG"); 2913 return (PY_LONG_LONG)-1; 2914 } 2915 return (PY_LONG_LONG)val; 2916 } else 2917#endif 2918 if (likely(PyLong_Check(x))) { 2919 if (is_unsigned) { 2920 if (unlikely(Py_SIZE(x) < 0)) { 2921 PyErr_SetString(PyExc_OverflowError, 2922 "can't convert negative value to PY_LONG_LONG"); 2923 return (PY_LONG_LONG)-1; 2924 } 2925 return (PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2926 } else { 2927 return (PY_LONG_LONG)PyLong_AsLongLong(x); 2928 } 2929 } else { 2930 PY_LONG_LONG val; 2931 PyObject *tmp = __Pyx_PyNumber_Int(x); 2932 if (!tmp) return (PY_LONG_LONG)-1; 2933 val = __Pyx_PyInt_AsLongLong(tmp); 2934 Py_DECREF(tmp); 2935 return val; 2936 } 2937} 2938 2939static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject* x) { 2940 const signed long neg_one = (signed long)-1, const_zero = 0; 2941 const int is_unsigned = neg_one > const_zero; 2942#if PY_VERSION_HEX < 0x03000000 2943 if (likely(PyInt_Check(x))) { 2944 long val = PyInt_AS_LONG(x); 2945 if (is_unsigned && unlikely(val < 0)) { 2946 PyErr_SetString(PyExc_OverflowError, 2947 "can't convert negative value to signed long"); 2948 return (signed long)-1; 2949 } 2950 return (signed long)val; 2951 } else 2952#endif 2953 if (likely(PyLong_Check(x))) { 2954 if (is_unsigned) { 2955 if (unlikely(Py_SIZE(x) < 0)) { 2956 PyErr_SetString(PyExc_OverflowError, 2957 "can't convert negative value to signed long"); 2958 return (signed long)-1; 2959 } 2960 return (signed long)PyLong_AsUnsignedLong(x); 2961 } else { 2962 return (signed long)PyLong_AsLong(x); 2963 } 2964 } else { 2965 signed long val; 2966 PyObject *tmp = __Pyx_PyNumber_Int(x); 2967 if (!tmp) return (signed long)-1; 2968 val = __Pyx_PyInt_AsSignedLong(tmp); 2969 Py_DECREF(tmp); 2970 return val; 2971 } 2972} 2973 2974static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject* x) { 2975 const signed PY_LONG_LONG neg_one = (signed PY_LONG_LONG)-1, const_zero = 0; 2976 const int is_unsigned = neg_one > const_zero; 2977#if PY_VERSION_HEX < 0x03000000 2978 if (likely(PyInt_Check(x))) { 2979 long val = PyInt_AS_LONG(x); 2980 if (is_unsigned && unlikely(val < 0)) { 2981 PyErr_SetString(PyExc_OverflowError, 2982 "can't convert negative value to signed PY_LONG_LONG"); 2983 return (signed PY_LONG_LONG)-1; 2984 } 2985 return (signed PY_LONG_LONG)val; 2986 } else 2987#endif 2988 if (likely(PyLong_Check(x))) { 2989 if (is_unsigned) { 2990 if (unlikely(Py_SIZE(x) < 0)) { 2991 PyErr_SetString(PyExc_OverflowError, 2992 "can't convert negative value to signed PY_LONG_LONG"); 2993 return (signed PY_LONG_LONG)-1; 2994 } 2995 return (signed PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2996 } else { 2997 return (signed PY_LONG_LONG)PyLong_AsLongLong(x); 2998 } 2999 } else { 3000 signed PY_LONG_LONG val; 3001 PyObject *tmp = __Pyx_PyNumber_Int(x); 3002 if (!tmp) return (signed PY_LONG_LONG)-1; 3003 val = __Pyx_PyInt_AsSignedLongLong(tmp); 3004 Py_DECREF(tmp); 3005 return val; 3006 } 3007} 3008 3009static int __Pyx_check_binary_version(void) { 3010 char ctversion[4], rtversion[4]; 3011 PyOS_snprintf(ctversion, 4, "%d.%d", PY_MAJOR_VERSION, PY_MINOR_VERSION); 3012 PyOS_snprintf(rtversion, 4, "%s", Py_GetVersion()); 3013 if (ctversion[0] != rtversion[0] || ctversion[2] != rtversion[2]) { 3014 char message[200]; 3015 PyOS_snprintf(message, sizeof(message), 3016 "compiletime version %s of module '%.100s' " 3017 "does not match runtime version %s", 3018 ctversion, __Pyx_MODULE_NAME, rtversion); 3019 #if PY_VERSION_HEX < 0x02050000 3020 return PyErr_Warn(NULL, message); 3021 #else 3022 return PyErr_WarnEx(NULL, message, 1); 3023 #endif 3024 } 3025 return 0; 3026} 3027 3028#ifndef __PYX_HAVE_RT_ImportModule 3029#define __PYX_HAVE_RT_ImportModule 3030static PyObject *__Pyx_ImportModule(const char *name) { 3031 PyObject *py_name = 0; 3032 PyObject *py_module = 0; 3033 py_name = __Pyx_PyIdentifier_FromString(name); 3034 if (!py_name) 3035 goto bad; 3036 py_module = PyImport_Import(py_name); 3037 Py_DECREF(py_name); 3038 return py_module; 3039bad: 3040 Py_XDECREF(py_name); 3041 return 0; 3042} 3043#endif 3044 3045#ifndef __PYX_HAVE_RT_ImportType 3046#define __PYX_HAVE_RT_ImportType 3047static PyTypeObject *__Pyx_ImportType(const char *module_name, const char *class_name, 3048 size_t size, int strict) 3049{ 3050 PyObject *py_module = 0; 3051 PyObject *result = 0; 3052 PyObject *py_name = 0; 3053 char warning[200]; 3054 py_module = __Pyx_ImportModule(module_name); 3055 if (!py_module) 3056 goto bad; 3057 py_name = __Pyx_PyIdentifier_FromString(class_name); 3058 if (!py_name) 3059 goto bad; 3060 result = PyObject_GetAttr(py_module, py_name); 3061 Py_DECREF(py_name); 3062 py_name = 0; 3063 Py_DECREF(py_module); 3064 py_module = 0; 3065 if (!result) 3066 goto bad; 3067 if (!PyType_Check(result)) { 3068 PyErr_Format(PyExc_TypeError, 3069 "%s.%s is not a type object", 3070 module_name, class_name); 3071 goto bad; 3072 } 3073 if (!strict && (size_t)((PyTypeObject *)result)->tp_basicsize > size) { 3074 PyOS_snprintf(warning, sizeof(warning), 3075 "%s.%s size changed, may indicate binary incompatibility", 3076 module_name, class_name); 3077 #if PY_VERSION_HEX < 0x02050000 3078 if (PyErr_Warn(NULL, warning) < 0) goto bad; 3079 #else 3080 if (PyErr_WarnEx(NULL, warning, 0) < 0) goto bad; 3081 #endif 3082 } 3083 else if ((size_t)((PyTypeObject *)result)->tp_basicsize != size) { 3084 PyErr_Format(PyExc_ValueError, 3085 "%s.%s has the wrong size, try recompiling", 3086 module_name, class_name); 3087 goto bad; 3088 } 3089 return (PyTypeObject *)result; 3090bad: 3091 Py_XDECREF(py_module); 3092 Py_XDECREF(result); 3093 return NULL; 3094} 3095#endif 3096 3097static void* __Pyx_GetVtable(PyObject *dict) { 3098 void* ptr; 3099 PyObject *ob = PyMapping_GetItemString(dict, (char *)"__pyx_vtable__"); 3100 if (!ob) 3101 goto bad; 3102#if PY_VERSION_HEX >= 0x02070000 && !(PY_MAJOR_VERSION==3&&PY_MINOR_VERSION==0) 3103 ptr = PyCapsule_GetPointer(ob, 0); 3104#else 3105 ptr = PyCObject_AsVoidPtr(ob); 3106#endif 3107 if (!ptr && !PyErr_Occurred()) 3108 PyErr_SetString(PyExc_RuntimeError, "invalid vtable found for imported type"); 3109 Py_DECREF(ob); 3110 return ptr; 3111bad: 3112 Py_XDECREF(ob); 3113 return NULL; 3114} 3115 3116static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line) { 3117 int start = 0, mid = 0, end = count - 1; 3118 if (end >= 0 && code_line > entries[end].code_line) { 3119 return count; 3120 } 3121 while (start < end) { 3122 mid = (start + end) / 2; 3123 if (code_line < entries[mid].code_line) { 3124 end = mid; 3125 } else if (code_line > entries[mid].code_line) { 3126 start = mid + 1; 3127 } else { 3128 return mid; 3129 } 3130 } 3131 if (code_line <= entries[mid].code_line) { 3132 return mid; 3133 } else { 3134 return mid + 1; 3135 } 3136} 3137static PyCodeObject *__pyx_find_code_object(int code_line) { 3138 PyCodeObject* code_object; 3139 int pos; 3140 if (unlikely(!code_line) || unlikely(!__pyx_code_cache.entries)) { 3141 return NULL; 3142 } 3143 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3144 if (unlikely(pos >= __pyx_code_cache.count) || unlikely(__pyx_code_cache.entries[pos].code_line != code_line)) { 3145 return NULL; 3146 } 3147 code_object = __pyx_code_cache.entries[pos].code_object; 3148 Py_INCREF(code_object); 3149 return code_object; 3150} 3151static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object) { 3152 int pos, i; 3153 __Pyx_CodeObjectCacheEntry* entries = __pyx_code_cache.entries; 3154 if (unlikely(!code_line)) { 3155 return; 3156 } 3157 if (unlikely(!entries)) { 3158 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Malloc(64*sizeof(__Pyx_CodeObjectCacheEntry)); 3159 if (likely(entries)) { 3160 __pyx_code_cache.entries = entries; 3161 __pyx_code_cache.max_count = 64; 3162 __pyx_code_cache.count = 1; 3163 entries[0].code_line = code_line; 3164 entries[0].code_object = code_object; 3165 Py_INCREF(code_object); 3166 } 3167 return; 3168 } 3169 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3170 if ((pos < __pyx_code_cache.count) && unlikely(__pyx_code_cache.entries[pos].code_line == code_line)) { 3171 PyCodeObject* tmp = entries[pos].code_object; 3172 entries[pos].code_object = code_object; 3173 Py_DECREF(tmp); 3174 return; 3175 } 3176 if (__pyx_code_cache.count == __pyx_code_cache.max_count) { 3177 int new_max = __pyx_code_cache.max_count + 64; 3178 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Realloc( 3179 __pyx_code_cache.entries, new_max*sizeof(__Pyx_CodeObjectCacheEntry)); 3180 if (unlikely(!entries)) { 3181 return; 3182 } 3183 __pyx_code_cache.entries = entries; 3184 __pyx_code_cache.max_count = new_max; 3185 } 3186 for (i=__pyx_code_cache.count; i>pos; i--) { 3187 entries[i] = entries[i-1]; 3188 } 3189 entries[pos].code_line = code_line; 3190 entries[pos].code_object = code_object; 3191 __pyx_code_cache.count++; 3192 Py_INCREF(code_object); 3193} 3194 3195#include "compile.h" 3196#include "frameobject.h" 3197#include "traceback.h" 3198static PyCodeObject* __Pyx_CreateCodeObjectForTraceback( 3199 const char *funcname, int c_line, 3200 int py_line, const char *filename) { 3201 PyCodeObject *py_code = 0; 3202 PyObject *py_srcfile = 0; 3203 PyObject *py_funcname = 0; 3204 #if PY_MAJOR_VERSION < 3 3205 py_srcfile = PyString_FromString(filename); 3206 #else 3207 py_srcfile = PyUnicode_FromString(filename); 3208 #endif 3209 if (!py_srcfile) goto bad; 3210 if (c_line) { 3211 #if PY_MAJOR_VERSION < 3 3212 py_funcname = PyString_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3213 #else 3214 py_funcname = PyUnicode_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3215 #endif 3216 } 3217 else { 3218 #if PY_MAJOR_VERSION < 3 3219 py_funcname = PyString_FromString(funcname); 3220 #else 3221 py_funcname = PyUnicode_FromString(funcname); 3222 #endif 3223 } 3224 if (!py_funcname) goto bad; 3225 py_code = __Pyx_PyCode_New( 3226 0, /*int argcount,*/ 3227 0, /*int kwonlyargcount,*/ 3228 0, /*int nlocals,*/ 3229 0, /*int stacksize,*/ 3230 0, /*int flags,*/ 3231 __pyx_empty_bytes, /*PyObject *code,*/ 3232 __pyx_empty_tuple, /*PyObject *consts,*/ 3233 __pyx_empty_tuple, /*PyObject *names,*/ 3234 __pyx_empty_tuple, /*PyObject *varnames,*/ 3235 __pyx_empty_tuple, /*PyObject *freevars,*/ 3236 __pyx_empty_tuple, /*PyObject *cellvars,*/ 3237 py_srcfile, /*PyObject *filename,*/ 3238 py_funcname, /*PyObject *name,*/ 3239 py_line, /*int firstlineno,*/ 3240 __pyx_empty_bytes /*PyObject *lnotab*/ 3241 ); 3242 Py_DECREF(py_srcfile); 3243 Py_DECREF(py_funcname); 3244 return py_code; 3245bad: 3246 Py_XDECREF(py_srcfile); 3247 Py_XDECREF(py_funcname); 3248 return NULL; 3249} 3250static void __Pyx_AddTraceback(const char *funcname, int c_line, 3251 int py_line, const char *filename) { 3252 PyCodeObject *py_code = 0; 3253 PyObject *py_globals = 0; 3254 PyFrameObject *py_frame = 0; 3255 py_code = __pyx_find_code_object(c_line ? c_line : py_line); 3256 if (!py_code) { 3257 py_code = __Pyx_CreateCodeObjectForTraceback( 3258 funcname, c_line, py_line, filename); 3259 if (!py_code) goto bad; 3260 __pyx_insert_code_object(c_line ? c_line : py_line, py_code); 3261 } 3262 py_globals = PyModule_GetDict(__pyx_m); 3263 if (!py_globals) goto bad; 3264 py_frame = PyFrame_New( 3265 PyThreadState_GET(), /*PyThreadState *tstate,*/ 3266 py_code, /*PyCodeObject *code,*/ 3267 py_globals, /*PyObject *globals,*/ 3268 0 /*PyObject *locals*/ 3269 ); 3270 if (!py_frame) goto bad; 3271 py_frame->f_lineno = py_line; 3272 PyTraceBack_Here(py_frame); 3273bad: 3274 Py_XDECREF(py_code); 3275 Py_XDECREF(py_frame); 3276} 3277 3278static int __Pyx_InitStrings(__Pyx_StringTabEntry *t) { 3279 while (t->p) { 3280 #if PY_MAJOR_VERSION < 3 3281 if (t->is_unicode) { 3282 *t->p = PyUnicode_DecodeUTF8(t->s, t->n - 1, NULL); 3283 } else if (t->intern) { 3284 *t->p = PyString_InternFromString(t->s); 3285 } else { 3286 *t->p = PyString_FromStringAndSize(t->s, t->n - 1); 3287 } 3288 #else /* Python 3+ has unicode identifiers */ 3289 if (t->is_unicode | t->is_str) { 3290 if (t->intern) { 3291 *t->p = PyUnicode_InternFromString(t->s); 3292 } else if (t->encoding) { 3293 *t->p = PyUnicode_Decode(t->s, t->n - 1, t->encoding, NULL); 3294 } else { 3295 *t->p = PyUnicode_FromStringAndSize(t->s, t->n - 1); 3296 } 3297 } else { 3298 *t->p = PyBytes_FromStringAndSize(t->s, t->n - 1); 3299 } 3300 #endif 3301 if (!*t->p) 3302 return -1; 3303 ++t; 3304 } 3305 return 0; 3306} 3307 3308 3309/* Type Conversion Functions */ 3310 3311static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject* x) { 3312 int is_true = x == Py_True; 3313 if (is_true | (x == Py_False) | (x == Py_None)) return is_true; 3314 else return PyObject_IsTrue(x); 3315} 3316 3317static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x) { 3318 PyNumberMethods *m; 3319 const char *name = NULL; 3320 PyObject *res = NULL; 3321#if PY_VERSION_HEX < 0x03000000 3322 if (PyInt_Check(x) || PyLong_Check(x)) 3323#else 3324 if (PyLong_Check(x)) 3325#endif 3326 return Py_INCREF(x), x; 3327 m = Py_TYPE(x)->tp_as_number; 3328#if PY_VERSION_HEX < 0x03000000 3329 if (m && m->nb_int) { 3330 name = "int"; 3331 res = PyNumber_Int(x); 3332 } 3333 else if (m && m->nb_long) { 3334 name = "long"; 3335 res = PyNumber_Long(x); 3336 } 3337#else 3338 if (m && m->nb_int) { 3339 name = "int"; 3340 res = PyNumber_Long(x); 3341 } 3342#endif 3343 if (res) { 3344#if PY_VERSION_HEX < 0x03000000 3345 if (!PyInt_Check(res) && !PyLong_Check(res)) { 3346#else 3347 if (!PyLong_Check(res)) { 3348#endif 3349 PyErr_Format(PyExc_TypeError, 3350 "__%s__ returned non-%s (type %.200s)", 3351 name, name, Py_TYPE(res)->tp_name); 3352 Py_DECREF(res); 3353 return NULL; 3354 } 3355 } 3356 else if (!PyErr_Occurred()) { 3357 PyErr_SetString(PyExc_TypeError, 3358 "an integer is required"); 3359 } 3360 return res; 3361} 3362 3363static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject* b) { 3364 Py_ssize_t ival; 3365 PyObject* x = PyNumber_Index(b); 3366 if (!x) return -1; 3367 ival = PyInt_AsSsize_t(x); 3368 Py_DECREF(x); 3369 return ival; 3370} 3371 3372static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) { 3373#if PY_VERSION_HEX < 0x02050000 3374 if (ival <= LONG_MAX) 3375 return PyInt_FromLong((long)ival); 3376 else { 3377 unsigned char *bytes = (unsigned char *) &ival; 3378 int one = 1; int little = (int)*(unsigned char*)&one; 3379 return _PyLong_FromByteArray(bytes, sizeof(size_t), little, 0); 3380 } 3381#else 3382 return PyInt_FromSize_t(ival); 3383#endif 3384} 3385 3386static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject* x) { 3387 unsigned PY_LONG_LONG val = __Pyx_PyInt_AsUnsignedLongLong(x); 3388 if (unlikely(val == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred())) { 3389 return (size_t)-1; 3390 } else if (unlikely(val != (unsigned PY_LONG_LONG)(size_t)val)) { 3391 PyErr_SetString(PyExc_OverflowError, 3392 "value too large to convert to size_t"); 3393 return (size_t)-1; 3394 } 3395 return (size_t)val; 3396} 3397 3398 3399#endif /* Py_PYTHON_H */ 3400