Changeset 391 for python/trunk/Modules/_collectionsmodule.c
- Timestamp:
- Mar 19, 2014, 11:31:01 PM (11 years ago)
- Location:
- python/trunk
- Files:
-
- 2 edited
-
. (modified) (1 prop)
-
Modules/_collectionsmodule.c (modified) (51 diffs)
Legend:
- Unmodified
- Added
- Removed
-
python/trunk
-
Property svn:mergeinfo
set to
/python/vendor/Python-2.7.6 merged eligible /python/vendor/current merged eligible
-
Property svn:mergeinfo
set to
-
python/trunk/Modules/_collectionsmodule.c
r2 r391 9 9 10 10 /* The block length may be set to any number over 1. Larger numbers 11 * reduce the number of calls to the memory allocator but take more 12 * memory. Ideally, BLOCKLEN should be set with an eye to the 13 * length of a cache line. 11 * reduce the number of calls to the memory allocator, give faster 12 * indexing and rotation, and reduce the link::data overhead ratio. 13 * 14 * Ideally, the block length will be set to two less than some 15 * multiple of the cache-line length (so that the full block 16 * including the leftlink and rightlink will fit neatly into 17 * cache lines). 14 18 */ 15 19 … … 47 51 48 52 typedef struct BLOCK { 49 struct BLOCK *leftlink;50 51 PyObject *data[BLOCKLEN];53 PyObject *data[BLOCKLEN]; 54 struct BLOCK *rightlink; 55 struct BLOCK *leftlink; 52 56 } block; 53 57 … … 58 62 static block * 59 63 newblock(block *leftlink, block *rightlink, Py_ssize_t len) { 60 block *b; 61 /* To prevent len from overflowing PY_SSIZE_T_MAX on 64-bit machines, we 62 * refuse to allocate new blocks if the current len is dangerously 63 * close. There is some extra margin to prevent spurious arithmetic 64 * overflows at various places. The following check ensures that 65 * the blocks allocated to the deque, in the worst case, can only 66 * have PY_SSIZE_T_MAX-2 entries in total. 67 */ 68 if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) { 69 PyErr_SetString(PyExc_OverflowError, 70 "cannot add more blocks to the deque"); 71 return NULL; 72 } 73 if (numfreeblocks) { 74 numfreeblocks -= 1; 75 b = freeblocks[numfreeblocks]; 76 } else { 77 b = PyMem_Malloc(sizeof(block)); 78 if (b == NULL) { 79 PyErr_NoMemory(); 80 return NULL; 81 } 82 } 83 b->leftlink = leftlink; 84 b->rightlink = rightlink; 85 return b; 64 block *b; 65 /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we 66 * refuse to allocate new blocks if the current len is nearing overflow. */ 67 if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) { 68 PyErr_SetString(PyExc_OverflowError, 69 "cannot add more blocks to the deque"); 70 return NULL; 71 } 72 if (numfreeblocks) { 73 numfreeblocks -= 1; 74 b = freeblocks[numfreeblocks]; 75 } else { 76 b = PyMem_Malloc(sizeof(block)); 77 if (b == NULL) { 78 PyErr_NoMemory(); 79 return NULL; 80 } 81 } 82 b->leftlink = leftlink; 83 b->rightlink = rightlink; 84 return b; 86 85 } 87 86 … … 89 88 freeblock(block *b) 90 89 { 91 92 93 94 95 96 90 if (numfreeblocks < MAXFREEBLOCKS) { 91 freeblocks[numfreeblocks] = b; 92 numfreeblocks++; 93 } else { 94 PyMem_Free(b); 95 } 97 96 } 98 97 99 98 typedef struct { 100 101 102 103 Py_ssize_t leftindex;/* in range(BLOCKLEN) */104 Py_ssize_t rightindex;/* in range(BLOCKLEN) */105 106 Py_ssize_t maxlen; 107 long state; /* incremented whenever the indices move */ 108 99 PyObject_HEAD 100 block *leftblock; 101 block *rightblock; 102 Py_ssize_t leftindex; /* in range(BLOCKLEN) */ 103 Py_ssize_t rightindex; /* in range(BLOCKLEN) */ 104 Py_ssize_t len; 105 long state; /* incremented whenever the indices move */ 106 Py_ssize_t maxlen; 107 PyObject *weakreflist; /* List of weak references */ 109 108 } dequeobject; 110 109 111 110 /* The deque's size limit is d.maxlen. The limit can be zero or positive. 112 111 * If there is no limit, then d.maxlen == -1. 113 * 112 * 114 113 * After an item is added to a deque, we check to see if the size has grown past 115 114 * the limit. If it has, we get the size back down to the limit by popping an … … 118 117 */ 119 118 120 #define TRIM(d, popfunction) 121 if (d->maxlen != -1 && d->len > d->maxlen) { 122 123 124 119 #define TRIM(d, popfunction) \ 120 if (d->maxlen != -1 && d->len > d->maxlen) { \ 121 PyObject *rv = popfunction(d, NULL); \ 122 assert(rv != NULL && d->len <= d->maxlen); \ 123 Py_DECREF(rv); \ 125 124 } 126 125 … … 130 129 deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 131 130 { 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 131 dequeobject *deque; 132 block *b; 133 134 /* create dequeobject structure */ 135 deque = (dequeobject *)type->tp_alloc(type, 0); 136 if (deque == NULL) 137 return NULL; 138 139 b = newblock(NULL, NULL, 0); 140 if (b == NULL) { 141 Py_DECREF(deque); 142 return NULL; 143 } 144 145 assert(BLOCKLEN >= 2); 146 deque->leftblock = b; 147 deque->rightblock = b; 148 deque->leftindex = CENTER + 1; 149 deque->rightindex = CENTER; 150 deque->len = 0; 151 deque->state = 0; 152 deque->weakreflist = NULL; 153 deque->maxlen = -1; 154 155 return (PyObject *)deque; 157 156 } 158 157 … … 160 159 deque_pop(dequeobject *deque, PyObject *unused) 161 160 { 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 161 PyObject *item; 162 block *prevblock; 163 164 if (deque->len == 0) { 165 PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 166 return NULL; 167 } 168 item = deque->rightblock->data[deque->rightindex]; 169 deque->rightindex--; 170 deque->len--; 171 deque->state++; 172 173 if (deque->rightindex == -1) { 174 if (deque->len == 0) { 175 assert(deque->leftblock == deque->rightblock); 176 assert(deque->leftindex == deque->rightindex+1); 177 /* re-center instead of freeing a block */ 178 deque->leftindex = CENTER + 1; 179 deque->rightindex = CENTER; 180 } else { 181 prevblock = deque->rightblock->leftlink; 182 assert(deque->leftblock != deque->rightblock); 183 freeblock(deque->rightblock); 184 prevblock->rightlink = NULL; 185 deque->rightblock = prevblock; 186 deque->rightindex = BLOCKLEN - 1; 187 } 188 } 189 return item; 191 190 } 192 191 … … 196 195 deque_popleft(dequeobject *deque, PyObject *unused) 197 196 { 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 197 PyObject *item; 198 block *prevblock; 199 200 if (deque->len == 0) { 201 PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 202 return NULL; 203 } 204 assert(deque->leftblock != NULL); 205 item = deque->leftblock->data[deque->leftindex]; 206 deque->leftindex++; 207 deque->len--; 208 deque->state++; 209 210 if (deque->leftindex == BLOCKLEN) { 211 if (deque->len == 0) { 212 assert(deque->leftblock == deque->rightblock); 213 assert(deque->leftindex == deque->rightindex+1); 214 /* re-center instead of freeing a block */ 215 deque->leftindex = CENTER + 1; 216 deque->rightindex = CENTER; 217 } else { 218 assert(deque->leftblock != deque->rightblock); 219 prevblock = deque->leftblock->rightlink; 220 freeblock(deque->leftblock); 221 assert(prevblock != NULL); 222 prevblock->leftlink = NULL; 223 deque->leftblock = prevblock; 224 deque->leftindex = 0; 225 } 226 } 227 return item; 229 228 } 230 229 … … 234 233 deque_append(dequeobject *deque, PyObject *item) 235 234 { 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 235 deque->state++; 236 if (deque->rightindex == BLOCKLEN-1) { 237 block *b = newblock(deque->rightblock, NULL, deque->len); 238 if (b == NULL) 239 return NULL; 240 assert(deque->rightblock->rightlink == NULL); 241 deque->rightblock->rightlink = b; 242 deque->rightblock = b; 243 deque->rightindex = -1; 244 } 245 Py_INCREF(item); 246 deque->len++; 247 deque->rightindex++; 248 deque->rightblock->data[deque->rightindex] = item; 249 TRIM(deque, deque_popleft); 250 Py_RETURN_NONE; 252 251 } 253 252 … … 257 256 deque_appendleft(dequeobject *deque, PyObject *item) 258 257 { 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 258 deque->state++; 259 if (deque->leftindex == 0) { 260 block *b = newblock(NULL, deque->leftblock, deque->len); 261 if (b == NULL) 262 return NULL; 263 assert(deque->leftblock->leftlink == NULL); 264 deque->leftblock->leftlink = b; 265 deque->leftblock = b; 266 deque->leftindex = BLOCKLEN; 267 } 268 Py_INCREF(item); 269 deque->len++; 270 deque->leftindex--; 271 deque->leftblock->data[deque->leftindex] = item; 272 TRIM(deque, deque_pop); 273 Py_RETURN_NONE; 275 274 } 276 275 277 276 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque."); 278 277 278 279 /* Run an iterator to exhaustion. Shortcut for 280 the extend/extendleft methods when maxlen == 0. */ 281 static PyObject* 282 consume_iterator(PyObject *it) 283 { 284 PyObject *item; 285 286 while ((item = PyIter_Next(it)) != NULL) { 287 Py_DECREF(item); 288 } 289 Py_DECREF(it); 290 if (PyErr_Occurred()) 291 return NULL; 292 Py_RETURN_NONE; 293 } 294 279 295 static PyObject * 280 296 deque_extend(dequeobject *deque, PyObject *iterable) 281 297 { 282 PyObject *it, *item; 283 284 /* Handle case where id(deque) == id(iterable) */ 285 if ((PyObject *)deque == iterable) { 286 PyObject *result; 287 PyObject *s = PySequence_List(iterable); 288 if (s == NULL) 289 return NULL; 290 result = deque_extend(deque, s); 291 Py_DECREF(s); 292 return result; 293 } 294 295 it = PyObject_GetIter(iterable); 296 if (it == NULL) 297 return NULL; 298 299 while ((item = PyIter_Next(it)) != NULL) { 300 deque->state++; 301 if (deque->rightindex == BLOCKLEN-1) { 302 block *b = newblock(deque->rightblock, NULL, 303 deque->len); 304 if (b == NULL) { 305 Py_DECREF(item); 306 Py_DECREF(it); 307 return NULL; 308 } 309 assert(deque->rightblock->rightlink == NULL); 310 deque->rightblock->rightlink = b; 311 deque->rightblock = b; 312 deque->rightindex = -1; 313 } 314 deque->len++; 315 deque->rightindex++; 316 deque->rightblock->data[deque->rightindex] = item; 317 TRIM(deque, deque_popleft); 318 } 319 Py_DECREF(it); 320 if (PyErr_Occurred()) 321 return NULL; 322 Py_RETURN_NONE; 298 PyObject *it, *item; 299 300 /* Handle case where id(deque) == id(iterable) */ 301 if ((PyObject *)deque == iterable) { 302 PyObject *result; 303 PyObject *s = PySequence_List(iterable); 304 if (s == NULL) 305 return NULL; 306 result = deque_extend(deque, s); 307 Py_DECREF(s); 308 return result; 309 } 310 311 it = PyObject_GetIter(iterable); 312 if (it == NULL) 313 return NULL; 314 315 if (deque->maxlen == 0) 316 return consume_iterator(it); 317 318 while ((item = PyIter_Next(it)) != NULL) { 319 deque->state++; 320 if (deque->rightindex == BLOCKLEN-1) { 321 block *b = newblock(deque->rightblock, NULL, 322 deque->len); 323 if (b == NULL) { 324 Py_DECREF(item); 325 Py_DECREF(it); 326 return NULL; 327 } 328 assert(deque->rightblock->rightlink == NULL); 329 deque->rightblock->rightlink = b; 330 deque->rightblock = b; 331 deque->rightindex = -1; 332 } 333 deque->len++; 334 deque->rightindex++; 335 deque->rightblock->data[deque->rightindex] = item; 336 TRIM(deque, deque_popleft); 337 } 338 Py_DECREF(it); 339 if (PyErr_Occurred()) 340 return NULL; 341 Py_RETURN_NONE; 323 342 } 324 343 … … 329 348 deque_extendleft(dequeobject *deque, PyObject *iterable) 330 349 { 331 PyObject *it, *item; 332 333 /* Handle case where id(deque) == id(iterable) */ 334 if ((PyObject *)deque == iterable) { 335 PyObject *result; 336 PyObject *s = PySequence_List(iterable); 337 if (s == NULL) 338 return NULL; 339 result = deque_extendleft(deque, s); 340 Py_DECREF(s); 341 return result; 342 } 343 344 it = PyObject_GetIter(iterable); 345 if (it == NULL) 346 return NULL; 347 348 while ((item = PyIter_Next(it)) != NULL) { 349 deque->state++; 350 if (deque->leftindex == 0) { 351 block *b = newblock(NULL, deque->leftblock, 352 deque->len); 353 if (b == NULL) { 354 Py_DECREF(item); 355 Py_DECREF(it); 356 return NULL; 357 } 358 assert(deque->leftblock->leftlink == NULL); 359 deque->leftblock->leftlink = b; 360 deque->leftblock = b; 361 deque->leftindex = BLOCKLEN; 362 } 363 deque->len++; 364 deque->leftindex--; 365 deque->leftblock->data[deque->leftindex] = item; 366 TRIM(deque, deque_pop); 367 } 368 Py_DECREF(it); 369 if (PyErr_Occurred()) 370 return NULL; 371 Py_RETURN_NONE; 350 PyObject *it, *item; 351 352 /* Handle case where id(deque) == id(iterable) */ 353 if ((PyObject *)deque == iterable) { 354 PyObject *result; 355 PyObject *s = PySequence_List(iterable); 356 if (s == NULL) 357 return NULL; 358 result = deque_extendleft(deque, s); 359 Py_DECREF(s); 360 return result; 361 } 362 363 it = PyObject_GetIter(iterable); 364 if (it == NULL) 365 return NULL; 366 367 if (deque->maxlen == 0) 368 return consume_iterator(it); 369 370 while ((item = PyIter_Next(it)) != NULL) { 371 deque->state++; 372 if (deque->leftindex == 0) { 373 block *b = newblock(NULL, deque->leftblock, 374 deque->len); 375 if (b == NULL) { 376 Py_DECREF(item); 377 Py_DECREF(it); 378 return NULL; 379 } 380 assert(deque->leftblock->leftlink == NULL); 381 deque->leftblock->leftlink = b; 382 deque->leftblock = b; 383 deque->leftindex = BLOCKLEN; 384 } 385 deque->len++; 386 deque->leftindex--; 387 deque->leftblock->data[deque->leftindex] = item; 388 TRIM(deque, deque_pop); 389 } 390 Py_DECREF(it); 391 if (PyErr_Occurred()) 392 return NULL; 393 Py_RETURN_NONE; 372 394 } 373 395 … … 378 400 deque_inplace_concat(dequeobject *deque, PyObject *other) 379 401 { 380 381 382 383 384 385 386 387 402 PyObject *result; 403 404 result = deque_extend(deque, other); 405 if (result == NULL) 406 return result; 407 Py_DECREF(result); 408 Py_INCREF(deque); 409 return (PyObject *)deque; 388 410 } 389 411 … … 391 413 _deque_rotate(dequeobject *deque, Py_ssize_t n) 392 414 { 393 Py_ssize_t i, len=deque->len, halflen=(len+1)>>1; 394 PyObject *item, *rv; 395 396 if (len == 0) 397 return 0; 398 if (n > halflen || n < -halflen) { 399 n %= len; 400 if (n > halflen) 401 n -= len; 402 else if (n < -halflen) 403 n += len; 404 } 405 406 for (i=0 ; i<n ; i++) { 407 item = deque_pop(deque, NULL); 408 assert (item != NULL); 409 rv = deque_appendleft(deque, item); 410 Py_DECREF(item); 411 if (rv == NULL) 412 return -1; 413 Py_DECREF(rv); 414 } 415 for (i=0 ; i>n ; i--) { 416 item = deque_popleft(deque, NULL); 417 assert (item != NULL); 418 rv = deque_append(deque, item); 419 Py_DECREF(item); 420 if (rv == NULL) 421 return -1; 422 Py_DECREF(rv); 423 } 424 return 0; 415 Py_ssize_t m, len=deque->len, halflen=len>>1; 416 417 if (len <= 1) 418 return 0; 419 if (n > halflen || n < -halflen) { 420 n %= len; 421 if (n > halflen) 422 n -= len; 423 else if (n < -halflen) 424 n += len; 425 } 426 assert(len > 1); 427 assert(-halflen <= n && n <= halflen); 428 429 deque->state++; 430 while (n > 0) { 431 if (deque->leftindex == 0) { 432 block *b = newblock(NULL, deque->leftblock, len); 433 if (b == NULL) 434 return -1; 435 assert(deque->leftblock->leftlink == NULL); 436 deque->leftblock->leftlink = b; 437 deque->leftblock = b; 438 deque->leftindex = BLOCKLEN; 439 } 440 assert(deque->leftindex > 0); 441 442 m = n; 443 if (m > deque->rightindex + 1) 444 m = deque->rightindex + 1; 445 if (m > deque->leftindex) 446 m = deque->leftindex; 447 assert (m > 0 && m <= len); 448 memcpy(&deque->leftblock->data[deque->leftindex - m], 449 &deque->rightblock->data[deque->rightindex + 1 - m], 450 m * sizeof(PyObject *)); 451 deque->rightindex -= m; 452 deque->leftindex -= m; 453 n -= m; 454 455 if (deque->rightindex == -1) { 456 block *prevblock = deque->rightblock->leftlink; 457 assert(deque->rightblock != NULL); 458 assert(deque->leftblock != deque->rightblock); 459 freeblock(deque->rightblock); 460 prevblock->rightlink = NULL; 461 deque->rightblock = prevblock; 462 deque->rightindex = BLOCKLEN - 1; 463 } 464 } 465 while (n < 0) { 466 if (deque->rightindex == BLOCKLEN - 1) { 467 block *b = newblock(deque->rightblock, NULL, len); 468 if (b == NULL) 469 return -1; 470 assert(deque->rightblock->rightlink == NULL); 471 deque->rightblock->rightlink = b; 472 deque->rightblock = b; 473 deque->rightindex = -1; 474 } 475 assert (deque->rightindex < BLOCKLEN - 1); 476 477 m = -n; 478 if (m > BLOCKLEN - deque->leftindex) 479 m = BLOCKLEN - deque->leftindex; 480 if (m > BLOCKLEN - 1 - deque->rightindex) 481 m = BLOCKLEN - 1 - deque->rightindex; 482 assert (m > 0 && m <= len); 483 memcpy(&deque->rightblock->data[deque->rightindex + 1], 484 &deque->leftblock->data[deque->leftindex], 485 m * sizeof(PyObject *)); 486 deque->leftindex += m; 487 deque->rightindex += m; 488 n += m; 489 490 if (deque->leftindex == BLOCKLEN) { 491 block *nextblock = deque->leftblock->rightlink; 492 assert(deque->leftblock != deque->rightblock); 493 freeblock(deque->leftblock); 494 assert(nextblock != NULL); 495 nextblock->leftlink = NULL; 496 deque->leftblock = nextblock; 497 deque->leftindex = 0; 498 } 499 } 500 return 0; 425 501 } 426 502 … … 428 504 deque_rotate(dequeobject *deque, PyObject *args) 429 505 { 430 431 432 433 434 435 436 506 Py_ssize_t n=1; 507 508 if (!PyArg_ParseTuple(args, "|n:rotate", &n)) 509 return NULL; 510 if (_deque_rotate(deque, n) == 0) 511 Py_RETURN_NONE; 512 return NULL; 437 513 } 438 514 … … 440 516 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left."); 441 517 518 static PyObject * 519 deque_reverse(dequeobject *deque, PyObject *unused) 520 { 521 block *leftblock = deque->leftblock; 522 block *rightblock = deque->rightblock; 523 Py_ssize_t leftindex = deque->leftindex; 524 Py_ssize_t rightindex = deque->rightindex; 525 Py_ssize_t n = (deque->len)/2; 526 Py_ssize_t i; 527 PyObject *tmp; 528 529 for (i=0 ; i<n ; i++) { 530 /* Validate that pointers haven't met in the middle */ 531 assert(leftblock != rightblock || leftindex < rightindex); 532 533 /* Swap */ 534 tmp = leftblock->data[leftindex]; 535 leftblock->data[leftindex] = rightblock->data[rightindex]; 536 rightblock->data[rightindex] = tmp; 537 538 /* Advance left block/index pair */ 539 leftindex++; 540 if (leftindex == BLOCKLEN) { 541 if (leftblock->rightlink == NULL) 542 break; 543 leftblock = leftblock->rightlink; 544 leftindex = 0; 545 } 546 547 /* Step backwards with the right block/index pair */ 548 rightindex--; 549 if (rightindex == -1) { 550 if (rightblock->leftlink == NULL) 551 break; 552 rightblock = rightblock->leftlink; 553 rightindex = BLOCKLEN - 1; 554 } 555 } 556 Py_RETURN_NONE; 557 } 558 559 PyDoc_STRVAR(reverse_doc, 560 "D.reverse() -- reverse *IN PLACE*"); 561 562 static PyObject * 563 deque_count(dequeobject *deque, PyObject *v) 564 { 565 block *leftblock = deque->leftblock; 566 Py_ssize_t leftindex = deque->leftindex; 567 Py_ssize_t n = deque->len; 568 Py_ssize_t i; 569 Py_ssize_t count = 0; 570 PyObject *item; 571 long start_state = deque->state; 572 int cmp; 573 574 for (i=0 ; i<n ; i++) { 575 item = leftblock->data[leftindex]; 576 cmp = PyObject_RichCompareBool(item, v, Py_EQ); 577 if (cmp > 0) 578 count++; 579 else if (cmp < 0) 580 return NULL; 581 582 if (start_state != deque->state) { 583 PyErr_SetString(PyExc_RuntimeError, 584 "deque mutated during iteration"); 585 return NULL; 586 } 587 588 /* Advance left block/index pair */ 589 leftindex++; 590 if (leftindex == BLOCKLEN) { 591 if (leftblock->rightlink == NULL) /* can occur when i==n-1 */ 592 break; 593 leftblock = leftblock->rightlink; 594 leftindex = 0; 595 } 596 } 597 return PyInt_FromSsize_t(count); 598 } 599 600 PyDoc_STRVAR(count_doc, 601 "D.count(value) -> integer -- return number of occurrences of value"); 602 442 603 static Py_ssize_t 443 604 deque_len(dequeobject *deque) 444 605 { 445 606 return deque->len; 446 607 } 447 608 … … 449 610 deque_remove(dequeobject *deque, PyObject *value) 450 611 { 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 612 Py_ssize_t i, n=deque->len; 613 614 for (i=0 ; i<n ; i++) { 615 PyObject *item = deque->leftblock->data[deque->leftindex]; 616 int cmp = PyObject_RichCompareBool(item, value, Py_EQ); 617 618 if (deque->len != n) { 619 PyErr_SetString(PyExc_IndexError, 620 "deque mutated during remove()."); 621 return NULL; 622 } 623 if (cmp > 0) { 624 PyObject *tgt = deque_popleft(deque, NULL); 625 assert (tgt != NULL); 626 Py_DECREF(tgt); 627 if (_deque_rotate(deque, i) == -1) 628 return NULL; 629 Py_RETURN_NONE; 630 } 631 else if (cmp < 0) { 632 _deque_rotate(deque, i); 633 return NULL; 634 } 635 _deque_rotate(deque, -1); 636 } 637 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque"); 638 return NULL; 478 639 } 479 640 … … 481 642 "D.remove(value) -- remove first occurrence of value."); 482 643 483 static int644 static void 484 645 deque_clear(dequeobject *deque) 485 646 { 486 PyObject *item; 487 488 while (deque->len) { 489 item = deque_pop(deque, NULL); 490 assert (item != NULL); 491 Py_DECREF(item); 492 } 493 assert(deque->leftblock == deque->rightblock && 494 deque->leftindex - 1 == deque->rightindex && 495 deque->len == 0); 496 return 0; 647 PyObject *item; 648 649 while (deque->len) { 650 item = deque_pop(deque, NULL); 651 assert (item != NULL); 652 Py_DECREF(item); 653 } 654 assert(deque->leftblock == deque->rightblock && 655 deque->leftindex - 1 == deque->rightindex && 656 deque->len == 0); 497 657 } 498 658 … … 500 660 deque_item(dequeobject *deque, Py_ssize_t i) 501 661 { 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 662 block *b; 663 PyObject *item; 664 Py_ssize_t n, index=i; 665 666 if (i < 0 || i >= deque->len) { 667 PyErr_SetString(PyExc_IndexError, 668 "deque index out of range"); 669 return NULL; 670 } 671 672 if (i == 0) { 673 i = deque->leftindex; 674 b = deque->leftblock; 675 } else if (i == deque->len - 1) { 676 i = deque->rightindex; 677 b = deque->rightblock; 678 } else { 679 i += deque->leftindex; 680 n = i / BLOCKLEN; 681 i %= BLOCKLEN; 682 if (index < (deque->len >> 1)) { 683 b = deque->leftblock; 684 while (n--) 685 b = b->rightlink; 686 } else { 687 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n; 688 b = deque->rightblock; 689 while (n--) 690 b = b->leftlink; 691 } 692 } 693 item = b->data[i]; 694 Py_INCREF(item); 695 return item; 536 696 } 537 697 … … 546 706 deque_del_item(dequeobject *deque, Py_ssize_t i) 547 707 { 548 549 550 551 552 553 554 555 556 557 558 708 PyObject *item; 709 710 assert (i >= 0 && i < deque->len); 711 if (_deque_rotate(deque, -i) == -1) 712 return -1; 713 714 item = deque_popleft(deque, NULL); 715 assert (item != NULL); 716 Py_DECREF(item); 717 718 return _deque_rotate(deque, i); 559 719 } 560 720 … … 562 722 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) 563 723 { 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 724 PyObject *old_value; 725 block *b; 726 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i; 727 728 if (i < 0 || i >= len) { 729 PyErr_SetString(PyExc_IndexError, 730 "deque index out of range"); 731 return -1; 732 } 733 if (v == NULL) 734 return deque_del_item(deque, i); 735 736 i += deque->leftindex; 737 n = i / BLOCKLEN; 738 i %= BLOCKLEN; 739 if (index <= halflen) { 740 b = deque->leftblock; 741 while (n--) 742 b = b->rightlink; 743 } else { 744 n = (deque->leftindex + len - 1) / BLOCKLEN - n; 745 b = deque->rightblock; 746 while (n--) 747 b = b->leftlink; 748 } 749 Py_INCREF(v); 750 old_value = b->data[i]; 751 b->data[i] = v; 752 Py_DECREF(old_value); 753 return 0; 594 754 } 595 755 … … 597 757 deque_clearmethod(dequeobject *deque) 598 758 { 599 int rv; 600 601 rv = deque_clear(deque); 602 assert (rv != -1); 603 Py_RETURN_NONE; 759 deque_clear(deque); 760 Py_RETURN_NONE; 604 761 } 605 762 … … 609 766 deque_dealloc(dequeobject *deque) 610 767 { 611 612 613 614 615 616 617 618 619 620 621 768 PyObject_GC_UnTrack(deque); 769 if (deque->weakreflist != NULL) 770 PyObject_ClearWeakRefs((PyObject *) deque); 771 if (deque->leftblock != NULL) { 772 deque_clear(deque); 773 assert(deque->leftblock != NULL); 774 freeblock(deque->leftblock); 775 } 776 deque->leftblock = NULL; 777 deque->rightblock = NULL; 778 Py_TYPE(deque)->tp_free(deque); 622 779 } 623 780 … … 625 782 deque_traverse(dequeobject *deque, visitproc visit, void *arg) 626 783 { 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 784 block *b; 785 PyObject *item; 786 Py_ssize_t index; 787 Py_ssize_t indexlo = deque->leftindex; 788 789 for (b = deque->leftblock; b != NULL; b = b->rightlink) { 790 const Py_ssize_t indexhi = b == deque->rightblock ? 791 deque->rightindex : 792 BLOCKLEN - 1; 793 794 for (index = indexlo; index <= indexhi; ++index) { 795 item = b->data[index]; 796 Py_VISIT(item); 797 } 798 indexlo = 0; 799 } 800 return 0; 644 801 } 645 802 … … 647 804 deque_copy(PyObject *deque) 648 805 { 649 650 651 652 653 806 if (((dequeobject *)deque)->maxlen == -1) 807 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL); 808 else 809 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi", 810 deque, ((dequeobject *)deque)->maxlen, NULL); 654 811 } 655 812 … … 659 816 deque_reduce(dequeobject *deque) 660 817 { 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 818 PyObject *dict, *result, *aslist; 819 820 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__"); 821 if (dict == NULL) 822 PyErr_Clear(); 823 aslist = PySequence_List((PyObject *)deque); 824 if (aslist == NULL) { 825 Py_XDECREF(dict); 826 return NULL; 827 } 828 if (dict == NULL) { 829 if (deque->maxlen == -1) 830 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist); 831 else 832 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen); 833 } else { 834 if (deque->maxlen == -1) 835 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict); 836 else 837 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict); 838 } 839 Py_XDECREF(dict); 840 Py_DECREF(aslist); 841 return result; 685 842 } 686 843 … … 690 847 deque_repr(PyObject *deque) 691 848 { 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)", 709 710 711 fmt = PyString_FromString("deque(%r)"); 712 713 714 715 716 717 718 719 720 721 849 PyObject *aslist, *result, *fmt; 850 int i; 851 852 i = Py_ReprEnter(deque); 853 if (i != 0) { 854 if (i < 0) 855 return NULL; 856 return PyString_FromString("[...]"); 857 } 858 859 aslist = PySequence_List(deque); 860 if (aslist == NULL) { 861 Py_ReprLeave(deque); 862 return NULL; 863 } 864 if (((dequeobject *)deque)->maxlen != -1) 865 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)", 866 ((dequeobject *)deque)->maxlen); 867 else 868 fmt = PyString_FromString("deque(%r)"); 869 if (fmt == NULL) { 870 Py_DECREF(aslist); 871 Py_ReprLeave(deque); 872 return NULL; 873 } 874 result = PyString_Format(fmt, aslist); 875 Py_DECREF(fmt); 876 Py_DECREF(aslist); 877 Py_ReprLeave(deque); 878 return result; 722 879 } 723 880 … … 725 882 deque_tp_print(PyObject *deque, FILE *fp, int flags) 726 883 { 727 728 char *emit = "";/* No separator emitted on first pass */729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 884 PyObject *it, *item; 885 char *emit = ""; /* No separator emitted on first pass */ 886 char *separator = ", "; 887 int i; 888 889 i = Py_ReprEnter(deque); 890 if (i != 0) { 891 if (i < 0) 892 return i; 893 Py_BEGIN_ALLOW_THREADS 894 fputs("[...]", fp); 895 Py_END_ALLOW_THREADS 896 return 0; 897 } 898 899 it = PyObject_GetIter(deque); 900 if (it == NULL) 901 return -1; 902 903 Py_BEGIN_ALLOW_THREADS 904 fputs("deque([", fp); 905 Py_END_ALLOW_THREADS 906 while ((item = PyIter_Next(it)) != NULL) { 907 Py_BEGIN_ALLOW_THREADS 908 fputs(emit, fp); 909 Py_END_ALLOW_THREADS 910 emit = separator; 911 if (PyObject_Print(item, fp, 0) != 0) { 912 Py_DECREF(item); 913 Py_DECREF(it); 914 Py_ReprLeave(deque); 915 return -1; 916 } 917 Py_DECREF(item); 918 } 919 Py_ReprLeave(deque); 920 Py_DECREF(it); 921 if (PyErr_Occurred()) 922 return -1; 923 924 Py_BEGIN_ALLOW_THREADS 925 if (((dequeobject *)deque)->maxlen == -1) 926 fputs("])", fp); 927 else 928 fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen); 929 Py_END_ALLOW_THREADS 930 return 0; 774 931 } 775 932 … … 777 934 deque_richcompare(PyObject *v, PyObject *w, int op) 778 935 { 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 936 PyObject *it1=NULL, *it2=NULL, *x, *y; 937 Py_ssize_t vs, ws; 938 int b, cmp=-1; 939 940 if (!PyObject_TypeCheck(v, &deque_type) || 941 !PyObject_TypeCheck(w, &deque_type)) { 942 Py_INCREF(Py_NotImplemented); 943 return Py_NotImplemented; 944 } 945 946 /* Shortcuts */ 947 vs = ((dequeobject *)v)->len; 948 ws = ((dequeobject *)w)->len; 949 if (op == Py_EQ) { 950 if (v == w) 951 Py_RETURN_TRUE; 952 if (vs != ws) 953 Py_RETURN_FALSE; 954 } 955 if (op == Py_NE) { 956 if (v == w) 957 Py_RETURN_FALSE; 958 if (vs != ws) 959 Py_RETURN_TRUE; 960 } 961 962 /* Search for the first index where items are different */ 963 it1 = PyObject_GetIter(v); 964 if (it1 == NULL) 965 goto done; 966 it2 = PyObject_GetIter(w); 967 if (it2 == NULL) 968 goto done; 969 for (;;) { 970 x = PyIter_Next(it1); 971 if (x == NULL && PyErr_Occurred()) 972 goto done; 973 y = PyIter_Next(it2); 974 if (x == NULL || y == NULL) 975 break; 976 b = PyObject_RichCompareBool(x, y, Py_EQ); 977 if (b == 0) { 978 cmp = PyObject_RichCompareBool(x, y, op); 979 Py_DECREF(x); 980 Py_DECREF(y); 981 goto done; 982 } 983 Py_DECREF(x); 984 Py_DECREF(y); 985 if (b == -1) 986 goto done; 987 } 988 /* We reached the end of one deque or both */ 989 Py_XDECREF(x); 990 Py_XDECREF(y); 991 if (PyErr_Occurred()) 992 goto done; 993 switch (op) { 994 case Py_LT: cmp = y != NULL; break; /* if w was longer */ 995 case Py_LE: cmp = x == NULL; break; /* if v was not longer */ 996 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */ 997 case Py_NE: cmp = x != y; break; /* if one deque continues */ 998 case Py_GT: cmp = x != NULL; break; /* if v was longer */ 999 case Py_GE: cmp = y == NULL; break; /* if w was not longer */ 1000 } 844 1001 845 1002 done: 846 847 848 849 850 851 852 1003 Py_XDECREF(it1); 1004 Py_XDECREF(it2); 1005 if (cmp == 1) 1006 Py_RETURN_TRUE; 1007 if (cmp == 0) 1008 Py_RETURN_FALSE; 1009 return NULL; 853 1010 } 854 1011 … … 856 1013 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) 857 1014 { 858 PyObject *iterable = NULL; 859 PyObject *maxlenobj = NULL; 860 Py_ssize_t maxlen = -1; 861 char *kwlist[] = {"iterable", "maxlen", 0}; 862 863 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj)) 864 return -1; 865 if (maxlenobj != NULL && maxlenobj != Py_None) { 866 maxlen = PyInt_AsSsize_t(maxlenobj); 867 if (maxlen == -1 && PyErr_Occurred()) 868 return -1; 869 if (maxlen < 0) { 870 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative"); 871 return -1; 872 } 873 } 874 deque->maxlen = maxlen; 875 deque_clear(deque); 876 if (iterable != NULL) { 877 PyObject *rv = deque_extend(deque, iterable); 878 if (rv == NULL) 879 return -1; 880 Py_DECREF(rv); 881 } 882 return 0; 883 } 1015 PyObject *iterable = NULL; 1016 PyObject *maxlenobj = NULL; 1017 Py_ssize_t maxlen = -1; 1018 char *kwlist[] = {"iterable", "maxlen", 0}; 1019 1020 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj)) 1021 return -1; 1022 if (maxlenobj != NULL && maxlenobj != Py_None) { 1023 maxlen = PyInt_AsSsize_t(maxlenobj); 1024 if (maxlen == -1 && PyErr_Occurred()) 1025 return -1; 1026 if (maxlen < 0) { 1027 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative"); 1028 return -1; 1029 } 1030 } 1031 deque->maxlen = maxlen; 1032 deque_clear(deque); 1033 if (iterable != NULL) { 1034 PyObject *rv = deque_extend(deque, iterable); 1035 if (rv == NULL) 1036 return -1; 1037 Py_DECREF(rv); 1038 } 1039 return 0; 1040 } 1041 1042 static PyObject * 1043 deque_sizeof(dequeobject *deque, void *unused) 1044 { 1045 Py_ssize_t res; 1046 Py_ssize_t blocks; 1047 1048 res = sizeof(dequeobject); 1049 blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN; 1050 assert(deque->leftindex + deque->len - 1 == 1051 (blocks - 1) * BLOCKLEN + deque->rightindex); 1052 res += blocks * sizeof(block); 1053 return PyLong_FromSsize_t(res); 1054 } 1055 1056 PyDoc_STRVAR(sizeof_doc, 1057 "D.__sizeof__() -- size of D in memory, in bytes"); 1058 1059 static PyObject * 1060 deque_get_maxlen(dequeobject *deque) 1061 { 1062 if (deque->maxlen == -1) 1063 Py_RETURN_NONE; 1064 return PyInt_FromSsize_t(deque->maxlen); 1065 } 1066 1067 static PyGetSetDef deque_getset[] = { 1068 {"maxlen", (getter)deque_get_maxlen, (setter)NULL, 1069 "maximum size of a deque or None if unbounded"}, 1070 {0} 1071 }; 884 1072 885 1073 static PySequenceMethods deque_as_sequence = { 886 (lenfunc)deque_len,/* sq_length */887 0,/* sq_concat */888 0,/* sq_repeat */889 (ssizeargfunc)deque_item,/* sq_item */890 0,/* sq_slice */891 (ssizeobjargproc)deque_ass_item,/* sq_ass_item */892 0,/* sq_ass_slice */893 0,/* sq_contains */894 (binaryfunc)deque_inplace_concat,/* sq_inplace_concat */895 0,/* sq_inplace_repeat */1074 (lenfunc)deque_len, /* sq_length */ 1075 0, /* sq_concat */ 1076 0, /* sq_repeat */ 1077 (ssizeargfunc)deque_item, /* sq_item */ 1078 0, /* sq_slice */ 1079 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */ 1080 0, /* sq_ass_slice */ 1081 0, /* sq_contains */ 1082 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */ 1083 0, /* sq_inplace_repeat */ 896 1084 897 1085 }; … … 902 1090 static PyObject *deque_reviter(dequeobject *deque); 903 1091 PyDoc_STRVAR(reversed_doc, 904 1092 "D.__reversed__() -- return a reverse iterator over the deque"); 905 1093 906 1094 static PyMethodDef deque_methods[] = { 907 {"append", (PyCFunction)deque_append, 908 METH_O, append_doc}, 909 {"appendleft", (PyCFunction)deque_appendleft, 910 METH_O, appendleft_doc}, 911 {"clear", (PyCFunction)deque_clearmethod, 912 METH_NOARGS, clear_doc}, 913 {"__copy__", (PyCFunction)deque_copy, 914 METH_NOARGS, copy_doc}, 915 {"extend", (PyCFunction)deque_extend, 916 METH_O, extend_doc}, 917 {"extendleft", (PyCFunction)deque_extendleft, 918 METH_O, extendleft_doc}, 919 {"pop", (PyCFunction)deque_pop, 920 METH_NOARGS, pop_doc}, 921 {"popleft", (PyCFunction)deque_popleft, 922 METH_NOARGS, popleft_doc}, 923 {"__reduce__", (PyCFunction)deque_reduce, 924 METH_NOARGS, reduce_doc}, 925 {"remove", (PyCFunction)deque_remove, 926 METH_O, remove_doc}, 927 {"__reversed__", (PyCFunction)deque_reviter, 928 METH_NOARGS, reversed_doc}, 929 {"rotate", (PyCFunction)deque_rotate, 930 METH_VARARGS, rotate_doc}, 931 {NULL, NULL} /* sentinel */ 1095 {"append", (PyCFunction)deque_append, 1096 METH_O, append_doc}, 1097 {"appendleft", (PyCFunction)deque_appendleft, 1098 METH_O, appendleft_doc}, 1099 {"clear", (PyCFunction)deque_clearmethod, 1100 METH_NOARGS, clear_doc}, 1101 {"__copy__", (PyCFunction)deque_copy, 1102 METH_NOARGS, copy_doc}, 1103 {"count", (PyCFunction)deque_count, 1104 METH_O, count_doc}, 1105 {"extend", (PyCFunction)deque_extend, 1106 METH_O, extend_doc}, 1107 {"extendleft", (PyCFunction)deque_extendleft, 1108 METH_O, extendleft_doc}, 1109 {"pop", (PyCFunction)deque_pop, 1110 METH_NOARGS, pop_doc}, 1111 {"popleft", (PyCFunction)deque_popleft, 1112 METH_NOARGS, popleft_doc}, 1113 {"__reduce__", (PyCFunction)deque_reduce, 1114 METH_NOARGS, reduce_doc}, 1115 {"remove", (PyCFunction)deque_remove, 1116 METH_O, remove_doc}, 1117 {"__reversed__", (PyCFunction)deque_reviter, 1118 METH_NOARGS, reversed_doc}, 1119 {"reverse", (PyCFunction)deque_reverse, 1120 METH_NOARGS, reverse_doc}, 1121 {"rotate", (PyCFunction)deque_rotate, 1122 METH_VARARGS, rotate_doc}, 1123 {"__sizeof__", (PyCFunction)deque_sizeof, 1124 METH_NOARGS, sizeof_doc}, 1125 {NULL, NULL} /* sentinel */ 932 1126 }; 933 1127 934 1128 PyDoc_STRVAR(deque_doc, 935 "deque( iterable[, maxlen]) --> deque object\n\1129 "deque([iterable[, maxlen]]) --> deque object\n\ 936 1130 \n\ 937 Build an ordered collection accessible from endpoints only.");1131 Build an ordered collection with optimized access from its endpoints."); 938 1132 939 1133 static PyTypeObject deque_type = { 940 941 "collections.deque",/* tp_name */942 sizeof(dequeobject),/* tp_basicsize */943 0,/* tp_itemsize */944 945 (destructor)deque_dealloc,/* tp_dealloc */946 deque_tp_print,/* tp_print */947 0,/* tp_getattr */948 0,/* tp_setattr */949 0,/* tp_compare */950 deque_repr,/* tp_repr */951 0,/* tp_as_number */952 &deque_as_sequence,/* tp_as_sequence */953 0,/* tp_as_mapping */954 (hashfunc)PyObject_HashNotImplemented,/* tp_hash */955 0,/* tp_call */956 0,/* tp_str */957 PyObject_GenericGetAttr,/* tp_getattro */958 0,/* tp_setattro */959 0,/* tp_as_buffer */960 961 Py_TPFLAGS_HAVE_WEAKREFS,/* tp_flags */962 deque_doc,/* tp_doc */963 (traverseproc)deque_traverse,/* tp_traverse */964 (inquiry)deque_clear,/* tp_clear */965 (richcmpfunc)deque_richcompare,/* tp_richcompare */966 offsetof(dequeobject, weakreflist),/* tp_weaklistoffset*/967 (getiterfunc)deque_iter,/* tp_iter */968 0,/* tp_iternext */969 deque_methods,/* tp_methods */970 0,/* tp_members */971 0,/* tp_getset */972 0,/* tp_base */973 0,/* tp_dict */974 0,/* tp_descr_get */975 0,/* tp_descr_set */976 0,/* tp_dictoffset */977 (initproc)deque_init,/* tp_init */978 PyType_GenericAlloc,/* tp_alloc */979 deque_new,/* tp_new */980 PyObject_GC_Del,/* tp_free */1134 PyVarObject_HEAD_INIT(NULL, 0) 1135 "collections.deque", /* tp_name */ 1136 sizeof(dequeobject), /* tp_basicsize */ 1137 0, /* tp_itemsize */ 1138 /* methods */ 1139 (destructor)deque_dealloc, /* tp_dealloc */ 1140 deque_tp_print, /* tp_print */ 1141 0, /* tp_getattr */ 1142 0, /* tp_setattr */ 1143 0, /* tp_compare */ 1144 deque_repr, /* tp_repr */ 1145 0, /* tp_as_number */ 1146 &deque_as_sequence, /* tp_as_sequence */ 1147 0, /* tp_as_mapping */ 1148 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 1149 0, /* tp_call */ 1150 0, /* tp_str */ 1151 PyObject_GenericGetAttr, /* tp_getattro */ 1152 0, /* tp_setattro */ 1153 0, /* tp_as_buffer */ 1154 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC | 1155 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */ 1156 deque_doc, /* tp_doc */ 1157 (traverseproc)deque_traverse, /* tp_traverse */ 1158 (inquiry)deque_clear, /* tp_clear */ 1159 (richcmpfunc)deque_richcompare, /* tp_richcompare */ 1160 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/ 1161 (getiterfunc)deque_iter, /* tp_iter */ 1162 0, /* tp_iternext */ 1163 deque_methods, /* tp_methods */ 1164 0, /* tp_members */ 1165 deque_getset, /* tp_getset */ 1166 0, /* tp_base */ 1167 0, /* tp_dict */ 1168 0, /* tp_descr_get */ 1169 0, /* tp_descr_set */ 1170 0, /* tp_dictoffset */ 1171 (initproc)deque_init, /* tp_init */ 1172 PyType_GenericAlloc, /* tp_alloc */ 1173 deque_new, /* tp_new */ 1174 PyObject_GC_Del, /* tp_free */ 981 1175 }; 982 1176 … … 984 1178 985 1179 typedef struct { 986 987 988 989 990 long state;/* state when the iterator is created */991 1180 PyObject_HEAD 1181 Py_ssize_t index; 1182 block *b; 1183 dequeobject *deque; 1184 long state; /* state when the iterator is created */ 1185 Py_ssize_t counter; /* number of items remaining for iteration */ 992 1186 } dequeiterobject; 993 1187 … … 997 1191 deque_iter(dequeobject *deque) 998 1192 { 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1193 dequeiterobject *it; 1194 1195 it = PyObject_GC_New(dequeiterobject, &dequeiter_type); 1196 if (it == NULL) 1197 return NULL; 1198 it->b = deque->leftblock; 1199 it->index = deque->leftindex; 1200 Py_INCREF(deque); 1201 it->deque = deque; 1202 it->state = deque->state; 1203 it->counter = deque->len; 1204 PyObject_GC_Track(it); 1205 return (PyObject *)it; 1012 1206 } 1013 1207 … … 1015 1209 dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg) 1016 1210 { 1017 1018 1211 Py_VISIT(dio->deque); 1212 return 0; 1019 1213 } 1020 1214 … … 1022 1216 dequeiter_dealloc(dequeiterobject *dio) 1023 1217 { 1024 1025 1218 Py_XDECREF(dio->deque); 1219 PyObject_GC_Del(dio); 1026 1220 } 1027 1221 … … 1029 1223 dequeiter_next(dequeiterobject *it) 1030 1224 { 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 return NULL; 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1225 PyObject *item; 1226 1227 if (it->deque->state != it->state) { 1228 it->counter = 0; 1229 PyErr_SetString(PyExc_RuntimeError, 1230 "deque mutated during iteration"); 1231 return NULL; 1232 } 1233 if (it->counter == 0) 1234 return NULL; 1235 assert (!(it->b == it->deque->rightblock && 1236 it->index > it->deque->rightindex)); 1237 1238 item = it->b->data[it->index]; 1239 it->index++; 1240 it->counter--; 1241 if (it->index == BLOCKLEN && it->counter > 0) { 1242 assert (it->b->rightlink != NULL); 1243 it->b = it->b->rightlink; 1244 it->index = 0; 1245 } 1246 Py_INCREF(item); 1247 return item; 1054 1248 } 1055 1249 … … 1057 1251 dequeiter_len(dequeiterobject *it) 1058 1252 { 1059 1253 return PyInt_FromLong(it->counter); 1060 1254 } 1061 1255 … … 1063 1257 1064 1258 static PyMethodDef dequeiter_methods[] = { 1065 1066 {NULL, NULL}/* sentinel */1259 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc}, 1260 {NULL, NULL} /* sentinel */ 1067 1261 }; 1068 1262 1069 1263 static PyTypeObject dequeiter_type = { 1070 1071 "deque_iterator",/* tp_name */1072 sizeof(dequeiterobject),/* tp_basicsize */1073 0,/* tp_itemsize */1074 1075 (destructor)dequeiter_dealloc,/* tp_dealloc */1076 0,/* tp_print */1077 0,/* tp_getattr */1078 0,/* tp_setattr */1079 0,/* tp_compare */1080 0,/* tp_repr */1081 0,/* tp_as_number */1082 0,/* tp_as_sequence */1083 0,/* tp_as_mapping */1084 0,/* tp_hash */1085 0,/* tp_call */1086 0,/* tp_str */1087 PyObject_GenericGetAttr,/* tp_getattro */1088 0,/* tp_setattro */1089 0,/* tp_as_buffer */1090 1091 0,/* tp_doc */1092 (traverseproc)dequeiter_traverse,/* tp_traverse */1093 0,/* tp_clear */1094 0,/* tp_richcompare */1095 0,/* tp_weaklistoffset */1096 PyObject_SelfIter,/* tp_iter */1097 (iternextfunc)dequeiter_next,/* tp_iternext */1098 dequeiter_methods,/* tp_methods */1099 1264 PyVarObject_HEAD_INIT(NULL, 0) 1265 "deque_iterator", /* tp_name */ 1266 sizeof(dequeiterobject), /* tp_basicsize */ 1267 0, /* tp_itemsize */ 1268 /* methods */ 1269 (destructor)dequeiter_dealloc, /* tp_dealloc */ 1270 0, /* tp_print */ 1271 0, /* tp_getattr */ 1272 0, /* tp_setattr */ 1273 0, /* tp_compare */ 1274 0, /* tp_repr */ 1275 0, /* tp_as_number */ 1276 0, /* tp_as_sequence */ 1277 0, /* tp_as_mapping */ 1278 0, /* tp_hash */ 1279 0, /* tp_call */ 1280 0, /* tp_str */ 1281 PyObject_GenericGetAttr, /* tp_getattro */ 1282 0, /* tp_setattro */ 1283 0, /* tp_as_buffer */ 1284 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 1285 0, /* tp_doc */ 1286 (traverseproc)dequeiter_traverse, /* tp_traverse */ 1287 0, /* tp_clear */ 1288 0, /* tp_richcompare */ 1289 0, /* tp_weaklistoffset */ 1290 PyObject_SelfIter, /* tp_iter */ 1291 (iternextfunc)dequeiter_next, /* tp_iternext */ 1292 dequeiter_methods, /* tp_methods */ 1293 0, 1100 1294 }; 1101 1295 … … 1107 1301 deque_reviter(dequeobject *deque) 1108 1302 { 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1303 dequeiterobject *it; 1304 1305 it = PyObject_GC_New(dequeiterobject, &dequereviter_type); 1306 if (it == NULL) 1307 return NULL; 1308 it->b = deque->rightblock; 1309 it->index = deque->rightindex; 1310 Py_INCREF(deque); 1311 it->deque = deque; 1312 it->state = deque->state; 1313 it->counter = deque->len; 1314 PyObject_GC_Track(it); 1315 return (PyObject *)it; 1122 1316 } 1123 1317 … … 1125 1319 dequereviter_next(dequeiterobject *it) 1126 1320 { 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1321 PyObject *item; 1322 if (it->counter == 0) 1323 return NULL; 1324 1325 if (it->deque->state != it->state) { 1326 it->counter = 0; 1327 PyErr_SetString(PyExc_RuntimeError, 1328 "deque mutated during iteration"); 1329 return NULL; 1330 } 1331 assert (!(it->b == it->deque->leftblock && 1332 it->index < it->deque->leftindex)); 1333 1334 item = it->b->data[it->index]; 1335 it->index--; 1336 it->counter--; 1337 if (it->index == -1 && it->counter > 0) { 1338 assert (it->b->leftlink != NULL); 1339 it->b = it->b->leftlink; 1340 it->index = BLOCKLEN - 1; 1341 } 1342 Py_INCREF(item); 1343 return item; 1150 1344 } 1151 1345 1152 1346 static PyTypeObject dequereviter_type = { 1153 1154 "deque_reverse_iterator",/* tp_name */1155 sizeof(dequeiterobject),/* tp_basicsize */1156 0,/* tp_itemsize */1157 1158 (destructor)dequeiter_dealloc,/* tp_dealloc */1159 0,/* tp_print */1160 0,/* tp_getattr */1161 0,/* tp_setattr */1162 0,/* tp_compare */1163 0,/* tp_repr */1164 0,/* tp_as_number */1165 0,/* tp_as_sequence */1166 0,/* tp_as_mapping */1167 0,/* tp_hash */1168 0,/* tp_call */1169 0,/* tp_str */1170 PyObject_GenericGetAttr,/* tp_getattro */1171 0,/* tp_setattro */1172 0,/* tp_as_buffer */1173 1174 0,/* tp_doc */1175 (traverseproc)dequeiter_traverse,/* tp_traverse */1176 0,/* tp_clear */1177 0,/* tp_richcompare */1178 0,/* tp_weaklistoffset */1179 PyObject_SelfIter,/* tp_iter */1180 (iternextfunc)dequereviter_next,/* tp_iternext */1181 dequeiter_methods,/* tp_methods */1182 1347 PyVarObject_HEAD_INIT(NULL, 0) 1348 "deque_reverse_iterator", /* tp_name */ 1349 sizeof(dequeiterobject), /* tp_basicsize */ 1350 0, /* tp_itemsize */ 1351 /* methods */ 1352 (destructor)dequeiter_dealloc, /* tp_dealloc */ 1353 0, /* tp_print */ 1354 0, /* tp_getattr */ 1355 0, /* tp_setattr */ 1356 0, /* tp_compare */ 1357 0, /* tp_repr */ 1358 0, /* tp_as_number */ 1359 0, /* tp_as_sequence */ 1360 0, /* tp_as_mapping */ 1361 0, /* tp_hash */ 1362 0, /* tp_call */ 1363 0, /* tp_str */ 1364 PyObject_GenericGetAttr, /* tp_getattro */ 1365 0, /* tp_setattro */ 1366 0, /* tp_as_buffer */ 1367 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 1368 0, /* tp_doc */ 1369 (traverseproc)dequeiter_traverse, /* tp_traverse */ 1370 0, /* tp_clear */ 1371 0, /* tp_richcompare */ 1372 0, /* tp_weaklistoffset */ 1373 PyObject_SelfIter, /* tp_iter */ 1374 (iternextfunc)dequereviter_next, /* tp_iternext */ 1375 dequeiter_methods, /* tp_methods */ 1376 0, 1183 1377 }; 1184 1378 … … 1186 1380 1187 1381 typedef struct { 1188 1189 1382 PyDictObject dict; 1383 PyObject *default_factory; 1190 1384 } defdictobject; 1191 1385 … … 1202 1396 defdict_missing(defdictobject *dd, PyObject *key) 1203 1397 { 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1398 PyObject *factory = dd->default_factory; 1399 PyObject *value; 1400 if (factory == NULL || factory == Py_None) { 1401 /* XXX Call dict.__missing__(key) */ 1402 PyObject *tup; 1403 tup = PyTuple_Pack(1, key); 1404 if (!tup) return NULL; 1405 PyErr_SetObject(PyExc_KeyError, tup); 1406 Py_DECREF(tup); 1407 return NULL; 1408 } 1409 value = PyEval_CallObject(factory, NULL); 1410 if (value == NULL) 1411 return value; 1412 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) { 1413 Py_DECREF(value); 1414 return NULL; 1415 } 1416 return value; 1223 1417 } 1224 1418 … … 1228 1422 defdict_copy(defdictobject *dd) 1229 1423 { 1230 1231 1232 1233 1234 1235 1236 1237 1238 1424 /* This calls the object's class. That only works for subclasses 1425 whose class constructor has the same signature. Subclasses that 1426 define a different constructor signature must override copy(). 1427 */ 1428 1429 if (dd->default_factory == NULL) 1430 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL); 1431 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), 1432 dd->default_factory, dd, NULL); 1239 1433 } 1240 1434 … … 1242 1436 defdict_reduce(defdictobject *dd) 1243 1437 { 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1438 /* __reduce__ must return a 5-tuple as follows: 1439 1440 - factory function 1441 - tuple of args for the factory function 1442 - additional state (here None) 1443 - sequence iterator (here None) 1444 - dictionary iterator (yielding successive (key, value) pairs 1445 1446 This API is used by pickle.py and copy.py. 1447 1448 For this to be useful with pickle.py, the default_factory 1449 must be picklable; e.g., None, a built-in, or a global 1450 function in a module or package. 1451 1452 Both shallow and deep copying are supported, but for deep 1453 copying, the default_factory must be deep-copyable; e.g. None, 1454 or a built-in (functions are not copyable at this time). 1455 1456 This only works for subclasses as long as their constructor 1457 signature is compatible; the first argument must be the 1458 optional default_factory, defaulting to None. 1459 */ 1460 PyObject *args; 1461 PyObject *items; 1462 PyObject *result; 1463 if (dd->default_factory == NULL || dd->default_factory == Py_None) 1464 args = PyTuple_New(0); 1465 else 1466 args = PyTuple_Pack(1, dd->default_factory); 1467 if (args == NULL) 1468 return NULL; 1469 items = PyObject_CallMethod((PyObject *)dd, "iteritems", "()"); 1470 if (items == NULL) { 1471 Py_DECREF(args); 1472 return NULL; 1473 } 1474 result = PyTuple_Pack(5, Py_TYPE(dd), args, 1475 Py_None, Py_None, items); 1476 Py_DECREF(items); 1477 Py_DECREF(args); 1478 return result; 1285 1479 } 1286 1480 1287 1481 static PyMethodDef defdict_methods[] = { 1288 1289 1290 1291 1292 1293 1294 1295 1296 1482 {"__missing__", (PyCFunction)defdict_missing, METH_O, 1483 defdict_missing_doc}, 1484 {"copy", (PyCFunction)defdict_copy, METH_NOARGS, 1485 defdict_copy_doc}, 1486 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS, 1487 defdict_copy_doc}, 1488 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS, 1489 reduce_doc}, 1490 {NULL} 1297 1491 }; 1298 1492 1299 1493 static PyMemberDef defdict_members[] = { 1300 1301 1302 1303 1494 {"default_factory", T_OBJECT, 1495 offsetof(defdictobject, default_factory), 0, 1496 PyDoc_STR("Factory for default value called by __missing__().")}, 1497 {NULL} 1304 1498 }; 1305 1499 … … 1307 1501 defdict_dealloc(defdictobject *dd) 1308 1502 { 1309 1310 1503 Py_CLEAR(dd->default_factory); 1504 PyDict_Type.tp_dealloc((PyObject *)dd); 1311 1505 } 1312 1506 … … 1314 1508 defdict_print(defdictobject *dd, FILE *fp, int flags) 1315 1509 { 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1510 int sts; 1511 Py_BEGIN_ALLOW_THREADS 1512 fprintf(fp, "defaultdict("); 1513 Py_END_ALLOW_THREADS 1514 if (dd->default_factory == NULL) { 1515 Py_BEGIN_ALLOW_THREADS 1516 fprintf(fp, "None"); 1517 Py_END_ALLOW_THREADS 1518 } else { 1519 PyObject_Print(dd->default_factory, fp, 0); 1520 } 1521 Py_BEGIN_ALLOW_THREADS 1522 fprintf(fp, ", "); 1523 Py_END_ALLOW_THREADS 1524 sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0); 1525 Py_BEGIN_ALLOW_THREADS 1526 fprintf(fp, ")"); 1527 Py_END_ALLOW_THREADS 1528 return sts; 1335 1529 } 1336 1530 … … 1338 1532 defdict_repr(defdictobject *dd) 1339 1533 { 1340 PyObject *defrepr; 1341 PyObject *baserepr; 1342 PyObject *result; 1343 baserepr = PyDict_Type.tp_repr((PyObject *)dd); 1344 if (baserepr == NULL) 1345 return NULL; 1346 if (dd->default_factory == NULL) 1347 defrepr = PyString_FromString("None"); 1348 else 1349 { 1350 int status = Py_ReprEnter(dd->default_factory); 1351 if (status != 0) { 1352 if (status < 0) 1353 return NULL; 1354 defrepr = PyString_FromString("..."); 1355 } 1356 else 1357 defrepr = PyObject_Repr(dd->default_factory); 1358 Py_ReprLeave(dd->default_factory); 1359 } 1360 if (defrepr == NULL) { 1361 Py_DECREF(baserepr); 1362 return NULL; 1363 } 1364 result = PyString_FromFormat("defaultdict(%s, %s)", 1365 PyString_AS_STRING(defrepr), 1366 PyString_AS_STRING(baserepr)); 1367 Py_DECREF(defrepr); 1368 Py_DECREF(baserepr); 1369 return result; 1534 PyObject *defrepr; 1535 PyObject *baserepr; 1536 PyObject *result; 1537 baserepr = PyDict_Type.tp_repr((PyObject *)dd); 1538 if (baserepr == NULL) 1539 return NULL; 1540 if (dd->default_factory == NULL) 1541 defrepr = PyString_FromString("None"); 1542 else 1543 { 1544 int status = Py_ReprEnter(dd->default_factory); 1545 if (status != 0) { 1546 if (status < 0) { 1547 Py_DECREF(baserepr); 1548 return NULL; 1549 } 1550 defrepr = PyString_FromString("..."); 1551 } 1552 else 1553 defrepr = PyObject_Repr(dd->default_factory); 1554 Py_ReprLeave(dd->default_factory); 1555 } 1556 if (defrepr == NULL) { 1557 Py_DECREF(baserepr); 1558 return NULL; 1559 } 1560 result = PyString_FromFormat("defaultdict(%s, %s)", 1561 PyString_AS_STRING(defrepr), 1562 PyString_AS_STRING(baserepr)); 1563 Py_DECREF(defrepr); 1564 Py_DECREF(baserepr); 1565 return result; 1370 1566 } 1371 1567 … … 1373 1569 defdict_traverse(PyObject *self, visitproc visit, void *arg) 1374 1570 { 1375 1376 1571 Py_VISIT(((defdictobject *)self)->default_factory); 1572 return PyDict_Type.tp_traverse(self, visit, arg); 1377 1573 } 1378 1574 … … 1380 1576 defdict_tp_clear(defdictobject *dd) 1381 1577 { 1382 1383 1578 Py_CLEAR(dd->default_factory); 1579 return PyDict_Type.tp_clear((PyObject *)dd); 1384 1580 } 1385 1581 … … 1387 1583 defdict_init(PyObject *self, PyObject *args, PyObject *kwds) 1388 1584 { 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 "first argument must be callable"); 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1585 defdictobject *dd = (defdictobject *)self; 1586 PyObject *olddefault = dd->default_factory; 1587 PyObject *newdefault = NULL; 1588 PyObject *newargs; 1589 int result; 1590 if (args == NULL || !PyTuple_Check(args)) 1591 newargs = PyTuple_New(0); 1592 else { 1593 Py_ssize_t n = PyTuple_GET_SIZE(args); 1594 if (n > 0) { 1595 newdefault = PyTuple_GET_ITEM(args, 0); 1596 if (!PyCallable_Check(newdefault) && newdefault != Py_None) { 1597 PyErr_SetString(PyExc_TypeError, 1598 "first argument must be callable"); 1599 return -1; 1600 } 1601 } 1602 newargs = PySequence_GetSlice(args, 1, n); 1603 } 1604 if (newargs == NULL) 1605 return -1; 1606 Py_XINCREF(newdefault); 1607 dd->default_factory = newdefault; 1608 result = PyDict_Type.tp_init(self, newargs, kwds); 1609 Py_DECREF(newargs); 1610 Py_XDECREF(olddefault); 1611 return result; 1416 1612 } 1417 1613 … … 1428 1624 1429 1625 static PyTypeObject defdict_type = { 1430 1431 "collections.defaultdict",/* tp_name */1432 sizeof(defdictobject),/* tp_basicsize */1433 0,/* tp_itemsize */1434 1435 (destructor)defdict_dealloc,/* tp_dealloc */1436 (printfunc)defdict_print,/* tp_print */1437 0,/* tp_getattr */1438 0,/* tp_setattr */1439 0,/* tp_compare */1440 (reprfunc)defdict_repr,/* tp_repr */1441 0,/* tp_as_number */1442 0,/* tp_as_sequence */1443 0,/* tp_as_mapping */1444 0,/* tp_hash */1445 0,/* tp_call */1446 0,/* tp_str */1447 PyObject_GenericGetAttr,/* tp_getattro */1448 0,/* tp_setattro */1449 0,/* tp_as_buffer */1450 1451 Py_TPFLAGS_HAVE_WEAKREFS,/* tp_flags */1452 defdict_doc,/* tp_doc */1453 defdict_traverse,/* tp_traverse */1454 (inquiry)defdict_tp_clear,/* tp_clear */1455 0,/* tp_richcompare */1456 0,/* tp_weaklistoffset*/1457 0,/* tp_iter */1458 0,/* tp_iternext */1459 defdict_methods,/* tp_methods */1460 defdict_members,/* tp_members */1461 0,/* tp_getset */1462 DEFERRED_ADDRESS(&PyDict_Type),/* tp_base */1463 0,/* tp_dict */1464 0,/* tp_descr_get */1465 0,/* tp_descr_set */1466 0,/* tp_dictoffset */1467 defdict_init,/* tp_init */1468 PyType_GenericAlloc,/* tp_alloc */1469 0,/* tp_new */1470 PyObject_GC_Del,/* tp_free */1626 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0) 1627 "collections.defaultdict", /* tp_name */ 1628 sizeof(defdictobject), /* tp_basicsize */ 1629 0, /* tp_itemsize */ 1630 /* methods */ 1631 (destructor)defdict_dealloc, /* tp_dealloc */ 1632 (printfunc)defdict_print, /* tp_print */ 1633 0, /* tp_getattr */ 1634 0, /* tp_setattr */ 1635 0, /* tp_compare */ 1636 (reprfunc)defdict_repr, /* tp_repr */ 1637 0, /* tp_as_number */ 1638 0, /* tp_as_sequence */ 1639 0, /* tp_as_mapping */ 1640 0, /* tp_hash */ 1641 0, /* tp_call */ 1642 0, /* tp_str */ 1643 PyObject_GenericGetAttr, /* tp_getattro */ 1644 0, /* tp_setattro */ 1645 0, /* tp_as_buffer */ 1646 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC | 1647 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */ 1648 defdict_doc, /* tp_doc */ 1649 defdict_traverse, /* tp_traverse */ 1650 (inquiry)defdict_tp_clear, /* tp_clear */ 1651 0, /* tp_richcompare */ 1652 0, /* tp_weaklistoffset*/ 1653 0, /* tp_iter */ 1654 0, /* tp_iternext */ 1655 defdict_methods, /* tp_methods */ 1656 defdict_members, /* tp_members */ 1657 0, /* tp_getset */ 1658 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */ 1659 0, /* tp_dict */ 1660 0, /* tp_descr_get */ 1661 0, /* tp_descr_set */ 1662 0, /* tp_dictoffset */ 1663 defdict_init, /* tp_init */ 1664 PyType_GenericAlloc, /* tp_alloc */ 1665 0, /* tp_new */ 1666 PyObject_GC_Del, /* tp_free */ 1471 1667 }; 1472 1668 … … 1482 1678 init_collections(void) 1483 1679 { 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 } 1680 PyObject *m; 1681 1682 m = Py_InitModule3("_collections", NULL, module_doc); 1683 if (m == NULL) 1684 return; 1685 1686 if (PyType_Ready(&deque_type) < 0) 1687 return; 1688 Py_INCREF(&deque_type); 1689 PyModule_AddObject(m, "deque", (PyObject *)&deque_type); 1690 1691 defdict_type.tp_base = &PyDict_Type; 1692 if (PyType_Ready(&defdict_type) < 0) 1693 return; 1694 Py_INCREF(&defdict_type); 1695 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type); 1696 1697 if (PyType_Ready(&dequeiter_type) < 0) 1698 return; 1699 1700 if (PyType_Ready(&dequereviter_type) < 0) 1701 return; 1702 1703 return; 1704 }
Note:
See TracChangeset
for help on using the changeset viewer.
