# Ticket #15367: coerce_dict.pyx

File coerce_dict.pyx, 52.3 KB (added by , 9 years ago) |
---|

Line | |
---|---|

1 | #***************************************************************************** |

2 | # Copyright (C) 2007 Robert Bradshaw <robertwb@math.washington.edu> |

3 | # 2012 Simon King <simon.king@uni-jena.de> |

4 | # 2013 Nils Bruin <nbruin@sfu.ca> |

5 | # |

6 | # Distributed under the terms of the GNU General Public License (GPL) |

7 | # |

8 | # http://www.gnu.org/licenses/ |

9 | #***************************************************************************** |

10 | """ |

11 | Containers for storing coercion data |

12 | |

13 | This module provides :class:`TripleDict` and :class:`MonoDict`. These are |

14 | structures similar to :class:`~weakref.WeakKeyDictionary` in Python's weakref |

15 | module, and are optimized for lookup speed. The keys for :class:`TripleDict` |

16 | consist of triples (k1,k2,k3) and are looked up by identity rather than |

17 | equality. The keys are stored by weakrefs if possible. If any one of the |

18 | components k1, k2, k3 gets garbage collected, then the entry is removed from |

19 | the :class:`TripleDict`. |

20 | |

21 | Key components that do not allow for weakrefs are stored via a normal |

22 | refcounted reference. That means that any entry stored using a triple |

23 | (k1,k2,k3) so that none of the k1,k2,k3 allows a weak reference behaves |

24 | as an entry in a normal dictionary: Its existence in :class:`TripleDict` |

25 | prevents it from being garbage collected. |

26 | |

27 | That container currently is used to store coercion and conversion maps between |

28 | two parents (:trac:`715`) and to store homsets of pairs of objects of a |

29 | category (:trac:`11521`). In both cases, it is essential that the parent |

30 | structures remain garbage collectable, it is essential that the data access is |

31 | faster than with a usual :class:`~weakref.WeakKeyDictionary`, and we enforce |

32 | the "unique parent condition" in Sage (parent structures should be identical |

33 | if they are equal). |

34 | |

35 | :class:`MonoDict` behaves similarly, but it takes a single item as a key. It |

36 | is used for caching the parents which allow a coercion map into a fixed other |

37 | parent (:trac:`12313`). |

38 | |

39 | By :trac:`14159`, :class:`MonoDict` and :class:`TripleDict` can be optionally |

40 | used with weak references on the values. |

41 | |

42 | """ |

43 | from cpython.list cimport * |

44 | from cpython.mem cimport * |

45 | from cpython.string cimport PyString_FromString |

46 | from libc.string cimport memset |

47 | from weakref import KeyedRef |

48 | |

49 | from cpython cimport Py_XINCREF, Py_XDECREF |

50 | |

51 | cdef extern from "Python.h": |

52 | |

53 | Py_ssize_t PyInt_AsSsize_t(PyObject* io) |

54 | PyObject* PyWeakref_GetObject(object ref) |

55 | PyObject* Py_None |

56 | int PyList_SetItem(object list, Py_ssize_t index,PyObject * item) except -1 |

57 | |

58 | ctypedef int (*visitproc)(PyObject* ob, void* arg) |

59 | ctypedef struct PyTypeObject: |

60 | void * tp_traverse |

61 | void * tp_clear |

62 | |

63 | cpdef inline Py_ssize_t signed_id(x): |

64 | """ |

65 | A function like Python's :func:`id` returning *signed* integers, |

66 | which are guaranteed to fit in a ``Py_ssize_t``. |

67 | |

68 | Theoretically, there is no guarantee that two different Python |

69 | objects have different ``signed_id()`` values. However, under the |

70 | mild assumption that a C pointer fits in a ``Py_ssize_t``, this |

71 | is guaranteed. |

72 | |

73 | TESTS:: |

74 | |

75 | sage: a = 1.23e45 # some object |

76 | sage: from sage.structure.coerce_dict import signed_id |

77 | sage: s = signed_id(a) |

78 | sage: id(a) == s or id(a) == s + 2**32 or id(a) == s + 2**64 |

79 | True |

80 | sage: signed_id(a) <= sys.maxsize |

81 | True |

82 | """ |

83 | return <Py_ssize_t><void *>(x) |

84 | |

85 | #it's important that this is not an interned string: this object |

86 | #must be a unique sentinel. We could reuse the "dummy" sentinel |

87 | #that is defined in python's dictobject.c |

88 | |

89 | cdef object dummy_object = PyString_FromString("dummy") |

90 | cdef PyObject* dummy = <PyObject*><void *>dummy_object |

91 | |

92 | ############################################ |

93 | # A note about how to store "id" keys in python structures: |

94 | # |

95 | # We use the type Py_ssize_t to store "id"s generated by the signed_id |

96 | # function defined above. Assuming that Py_ssize_t is the same as a C |

97 | # long (which is true on most Unix-like systems), this also has the |

98 | # advantage that these Py_ssize_t values are stored as a Python "int" |

99 | # (as opposed to "long"), which allow for fast conversion to/from C |

100 | # types. |

101 | # |

102 | # There is one place where we have to be careful about signs: |

103 | # Our hash values most naturally live in Py_ssize_t. We convert those into |

104 | # an index into our bucket list by taking the hash modulo the number of buckets. |

105 | # However, the modulo operator in C preserves the sign of the number we take the |

106 | # modulus of, which is not what we want. |

107 | # The solution is to always do |

108 | # (<size_t> h) % modulus |

109 | # to ensure we're doing an unsigned modulus. |

110 | |

111 | cdef struct mono_cell: |

112 | void* key_id |

113 | PyObject* key_weakref |

114 | PyObject* value |

115 | |

116 | cdef object extract_mono_cell(mono_cell *cell): |

117 | #takes the refcounted components from a mono_cell |

118 | #and puts them in a list and returns it. |

119 | #The mono_cell itself is marked as "freed". |

120 | #The refcounts originally accounting for the |

121 | #presence in the mono_cell now account for the presence |

122 | #in the returned list. |

123 | # |

124 | #the returned result is only used to throw away: |

125 | #an advantage is that the containing list participates |

126 | #in CPython's trashcan, which prevents stack overflow |

127 | #on large dereffing cascades. |

128 | # |

129 | #a slight disadvantage is that this routine needs to |

130 | #allocate a list (mainly just to be thrown away) |

131 | if cell.key_id != NULL and cell.key_id != dummy : |

132 | L=PyList_New(2) |

133 | PyList_SetItem(L,0,cell.key_weakref) |

134 | PyList_SetItem(L,1,cell.value) |

135 | cell.key_id=dummy |

136 | cell.key_weakref=NULL |

137 | cell.value=NULL |

138 | return L |

139 | else: |

140 | raise RuntimeError("unused mono_cell") |

141 | |

142 | cdef struct triple_cell: |

143 | void* key_id1 |

144 | void* key_id2 |

145 | void* key_id3 |

146 | PyObject* key_weakref1 |

147 | PyObject* key_weakref2 |

148 | PyObject* key_weakref3 |

149 | PyObject* value |

150 | |

151 | cdef object extract_triple_cell(triple_cell *cell): |

152 | #see extract_mono_cell for the rationale |

153 | #behind this routine. |

154 | if cell.key_id1 != NULL and cell.key_id1 != dummy : |

155 | L=PyList_New(4) |

156 | PyList_SetItem(L,0,cell.key_weakref1) |

157 | PyList_SetItem(L,1,cell.key_weakref2) |

158 | PyList_SetItem(L,2,cell.key_weakref3) |

159 | PyList_SetItem(L,3,cell.value) |

160 | cell.key_id1=dummy |

161 | cell.key_id2=NULL |

162 | cell.key_id3=NULL |

163 | cell.key_weakref1=NULL |

164 | cell.key_weakref2=NULL |

165 | cell.key_weakref3=NULL |

166 | cell.value=NULL |

167 | return L |

168 | else: |

169 | raise RuntimeError("unused triple_cell") |

170 | |

171 | cdef class MonoDict: |

172 | """ |

173 | This is a hashtable specifically designed for (read) speed in |

174 | the coercion model. |

175 | |

176 | It differs from a python WeakKeyDictionary in the following important ways: |

177 | |

178 | - Comparison is done using the 'is' rather than '==' operator. |

179 | - Only weak references to the keys are stored if at all possible. |

180 | Keys that do not allow for weak references are stored with a normal |

181 | refcounted reference. |

182 | - The callback of the weak references is safe against recursion, see below. |

183 | |

184 | There are special cdef set/get methods for faster access. |

185 | It is bare-bones in the sense that not all dictionary methods are |

186 | implemented. |

187 | |

188 | IMPLEMENTATION: |

189 | |

190 | It is implemented as a hash table with open addressing, similar to python's |

191 | dict. |

192 | |

193 | If ki supports weak references then ri is a weak reference to ki with a |

194 | callback to remove the entry from the dictionary if ki gets garbage |

195 | collected. If ki is does not support weak references then ri is identical to ki. |

196 | In the latter case the presence of the key in the dictionary prevents it from |

197 | being garbage collected. |

198 | |

199 | INPUT: |

200 | |

201 | - ``size`` -- unused parameter, present for backward compatibility. |

202 | - ``data`` -- optional iterable defining initial data. |

203 | - ``threshold`` -- unused parameter, present for backward compatibility. |

204 | - ``weak_values`` -- optional bool (default False). If it is true, weak references |

205 | to the values in this dictionary will be used, when possible. |

206 | |

207 | EXAMPLES:: |

208 | |

209 | sage: from sage.structure.coerce_dict import MonoDict |

210 | sage: L = MonoDict(31) |

211 | sage: a = 'a'; b = 'ab'; c = -15 |

212 | sage: L[a] = 1 |

213 | sage: L[b] = 2 |

214 | sage: L[c] = 3 |

215 | |

216 | The key is expected to be a unique object. Hence, the item stored for ``c`` |

217 | can not be obtained by providing another equal number:: |

218 | |

219 | sage: L[a] |

220 | 1 |

221 | sage: L[b] |

222 | 2 |

223 | sage: L[c] |

224 | 3 |

225 | sage: L[-15] |

226 | Traceback (most recent call last): |

227 | ... |

228 | KeyError: -15 |

229 | |

230 | Not all features of Python dictionaries are available, but iteration over |

231 | the dictionary items is possible:: |

232 | |

233 | sage: # for some reason the following failed in "make ptest" |

234 | sage: # on some installations, see #12313 for details |

235 | sage: sorted(L.iteritems()) # random layout |

236 | [(-15, 3), ('a', 1), ('ab', 2)] |

237 | sage: # the following seems to be more consistent |

238 | sage: set(L.iteritems()) |

239 | set([('a', 1), ('ab', 2), (-15, 3)]) |

240 | sage: del L[c] |

241 | sage: sorted(L.iteritems()) |

242 | [('a', 1), ('ab', 2)] |

243 | sage: len(L) |

244 | 2 |

245 | sage: for i in range(1000): |

246 | ... L[i] = i |

247 | sage: len(L) |

248 | 1002 |

249 | sage: L['a'] |

250 | 1 |

251 | sage: L['c'] |

252 | Traceback (most recent call last): |

253 | ... |

254 | KeyError: 'c' |

255 | |

256 | Note that this kind of dictionary is also used for caching actions |

257 | and coerce maps. In previous versions of Sage, the cache was by |

258 | strong references and resulted in a memory leak in the following |

259 | example. However, this leak was fixed by :trac:`715`, using |

260 | weak references:: |

261 | |

262 | sage: K = GF(1<<55,'t') |

263 | sage: for i in range(50): |

264 | ... a = K.random_element() |

265 | ... E = EllipticCurve(j=a) |

266 | ... P = E.random_point() |

267 | ... Q = 2*P |

268 | sage: import gc |

269 | sage: n = gc.collect() |

270 | sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field |

271 | sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)] |

272 | sage: len(LE) # indirect doctest |

273 | 1 |

274 | |

275 | TESTS: |

276 | |

277 | Here, we demonstrate the use of weak values. |

278 | :: |

279 | |

280 | sage: M = MonoDict(13) |

281 | sage: MW = MonoDict(13, weak_values=True) |

282 | sage: class Foo: pass |

283 | sage: a = Foo() |

284 | sage: b = Foo() |

285 | sage: k = 1 |

286 | sage: M[k] = a |

287 | sage: MW[k] = b |

288 | sage: M[k] is a |

289 | True |

290 | sage: MW[k] is b |

291 | True |

292 | sage: k in M |

293 | True |

294 | sage: k in MW |

295 | True |

296 | |

297 | While ``M`` uses a strong reference to ``a``, ``MW`` uses a *weak* |

298 | reference to ``b``, and after deleting ``b``, the corresponding item of |

299 | ``MW`` will be removed during the next garbage collection:: |

300 | |

301 | sage: import gc |

302 | sage: del a,b |

303 | sage: _ = gc.collect() |

304 | sage: k in M |

305 | True |

306 | sage: k in MW |

307 | False |

308 | sage: len(MW) |

309 | 0 |

310 | sage: len(M) |

311 | 1 |

312 | |

313 | Note that ``MW`` also accepts values that do not allow for weak references:: |

314 | |

315 | sage: MW[k] = int(5) |

316 | sage: MW[k] |

317 | 5 |

318 | |

319 | The following demonstrates that :class:`MonoDict` is safer than |

320 | :class:`~weakref.WeakKeyDictionary` against recursions created by nested |

321 | callbacks; compare :trac:`15069` (the mechanism used now is different, though):: |

322 | |

323 | sage: M = MonoDict(11) |

324 | sage: class A: pass |

325 | sage: a = A() |

326 | sage: prev = a |

327 | sage: for i in range(1000): |

328 | ....: newA = A() |

329 | ....: M[prev] = newA |

330 | ....: prev = newA |

331 | sage: len(M) |

332 | 1000 |

333 | sage: del a |

334 | sage: len(M) |

335 | 0 |

336 | |

337 | The corresponding example with a Python :class:`weakref.WeakKeyDictionary` |

338 | would result in a too deep recursion during deletion of the dictionary |

339 | items:: |

340 | |

341 | sage: import weakref |

342 | sage: M = weakref.WeakKeyDictionary() |

343 | sage: a = A() |

344 | sage: prev = a |

345 | sage: for i in range(1000): |

346 | ....: newA = A() |

347 | ....: M[prev] = newA |

348 | ....: prev = newA |

349 | sage: len(M) |

350 | 1000 |

351 | sage: del a |

352 | Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <function remove at ...> ignored |

353 | sage: len(M)>0 |

354 | True |

355 | |

356 | Check that also in the presence of circular references, :class:`MonoDict` |

357 | gets properly collected:: |

358 | |

359 | sage: import gc |

360 | sage: def count_type(T): |

361 | ....: return len([c for c in gc.get_objects() if isinstance(c,T)]) |

362 | sage: _=gc.collect() |

363 | sage: N=count_type(MonoDict) |

364 | sage: for i in range(100): |

365 | ....: V = [ MonoDict(11,{"id":j+100*i}) for j in range(100)] |

366 | ....: n= len(V) |

367 | ....: for i in range(n): V[i][V[(i+1)%n]]=(i+1)%n |

368 | ....: del V |

369 | ....: _=gc.collect() |

370 | ....: assert count_type(MonoDict) == N |

371 | sage: count_type(MonoDict) == N |

372 | True |

373 | |

374 | AUTHORS: |

375 | |

376 | - Simon King (2012-01) |

377 | - Nils Bruin (2012-08) |

378 | - Simon King (2013-02) |

379 | - Nils Bruin (2013-11) |

380 | """ |

381 | cdef mono_cell* lookup(self, PyObject* key): |

382 | """ |

383 | This routine is used for all cases where a (potential) spot for |

384 | a key is looked up. The returned value is a pointer into the dictionary |

385 | store that either contains an entry with the requested key or a free spot |

386 | where an entry for that key should go. |

387 | """ |

388 | cdef size_t perturb |

389 | cdef size_t mask = self.mask |

390 | cdef mono_cell* table = self.table |

391 | cdef mono_cell* cursor |

392 | cdef mono_cell* first_freed = NULL |

393 | |

394 | #We seed our starting probe using the higher bits of the key as well. |

395 | #Our hash is a memory location, so the bottom bits are likely 0. |

396 | |

397 | cdef size_t i = ((<size_t>key)>>8+(<size_t>key)) |

398 | if key == NULL or key == dummy: |

399 | print("Request to look up invalid key") |

400 | cursor = &(table[i & mask]) |

401 | # if the cell was never used, the entry wasn't there |

402 | perturb = (<size_t>key)>>3 |

403 | |

404 | #the probing algorithm is heavily inspired by python's own dict. |

405 | #there is always at least one NULL entry in the store, and the probe |

406 | #sequence eventually covers the entire store (see python's dictobject.c), |

407 | #so the loop below does terminate. Since this loop executes only |

408 | #straightforward C, we know the table will not change. |

409 | |

410 | while (cursor.key_id != key): |

411 | if cursor.key_id == NULL: |

412 | return first_freed if (first_freed != NULL) else cursor |

413 | if first_freed == NULL and cursor.key_id == dummy: |

414 | first_freed = cursor |

415 | i = 5*i + perturb +1 |

416 | cursor = &(table[i & mask]) |

417 | perturb = perturb >> 5 |

418 | return cursor |

419 | |

420 | cdef resize(self): |

421 | """ |

422 | Resize dictionary. That can also mean shrink! Size is always a power of 2. |

423 | """ |

424 | cdef mono_cell* old_table=self.table |

425 | cdef size_t old_mask = self.mask |

426 | cdef size_t newsize = 8 |

427 | cdef size_t minsize = 2*self.used |

428 | cdef size_t i |

429 | cdef mono_cell* cursor |

430 | cdef mono_cell* entry |

431 | while newsize < minsize: |

432 | newsize = newsize<<1 |

433 | cdef mono_cell* table = <mono_cell*> PyMem_Malloc((newsize)*sizeof(mono_cell)) |

434 | if table == NULL: |

435 | raise MemoryError() |

436 | memset(table,0,(newsize)*sizeof(mono_cell)) |

437 | |

438 | #we're done with memory activity. We can move the new (empty) table into place: |

439 | |

440 | self.table = table |

441 | self.mask = newsize-1 |

442 | self.used = 0 |

443 | self.fill = 0 |

444 | |

445 | #and move all entries over. We're not changing any refcounts here, so this is a very |

446 | #tight loop that doesn't need to worry about tables changing. |

447 | |

448 | for i in range(old_mask+1): |

449 | entry = &(old_table[i]) |

450 | if entry.key_id != NULL and entry.key_id != dummy: |

451 | cursor=self.lookup(<PyObject*>(entry.key_id)) |

452 | assert cursor.key_id == NULL |

453 | cursor[0]=entry[0] |

454 | self.used +=1 |

455 | self.fill +=1 |

456 | PyMem_Free(old_table) |

457 | |

458 | def __init__(self, size=11, data=None, threshold=0.7, weak_values=False): |

459 | """ |

460 | Create a special dict using singletons for keys. |

461 | |

462 | EXAMPLES:: |

463 | |

464 | sage: from sage.structure.coerce_dict import MonoDict |

465 | sage: L = MonoDict(31) |

466 | sage: a = 'a' |

467 | sage: L[a] = 1 |

468 | sage: L[a] |

469 | 1 |

470 | sage: L = MonoDict({a: 1}) |

471 | sage: L[a] |

472 | 1 |

473 | """ |

474 | #if only one argument is supplied and it's iterable, use it for data rather than |

475 | #for size. This way we're compatible with the old calling sequence (an integer is |

476 | #just ignored) and we can also use the more usual construction. |

477 | if data is None: |

478 | try: |

479 | data=size.iteritems() |

480 | except AttributeError: |

481 | try: |

482 | data=iter(size) |

483 | except TypeError: |

484 | pass |

485 | else: |

486 | try: |

487 | data=data.iteritems() |

488 | except AttributeError: |

489 | pass |

490 | if self.table != NULL: |

491 | raise RuntimeError("table already initialized. Called __init__ second time?") |

492 | cdef minsize = 8 |

493 | cdef size_t newsize = 1<<3 |

494 | while newsize < minsize: |

495 | newsize = newsize <<1 |

496 | self.mask = newsize - 1 |

497 | cdef mono_cell* table = <mono_cell*> PyMem_Malloc(newsize*sizeof(mono_cell)) |

498 | if table == NULL: |

499 | raise MemoryError() |

500 | memset(table,0,newsize*sizeof(mono_cell)) |

501 | self.table = table |

502 | self.used = 0 |

503 | self.fill = 0 |

504 | |

505 | #our eraser is defined using a closure |

506 | def eraser(r): |

507 | cdef MonoDict cself = self |

508 | |

509 | #upon table teardown the table could be set to NULL, in which case |

510 | #erasing is not required |

511 | if cself.table == NULL: |

512 | return |

513 | |

514 | cdef mono_cell* cursor = cself.lookup(<PyObject*><Py_ssize_t>r.key) |

515 | if (cursor.key_id != NULL and cursor.key_id != dummy): |

516 | if (cursor.key_weakref == <PyObject*><void*>r or cursor.value == <PyObject*><void*>r): |

517 | L=extract_mono_cell(cursor) |

518 | self.used -= 1 |

519 | else: |

520 | #this should probably never happen |

521 | raise RuntimeError("eraser: key match but no weakref match") |

522 | else: |

523 | #this is conceivable, but I haven't seen it happen. |

524 | #raise RuntimeError("eraser: no key match") |

525 | pass |

526 | self.eraser = eraser |

527 | self.weak_values = weak_values |

528 | if data: |

529 | for k,v in data: |

530 | self.set(k,v) |

531 | |

532 | def __dealloc__(self): |

533 | """ |

534 | Ensure that the memory allocated by a MonoDict is properly freed. |

535 | """ |

536 | #is this required or does this get called anyway if we set tp_clear properly? |

537 | #at least it's safe, since MonoDict_clear check if it has already run. |

538 | MonoDict_clear(self) |

539 | |

540 | def __len__(self): |

541 | """ |

542 | The number of items in self. |

543 | EXAMPLES:: |

544 | |

545 | sage: from sage.structure.coerce_dict import MonoDict |

546 | sage: L = MonoDict(37) |

547 | sage: a = 'a'; b = 'b'; c = 'c' |

548 | sage: L[a] = 1 |

549 | sage: L[a] = -1 # re-assign |

550 | sage: L[b] = 1 |

551 | sage: L[c] = None |

552 | sage: len(L) |

553 | 3 |

554 | """ |

555 | return self.used |

556 | |

557 | def __contains__(self, k): |

558 | """ |

559 | Test if the dictionary contains a given key. |

560 | |

561 | EXAMPLES:: |

562 | |

563 | sage: from sage.structure.coerce_dict import MonoDict |

564 | sage: L = MonoDict(31) |

565 | sage: a = 'a'; b = 'ab'; c = 15 |

566 | sage: L[a] = 1 |

567 | sage: L[b] = 2 |

568 | sage: L[c] = 3 |

569 | sage: c in L # indirect doctest |

570 | True |

571 | |

572 | The keys are compared by identity, not by equality. Hence, we have:: |

573 | |

574 | sage: c == 15 |

575 | True |

576 | sage: 15 in L |

577 | False |

578 | """ |

579 | cdef mono_cell* cursor = self.lookup(<PyObject*><void*>k) |

580 | if cursor.key_id == NULL or cursor.key_id == dummy: |

581 | return False |

582 | r = <object>cursor.key_weakref |

583 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

584 | return False |

585 | elif not(self.weak_values): |

586 | return True |

587 | else: |

588 | value = <object>cursor.value |

589 | return (not isinstance(value,KeyedRef)) or PyWeakref_GetObject(value) != Py_None |

590 | |

591 | def __getitem__(self, k): |

592 | """ |

593 | Get the value corresponding to a key. |

594 | |

595 | EXAMPLES:: |

596 | |

597 | sage: from sage.structure.coerce_dict import MonoDict |

598 | sage: L = MonoDict(31) |

599 | sage: a = 'a'; b = 'b'; c = 15 |

600 | sage: L[a] = 1 |

601 | sage: L[b] = 2 |

602 | sage: L[c] = 3 |

603 | sage: L[c] # indirect doctest |

604 | 3 |

605 | |

606 | Note that the keys are supposed to be unique:: |

607 | |

608 | sage: c==15 |

609 | True |

610 | sage: c is 15 |

611 | False |

612 | sage: L[15] |

613 | Traceback (most recent call last): |

614 | ... |

615 | KeyError: 15 |

616 | """ |

617 | return self.get(k) |

618 | |

619 | cdef get(self, object k): |

620 | cdef mono_cell* cursor = self.lookup(<PyObject*><void *>k) |

621 | if cursor.key_id == NULL or cursor.key_id == dummy: |

622 | raise KeyError, k |

623 | r = <object>cursor.key_weakref |

624 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

625 | raise KeyError, k |

626 | value = <object>cursor.value |

627 | if self.weak_values and isinstance(value,KeyedRef): |

628 | value = <object>PyWeakref_GetObject(value) |

629 | if value is None: |

630 | raise KeyError, k |

631 | return value |

632 | |

633 | def __setitem__(self, k, value): |

634 | """ |

635 | Set the value corresponding to a key. |

636 | |

637 | EXAMPLES:: |

638 | |

639 | sage: from sage.structure.coerce_dict import MonoDict |

640 | sage: L = MonoDict(31) |

641 | sage: a = 'a' |

642 | sage: L[a] = -1 # indirect doctest |

643 | sage: L[a] |

644 | -1 |

645 | sage: L[a] = 1 |

646 | sage: L[a] |

647 | 1 |

648 | sage: len(L) |

649 | 1 |

650 | """ |

651 | self.set(k,value) |

652 | |

653 | cdef set(self,object k, object value): |

654 | cdef mono_cell entry |

655 | cdef PyObject* old_value = NULL |

656 | cdef bint maybe_resize = False |

657 | entry.key_id = <void*>k |

658 | if self.weak_values: |

659 | try: |

660 | value_store = KeyedRef(value,self.eraser,<Py_ssize_t><void *>(k)) |

661 | entry.value = <PyObject*><void*>value_store |

662 | except TypeError: |

663 | entry.value = <PyObject*><void*>value |

664 | else: |

665 | entry.value = <PyObject*><void*>value |

666 | Py_XINCREF(entry.value) |

667 | cursor = self.lookup(<PyObject*><void*>k) |

668 | if cursor.key_id == NULL or cursor.key_id == dummy: |

669 | self.used += 1 |

670 | if cursor.key_id == NULL: |

671 | self.fill += 1 |

672 | maybe_resize = True |

673 | try: |

674 | key_store=KeyedRef(k,self.eraser,<Py_ssize_t><void *>(k)) |

675 | entry.key_weakref = <PyObject*><void*>key_store |

676 | except TypeError: |

677 | entry.key_weakref = <PyObject*><void*>k |

678 | Py_XINCREF(entry.key_weakref) |

679 | |

680 | #we're taking a bit of a gamble here: we're assuming the dictionary has |

681 | #not been resized (otherwise cursor might not be a valid location |

682 | #anymore). The only way in which that could happen is if the allocation |

683 | #activity above forced a GC that triggered code that ADDS entries to this |

684 | #dictionary: the dictionary can only get reshaped if self.fill increases. |

685 | #(as happens below). Note that we're holding a strong ref to the dict |

686 | #itself, so that's not liable to disappear. |

687 | #for the truly paranoid: we could detect a change by checking if self.table |

688 | #has changed value |

689 | cursor[0] = entry |

690 | |

691 | #this is the one place where resize gets called: |

692 | if maybe_resize and 3*self.fill > 2*self.mask: self.resize() |

693 | else: |

694 | old_value = cursor.value |

695 | cursor.value = entry.value |

696 | Py_XDECREF(old_value) |

697 | |

698 | def __delitem__(self, k): |

699 | """ |

700 | Delete the value corresponding to a key. |

701 | |

702 | EXAMPLES:: |

703 | |

704 | sage: from sage.structure.coerce_dict import MonoDict |

705 | sage: L = MonoDict(31) |

706 | sage: a = 15 |

707 | sage: L[a] = -1 |

708 | sage: len(L) |

709 | 1 |

710 | |

711 | Note that the keys are unique, hence using a key that is equal but not |

712 | identical to a results in an error:: |

713 | |

714 | sage: del L[15] |

715 | Traceback (most recent call last): |

716 | ... |

717 | KeyError: 15 |

718 | sage: a in L |

719 | True |

720 | sage: del L[a] |

721 | sage: len(L) |

722 | 0 |

723 | sage: a in L |

724 | False |

725 | """ |

726 | cdef mono_cell* cursor = self.lookup(<PyObject *><void *>k) |

727 | if cursor.key_id == NULL or cursor.key_id==dummy: |

728 | raise KeyError, k |

729 | L=extract_mono_cell(cursor) |

730 | self.used -= 1 |

731 | |

732 | def iteritems(self): |

733 | """ |

734 | EXAMPLES:: |

735 | |

736 | sage: from sage.structure.coerce_dict import MonoDict |

737 | sage: L = MonoDict(31) |

738 | sage: L[1] = None |

739 | sage: L[2] = True |

740 | sage: list(sorted(L.iteritems())) |

741 | [(1, None), (2, True)] |

742 | """ |

743 | #iteration is tricky because the table could change from under us. |

744 | #the following iterates properly if the dictionary does not |

745 | #get "resize"d, which is guaranteed if no NEW entries in the |

746 | #dictionary are introduced. At least we make sure to get our data fresh |

747 | #from "self" every iteration, so that at least we're not reading random memory |

748 | #(if the dictionary changes, it's not guaranteed you get to see any particular entry) |

749 | cdef size_t i = 0 |

750 | while i <= self.mask: |

751 | cursor = &(self.table[i]) |

752 | i += 1 |

753 | if cursor.key_id != NULL and cursor.key_id != dummy: |

754 | key = <object>(cursor.key_weakref) |

755 | value = <object>(cursor.value) |

756 | if isinstance(key,KeyedRef): |

757 | key = <object>PyWeakref_GetObject(key) |

758 | if key is None: |

759 | print "found defunct key" |

760 | continue |

761 | if self.weak_values and isinstance(value,KeyedRef): |

762 | value = <object>PyWeakref_GetObject(value) |

763 | if value is None: |

764 | print "found defunct value" |

765 | continue |

766 | yield (key, value) |

767 | |

768 | def pr(self): |

769 | cdef size_t i = 0 |

770 | print "weak_values:",self.weak_values |

771 | print "used:",self.used |

772 | print "fill:",self.fill |

773 | print "mask:",self.mask |

774 | while i <= self.mask: |

775 | cursor = &(self.table[i]) |

776 | i+=1 |

777 | if cursor.key_id == NULL: |

778 | s0 = "-NUL-" |

779 | elif cursor.key_id == dummy: |

780 | s0 = "dummy" |

781 | else: |

782 | s0 = str(<long>cursor.key_id) |

783 | s1 = "NULL" if (cursor.key_weakref == NULL) else (str(<object>cursor.key_weakref)) |

784 | s2 = "NULL" if (cursor.value == NULL) else (str(<object>cursor.value)) |

785 | print "%s %s %s %s"%(i,s0,s1,s2) |

786 | |

787 | def __reduce__(self): |

788 | """ |

789 | Note that we don't expect equality as this class concerns itself with |

790 | object identity rather than object equality. |

791 | |

792 | EXAMPLES:: |

793 | |

794 | sage: from sage.structure.coerce_dict import MonoDict |

795 | sage: L = MonoDict(31) |

796 | sage: L[1] = True |

797 | sage: loads(dumps(L)) == L |

798 | False |

799 | sage: list(loads(dumps(L)).iteritems()) |

800 | [(1, True)] |

801 | """ |

802 | return MonoDict, (11, dict(self.iteritems()), 0.7) |

803 | |

804 | #the cython supplied tp_traverse and tp_clear do not take the dynamically |

805 | #allocated table into account, so we have to supply our own. |

806 | #the only additional link to follow (that cython does pick up and we have |

807 | #to replicate here) is the "eraser" which in its closure stores a reference |

808 | #back to the dictionary itself (meaning that MonoDicts only disappear |

809 | #on cyclic GC) |

810 | |

811 | cdef int MonoDict_traverse(MonoDict op, visitproc visit, void *arg): |

812 | cdef int r |

813 | if op.table == NULL: |

814 | return 0 |

815 | table=op.table |

816 | cdef size_t i = 0 |

817 | if (<void*>(op.eraser)): |

818 | r=visit(<PyObject*><void*>(op.eraser),arg) |

819 | if r: return r |

820 | for i in range(op.mask+1): |

821 | cursor = &table[i] |

822 | if cursor.key_id != NULL and cursor.key_id != dummy: |

823 | r=visit(cursor.key_weakref,arg) |

824 | if r: return r |

825 | r=visit(cursor.value,arg) |

826 | if r: return r |

827 | return 0 |

828 | |

829 | |

830 | #we clear a monodict by taking first taking away the table before dereffing |

831 | #its contents. That shortcuts callbacks, so we deref the entries straight here. |

832 | #that means this code does not participate in Python's trashcan the way that |

833 | #deletion code based on extract_mono_cell does, so there is probably a way |

834 | #this code can be used to overflow the C stack. It would have to be a pretty |

835 | #devious example, though. |

836 | cdef int MonoDict_clear(MonoDict op): |

837 | if op.table == NULL: |

838 | return 0 |

839 | |

840 | tmp=op.eraser |

841 | cdef mono_cell* table=op.table |

842 | cdef size_t mask=op.mask |

843 | op.table=NULL |

844 | |

845 | op.eraser=None |

846 | op.mask=0 |

847 | op.used=0 |

848 | op.fill=0 |

849 | |

850 | #this deletion method incurs an extra refcount +-, but it seems very difficult in cython to do it |

851 | #any other way and still be sure that the reference op.eraser is gone by the time the object gets |

852 | #deallocated. |

853 | del tmp |

854 | for i in range(mask+1): |

855 | cursor = &(table[i]) |

856 | if cursor.key_id != NULL and cursor.key_id != dummy: |

857 | cursor.key_id = dummy |

858 | Py_XDECREF(cursor.key_weakref) |

859 | Py_XDECREF(cursor.value) |

860 | PyMem_Free(table) |

861 | return 0 |

862 | |

863 | (<PyTypeObject *><void *>MonoDict).tp_traverse = &MonoDict_traverse |

864 | (<PyTypeObject *><void *>MonoDict).tp_clear = &MonoDict_clear |

865 | |

866 | cdef class TripleDict: |

867 | """ |

868 | This is a hashtable specifically designed for (read) speed in |

869 | the coercion model. |

870 | |

871 | It differs from a python dict in the following important ways: |

872 | |

873 | - All keys must be sequence of exactly three elements. All sequence |

874 | types (tuple, list, etc.) map to the same item. |

875 | - Comparison is done using the 'is' rather than '==' operator. |

876 | |

877 | There are special cdef set/get methods for faster access. |

878 | It is bare-bones in the sense that not all dictionary methods are |

879 | implemented. |

880 | |

881 | It is implemented as a list of lists (hereafter called buckets). The bucket is |

882 | chosen according to a very simple hash based on the object pointer, and each |

883 | bucket is of the form [id(k1), id(k2), id(k3), r1, r2, r3, value, id(k1), |

884 | id(k2), id(k3), r1, r2, r3, value, ...], on which a linear search is performed. |

885 | If a key component ki supports weak references then ri is a weak reference to |

886 | ki; otherwise ri is identical to ki. |

887 | |

888 | INPUT: |

889 | |

890 | - ``size`` -- an integer, the initial number of buckets. To spread objects |

891 | evenly, the size should ideally be a prime, and certainly not divisible |

892 | by 2. |

893 | - ``data`` -- optional iterable defining initial data. |

894 | - ``threshold`` -- optional number, default `0.7`. It determines how frequently |

895 | the dictionary will be resized (large threshold implies rare resizing). |

896 | - ``weak_values`` -- optional bool (default False). If it is true, weak references |

897 | to the values in this dictionary will be used, when possible. |

898 | |

899 | If any of the key components k1,k2,k3 (this can happen for a key component |

900 | that supports weak references) gets garbage collected then the entire |

901 | entry disappears. In that sense this structure behaves like a nested |

902 | :class:`~weakref.WeakKeyDictionary`. |

903 | |

904 | EXAMPLES:: |

905 | |

906 | sage: from sage.structure.coerce_dict import TripleDict |

907 | sage: L = TripleDict(31) |

908 | sage: a = 'a'; b = 'b'; c = 'c' |

909 | sage: L[a,b,c] = 1 |

910 | sage: L[a,b,c] |

911 | 1 |

912 | sage: L[c,b,a] = -1 |

913 | sage: list(L.iteritems()) # random order of output. |

914 | [(('c', 'b', 'a'), -1), (('a', 'b', 'c'), 1)] |

915 | sage: del L[a,b,c] |

916 | sage: list(L.iteritems()) |

917 | [(('c', 'b', 'a'), -1)] |

918 | sage: len(L) |

919 | 1 |

920 | sage: for i in range(1000): |

921 | ... L[i,i,i] = i |

922 | sage: len(L) |

923 | 1001 |

924 | sage: L = TripleDict(101, L) |

925 | sage: L = TripleDict(3, L) |

926 | sage: L[c,b,a] |

927 | -1 |

928 | sage: L[a,b,c] |

929 | Traceback (most recent call last): |

930 | ... |

931 | KeyError: ('a', 'b', 'c') |

932 | sage: L[a] |

933 | Traceback (most recent call last): |

934 | ... |

935 | KeyError: 'a' |

936 | sage: L[a] = 1 |

937 | Traceback (most recent call last): |

938 | ... |

939 | KeyError: 'a' |

940 | |

941 | The following illustrates why even sizes are bad (setting the threshold |

942 | zero, so that no beneficial resizing happens):: |

943 | |

944 | sage: L = TripleDict(4, L, threshold=0) |

945 | |

946 | Note that this kind of dictionary is also used for caching actions |

947 | and coerce maps. In previous versions of Sage, the cache was by |

948 | strong references and resulted in a memory leak in the following |

949 | example. However, this leak was fixed by :trac:`715`, using weak |

950 | references:: |

951 | |

952 | sage: K = GF(1<<55,'t') |

953 | sage: for i in range(50): |

954 | ... a = K.random_element() |

955 | ... E = EllipticCurve(j=a) |

956 | ... P = E.random_point() |

957 | ... Q = 2*P |

958 | sage: import gc |

959 | sage: n = gc.collect() |

960 | sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field |

961 | sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)] |

962 | sage: len(LE) # indirect doctest |

963 | 1 |

964 | |

965 | TESTS: |

966 | |

967 | Here, we demonstrate the use of weak values. |

968 | :: |

969 | |

970 | sage: class Foo: pass |

971 | sage: T = TripleDict(13) |

972 | sage: TW = TripleDict(13, weak_values=True) |

973 | sage: a = Foo() |

974 | sage: b = Foo() |

975 | sage: k = 1 |

976 | sage: T[a,k,k]=1 |

977 | sage: T[k,a,k]=2 |

978 | sage: T[k,k,a]=3 |

979 | sage: T[k,k,k]=a |

980 | sage: TW[b,k,k]=1 |

981 | sage: TW[k,b,k]=2 |

982 | sage: TW[k,k,b]=3 |

983 | sage: TW[k,k,k]=b |

984 | sage: len(T) |

985 | 4 |

986 | sage: len(TW) |

987 | 4 |

988 | sage: (k,k,k) in T |

989 | True |

990 | sage: (k,k,k) in TW |

991 | True |

992 | sage: T[k,k,k] is a |

993 | True |

994 | sage: TW[k,k,k] is b |

995 | True |

996 | |

997 | Now, ``T`` holds a strong reference to ``a``, namely in ``T[k,k,k]``. Hence, |

998 | when we delete ``a``, *all* items of ``T`` survive:: |

999 | |

1000 | sage: del a |

1001 | sage: _ = gc.collect() |

1002 | sage: len(T) |

1003 | 4 |

1004 | |

1005 | Only when we remove the strong reference, the items become collectable:: |

1006 | |

1007 | sage: del T[k,k,k] |

1008 | sage: _ = gc.collect() |

1009 | sage: len(T) |

1010 | 0 |

1011 | |

1012 | The situation is different for ``TW``, since it only holds *weak* |

1013 | references to ``a``. Therefore, all items become collectable after |

1014 | deleting ``a``:: |

1015 | |

1016 | sage: del b |

1017 | sage: _ = gc.collect() |

1018 | sage: len(TW) |

1019 | 0 |

1020 | |

1021 | .. NOTE:: |

1022 | |

1023 | The index `h` corresponding to the key [k1, k2, k3] is computed as a |

1024 | value of unsigned type size_t as follows: |

1025 | |

1026 | .. MATH:: |

1027 | |

1028 | h = id(k1) + 13*id(k2) xor 503 id(k3) |

1029 | |

1030 | The natural type for this quantity is Py_ssize_t, which is a signed |

1031 | quantity with the same length as size_t. Storing it in a signed way gives the most |

1032 | efficient storage into PyInt, while preserving sign information. |

1033 | |

1034 | As usual for a hashtable, we take h modulo some integer to obtain the bucket |

1035 | number into which to store the key/value pair. A problem here is that C mandates |

1036 | sign-preservation for the modulo operator "%". We cast to an unsigned type, i.e., |

1037 | (<size_t> h)% N |

1038 | If we don't do this we may end up indexing lists with negative indices, which may lead to |

1039 | segfaults if using the non-error-checking python macros, as happens here. |

1040 | |

1041 | This has been observed on 32 bits systems, see :trac:`715` for details. |

1042 | |

1043 | AUTHORS: |

1044 | |

1045 | - Robert Bradshaw, 2007-08 |

1046 | |

1047 | - Simon King, 2012-01 |

1048 | |

1049 | - Nils Bruin, 2012-08 |

1050 | |

1051 | - Simon King, 2013-02 |

1052 | |

1053 | - Nils Bruin, 2013-11 |

1054 | """ |

1055 | cdef triple_cell* lookup(self, PyObject* key1, PyObject* key2, PyObject* key3): |

1056 | #returns a pointer to where key should be stored in this dictionary. |

1057 | cdef size_t perturb |

1058 | cdef size_t mask = self.mask |

1059 | cdef triple_cell* table = self.table |

1060 | cdef triple_cell* cursor |

1061 | cdef triple_cell* first_freed = NULL |

1062 | #we device some hash that reasonably depends on bits of all keys |

1063 | #making sure it's not commutative and also involves some of the higher order |

1064 | #bits at an early stage. |

1065 | cdef size_t key = <size_t>key1 + (<size_t>key2)<<2 + (<size_t>key3)<<4 |

1066 | cdef size_t i = key>>8 + key |

1067 | cursor = &(table[i & mask]) |

1068 | perturb = (key)>>3 |

1069 | while (cursor.key_id1 != key1 or cursor.key_id2 != key2 or cursor.key_id3 != key3): |

1070 | if cursor.key_id1 == NULL: |

1071 | return first_freed if (first_freed != NULL) else cursor |

1072 | if first_freed == NULL and cursor.key_id1 == dummy: |

1073 | first_freed = cursor |

1074 | i = 5*i + perturb +1 |

1075 | cursor = &(table[i & mask]) |

1076 | perturb = perturb >> 5 |

1077 | return cursor |

1078 | |

1079 | cdef resize(self): |

1080 | cdef triple_cell* old_table=self.table |

1081 | cdef size_t old_mask = self.mask |

1082 | cdef size_t newsize = 8 |

1083 | cdef size_t minsize = 2*self.used |

1084 | cdef size_t i |

1085 | cdef triple_cell* cursor |

1086 | cdef triple_cell* entry |

1087 | while newsize < minsize: |

1088 | newsize = newsize<<1 |

1089 | cdef triple_cell* table = <triple_cell*> PyMem_Malloc((newsize)*sizeof(triple_cell)) |

1090 | if table == NULL: |

1091 | raise MemoryError() |

1092 | memset(table,0,(newsize)*sizeof(triple_cell)) |

1093 | self.table = table |

1094 | self.mask = newsize-1 |

1095 | self.used = 0 |

1096 | self.fill = 0 |

1097 | for i in range(old_mask+1): |

1098 | entry = &(old_table[i]) |

1099 | if entry.key_id1 != NULL and entry.key_id1 != dummy: |

1100 | cursor=self.lookup(<PyObject*>(entry.key_id1),<PyObject*>(entry.key_id2),<PyObject*>(entry.key_id3)) |

1101 | assert cursor.key_id1 == NULL |

1102 | cursor[0]=entry[0] |

1103 | self.used +=1 |

1104 | self.fill +=1 |

1105 | PyMem_Free(old_table) |

1106 | |

1107 | def __init__(self, size=11, data=None, threshold=0.7, weak_values=False): |

1108 | """ |

1109 | Create a special dict using triples for keys. |

1110 | |

1111 | EXAMPLES:: |

1112 | |

1113 | sage: from sage.structure.coerce_dict import TripleDict |

1114 | sage: L = TripleDict(31) |

1115 | sage: a = 'a'; b = 'b'; c = 'c' |

1116 | sage: L[a,b,c] = 1 |

1117 | sage: L[a,b,c] |

1118 | 1 |

1119 | """ |

1120 | #if only one argument is supplied and it's iterable, use it for data rather than |

1121 | #for size |

1122 | if data is None: |

1123 | try: |

1124 | data=size.iteritems() |

1125 | except AttributeError: |

1126 | try: |

1127 | data=iter(size) |

1128 | except TypeError: |

1129 | pass |

1130 | else: |

1131 | try: |

1132 | data=data.iteritems() |

1133 | except AttributeError: |

1134 | pass |

1135 | if self.table != NULL: |

1136 | raise RuntimeError("table already initialized. Called __init__ second time?") |

1137 | cdef minsize = 8 |

1138 | cdef size_t newsize = 1<<3 |

1139 | while newsize < minsize: |

1140 | newsize = newsize <<1 |

1141 | self.mask = newsize - 1 |

1142 | cdef triple_cell* table = <triple_cell*> PyMem_Malloc(newsize*sizeof(triple_cell)) |

1143 | if table == NULL: |

1144 | raise MemoryError() |

1145 | memset(table,0,newsize*sizeof(triple_cell)) |

1146 | self.table = table |

1147 | self.used = 0 |

1148 | self.fill = 0 |

1149 | |

1150 | def eraser(r): |

1151 | cdef TripleDict cself = self |

1152 | if cself.table == NULL: |

1153 | return |

1154 | |

1155 | k1,k2,k3 = r.key |

1156 | cdef triple_cell* cursor = cself.lookup(<PyObject*><Py_ssize_t>k1,<PyObject*><Py_ssize_t>k2,<PyObject*><Py_ssize_t>k3) |

1157 | if (cursor.key_id1 != NULL and cursor.key_id1 != dummy): |

1158 | if (cursor.key_weakref1 == <PyObject*><void*>r or |

1159 | cursor.key_weakref2 == <PyObject*><void*>r or |

1160 | cursor.key_weakref3 == <PyObject*><void*>r or |

1161 | cursor.value == <PyObject*><void*>r): |

1162 | L=extract_triple_cell(cursor) |

1163 | self.used -= 1 |

1164 | else: |

1165 | raise RuntimeError("eraser: key match but no weakref match") |

1166 | else: |

1167 | #raise RuntimeError("eraser: no key match") |

1168 | pass |

1169 | self.eraser = eraser |

1170 | self.weak_values = weak_values |

1171 | if data: |

1172 | for k,v in data: |

1173 | self[k]=v |

1174 | |

1175 | def __dealloc__(self): |

1176 | #is this required? (TripleDict_clear is safe to call multiple times) |

1177 | TripleDict_clear(self) |

1178 | |

1179 | def __len__(self): |

1180 | """ |

1181 | The number of items in self. |

1182 | |

1183 | EXAMPLES:: |

1184 | |

1185 | sage: from sage.structure.coerce_dict import TripleDict |

1186 | sage: L = TripleDict(37) |

1187 | sage: a = 'a'; b = 'b'; c = 'c' |

1188 | sage: L[a,b,c] = 1 |

1189 | sage: L[a,b,c] = -1 # re-assign |

1190 | sage: L[a,c,b] = 1 |

1191 | sage: L[a,a,None] = None |

1192 | sage: len(L) |

1193 | 3 |

1194 | """ |

1195 | return self.used |

1196 | |

1197 | def __contains__(self, k): |

1198 | """ |

1199 | Test if the dictionary contains a given key. |

1200 | |

1201 | EXAMPLES:: |

1202 | |

1203 | sage: from sage.structure.coerce_dict import TripleDict |

1204 | sage: L = TripleDict(31) |

1205 | sage: a = 'a'; b = 'ab'; c = 15 |

1206 | sage: L[a,b,c] = 123 |

1207 | sage: (a,b,c) in L # indirect doctest |

1208 | True |

1209 | |

1210 | The keys are compared by identity, not by equality. Hence, we have:: |

1211 | |

1212 | sage: c == 15 |

1213 | True |

1214 | sage: (a,b,15) in L |

1215 | False |

1216 | """ |

1217 | cdef object k1,k2,k3 |

1218 | try: |

1219 | k1, k2, k3 = k |

1220 | except (TypeError,ValueError): |

1221 | raise KeyError, k |

1222 | cdef triple_cell* cursor = self.lookup(<PyObject*><void*>k1,<PyObject*><void*>k2,<PyObject*><void*>k3) |

1223 | if cursor.key_id1 == NULL or cursor.key_id1 == dummy: |

1224 | return False |

1225 | r = <object>cursor.key_weakref1 |

1226 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1227 | return False |

1228 | r = <object>cursor.key_weakref2 |

1229 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1230 | return False |

1231 | r = <object>cursor.key_weakref3 |

1232 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1233 | return False |

1234 | if not(self.weak_values): |

1235 | return True |

1236 | value = <object>cursor.value |

1237 | return (not isinstance(value,KeyedRef)) or PyWeakref_GetObject(value) != Py_None |

1238 | |

1239 | def __getitem__(self, k): |

1240 | """ |

1241 | Get the value corresponding to a key. |

1242 | |

1243 | EXAMPLES:: |

1244 | |

1245 | sage: from sage.structure.coerce_dict import TripleDict |

1246 | sage: L = TripleDict(31) |

1247 | sage: a = 'a'; b = 'b'; c = 'c' |

1248 | sage: L[a,b,c] = 1 |

1249 | sage: L[a,b,c] |

1250 | 1 |

1251 | """ |

1252 | cdef object k1,k2,k3 |

1253 | try: |

1254 | k1, k2, k3 = k |

1255 | except (TypeError,ValueError): |

1256 | raise KeyError, k |

1257 | return self.get(k1, k2, k3) |

1258 | |

1259 | cdef get(self, object k1, object k2, object k3): |

1260 | cdef triple_cell* cursor = self.lookup(<PyObject*><void *>k1,<PyObject*><void *>k2,<PyObject*><void *>k3) |

1261 | if cursor.key_id1 == NULL or cursor.key_id1 == dummy: |

1262 | raise KeyError, (k1, k2, k3) |

1263 | r = <object>cursor.key_weakref1 |

1264 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1265 | raise KeyError, (k1, k2, k3) |

1266 | r = <object>cursor.key_weakref2 |

1267 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1268 | raise KeyError, (k1, k2, k3) |

1269 | r = <object>cursor.key_weakref3 |

1270 | if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None: |

1271 | raise KeyError, (k1, k2, k3) |

1272 | value = <object>cursor.value |

1273 | if self.weak_values and isinstance(value,KeyedRef): |

1274 | value = <object>PyWeakref_GetObject(value) |

1275 | if value is None: |

1276 | raise KeyError, (k1, k2, k3) |

1277 | return value |

1278 | |

1279 | def __setitem__(self, k, value): |

1280 | """ |

1281 | Set the value corresponding to a key. |

1282 | |

1283 | EXAMPLES:: |

1284 | |

1285 | sage: from sage.structure.coerce_dict import TripleDict |

1286 | sage: L = TripleDict(31) |

1287 | sage: a = 'a'; b = 'b'; c = 'c' |

1288 | sage: L[a,b,c] = -1 |

1289 | sage: L[a,b,c] |

1290 | -1 |

1291 | """ |

1292 | cdef object k1,k2,k3 |

1293 | try: |

1294 | k1, k2, k3 = k |

1295 | except (TypeError,ValueError): |

1296 | raise KeyError, k |

1297 | self.set(k1, k2, k3, value) |

1298 | |

1299 | cdef set(self, object k1, object k2, object k3, value): |

1300 | cdef triple_cell entry |

1301 | cdef PyObject* old_value = NULL |

1302 | cdef bint maybe_resize = False |

1303 | entry.key_id1 = <void*>k1 |

1304 | entry.key_id2 = <void*>k2 |

1305 | entry.key_id3 = <void*>k3 |

1306 | k = (<Py_ssize_t><void *>(k1),<Py_ssize_t><void *>(k2),<Py_ssize_t><void *>(k3)) |

1307 | if self.weak_values: |

1308 | try: |

1309 | value_store = KeyedRef(value,self.eraser,k) |

1310 | entry.value = <PyObject*><void*>value_store |

1311 | except TypeError: |

1312 | entry.value = <PyObject*><void*>value |

1313 | else: |

1314 | entry.value = <PyObject*><void*>value |

1315 | Py_XINCREF(entry.value) |

1316 | cursor = self.lookup(<PyObject*><void*>k1,<PyObject*><void*>k2,<PyObject*><void*>k3) |

1317 | if cursor.key_id1 == NULL or cursor.key_id1 == dummy: |

1318 | self.used += 1 |

1319 | if cursor.key_id1 == NULL: |

1320 | self.fill += 1 |

1321 | maybe_resize = True |

1322 | try: |

1323 | key_store=KeyedRef(k1,self.eraser,k) |

1324 | entry.key_weakref1 = <PyObject*><void*>key_store |

1325 | except TypeError: |

1326 | entry.key_weakref1 = <PyObject*><void*>k1 |

1327 | Py_XINCREF(entry.key_weakref1) |

1328 | try: |

1329 | key_store=KeyedRef(k2,self.eraser,k) |

1330 | entry.key_weakref2 = <PyObject*><void*>key_store |

1331 | except TypeError: |

1332 | entry.key_weakref2 = <PyObject*><void*>k2 |

1333 | Py_XINCREF(entry.key_weakref2) |

1334 | try: |

1335 | key_store=KeyedRef(k3,self.eraser,k) |

1336 | entry.key_weakref3 = <PyObject*><void*>key_store |

1337 | except TypeError: |

1338 | entry.key_weakref3 = <PyObject*><void*>k3 |

1339 | Py_XINCREF(entry.key_weakref3) |

1340 | |

1341 | #we're taking a bit of a gamble here: we're assuming the dictionary has |

1342 | #not been resized (otherwise cursor might not be a valid location |

1343 | #anymore). The only way in which that could happen is if the allocation |

1344 | #activity above forced a GC that triggered code that ADDS entries to this |

1345 | #dictionary: the dictionary can only get reshaped if self.fill increases. |

1346 | #(as happens below). Note that we're holding a strong ref to the dict |

1347 | #itself, so that's not liable to disappear. |

1348 | #for the truly paranoid: we could detect a change by checking if self.table |

1349 | #has changed value |

1350 | cursor[0] = entry |

1351 | |

1352 | #this is the only place where resize gets called: |

1353 | if maybe_resize and 3*self.fill > 2*self.mask: self.resize() |

1354 | else: |

1355 | old_value = cursor.value |

1356 | cursor.value = entry.value |

1357 | Py_XDECREF(old_value) |

1358 | |

1359 | def __delitem__(self, k): |

1360 | """ |

1361 | Delete the value corresponding to a key. |

1362 | |

1363 | EXAMPLES:: |

1364 | |

1365 | sage: from sage.structure.coerce_dict import TripleDict |

1366 | sage: L = TripleDict(31) |

1367 | sage: a = 'a'; b = 'b'; c = 'c' |

1368 | sage: L[a,b,c] = -1 |

1369 | sage: (a,b,c) in L |

1370 | True |

1371 | sage: del L[a,b,c] |

1372 | sage: len(L) |

1373 | 0 |

1374 | sage: (a,b,c) in L |

1375 | False |

1376 | """ |

1377 | cdef object k1,k2,k3 |

1378 | try: |

1379 | k1, k2, k3 = k |

1380 | except (TypeError,ValueError): |

1381 | raise KeyError, k |

1382 | cdef triple_cell* cursor = self.lookup(<PyObject *><void *>k1,<PyObject *><void *>k2,<PyObject *><void *>k3) |

1383 | if cursor.key_id1 == NULL or cursor.key_id1==dummy: |

1384 | raise KeyError, k |

1385 | L=extract_triple_cell(cursor) |

1386 | self.used -= 1 |

1387 | |

1388 | def iteritems(self): |

1389 | """ |

1390 | EXAMPLES:: |

1391 | |

1392 | sage: from sage.structure.coerce_dict import TripleDict |

1393 | sage: L = TripleDict(31) |

1394 | sage: L[1,2,3] = None |

1395 | sage: list(L.iteritems()) |

1396 | [((1, 2, 3), None)] |

1397 | """ |

1398 | |

1399 | cdef size_t i = 0 |

1400 | while i <= self.mask: |

1401 | cursor = &(self.table[i]) |

1402 | i += 1 |

1403 | if cursor.key_id1 != NULL and cursor.key_id1 != dummy: |

1404 | key1 = <object>(cursor.key_weakref1) |

1405 | key2 = <object>(cursor.key_weakref2) |

1406 | key3 = <object>(cursor.key_weakref3) |

1407 | value = <object>(cursor.value) |

1408 | if isinstance(key1,KeyedRef): |

1409 | key1 = <object>PyWeakref_GetObject(key1) |

1410 | if key1 is None: |

1411 | print "found defunct key1" |

1412 | continue |

1413 | if isinstance(key2,KeyedRef): |

1414 | key2 = <object>PyWeakref_GetObject(key2) |

1415 | if key2 is None: |

1416 | print "found defunct key2" |

1417 | continue |

1418 | if isinstance(key3,KeyedRef): |

1419 | key3 = <object>PyWeakref_GetObject(key3) |

1420 | if key3 is None: |

1421 | print "found defunct key3" |

1422 | continue |

1423 | if self.weak_values and isinstance(value,KeyedRef): |

1424 | value = <object>PyWeakref_GetObject(value) |

1425 | if value is None: |

1426 | print "found defunct value" |

1427 | continue |

1428 | yield ((key1,key2,key3), value) |

1429 | |

1430 | def __reduce__(self): |

1431 | """ |

1432 | Note that we don't expect equality as this class concerns itself with |

1433 | object identity rather than object equality. |

1434 | |

1435 | EXAMPLES:: |

1436 | |

1437 | sage: from sage.structure.coerce_dict import TripleDict |

1438 | sage: L = TripleDict(31) |

1439 | sage: L[1,2,3] = True |

1440 | sage: loads(dumps(L)) == L |

1441 | False |

1442 | sage: list(loads(dumps(L)).iteritems()) |

1443 | [((1, 2, 3), True)] |

1444 | """ |

1445 | return TripleDict, (11, dict(self.iteritems()), 0.7) |

1446 | |

1447 | #the cython supplied tp_traverse and tp_clear do not take the dynamically |

1448 | #allocated table into account, so we have to supply our own. |

1449 | #the only additional link to follow (that cython does pick up and we have |

1450 | #to replicate here) is the "eraser" which in its closure stores a reference |

1451 | #back to the dictionary itself (meaning that MonoDicts only disappear |

1452 | #on cyclic GC) |

1453 | |

1454 | cdef int TripleDict_traverse(TripleDict op, visitproc visit, void *arg): |

1455 | cdef int r |

1456 | if op.table == NULL: |

1457 | return 0 |

1458 | table=op.table |

1459 | cdef size_t i = 0 |

1460 | if (<void*>(op.eraser)): |

1461 | r=visit(<PyObject*><void*>(op.eraser),arg) |

1462 | if r: return r |

1463 | for i in range(op.mask+1): |

1464 | cursor = &table[i] |

1465 | if cursor.key_id1 != NULL and cursor.key_id1 != dummy: |

1466 | r=visit(cursor.key_weakref1,arg) |

1467 | if r: return r |

1468 | r=visit(cursor.key_weakref2,arg) |

1469 | if r: return r |

1470 | r=visit(cursor.key_weakref3,arg) |

1471 | if r: return r |

1472 | r=visit(cursor.value,arg) |

1473 | if r: return r |

1474 | return 0 |

1475 | |

1476 | cdef int TripleDict_clear(TripleDict op): |

1477 | if op.table == NULL: |

1478 | return 0 |

1479 | |

1480 | tmp=op.eraser |

1481 | cdef triple_cell* table=op.table |

1482 | cdef size_t mask=op.mask |

1483 | op.table=NULL |

1484 | op.eraser=None |

1485 | op.mask=0 |

1486 | op.used=0 |

1487 | op.fill=0 |

1488 | |

1489 | #refcount dance to ensure op.eraser==None when the actual object gets deallocated |

1490 | del tmp |

1491 | for i in range(mask+1): |

1492 | cursor = &(table[i]) |

1493 | if cursor.key_id1 != NULL and cursor.key_id1 != dummy: |

1494 | cursor.key_id1 = dummy |

1495 | Py_XDECREF(cursor.key_weakref1) |

1496 | Py_XDECREF(cursor.key_weakref2) |

1497 | Py_XDECREF(cursor.key_weakref3) |

1498 | Py_XDECREF(cursor.value) |

1499 | PyMem_Free(table) |

1500 | return 0 |

1501 | |

1502 | (<PyTypeObject *><void *>TripleDict).tp_traverse = &TripleDict_traverse |

1503 | (<PyTypeObject *><void *>TripleDict).tp_clear = &TripleDict_clear |