ยปCore Development>Code coverage>Objects/setobject.c

Python code coverage for Objects/setobject.c

#countcontent
1n/a
2n/a/* set object implementation
3n/a
4n/a Written and maintained by Raymond D. Hettinger <python@rcn.com>
5n/a Derived from Lib/sets.py and Objects/dictobject.c.
6n/a
7n/a The basic lookup function used by all operations.
8n/a This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
9n/a
10n/a The initial probe index is computed as hash mod the table size.
11n/a Subsequent probe indices are computed as explained in Objects/dictobject.c.
12n/a
13n/a To improve cache locality, each probe inspects a series of consecutive
14n/a nearby entries before moving on to probes elsewhere in memory. This leaves
15n/a us with a hybrid of linear probing and open addressing. The linear probing
16n/a reduces the cost of hash collisions because consecutive memory accesses
17n/a tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
18n/a we then use open addressing with the upper bits from the hash value. This
19n/a helps break-up long chains of collisions.
20n/a
21n/a All arithmetic on hash should ignore overflow.
22n/a
23n/a Unlike the dictionary implementation, the lookkey function can return
24n/a NULL if the rich comparison returns an error.
25n/a*/
26n/a
27n/a#include "Python.h"
28n/a#include "structmember.h"
29n/a
30n/a/* Object used as dummy key to fill deleted entries */
31n/astatic PyObject _dummy_struct;
32n/a
33n/a#define dummy (&_dummy_struct)
34n/a
35n/a
36n/a/* ======================================================================== */
37n/a/* ======= Begin logic for probing the hash table ========================= */
38n/a
39n/a/* Set this to zero to turn-off linear probing */
40n/a#ifndef LINEAR_PROBES
41n/a#define LINEAR_PROBES 9
42n/a#endif
43n/a
44n/a/* This must be >= 1 */
45n/a#define PERTURB_SHIFT 5
46n/a
47n/astatic setentry *
48n/aset_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
49n/a{
50n/a setentry *table;
51n/a setentry *entry;
52n/a size_t perturb;
53n/a size_t mask = so->mask;
54n/a size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
55n/a size_t j;
56n/a int cmp;
57n/a
58n/a entry = &so->table[i];
59n/a if (entry->key == NULL)
60n/a return entry;
61n/a
62n/a perturb = hash;
63n/a
64n/a while (1) {
65n/a if (entry->hash == hash) {
66n/a PyObject *startkey = entry->key;
67n/a /* startkey cannot be a dummy because the dummy hash field is -1 */
68n/a assert(startkey != dummy);
69n/a if (startkey == key)
70n/a return entry;
71n/a if (PyUnicode_CheckExact(startkey)
72n/a && PyUnicode_CheckExact(key)
73n/a && _PyUnicode_EQ(startkey, key))
74n/a return entry;
75n/a table = so->table;
76n/a Py_INCREF(startkey);
77n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
78n/a Py_DECREF(startkey);
79n/a if (cmp < 0) /* unlikely */
80n/a return NULL;
81n/a if (table != so->table || entry->key != startkey) /* unlikely */
82n/a return set_lookkey(so, key, hash);
83n/a if (cmp > 0) /* likely */
84n/a return entry;
85n/a mask = so->mask; /* help avoid a register spill */
86n/a }
87n/a
88n/a if (i + LINEAR_PROBES <= mask) {
89n/a for (j = 0 ; j < LINEAR_PROBES ; j++) {
90n/a entry++;
91n/a if (entry->hash == 0 && entry->key == NULL)
92n/a return entry;
93n/a if (entry->hash == hash) {
94n/a PyObject *startkey = entry->key;
95n/a assert(startkey != dummy);
96n/a if (startkey == key)
97n/a return entry;
98n/a if (PyUnicode_CheckExact(startkey)
99n/a && PyUnicode_CheckExact(key)
100n/a && _PyUnicode_EQ(startkey, key))
101n/a return entry;
102n/a table = so->table;
103n/a Py_INCREF(startkey);
104n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
105n/a Py_DECREF(startkey);
106n/a if (cmp < 0)
107n/a return NULL;
108n/a if (table != so->table || entry->key != startkey)
109n/a return set_lookkey(so, key, hash);
110n/a if (cmp > 0)
111n/a return entry;
112n/a mask = so->mask;
113n/a }
114n/a }
115n/a }
116n/a
117n/a perturb >>= PERTURB_SHIFT;
118n/a i = (i * 5 + 1 + perturb) & mask;
119n/a
120n/a entry = &so->table[i];
121n/a if (entry->key == NULL)
122n/a return entry;
123n/a }
124n/a}
125n/a
126n/astatic int set_table_resize(PySetObject *, Py_ssize_t);
127n/a
128n/astatic int
129n/aset_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
130n/a{
131n/a setentry *table;
132n/a setentry *freeslot;
133n/a setentry *entry;
134n/a size_t perturb;
135n/a size_t mask;
136n/a size_t i; /* Unsigned for defined overflow behavior */
137n/a size_t j;
138n/a int cmp;
139n/a
140n/a /* Pre-increment is necessary to prevent arbitrary code in the rich
141n/a comparison from deallocating the key just before the insertion. */
142n/a Py_INCREF(key);
143n/a
144n/a restart:
145n/a
146n/a mask = so->mask;
147n/a i = (size_t)hash & mask;
148n/a
149n/a entry = &so->table[i];
150n/a if (entry->key == NULL)
151n/a goto found_unused;
152n/a
153n/a freeslot = NULL;
154n/a perturb = hash;
155n/a
156n/a while (1) {
157n/a if (entry->hash == hash) {
158n/a PyObject *startkey = entry->key;
159n/a /* startkey cannot be a dummy because the dummy hash field is -1 */
160n/a assert(startkey != dummy);
161n/a if (startkey == key)
162n/a goto found_active;
163n/a if (PyUnicode_CheckExact(startkey)
164n/a && PyUnicode_CheckExact(key)
165n/a && _PyUnicode_EQ(startkey, key))
166n/a goto found_active;
167n/a table = so->table;
168n/a Py_INCREF(startkey);
169n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
170n/a Py_DECREF(startkey);
171n/a if (cmp > 0) /* likely */
172n/a goto found_active;
173n/a if (cmp < 0)
174n/a goto comparison_error;
175n/a /* Continuing the search from the current entry only makes
176n/a sense if the table and entry are unchanged; otherwise,
177n/a we have to restart from the beginning */
178n/a if (table != so->table || entry->key != startkey)
179n/a goto restart;
180n/a mask = so->mask; /* help avoid a register spill */
181n/a }
182n/a else if (entry->hash == -1 && freeslot == NULL)
183n/a freeslot = entry;
184n/a
185n/a if (i + LINEAR_PROBES <= mask) {
186n/a for (j = 0 ; j < LINEAR_PROBES ; j++) {
187n/a entry++;
188n/a if (entry->hash == 0 && entry->key == NULL)
189n/a goto found_unused_or_dummy;
190n/a if (entry->hash == hash) {
191n/a PyObject *startkey = entry->key;
192n/a assert(startkey != dummy);
193n/a if (startkey == key)
194n/a goto found_active;
195n/a if (PyUnicode_CheckExact(startkey)
196n/a && PyUnicode_CheckExact(key)
197n/a && _PyUnicode_EQ(startkey, key))
198n/a goto found_active;
199n/a table = so->table;
200n/a Py_INCREF(startkey);
201n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
202n/a Py_DECREF(startkey);
203n/a if (cmp > 0)
204n/a goto found_active;
205n/a if (cmp < 0)
206n/a goto comparison_error;
207n/a if (table != so->table || entry->key != startkey)
208n/a goto restart;
209n/a mask = so->mask;
210n/a }
211n/a else if (entry->hash == -1 && freeslot == NULL)
212n/a freeslot = entry;
213n/a }
214n/a }
215n/a
216n/a perturb >>= PERTURB_SHIFT;
217n/a i = (i * 5 + 1 + perturb) & mask;
218n/a
219n/a entry = &so->table[i];
220n/a if (entry->key == NULL)
221n/a goto found_unused_or_dummy;
222n/a }
223n/a
224n/a found_unused_or_dummy:
225n/a if (freeslot == NULL)
226n/a goto found_unused;
227n/a so->used++;
228n/a freeslot->key = key;
229n/a freeslot->hash = hash;
230n/a return 0;
231n/a
232n/a found_unused:
233n/a so->fill++;
234n/a so->used++;
235n/a entry->key = key;
236n/a entry->hash = hash;
237n/a if ((size_t)so->fill*5 < mask*3)
238n/a return 0;
239n/a return set_table_resize(so, so->used);
240n/a
241n/a found_active:
242n/a Py_DECREF(key);
243n/a return 0;
244n/a
245n/a comparison_error:
246n/a Py_DECREF(key);
247n/a return -1;
248n/a}
249n/a
250n/a/*
251n/aInternal routine used by set_table_resize() to insert an item which is
252n/aknown to be absent from the set. This routine also assumes that
253n/athe set contains no deleted entries. Besides the performance benefit,
254n/athere is also safety benefit since using set_add_entry() risks making
255n/aa callback in the middle of a set_table_resize(), see issue 1456209.
256n/aThe caller is responsible for updating the key's reference count and
257n/athe setobject's fill and used fields.
258n/a*/
259n/astatic void
260n/aset_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash)
261n/a{
262n/a setentry *entry;
263n/a size_t perturb = hash;
264n/a size_t i = (size_t)hash & mask;
265n/a size_t j;
266n/a
267n/a while (1) {
268n/a entry = &table[i];
269n/a if (entry->key == NULL)
270n/a goto found_null;
271n/a if (i + LINEAR_PROBES <= mask) {
272n/a for (j = 0; j < LINEAR_PROBES; j++) {
273n/a entry++;
274n/a if (entry->key == NULL)
275n/a goto found_null;
276n/a }
277n/a }
278n/a perturb >>= PERTURB_SHIFT;
279n/a i = (i * 5 + 1 + perturb) & mask;
280n/a }
281n/a found_null:
282n/a entry->key = key;
283n/a entry->hash = hash;
284n/a}
285n/a
286n/a/* ======== End logic for probing the hash table ========================== */
287n/a/* ======================================================================== */
288n/a
289n/a/*
290n/aRestructure the table by allocating a new table and reinserting all
291n/akeys again. When entries have been deleted, the new table may
292n/aactually be smaller than the old one.
293n/a*/
294n/astatic int
295n/aset_table_resize(PySetObject *so, Py_ssize_t minused)
296n/a{
297n/a Py_ssize_t newsize;
298n/a setentry *oldtable, *newtable, *entry;
299n/a Py_ssize_t oldmask = so->mask;
300n/a size_t newmask;
301n/a int is_oldtable_malloced;
302n/a setentry small_copy[PySet_MINSIZE];
303n/a
304n/a assert(minused >= 0);
305n/a minused = (minused > 50000) ? minused * 2 : minused * 4;
306n/a
307n/a /* Find the smallest table size > minused. */
308n/a /* XXX speed-up with intrinsics */
309n/a for (newsize = PySet_MINSIZE;
310n/a newsize <= minused && newsize > 0;
311n/a newsize <<= 1)
312n/a ;
313n/a if (newsize <= 0) {
314n/a PyErr_NoMemory();
315n/a return -1;
316n/a }
317n/a
318n/a /* Get space for a new table. */
319n/a oldtable = so->table;
320n/a assert(oldtable != NULL);
321n/a is_oldtable_malloced = oldtable != so->smalltable;
322n/a
323n/a if (newsize == PySet_MINSIZE) {
324n/a /* A large table is shrinking, or we can't get any smaller. */
325n/a newtable = so->smalltable;
326n/a if (newtable == oldtable) {
327n/a if (so->fill == so->used) {
328n/a /* No dummies, so no point doing anything. */
329n/a return 0;
330n/a }
331n/a /* We're not going to resize it, but rebuild the
332n/a table anyway to purge old dummy entries.
333n/a Subtle: This is *necessary* if fill==size,
334n/a as set_lookkey needs at least one virgin slot to
335n/a terminate failing searches. If fill < size, it's
336n/a merely desirable, as dummies slow searches. */
337n/a assert(so->fill > so->used);
338n/a memcpy(small_copy, oldtable, sizeof(small_copy));
339n/a oldtable = small_copy;
340n/a }
341n/a }
342n/a else {
343n/a newtable = PyMem_NEW(setentry, newsize);
344n/a if (newtable == NULL) {
345n/a PyErr_NoMemory();
346n/a return -1;
347n/a }
348n/a }
349n/a
350n/a /* Make the set empty, using the new table. */
351n/a assert(newtable != oldtable);
352n/a memset(newtable, 0, sizeof(setentry) * newsize);
353n/a so->mask = newsize - 1;
354n/a so->table = newtable;
355n/a
356n/a /* Copy the data over; this is refcount-neutral for active entries;
357n/a dummy entries aren't copied over, of course */
358n/a newmask = (size_t)so->mask;
359n/a if (so->fill == so->used) {
360n/a for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
361n/a if (entry->key != NULL) {
362n/a set_insert_clean(newtable, newmask, entry->key, entry->hash);
363n/a }
364n/a }
365n/a } else {
366n/a so->fill = so->used;
367n/a for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
368n/a if (entry->key != NULL && entry->key != dummy) {
369n/a set_insert_clean(newtable, newmask, entry->key, entry->hash);
370n/a }
371n/a }
372n/a }
373n/a
374n/a if (is_oldtable_malloced)
375n/a PyMem_DEL(oldtable);
376n/a return 0;
377n/a}
378n/a
379n/astatic int
380n/aset_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
381n/a{
382n/a setentry *entry;
383n/a
384n/a entry = set_lookkey(so, key, hash);
385n/a if (entry != NULL)
386n/a return entry->key != NULL;
387n/a return -1;
388n/a}
389n/a
390n/a#define DISCARD_NOTFOUND 0
391n/a#define DISCARD_FOUND 1
392n/a
393n/astatic int
394n/aset_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
395n/a{
396n/a setentry *entry;
397n/a PyObject *old_key;
398n/a
399n/a entry = set_lookkey(so, key, hash);
400n/a if (entry == NULL)
401n/a return -1;
402n/a if (entry->key == NULL)
403n/a return DISCARD_NOTFOUND;
404n/a old_key = entry->key;
405n/a entry->key = dummy;
406n/a entry->hash = -1;
407n/a so->used--;
408n/a Py_DECREF(old_key);
409n/a return DISCARD_FOUND;
410n/a}
411n/a
412n/astatic int
413n/aset_add_key(PySetObject *so, PyObject *key)
414n/a{
415n/a Py_hash_t hash;
416n/a
417n/a if (!PyUnicode_CheckExact(key) ||
418n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
419n/a hash = PyObject_Hash(key);
420n/a if (hash == -1)
421n/a return -1;
422n/a }
423n/a return set_add_entry(so, key, hash);
424n/a}
425n/a
426n/astatic int
427n/aset_contains_key(PySetObject *so, PyObject *key)
428n/a{
429n/a Py_hash_t hash;
430n/a
431n/a if (!PyUnicode_CheckExact(key) ||
432n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
433n/a hash = PyObject_Hash(key);
434n/a if (hash == -1)
435n/a return -1;
436n/a }
437n/a return set_contains_entry(so, key, hash);
438n/a}
439n/a
440n/astatic int
441n/aset_discard_key(PySetObject *so, PyObject *key)
442n/a{
443n/a Py_hash_t hash;
444n/a
445n/a if (!PyUnicode_CheckExact(key) ||
446n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
447n/a hash = PyObject_Hash(key);
448n/a if (hash == -1)
449n/a return -1;
450n/a }
451n/a return set_discard_entry(so, key, hash);
452n/a}
453n/a
454n/astatic void
455n/aset_empty_to_minsize(PySetObject *so)
456n/a{
457n/a memset(so->smalltable, 0, sizeof(so->smalltable));
458n/a so->fill = 0;
459n/a so->used = 0;
460n/a so->mask = PySet_MINSIZE - 1;
461n/a so->table = so->smalltable;
462n/a so->hash = -1;
463n/a}
464n/a
465n/astatic int
466n/aset_clear_internal(PySetObject *so)
467n/a{
468n/a setentry *entry;
469n/a setentry *table = so->table;
470n/a Py_ssize_t fill = so->fill;
471n/a Py_ssize_t used = so->used;
472n/a int table_is_malloced = table != so->smalltable;
473n/a setentry small_copy[PySet_MINSIZE];
474n/a
475n/a assert (PyAnySet_Check(so));
476n/a assert(table != NULL);
477n/a
478n/a /* This is delicate. During the process of clearing the set,
479n/a * decrefs can cause the set to mutate. To avoid fatal confusion
480n/a * (voice of experience), we have to make the set empty before
481n/a * clearing the slots, and never refer to anything via so->ref while
482n/a * clearing.
483n/a */
484n/a if (table_is_malloced)
485n/a set_empty_to_minsize(so);
486n/a
487n/a else if (fill > 0) {
488n/a /* It's a small table with something that needs to be cleared.
489n/a * Afraid the only safe way is to copy the set entries into
490n/a * another small table first.
491n/a */
492n/a memcpy(small_copy, table, sizeof(small_copy));
493n/a table = small_copy;
494n/a set_empty_to_minsize(so);
495n/a }
496n/a /* else it's a small table that's already empty */
497n/a
498n/a /* Now we can finally clear things. If C had refcounts, we could
499n/a * assert that the refcount on table is 1 now, i.e. that this function
500n/a * has unique access to it, so decref side-effects can't alter it.
501n/a */
502n/a for (entry = table; used > 0; entry++) {
503n/a if (entry->key && entry->key != dummy) {
504n/a used--;
505n/a Py_DECREF(entry->key);
506n/a }
507n/a }
508n/a
509n/a if (table_is_malloced)
510n/a PyMem_DEL(table);
511n/a return 0;
512n/a}
513n/a
514n/a/*
515n/a * Iterate over a set table. Use like so:
516n/a *
517n/a * Py_ssize_t pos;
518n/a * setentry *entry;
519n/a * pos = 0; # important! pos should not otherwise be changed by you
520n/a * while (set_next(yourset, &pos, &entry)) {
521n/a * Refer to borrowed reference in entry->key.
522n/a * }
523n/a *
524n/a * CAUTION: In general, it isn't safe to use set_next in a loop that
525n/a * mutates the table.
526n/a */
527n/astatic int
528n/aset_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
529n/a{
530n/a Py_ssize_t i;
531n/a Py_ssize_t mask;
532n/a setentry *entry;
533n/a
534n/a assert (PyAnySet_Check(so));
535n/a i = *pos_ptr;
536n/a assert(i >= 0);
537n/a mask = so->mask;
538n/a entry = &so->table[i];
539n/a while (i <= mask && (entry->key == NULL || entry->key == dummy)) {
540n/a i++;
541n/a entry++;
542n/a }
543n/a *pos_ptr = i+1;
544n/a if (i > mask)
545n/a return 0;
546n/a assert(entry != NULL);
547n/a *entry_ptr = entry;
548n/a return 1;
549n/a}
550n/a
551n/astatic void
552n/aset_dealloc(PySetObject *so)
553n/a{
554n/a setentry *entry;
555n/a Py_ssize_t used = so->used;
556n/a
557n/a PyObject_GC_UnTrack(so);
558n/a Py_TRASHCAN_SAFE_BEGIN(so)
559n/a if (so->weakreflist != NULL)
560n/a PyObject_ClearWeakRefs((PyObject *) so);
561n/a
562n/a for (entry = so->table; used > 0; entry++) {
563n/a if (entry->key && entry->key != dummy) {
564n/a used--;
565n/a Py_DECREF(entry->key);
566n/a }
567n/a }
568n/a if (so->table != so->smalltable)
569n/a PyMem_DEL(so->table);
570n/a Py_TYPE(so)->tp_free(so);
571n/a Py_TRASHCAN_SAFE_END(so)
572n/a}
573n/a
574n/astatic PyObject *
575n/aset_repr(PySetObject *so)
576n/a{
577n/a PyObject *result=NULL, *keys, *listrepr, *tmp;
578n/a int status = Py_ReprEnter((PyObject*)so);
579n/a
580n/a if (status != 0) {
581n/a if (status < 0)
582n/a return NULL;
583n/a return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
584n/a }
585n/a
586n/a /* shortcut for the empty set */
587n/a if (!so->used) {
588n/a Py_ReprLeave((PyObject*)so);
589n/a return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
590n/a }
591n/a
592n/a keys = PySequence_List((PyObject *)so);
593n/a if (keys == NULL)
594n/a goto done;
595n/a
596n/a /* repr(keys)[1:-1] */
597n/a listrepr = PyObject_Repr(keys);
598n/a Py_DECREF(keys);
599n/a if (listrepr == NULL)
600n/a goto done;
601n/a tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
602n/a Py_DECREF(listrepr);
603n/a if (tmp == NULL)
604n/a goto done;
605n/a listrepr = tmp;
606n/a
607n/a if (Py_TYPE(so) != &PySet_Type)
608n/a result = PyUnicode_FromFormat("%s({%U})",
609n/a Py_TYPE(so)->tp_name,
610n/a listrepr);
611n/a else
612n/a result = PyUnicode_FromFormat("{%U}", listrepr);
613n/a Py_DECREF(listrepr);
614n/adone:
615n/a Py_ReprLeave((PyObject*)so);
616n/a return result;
617n/a}
618n/a
619n/astatic Py_ssize_t
620n/aset_len(PyObject *so)
621n/a{
622n/a return ((PySetObject *)so)->used;
623n/a}
624n/a
625n/astatic int
626n/aset_merge(PySetObject *so, PyObject *otherset)
627n/a{
628n/a PySetObject *other;
629n/a PyObject *key;
630n/a Py_ssize_t i;
631n/a setentry *so_entry;
632n/a setentry *other_entry;
633n/a
634n/a assert (PyAnySet_Check(so));
635n/a assert (PyAnySet_Check(otherset));
636n/a
637n/a other = (PySetObject*)otherset;
638n/a if (other == so || other->used == 0)
639n/a /* a.update(a) or a.update(set()); nothing to do */
640n/a return 0;
641n/a /* Do one big resize at the start, rather than
642n/a * incrementally resizing as we insert new keys. Expect
643n/a * that there will be no (or few) overlapping keys.
644n/a */
645n/a if ((so->fill + other->used)*5 >= so->mask*3) {
646n/a if (set_table_resize(so, so->used + other->used) != 0)
647n/a return -1;
648n/a }
649n/a so_entry = so->table;
650n/a other_entry = other->table;
651n/a
652n/a /* If our table is empty, and both tables have the same size, and
653n/a there are no dummies to eliminate, then just copy the pointers. */
654n/a if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) {
655n/a for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) {
656n/a key = other_entry->key;
657n/a if (key != NULL) {
658n/a assert(so_entry->key == NULL);
659n/a Py_INCREF(key);
660n/a so_entry->key = key;
661n/a so_entry->hash = other_entry->hash;
662n/a }
663n/a }
664n/a so->fill = other->fill;
665n/a so->used = other->used;
666n/a return 0;
667n/a }
668n/a
669n/a /* If our table is empty, we can use set_insert_clean() */
670n/a if (so->fill == 0) {
671n/a setentry *newtable = so->table;
672n/a size_t newmask = (size_t)so->mask;
673n/a so->fill = other->used;
674n/a so->used = other->used;
675n/a for (i = other->mask + 1; i > 0 ; i--, other_entry++) {
676n/a key = other_entry->key;
677n/a if (key != NULL && key != dummy) {
678n/a Py_INCREF(key);
679n/a set_insert_clean(newtable, newmask, key, other_entry->hash);
680n/a }
681n/a }
682n/a return 0;
683n/a }
684n/a
685n/a /* We can't assure there are no duplicates, so do normal insertions */
686n/a for (i = 0; i <= other->mask; i++) {
687n/a other_entry = &other->table[i];
688n/a key = other_entry->key;
689n/a if (key != NULL && key != dummy) {
690n/a if (set_add_entry(so, key, other_entry->hash))
691n/a return -1;
692n/a }
693n/a }
694n/a return 0;
695n/a}
696n/a
697n/astatic PyObject *
698n/aset_pop(PySetObject *so)
699n/a{
700n/a /* Make sure the search finger is in bounds */
701n/a Py_ssize_t i = so->finger & so->mask;
702n/a setentry *entry;
703n/a PyObject *key;
704n/a
705n/a assert (PyAnySet_Check(so));
706n/a if (so->used == 0) {
707n/a PyErr_SetString(PyExc_KeyError, "pop from an empty set");
708n/a return NULL;
709n/a }
710n/a
711n/a while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
712n/a i++;
713n/a if (i > so->mask)
714n/a i = 0;
715n/a }
716n/a key = entry->key;
717n/a entry->key = dummy;
718n/a entry->hash = -1;
719n/a so->used--;
720n/a so->finger = i + 1; /* next place to start */
721n/a return key;
722n/a}
723n/a
724n/aPyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
725n/aRaises KeyError if the set is empty.");
726n/a
727n/astatic int
728n/aset_traverse(PySetObject *so, visitproc visit, void *arg)
729n/a{
730n/a Py_ssize_t pos = 0;
731n/a setentry *entry;
732n/a
733n/a while (set_next(so, &pos, &entry))
734n/a Py_VISIT(entry->key);
735n/a return 0;
736n/a}
737n/a
738n/a/* Work to increase the bit dispersion for closely spaced hash values.
739n/a This is important because some use cases have many combinations of a
740n/a small number of elements with nearby hashes so that many distinct
741n/a combinations collapse to only a handful of distinct hash values. */
742n/a
743n/astatic Py_uhash_t
744n/a_shuffle_bits(Py_uhash_t h)
745n/a{
746n/a return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
747n/a}
748n/a
749n/a/* Most of the constants in this hash algorithm are randomly chosen
750n/a large primes with "interesting bit patterns" and that passed tests
751n/a for good collision statistics on a variety of problematic datasets
752n/a including powersets and graph structures (such as David Eppstein's
753n/a graph recipes in Lib/test/test_set.py) */
754n/a
755n/astatic Py_hash_t
756n/afrozenset_hash(PyObject *self)
757n/a{
758n/a PySetObject *so = (PySetObject *)self;
759n/a Py_uhash_t hash = 0;
760n/a setentry *entry;
761n/a
762n/a if (so->hash != -1)
763n/a return so->hash;
764n/a
765n/a /* Xor-in shuffled bits from every entry's hash field because xor is
766n/a commutative and a frozenset hash should be independent of order.
767n/a
768n/a For speed, include null entries and dummy entries and then
769n/a subtract out their effect afterwards so that the final hash
770n/a depends only on active entries. This allows the code to be
771n/a vectorized by the compiler and it saves the unpredictable
772n/a branches that would arise when trying to exclude null and dummy
773n/a entries on every iteration. */
774n/a
775n/a for (entry = so->table; entry <= &so->table[so->mask]; entry++)
776n/a hash ^= _shuffle_bits(entry->hash);
777n/a
778n/a /* Remove the effect of an odd number of NULL entries */
779n/a if ((so->mask + 1 - so->fill) & 1)
780n/a hash ^= _shuffle_bits(0);
781n/a
782n/a /* Remove the effect of an odd number of dummy entries */
783n/a if ((so->fill - so->used) & 1)
784n/a hash ^= _shuffle_bits(-1);
785n/a
786n/a /* Factor in the number of active entries */
787n/a hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;
788n/a
789n/a /* Disperse patterns arising in nested frozensets */
790n/a hash = hash * 69069U + 907133923UL;
791n/a
792n/a /* -1 is reserved as an error code */
793n/a if (hash == (Py_uhash_t)-1)
794n/a hash = 590923713UL;
795n/a
796n/a so->hash = hash;
797n/a return hash;
798n/a}
799n/a
800n/a/***** Set iterator type ***********************************************/
801n/a
802n/atypedef struct {
803n/a PyObject_HEAD
804n/a PySetObject *si_set; /* Set to NULL when iterator is exhausted */
805n/a Py_ssize_t si_used;
806n/a Py_ssize_t si_pos;
807n/a Py_ssize_t len;
808n/a} setiterobject;
809n/a
810n/astatic void
811n/asetiter_dealloc(setiterobject *si)
812n/a{
813n/a Py_XDECREF(si->si_set);
814n/a PyObject_GC_Del(si);
815n/a}
816n/a
817n/astatic int
818n/asetiter_traverse(setiterobject *si, visitproc visit, void *arg)
819n/a{
820n/a Py_VISIT(si->si_set);
821n/a return 0;
822n/a}
823n/a
824n/astatic PyObject *
825n/asetiter_len(setiterobject *si)
826n/a{
827n/a Py_ssize_t len = 0;
828n/a if (si->si_set != NULL && si->si_used == si->si_set->used)
829n/a len = si->len;
830n/a return PyLong_FromSsize_t(len);
831n/a}
832n/a
833n/aPyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
834n/a
835n/astatic PyObject *setiter_iternext(setiterobject *si);
836n/a
837n/astatic PyObject *
838n/asetiter_reduce(setiterobject *si)
839n/a{
840n/a PyObject *list;
841n/a setiterobject tmp;
842n/a
843n/a list = PyList_New(0);
844n/a if (!list)
845n/a return NULL;
846n/a
847n/a /* copy the iterator state */
848n/a tmp = *si;
849n/a Py_XINCREF(tmp.si_set);
850n/a
851n/a /* iterate the temporary into a list */
852n/a for(;;) {
853n/a PyObject *element = setiter_iternext(&tmp);
854n/a if (element) {
855n/a if (PyList_Append(list, element)) {
856n/a Py_DECREF(element);
857n/a Py_DECREF(list);
858n/a Py_XDECREF(tmp.si_set);
859n/a return NULL;
860n/a }
861n/a Py_DECREF(element);
862n/a } else
863n/a break;
864n/a }
865n/a Py_XDECREF(tmp.si_set);
866n/a /* check for error */
867n/a if (tmp.si_set != NULL) {
868n/a /* we have an error */
869n/a Py_DECREF(list);
870n/a return NULL;
871n/a }
872n/a return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
873n/a}
874n/a
875n/aPyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
876n/a
877n/astatic PyMethodDef setiter_methods[] = {
878n/a {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
879n/a {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
880n/a {NULL, NULL} /* sentinel */
881n/a};
882n/a
883n/astatic PyObject *setiter_iternext(setiterobject *si)
884n/a{
885n/a PyObject *key;
886n/a Py_ssize_t i, mask;
887n/a setentry *entry;
888n/a PySetObject *so = si->si_set;
889n/a
890n/a if (so == NULL)
891n/a return NULL;
892n/a assert (PyAnySet_Check(so));
893n/a
894n/a if (si->si_used != so->used) {
895n/a PyErr_SetString(PyExc_RuntimeError,
896n/a "Set changed size during iteration");
897n/a si->si_used = -1; /* Make this state sticky */
898n/a return NULL;
899n/a }
900n/a
901n/a i = si->si_pos;
902n/a assert(i>=0);
903n/a entry = so->table;
904n/a mask = so->mask;
905n/a while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
906n/a i++;
907n/a si->si_pos = i+1;
908n/a if (i > mask)
909n/a goto fail;
910n/a si->len--;
911n/a key = entry[i].key;
912n/a Py_INCREF(key);
913n/a return key;
914n/a
915n/afail:
916n/a si->si_set = NULL;
917n/a Py_DECREF(so);
918n/a return NULL;
919n/a}
920n/a
921n/aPyTypeObject PySetIter_Type = {
922n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
923n/a "set_iterator", /* tp_name */
924n/a sizeof(setiterobject), /* tp_basicsize */
925n/a 0, /* tp_itemsize */
926n/a /* methods */
927n/a (destructor)setiter_dealloc, /* tp_dealloc */
928n/a 0, /* tp_print */
929n/a 0, /* tp_getattr */
930n/a 0, /* tp_setattr */
931n/a 0, /* tp_reserved */
932n/a 0, /* tp_repr */
933n/a 0, /* tp_as_number */
934n/a 0, /* tp_as_sequence */
935n/a 0, /* tp_as_mapping */
936n/a 0, /* tp_hash */
937n/a 0, /* tp_call */
938n/a 0, /* tp_str */
939n/a PyObject_GenericGetAttr, /* tp_getattro */
940n/a 0, /* tp_setattro */
941n/a 0, /* tp_as_buffer */
942n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
943n/a 0, /* tp_doc */
944n/a (traverseproc)setiter_traverse, /* tp_traverse */
945n/a 0, /* tp_clear */
946n/a 0, /* tp_richcompare */
947n/a 0, /* tp_weaklistoffset */
948n/a PyObject_SelfIter, /* tp_iter */
949n/a (iternextfunc)setiter_iternext, /* tp_iternext */
950n/a setiter_methods, /* tp_methods */
951n/a 0,
952n/a};
953n/a
954n/astatic PyObject *
955n/aset_iter(PySetObject *so)
956n/a{
957n/a setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
958n/a if (si == NULL)
959n/a return NULL;
960n/a Py_INCREF(so);
961n/a si->si_set = so;
962n/a si->si_used = so->used;
963n/a si->si_pos = 0;
964n/a si->len = so->used;
965n/a _PyObject_GC_TRACK(si);
966n/a return (PyObject *)si;
967n/a}
968n/a
969n/astatic int
970n/aset_update_internal(PySetObject *so, PyObject *other)
971n/a{
972n/a PyObject *key, *it;
973n/a
974n/a if (PyAnySet_Check(other))
975n/a return set_merge(so, other);
976n/a
977n/a if (PyDict_CheckExact(other)) {
978n/a PyObject *value;
979n/a Py_ssize_t pos = 0;
980n/a Py_hash_t hash;
981n/a Py_ssize_t dictsize = PyDict_GET_SIZE(other);
982n/a
983n/a /* Do one big resize at the start, rather than
984n/a * incrementally resizing as we insert new keys. Expect
985n/a * that there will be no (or few) overlapping keys.
986n/a */
987n/a if (dictsize < 0)
988n/a return -1;
989n/a if ((so->fill + dictsize)*5 >= so->mask*3) {
990n/a if (set_table_resize(so, so->used + dictsize) != 0)
991n/a return -1;
992n/a }
993n/a while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
994n/a if (set_add_entry(so, key, hash))
995n/a return -1;
996n/a }
997n/a return 0;
998n/a }
999n/a
1000n/a it = PyObject_GetIter(other);
1001n/a if (it == NULL)
1002n/a return -1;
1003n/a
1004n/a while ((key = PyIter_Next(it)) != NULL) {
1005n/a if (set_add_key(so, key)) {
1006n/a Py_DECREF(it);
1007n/a Py_DECREF(key);
1008n/a return -1;
1009n/a }
1010n/a Py_DECREF(key);
1011n/a }
1012n/a Py_DECREF(it);
1013n/a if (PyErr_Occurred())
1014n/a return -1;
1015n/a return 0;
1016n/a}
1017n/a
1018n/astatic PyObject *
1019n/aset_update(PySetObject *so, PyObject *args)
1020n/a{
1021n/a Py_ssize_t i;
1022n/a
1023n/a for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1024n/a PyObject *other = PyTuple_GET_ITEM(args, i);
1025n/a if (set_update_internal(so, other))
1026n/a return NULL;
1027n/a }
1028n/a Py_RETURN_NONE;
1029n/a}
1030n/a
1031n/aPyDoc_STRVAR(update_doc,
1032n/a"Update a set with the union of itself and others.");
1033n/a
1034n/a/* XXX Todo:
1035n/a If aligned memory allocations become available, make the
1036n/a set object 64 byte aligned so that most of the fields
1037n/a can be retrieved or updated in a single cache line.
1038n/a*/
1039n/a
1040n/astatic PyObject *
1041n/amake_new_set(PyTypeObject *type, PyObject *iterable)
1042n/a{
1043n/a PySetObject *so;
1044n/a
1045n/a so = (PySetObject *)type->tp_alloc(type, 0);
1046n/a if (so == NULL)
1047n/a return NULL;
1048n/a
1049n/a so->fill = 0;
1050n/a so->used = 0;
1051n/a so->mask = PySet_MINSIZE - 1;
1052n/a so->table = so->smalltable;
1053n/a so->hash = -1;
1054n/a so->finger = 0;
1055n/a so->weakreflist = NULL;
1056n/a
1057n/a if (iterable != NULL) {
1058n/a if (set_update_internal(so, iterable)) {
1059n/a Py_DECREF(so);
1060n/a return NULL;
1061n/a }
1062n/a }
1063n/a
1064n/a return (PyObject *)so;
1065n/a}
1066n/a
1067n/astatic PyObject *
1068n/amake_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1069n/a{
1070n/a if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1071n/a if (PyType_IsSubtype(type, &PySet_Type))
1072n/a type = &PySet_Type;
1073n/a else
1074n/a type = &PyFrozenSet_Type;
1075n/a }
1076n/a return make_new_set(type, iterable);
1077n/a}
1078n/a
1079n/a/* The empty frozenset is a singleton */
1080n/astatic PyObject *emptyfrozenset = NULL;
1081n/a
1082n/astatic PyObject *
1083n/afrozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1084n/a{
1085n/a PyObject *iterable = NULL, *result;
1086n/a
1087n/a if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1088n/a return NULL;
1089n/a
1090n/a if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1091n/a return NULL;
1092n/a
1093n/a if (type != &PyFrozenSet_Type)
1094n/a return make_new_set(type, iterable);
1095n/a
1096n/a if (iterable != NULL) {
1097n/a /* frozenset(f) is idempotent */
1098n/a if (PyFrozenSet_CheckExact(iterable)) {
1099n/a Py_INCREF(iterable);
1100n/a return iterable;
1101n/a }
1102n/a result = make_new_set(type, iterable);
1103n/a if (result == NULL || PySet_GET_SIZE(result))
1104n/a return result;
1105n/a Py_DECREF(result);
1106n/a }
1107n/a /* The empty frozenset is a singleton */
1108n/a if (emptyfrozenset == NULL)
1109n/a emptyfrozenset = make_new_set(type, NULL);
1110n/a Py_XINCREF(emptyfrozenset);
1111n/a return emptyfrozenset;
1112n/a}
1113n/a
1114n/astatic PyObject *
1115n/aset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1116n/a{
1117n/a return make_new_set(type, NULL);
1118n/a}
1119n/a
1120n/a/* set_swap_bodies() switches the contents of any two sets by moving their
1121n/a internal data pointers and, if needed, copying the internal smalltables.
1122n/a Semantically equivalent to:
1123n/a
1124n/a t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1125n/a
1126n/a The function always succeeds and it leaves both objects in a stable state.
1127n/a Useful for operations that update in-place (by allowing an intermediate
1128n/a result to be swapped into one of the original inputs).
1129n/a*/
1130n/a
1131n/astatic void
1132n/aset_swap_bodies(PySetObject *a, PySetObject *b)
1133n/a{
1134n/a Py_ssize_t t;
1135n/a setentry *u;
1136n/a setentry tab[PySet_MINSIZE];
1137n/a Py_hash_t h;
1138n/a
1139n/a t = a->fill; a->fill = b->fill; b->fill = t;
1140n/a t = a->used; a->used = b->used; b->used = t;
1141n/a t = a->mask; a->mask = b->mask; b->mask = t;
1142n/a
1143n/a u = a->table;
1144n/a if (a->table == a->smalltable)
1145n/a u = b->smalltable;
1146n/a a->table = b->table;
1147n/a if (b->table == b->smalltable)
1148n/a a->table = a->smalltable;
1149n/a b->table = u;
1150n/a
1151n/a if (a->table == a->smalltable || b->table == b->smalltable) {
1152n/a memcpy(tab, a->smalltable, sizeof(tab));
1153n/a memcpy(a->smalltable, b->smalltable, sizeof(tab));
1154n/a memcpy(b->smalltable, tab, sizeof(tab));
1155n/a }
1156n/a
1157n/a if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1158n/a PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1159n/a h = a->hash; a->hash = b->hash; b->hash = h;
1160n/a } else {
1161n/a a->hash = -1;
1162n/a b->hash = -1;
1163n/a }
1164n/a}
1165n/a
1166n/astatic PyObject *
1167n/aset_copy(PySetObject *so)
1168n/a{
1169n/a return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
1170n/a}
1171n/a
1172n/astatic PyObject *
1173n/afrozenset_copy(PySetObject *so)
1174n/a{
1175n/a if (PyFrozenSet_CheckExact(so)) {
1176n/a Py_INCREF(so);
1177n/a return (PyObject *)so;
1178n/a }
1179n/a return set_copy(so);
1180n/a}
1181n/a
1182n/aPyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1183n/a
1184n/astatic PyObject *
1185n/aset_clear(PySetObject *so)
1186n/a{
1187n/a set_clear_internal(so);
1188n/a Py_RETURN_NONE;
1189n/a}
1190n/a
1191n/aPyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1192n/a
1193n/astatic PyObject *
1194n/aset_union(PySetObject *so, PyObject *args)
1195n/a{
1196n/a PySetObject *result;
1197n/a PyObject *other;
1198n/a Py_ssize_t i;
1199n/a
1200n/a result = (PySetObject *)set_copy(so);
1201n/a if (result == NULL)
1202n/a return NULL;
1203n/a
1204n/a for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1205n/a other = PyTuple_GET_ITEM(args, i);
1206n/a if ((PyObject *)so == other)
1207n/a continue;
1208n/a if (set_update_internal(result, other)) {
1209n/a Py_DECREF(result);
1210n/a return NULL;
1211n/a }
1212n/a }
1213n/a return (PyObject *)result;
1214n/a}
1215n/a
1216n/aPyDoc_STRVAR(union_doc,
1217n/a "Return the union of sets as a new set.\n\
1218n/a\n\
1219n/a(i.e. all elements that are in either set.)");
1220n/a
1221n/astatic PyObject *
1222n/aset_or(PySetObject *so, PyObject *other)
1223n/a{
1224n/a PySetObject *result;
1225n/a
1226n/a if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1227n/a Py_RETURN_NOTIMPLEMENTED;
1228n/a
1229n/a result = (PySetObject *)set_copy(so);
1230n/a if (result == NULL)
1231n/a return NULL;
1232n/a if ((PyObject *)so == other)
1233n/a return (PyObject *)result;
1234n/a if (set_update_internal(result, other)) {
1235n/a Py_DECREF(result);
1236n/a return NULL;
1237n/a }
1238n/a return (PyObject *)result;
1239n/a}
1240n/a
1241n/astatic PyObject *
1242n/aset_ior(PySetObject *so, PyObject *other)
1243n/a{
1244n/a if (!PyAnySet_Check(other))
1245n/a Py_RETURN_NOTIMPLEMENTED;
1246n/a
1247n/a if (set_update_internal(so, other))
1248n/a return NULL;
1249n/a Py_INCREF(so);
1250n/a return (PyObject *)so;
1251n/a}
1252n/a
1253n/astatic PyObject *
1254n/aset_intersection(PySetObject *so, PyObject *other)
1255n/a{
1256n/a PySetObject *result;
1257n/a PyObject *key, *it, *tmp;
1258n/a Py_hash_t hash;
1259n/a int rv;
1260n/a
1261n/a if ((PyObject *)so == other)
1262n/a return set_copy(so);
1263n/a
1264n/a result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1265n/a if (result == NULL)
1266n/a return NULL;
1267n/a
1268n/a if (PyAnySet_Check(other)) {
1269n/a Py_ssize_t pos = 0;
1270n/a setentry *entry;
1271n/a
1272n/a if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1273n/a tmp = (PyObject *)so;
1274n/a so = (PySetObject *)other;
1275n/a other = tmp;
1276n/a }
1277n/a
1278n/a while (set_next((PySetObject *)other, &pos, &entry)) {
1279n/a key = entry->key;
1280n/a hash = entry->hash;
1281n/a rv = set_contains_entry(so, key, hash);
1282n/a if (rv < 0) {
1283n/a Py_DECREF(result);
1284n/a return NULL;
1285n/a }
1286n/a if (rv) {
1287n/a if (set_add_entry(result, key, hash)) {
1288n/a Py_DECREF(result);
1289n/a return NULL;
1290n/a }
1291n/a }
1292n/a }
1293n/a return (PyObject *)result;
1294n/a }
1295n/a
1296n/a it = PyObject_GetIter(other);
1297n/a if (it == NULL) {
1298n/a Py_DECREF(result);
1299n/a return NULL;
1300n/a }
1301n/a
1302n/a while ((key = PyIter_Next(it)) != NULL) {
1303n/a hash = PyObject_Hash(key);
1304n/a if (hash == -1)
1305n/a goto error;
1306n/a rv = set_contains_entry(so, key, hash);
1307n/a if (rv < 0)
1308n/a goto error;
1309n/a if (rv) {
1310n/a if (set_add_entry(result, key, hash))
1311n/a goto error;
1312n/a }
1313n/a Py_DECREF(key);
1314n/a }
1315n/a Py_DECREF(it);
1316n/a if (PyErr_Occurred()) {
1317n/a Py_DECREF(result);
1318n/a return NULL;
1319n/a }
1320n/a return (PyObject *)result;
1321n/a error:
1322n/a Py_DECREF(it);
1323n/a Py_DECREF(result);
1324n/a Py_DECREF(key);
1325n/a return NULL;
1326n/a}
1327n/a
1328n/astatic PyObject *
1329n/aset_intersection_multi(PySetObject *so, PyObject *args)
1330n/a{
1331n/a Py_ssize_t i;
1332n/a PyObject *result = (PyObject *)so;
1333n/a
1334n/a if (PyTuple_GET_SIZE(args) == 0)
1335n/a return set_copy(so);
1336n/a
1337n/a Py_INCREF(so);
1338n/a for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1339n/a PyObject *other = PyTuple_GET_ITEM(args, i);
1340n/a PyObject *newresult = set_intersection((PySetObject *)result, other);
1341n/a if (newresult == NULL) {
1342n/a Py_DECREF(result);
1343n/a return NULL;
1344n/a }
1345n/a Py_DECREF(result);
1346n/a result = newresult;
1347n/a }
1348n/a return result;
1349n/a}
1350n/a
1351n/aPyDoc_STRVAR(intersection_doc,
1352n/a"Return the intersection of two sets as a new set.\n\
1353n/a\n\
1354n/a(i.e. all elements that are in both sets.)");
1355n/a
1356n/astatic PyObject *
1357n/aset_intersection_update(PySetObject *so, PyObject *other)
1358n/a{
1359n/a PyObject *tmp;
1360n/a
1361n/a tmp = set_intersection(so, other);
1362n/a if (tmp == NULL)
1363n/a return NULL;
1364n/a set_swap_bodies(so, (PySetObject *)tmp);
1365n/a Py_DECREF(tmp);
1366n/a Py_RETURN_NONE;
1367n/a}
1368n/a
1369n/astatic PyObject *
1370n/aset_intersection_update_multi(PySetObject *so, PyObject *args)
1371n/a{
1372n/a PyObject *tmp;
1373n/a
1374n/a tmp = set_intersection_multi(so, args);
1375n/a if (tmp == NULL)
1376n/a return NULL;
1377n/a set_swap_bodies(so, (PySetObject *)tmp);
1378n/a Py_DECREF(tmp);
1379n/a Py_RETURN_NONE;
1380n/a}
1381n/a
1382n/aPyDoc_STRVAR(intersection_update_doc,
1383n/a"Update a set with the intersection of itself and another.");
1384n/a
1385n/astatic PyObject *
1386n/aset_and(PySetObject *so, PyObject *other)
1387n/a{
1388n/a if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1389n/a Py_RETURN_NOTIMPLEMENTED;
1390n/a return set_intersection(so, other);
1391n/a}
1392n/a
1393n/astatic PyObject *
1394n/aset_iand(PySetObject *so, PyObject *other)
1395n/a{
1396n/a PyObject *result;
1397n/a
1398n/a if (!PyAnySet_Check(other))
1399n/a Py_RETURN_NOTIMPLEMENTED;
1400n/a result = set_intersection_update(so, other);
1401n/a if (result == NULL)
1402n/a return NULL;
1403n/a Py_DECREF(result);
1404n/a Py_INCREF(so);
1405n/a return (PyObject *)so;
1406n/a}
1407n/a
1408n/astatic PyObject *
1409n/aset_isdisjoint(PySetObject *so, PyObject *other)
1410n/a{
1411n/a PyObject *key, *it, *tmp;
1412n/a int rv;
1413n/a
1414n/a if ((PyObject *)so == other) {
1415n/a if (PySet_GET_SIZE(so) == 0)
1416n/a Py_RETURN_TRUE;
1417n/a else
1418n/a Py_RETURN_FALSE;
1419n/a }
1420n/a
1421n/a if (PyAnySet_CheckExact(other)) {
1422n/a Py_ssize_t pos = 0;
1423n/a setentry *entry;
1424n/a
1425n/a if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1426n/a tmp = (PyObject *)so;
1427n/a so = (PySetObject *)other;
1428n/a other = tmp;
1429n/a }
1430n/a while (set_next((PySetObject *)other, &pos, &entry)) {
1431n/a rv = set_contains_entry(so, entry->key, entry->hash);
1432n/a if (rv < 0)
1433n/a return NULL;
1434n/a if (rv)
1435n/a Py_RETURN_FALSE;
1436n/a }
1437n/a Py_RETURN_TRUE;
1438n/a }
1439n/a
1440n/a it = PyObject_GetIter(other);
1441n/a if (it == NULL)
1442n/a return NULL;
1443n/a
1444n/a while ((key = PyIter_Next(it)) != NULL) {
1445n/a Py_hash_t hash = PyObject_Hash(key);
1446n/a
1447n/a if (hash == -1) {
1448n/a Py_DECREF(key);
1449n/a Py_DECREF(it);
1450n/a return NULL;
1451n/a }
1452n/a rv = set_contains_entry(so, key, hash);
1453n/a Py_DECREF(key);
1454n/a if (rv < 0) {
1455n/a Py_DECREF(it);
1456n/a return NULL;
1457n/a }
1458n/a if (rv) {
1459n/a Py_DECREF(it);
1460n/a Py_RETURN_FALSE;
1461n/a }
1462n/a }
1463n/a Py_DECREF(it);
1464n/a if (PyErr_Occurred())
1465n/a return NULL;
1466n/a Py_RETURN_TRUE;
1467n/a}
1468n/a
1469n/aPyDoc_STRVAR(isdisjoint_doc,
1470n/a"Return True if two sets have a null intersection.");
1471n/a
1472n/astatic int
1473n/aset_difference_update_internal(PySetObject *so, PyObject *other)
1474n/a{
1475n/a if (PySet_GET_SIZE(so) == 0) {
1476n/a return 0;
1477n/a }
1478n/a
1479n/a if ((PyObject *)so == other)
1480n/a return set_clear_internal(so);
1481n/a
1482n/a if (PyAnySet_Check(other)) {
1483n/a setentry *entry;
1484n/a Py_ssize_t pos = 0;
1485n/a
1486n/a while (set_next((PySetObject *)other, &pos, &entry))
1487n/a if (set_discard_entry(so, entry->key, entry->hash) < 0)
1488n/a return -1;
1489n/a } else {
1490n/a PyObject *key, *it;
1491n/a it = PyObject_GetIter(other);
1492n/a if (it == NULL)
1493n/a return -1;
1494n/a
1495n/a while ((key = PyIter_Next(it)) != NULL) {
1496n/a if (set_discard_key(so, key) < 0) {
1497n/a Py_DECREF(it);
1498n/a Py_DECREF(key);
1499n/a return -1;
1500n/a }
1501n/a Py_DECREF(key);
1502n/a }
1503n/a Py_DECREF(it);
1504n/a if (PyErr_Occurred())
1505n/a return -1;
1506n/a }
1507n/a /* If more than 1/4th are dummies, then resize them away. */
1508n/a if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4)
1509n/a return 0;
1510n/a return set_table_resize(so, so->used);
1511n/a}
1512n/a
1513n/astatic PyObject *
1514n/aset_difference_update(PySetObject *so, PyObject *args)
1515n/a{
1516n/a Py_ssize_t i;
1517n/a
1518n/a for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1519n/a PyObject *other = PyTuple_GET_ITEM(args, i);
1520n/a if (set_difference_update_internal(so, other))
1521n/a return NULL;
1522n/a }
1523n/a Py_RETURN_NONE;
1524n/a}
1525n/a
1526n/aPyDoc_STRVAR(difference_update_doc,
1527n/a"Remove all elements of another set from this set.");
1528n/a
1529n/astatic PyObject *
1530n/aset_copy_and_difference(PySetObject *so, PyObject *other)
1531n/a{
1532n/a PyObject *result;
1533n/a
1534n/a result = set_copy(so);
1535n/a if (result == NULL)
1536n/a return NULL;
1537n/a if (set_difference_update_internal((PySetObject *) result, other) == 0)
1538n/a return result;
1539n/a Py_DECREF(result);
1540n/a return NULL;
1541n/a}
1542n/a
1543n/astatic PyObject *
1544n/aset_difference(PySetObject *so, PyObject *other)
1545n/a{
1546n/a PyObject *result;
1547n/a PyObject *key;
1548n/a Py_hash_t hash;
1549n/a setentry *entry;
1550n/a Py_ssize_t pos = 0;
1551n/a int rv;
1552n/a
1553n/a if (PySet_GET_SIZE(so) == 0) {
1554n/a return set_copy(so);
1555n/a }
1556n/a
1557n/a if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
1558n/a return set_copy_and_difference(so, other);
1559n/a }
1560n/a
1561n/a /* If len(so) much more than len(other), it's more efficient to simply copy
1562n/a * so and then iterate other looking for common elements. */
1563n/a if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1564n/a return set_copy_and_difference(so, other);
1565n/a }
1566n/a
1567n/a result = make_new_set_basetype(Py_TYPE(so), NULL);
1568n/a if (result == NULL)
1569n/a return NULL;
1570n/a
1571n/a if (PyDict_CheckExact(other)) {
1572n/a while (set_next(so, &pos, &entry)) {
1573n/a key = entry->key;
1574n/a hash = entry->hash;
1575n/a rv = _PyDict_Contains(other, key, hash);
1576n/a if (rv < 0) {
1577n/a Py_DECREF(result);
1578n/a return NULL;
1579n/a }
1580n/a if (!rv) {
1581n/a if (set_add_entry((PySetObject *)result, key, hash)) {
1582n/a Py_DECREF(result);
1583n/a return NULL;
1584n/a }
1585n/a }
1586n/a }
1587n/a return result;
1588n/a }
1589n/a
1590n/a /* Iterate over so, checking for common elements in other. */
1591n/a while (set_next(so, &pos, &entry)) {
1592n/a key = entry->key;
1593n/a hash = entry->hash;
1594n/a rv = set_contains_entry((PySetObject *)other, key, hash);
1595n/a if (rv < 0) {
1596n/a Py_DECREF(result);
1597n/a return NULL;
1598n/a }
1599n/a if (!rv) {
1600n/a if (set_add_entry((PySetObject *)result, key, hash)) {
1601n/a Py_DECREF(result);
1602n/a return NULL;
1603n/a }
1604n/a }
1605n/a }
1606n/a return result;
1607n/a}
1608n/a
1609n/astatic PyObject *
1610n/aset_difference_multi(PySetObject *so, PyObject *args)
1611n/a{
1612n/a Py_ssize_t i;
1613n/a PyObject *result, *other;
1614n/a
1615n/a if (PyTuple_GET_SIZE(args) == 0)
1616n/a return set_copy(so);
1617n/a
1618n/a other = PyTuple_GET_ITEM(args, 0);
1619n/a result = set_difference(so, other);
1620n/a if (result == NULL)
1621n/a return NULL;
1622n/a
1623n/a for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1624n/a other = PyTuple_GET_ITEM(args, i);
1625n/a if (set_difference_update_internal((PySetObject *)result, other)) {
1626n/a Py_DECREF(result);
1627n/a return NULL;
1628n/a }
1629n/a }
1630n/a return result;
1631n/a}
1632n/a
1633n/aPyDoc_STRVAR(difference_doc,
1634n/a"Return the difference of two or more sets as a new set.\n\
1635n/a\n\
1636n/a(i.e. all elements that are in this set but not the others.)");
1637n/astatic PyObject *
1638n/aset_sub(PySetObject *so, PyObject *other)
1639n/a{
1640n/a if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1641n/a Py_RETURN_NOTIMPLEMENTED;
1642n/a return set_difference(so, other);
1643n/a}
1644n/a
1645n/astatic PyObject *
1646n/aset_isub(PySetObject *so, PyObject *other)
1647n/a{
1648n/a if (!PyAnySet_Check(other))
1649n/a Py_RETURN_NOTIMPLEMENTED;
1650n/a if (set_difference_update_internal(so, other))
1651n/a return NULL;
1652n/a Py_INCREF(so);
1653n/a return (PyObject *)so;
1654n/a}
1655n/a
1656n/astatic PyObject *
1657n/aset_symmetric_difference_update(PySetObject *so, PyObject *other)
1658n/a{
1659n/a PySetObject *otherset;
1660n/a PyObject *key;
1661n/a Py_ssize_t pos = 0;
1662n/a Py_hash_t hash;
1663n/a setentry *entry;
1664n/a int rv;
1665n/a
1666n/a if ((PyObject *)so == other)
1667n/a return set_clear(so);
1668n/a
1669n/a if (PyDict_CheckExact(other)) {
1670n/a PyObject *value;
1671n/a while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1672n/a Py_INCREF(key);
1673n/a rv = set_discard_entry(so, key, hash);
1674n/a if (rv < 0) {
1675n/a Py_DECREF(key);
1676n/a return NULL;
1677n/a }
1678n/a if (rv == DISCARD_NOTFOUND) {
1679n/a if (set_add_entry(so, key, hash)) {
1680n/a Py_DECREF(key);
1681n/a return NULL;
1682n/a }
1683n/a }
1684n/a Py_DECREF(key);
1685n/a }
1686n/a Py_RETURN_NONE;
1687n/a }
1688n/a
1689n/a if (PyAnySet_Check(other)) {
1690n/a Py_INCREF(other);
1691n/a otherset = (PySetObject *)other;
1692n/a } else {
1693n/a otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1694n/a if (otherset == NULL)
1695n/a return NULL;
1696n/a }
1697n/a
1698n/a while (set_next(otherset, &pos, &entry)) {
1699n/a key = entry->key;
1700n/a hash = entry->hash;
1701n/a rv = set_discard_entry(so, key, hash);
1702n/a if (rv < 0) {
1703n/a Py_DECREF(otherset);
1704n/a return NULL;
1705n/a }
1706n/a if (rv == DISCARD_NOTFOUND) {
1707n/a if (set_add_entry(so, key, hash)) {
1708n/a Py_DECREF(otherset);
1709n/a return NULL;
1710n/a }
1711n/a }
1712n/a }
1713n/a Py_DECREF(otherset);
1714n/a Py_RETURN_NONE;
1715n/a}
1716n/a
1717n/aPyDoc_STRVAR(symmetric_difference_update_doc,
1718n/a"Update a set with the symmetric difference of itself and another.");
1719n/a
1720n/astatic PyObject *
1721n/aset_symmetric_difference(PySetObject *so, PyObject *other)
1722n/a{
1723n/a PyObject *rv;
1724n/a PySetObject *otherset;
1725n/a
1726n/a otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1727n/a if (otherset == NULL)
1728n/a return NULL;
1729n/a rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1730n/a if (rv == NULL)
1731n/a return NULL;
1732n/a Py_DECREF(rv);
1733n/a return (PyObject *)otherset;
1734n/a}
1735n/a
1736n/aPyDoc_STRVAR(symmetric_difference_doc,
1737n/a"Return the symmetric difference of two sets as a new set.\n\
1738n/a\n\
1739n/a(i.e. all elements that are in exactly one of the sets.)");
1740n/a
1741n/astatic PyObject *
1742n/aset_xor(PySetObject *so, PyObject *other)
1743n/a{
1744n/a if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1745n/a Py_RETURN_NOTIMPLEMENTED;
1746n/a return set_symmetric_difference(so, other);
1747n/a}
1748n/a
1749n/astatic PyObject *
1750n/aset_ixor(PySetObject *so, PyObject *other)
1751n/a{
1752n/a PyObject *result;
1753n/a
1754n/a if (!PyAnySet_Check(other))
1755n/a Py_RETURN_NOTIMPLEMENTED;
1756n/a result = set_symmetric_difference_update(so, other);
1757n/a if (result == NULL)
1758n/a return NULL;
1759n/a Py_DECREF(result);
1760n/a Py_INCREF(so);
1761n/a return (PyObject *)so;
1762n/a}
1763n/a
1764n/astatic PyObject *
1765n/aset_issubset(PySetObject *so, PyObject *other)
1766n/a{
1767n/a setentry *entry;
1768n/a Py_ssize_t pos = 0;
1769n/a int rv;
1770n/a
1771n/a if (!PyAnySet_Check(other)) {
1772n/a PyObject *tmp, *result;
1773n/a tmp = make_new_set(&PySet_Type, other);
1774n/a if (tmp == NULL)
1775n/a return NULL;
1776n/a result = set_issubset(so, tmp);
1777n/a Py_DECREF(tmp);
1778n/a return result;
1779n/a }
1780n/a if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1781n/a Py_RETURN_FALSE;
1782n/a
1783n/a while (set_next(so, &pos, &entry)) {
1784n/a rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash);
1785n/a if (rv < 0)
1786n/a return NULL;
1787n/a if (!rv)
1788n/a Py_RETURN_FALSE;
1789n/a }
1790n/a Py_RETURN_TRUE;
1791n/a}
1792n/a
1793n/aPyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1794n/a
1795n/astatic PyObject *
1796n/aset_issuperset(PySetObject *so, PyObject *other)
1797n/a{
1798n/a PyObject *tmp, *result;
1799n/a
1800n/a if (!PyAnySet_Check(other)) {
1801n/a tmp = make_new_set(&PySet_Type, other);
1802n/a if (tmp == NULL)
1803n/a return NULL;
1804n/a result = set_issuperset(so, tmp);
1805n/a Py_DECREF(tmp);
1806n/a return result;
1807n/a }
1808n/a return set_issubset((PySetObject *)other, (PyObject *)so);
1809n/a}
1810n/a
1811n/aPyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1812n/a
1813n/astatic PyObject *
1814n/aset_richcompare(PySetObject *v, PyObject *w, int op)
1815n/a{
1816n/a PyObject *r1;
1817n/a int r2;
1818n/a
1819n/a if(!PyAnySet_Check(w))
1820n/a Py_RETURN_NOTIMPLEMENTED;
1821n/a
1822n/a switch (op) {
1823n/a case Py_EQ:
1824n/a if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1825n/a Py_RETURN_FALSE;
1826n/a if (v->hash != -1 &&
1827n/a ((PySetObject *)w)->hash != -1 &&
1828n/a v->hash != ((PySetObject *)w)->hash)
1829n/a Py_RETURN_FALSE;
1830n/a return set_issubset(v, w);
1831n/a case Py_NE:
1832n/a r1 = set_richcompare(v, w, Py_EQ);
1833n/a if (r1 == NULL)
1834n/a return NULL;
1835n/a r2 = PyObject_IsTrue(r1);
1836n/a Py_DECREF(r1);
1837n/a if (r2 < 0)
1838n/a return NULL;
1839n/a return PyBool_FromLong(!r2);
1840n/a case Py_LE:
1841n/a return set_issubset(v, w);
1842n/a case Py_GE:
1843n/a return set_issuperset(v, w);
1844n/a case Py_LT:
1845n/a if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1846n/a Py_RETURN_FALSE;
1847n/a return set_issubset(v, w);
1848n/a case Py_GT:
1849n/a if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1850n/a Py_RETURN_FALSE;
1851n/a return set_issuperset(v, w);
1852n/a }
1853n/a Py_RETURN_NOTIMPLEMENTED;
1854n/a}
1855n/a
1856n/astatic PyObject *
1857n/aset_add(PySetObject *so, PyObject *key)
1858n/a{
1859n/a if (set_add_key(so, key))
1860n/a return NULL;
1861n/a Py_RETURN_NONE;
1862n/a}
1863n/a
1864n/aPyDoc_STRVAR(add_doc,
1865n/a"Add an element to a set.\n\
1866n/a\n\
1867n/aThis has no effect if the element is already present.");
1868n/a
1869n/astatic int
1870n/aset_contains(PySetObject *so, PyObject *key)
1871n/a{
1872n/a PyObject *tmpkey;
1873n/a int rv;
1874n/a
1875n/a rv = set_contains_key(so, key);
1876n/a if (rv < 0) {
1877n/a if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1878n/a return -1;
1879n/a PyErr_Clear();
1880n/a tmpkey = make_new_set(&PyFrozenSet_Type, key);
1881n/a if (tmpkey == NULL)
1882n/a return -1;
1883n/a rv = set_contains_key(so, tmpkey);
1884n/a Py_DECREF(tmpkey);
1885n/a }
1886n/a return rv;
1887n/a}
1888n/a
1889n/astatic PyObject *
1890n/aset_direct_contains(PySetObject *so, PyObject *key)
1891n/a{
1892n/a long result;
1893n/a
1894n/a result = set_contains(so, key);
1895n/a if (result < 0)
1896n/a return NULL;
1897n/a return PyBool_FromLong(result);
1898n/a}
1899n/a
1900n/aPyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1901n/a
1902n/astatic PyObject *
1903n/aset_remove(PySetObject *so, PyObject *key)
1904n/a{
1905n/a PyObject *tmpkey;
1906n/a int rv;
1907n/a
1908n/a rv = set_discard_key(so, key);
1909n/a if (rv < 0) {
1910n/a if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1911n/a return NULL;
1912n/a PyErr_Clear();
1913n/a tmpkey = make_new_set(&PyFrozenSet_Type, key);
1914n/a if (tmpkey == NULL)
1915n/a return NULL;
1916n/a rv = set_discard_key(so, tmpkey);
1917n/a Py_DECREF(tmpkey);
1918n/a if (rv < 0)
1919n/a return NULL;
1920n/a }
1921n/a
1922n/a if (rv == DISCARD_NOTFOUND) {
1923n/a _PyErr_SetKeyError(key);
1924n/a return NULL;
1925n/a }
1926n/a Py_RETURN_NONE;
1927n/a}
1928n/a
1929n/aPyDoc_STRVAR(remove_doc,
1930n/a"Remove an element from a set; it must be a member.\n\
1931n/a\n\
1932n/aIf the element is not a member, raise a KeyError.");
1933n/a
1934n/astatic PyObject *
1935n/aset_discard(PySetObject *so, PyObject *key)
1936n/a{
1937n/a PyObject *tmpkey;
1938n/a int rv;
1939n/a
1940n/a rv = set_discard_key(so, key);
1941n/a if (rv < 0) {
1942n/a if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1943n/a return NULL;
1944n/a PyErr_Clear();
1945n/a tmpkey = make_new_set(&PyFrozenSet_Type, key);
1946n/a if (tmpkey == NULL)
1947n/a return NULL;
1948n/a rv = set_discard_key(so, tmpkey);
1949n/a Py_DECREF(tmpkey);
1950n/a if (rv < 0)
1951n/a return NULL;
1952n/a }
1953n/a Py_RETURN_NONE;
1954n/a}
1955n/a
1956n/aPyDoc_STRVAR(discard_doc,
1957n/a"Remove an element from a set if it is a member.\n\
1958n/a\n\
1959n/aIf the element is not a member, do nothing.");
1960n/a
1961n/astatic PyObject *
1962n/aset_reduce(PySetObject *so)
1963n/a{
1964n/a PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
1965n/a _Py_IDENTIFIER(__dict__);
1966n/a
1967n/a keys = PySequence_List((PyObject *)so);
1968n/a if (keys == NULL)
1969n/a goto done;
1970n/a args = PyTuple_Pack(1, keys);
1971n/a if (args == NULL)
1972n/a goto done;
1973n/a dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
1974n/a if (dict == NULL) {
1975n/a PyErr_Clear();
1976n/a dict = Py_None;
1977n/a Py_INCREF(dict);
1978n/a }
1979n/a result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
1980n/adone:
1981n/a Py_XDECREF(args);
1982n/a Py_XDECREF(keys);
1983n/a Py_XDECREF(dict);
1984n/a return result;
1985n/a}
1986n/a
1987n/astatic PyObject *
1988n/aset_sizeof(PySetObject *so)
1989n/a{
1990n/a Py_ssize_t res;
1991n/a
1992n/a res = _PyObject_SIZE(Py_TYPE(so));
1993n/a if (so->table != so->smalltable)
1994n/a res = res + (so->mask + 1) * sizeof(setentry);
1995n/a return PyLong_FromSsize_t(res);
1996n/a}
1997n/a
1998n/aPyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
1999n/astatic int
2000n/aset_init(PySetObject *self, PyObject *args, PyObject *kwds)
2001n/a{
2002n/a PyObject *iterable = NULL;
2003n/a
2004n/a if (!_PyArg_NoKeywords("set()", kwds))
2005n/a return -1;
2006n/a if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2007n/a return -1;
2008n/a if (self->fill)
2009n/a set_clear_internal(self);
2010n/a self->hash = -1;
2011n/a if (iterable == NULL)
2012n/a return 0;
2013n/a return set_update_internal(self, iterable);
2014n/a}
2015n/a
2016n/astatic PySequenceMethods set_as_sequence = {
2017n/a set_len, /* sq_length */
2018n/a 0, /* sq_concat */
2019n/a 0, /* sq_repeat */
2020n/a 0, /* sq_item */
2021n/a 0, /* sq_slice */
2022n/a 0, /* sq_ass_item */
2023n/a 0, /* sq_ass_slice */
2024n/a (objobjproc)set_contains, /* sq_contains */
2025n/a};
2026n/a
2027n/a/* set object ********************************************************/
2028n/a
2029n/a#ifdef Py_DEBUG
2030n/astatic PyObject *test_c_api(PySetObject *so);
2031n/a
2032n/aPyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2033n/aAll is well if assertions don't fail.");
2034n/a#endif
2035n/a
2036n/astatic PyMethodDef set_methods[] = {
2037n/a {"add", (PyCFunction)set_add, METH_O,
2038n/a add_doc},
2039n/a {"clear", (PyCFunction)set_clear, METH_NOARGS,
2040n/a clear_doc},
2041n/a {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2042n/a contains_doc},
2043n/a {"copy", (PyCFunction)set_copy, METH_NOARGS,
2044n/a copy_doc},
2045n/a {"discard", (PyCFunction)set_discard, METH_O,
2046n/a discard_doc},
2047n/a {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2048n/a difference_doc},
2049n/a {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2050n/a difference_update_doc},
2051n/a {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2052n/a intersection_doc},
2053n/a {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2054n/a intersection_update_doc},
2055n/a {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2056n/a isdisjoint_doc},
2057n/a {"issubset", (PyCFunction)set_issubset, METH_O,
2058n/a issubset_doc},
2059n/a {"issuperset", (PyCFunction)set_issuperset, METH_O,
2060n/a issuperset_doc},
2061n/a {"pop", (PyCFunction)set_pop, METH_NOARGS,
2062n/a pop_doc},
2063n/a {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2064n/a reduce_doc},
2065n/a {"remove", (PyCFunction)set_remove, METH_O,
2066n/a remove_doc},
2067n/a {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2068n/a sizeof_doc},
2069n/a {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2070n/a symmetric_difference_doc},
2071n/a {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2072n/a symmetric_difference_update_doc},
2073n/a#ifdef Py_DEBUG
2074n/a {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2075n/a test_c_api_doc},
2076n/a#endif
2077n/a {"union", (PyCFunction)set_union, METH_VARARGS,
2078n/a union_doc},
2079n/a {"update", (PyCFunction)set_update, METH_VARARGS,
2080n/a update_doc},
2081n/a {NULL, NULL} /* sentinel */
2082n/a};
2083n/a
2084n/astatic PyNumberMethods set_as_number = {
2085n/a 0, /*nb_add*/
2086n/a (binaryfunc)set_sub, /*nb_subtract*/
2087n/a 0, /*nb_multiply*/
2088n/a 0, /*nb_remainder*/
2089n/a 0, /*nb_divmod*/
2090n/a 0, /*nb_power*/
2091n/a 0, /*nb_negative*/
2092n/a 0, /*nb_positive*/
2093n/a 0, /*nb_absolute*/
2094n/a 0, /*nb_bool*/
2095n/a 0, /*nb_invert*/
2096n/a 0, /*nb_lshift*/
2097n/a 0, /*nb_rshift*/
2098n/a (binaryfunc)set_and, /*nb_and*/
2099n/a (binaryfunc)set_xor, /*nb_xor*/
2100n/a (binaryfunc)set_or, /*nb_or*/
2101n/a 0, /*nb_int*/
2102n/a 0, /*nb_reserved*/
2103n/a 0, /*nb_float*/
2104n/a 0, /*nb_inplace_add*/
2105n/a (binaryfunc)set_isub, /*nb_inplace_subtract*/
2106n/a 0, /*nb_inplace_multiply*/
2107n/a 0, /*nb_inplace_remainder*/
2108n/a 0, /*nb_inplace_power*/
2109n/a 0, /*nb_inplace_lshift*/
2110n/a 0, /*nb_inplace_rshift*/
2111n/a (binaryfunc)set_iand, /*nb_inplace_and*/
2112n/a (binaryfunc)set_ixor, /*nb_inplace_xor*/
2113n/a (binaryfunc)set_ior, /*nb_inplace_or*/
2114n/a};
2115n/a
2116n/aPyDoc_STRVAR(set_doc,
2117n/a"set() -> new empty set object\n\
2118n/aset(iterable) -> new set object\n\
2119n/a\n\
2120n/aBuild an unordered collection of unique elements.");
2121n/a
2122n/aPyTypeObject PySet_Type = {
2123n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
2124n/a "set", /* tp_name */
2125n/a sizeof(PySetObject), /* tp_basicsize */
2126n/a 0, /* tp_itemsize */
2127n/a /* methods */
2128n/a (destructor)set_dealloc, /* tp_dealloc */
2129n/a 0, /* tp_print */
2130n/a 0, /* tp_getattr */
2131n/a 0, /* tp_setattr */
2132n/a 0, /* tp_reserved */
2133n/a (reprfunc)set_repr, /* tp_repr */
2134n/a &set_as_number, /* tp_as_number */
2135n/a &set_as_sequence, /* tp_as_sequence */
2136n/a 0, /* tp_as_mapping */
2137n/a PyObject_HashNotImplemented, /* tp_hash */
2138n/a 0, /* tp_call */
2139n/a 0, /* tp_str */
2140n/a PyObject_GenericGetAttr, /* tp_getattro */
2141n/a 0, /* tp_setattro */
2142n/a 0, /* tp_as_buffer */
2143n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2144n/a Py_TPFLAGS_BASETYPE, /* tp_flags */
2145n/a set_doc, /* tp_doc */
2146n/a (traverseproc)set_traverse, /* tp_traverse */
2147n/a (inquiry)set_clear_internal, /* tp_clear */
2148n/a (richcmpfunc)set_richcompare, /* tp_richcompare */
2149n/a offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2150n/a (getiterfunc)set_iter, /* tp_iter */
2151n/a 0, /* tp_iternext */
2152n/a set_methods, /* tp_methods */
2153n/a 0, /* tp_members */
2154n/a 0, /* tp_getset */
2155n/a 0, /* tp_base */
2156n/a 0, /* tp_dict */
2157n/a 0, /* tp_descr_get */
2158n/a 0, /* tp_descr_set */
2159n/a 0, /* tp_dictoffset */
2160n/a (initproc)set_init, /* tp_init */
2161n/a PyType_GenericAlloc, /* tp_alloc */
2162n/a set_new, /* tp_new */
2163n/a PyObject_GC_Del, /* tp_free */
2164n/a};
2165n/a
2166n/a/* frozenset object ********************************************************/
2167n/a
2168n/a
2169n/astatic PyMethodDef frozenset_methods[] = {
2170n/a {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2171n/a contains_doc},
2172n/a {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2173n/a copy_doc},
2174n/a {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2175n/a difference_doc},
2176n/a {"intersection", (PyCFunction)set_intersection_multi, METH_VARARGS,
2177n/a intersection_doc},
2178n/a {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2179n/a isdisjoint_doc},
2180n/a {"issubset", (PyCFunction)set_issubset, METH_O,
2181n/a issubset_doc},
2182n/a {"issuperset", (PyCFunction)set_issuperset, METH_O,
2183n/a issuperset_doc},
2184n/a {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2185n/a reduce_doc},
2186n/a {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2187n/a sizeof_doc},
2188n/a {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2189n/a symmetric_difference_doc},
2190n/a {"union", (PyCFunction)set_union, METH_VARARGS,
2191n/a union_doc},
2192n/a {NULL, NULL} /* sentinel */
2193n/a};
2194n/a
2195n/astatic PyNumberMethods frozenset_as_number = {
2196n/a 0, /*nb_add*/
2197n/a (binaryfunc)set_sub, /*nb_subtract*/
2198n/a 0, /*nb_multiply*/
2199n/a 0, /*nb_remainder*/
2200n/a 0, /*nb_divmod*/
2201n/a 0, /*nb_power*/
2202n/a 0, /*nb_negative*/
2203n/a 0, /*nb_positive*/
2204n/a 0, /*nb_absolute*/
2205n/a 0, /*nb_bool*/
2206n/a 0, /*nb_invert*/
2207n/a 0, /*nb_lshift*/
2208n/a 0, /*nb_rshift*/
2209n/a (binaryfunc)set_and, /*nb_and*/
2210n/a (binaryfunc)set_xor, /*nb_xor*/
2211n/a (binaryfunc)set_or, /*nb_or*/
2212n/a};
2213n/a
2214n/aPyDoc_STRVAR(frozenset_doc,
2215n/a"frozenset() -> empty frozenset object\n\
2216n/afrozenset(iterable) -> frozenset object\n\
2217n/a\n\
2218n/aBuild an immutable unordered collection of unique elements.");
2219n/a
2220n/aPyTypeObject PyFrozenSet_Type = {
2221n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
2222n/a "frozenset", /* tp_name */
2223n/a sizeof(PySetObject), /* tp_basicsize */
2224n/a 0, /* tp_itemsize */
2225n/a /* methods */
2226n/a (destructor)set_dealloc, /* tp_dealloc */
2227n/a 0, /* tp_print */
2228n/a 0, /* tp_getattr */
2229n/a 0, /* tp_setattr */
2230n/a 0, /* tp_reserved */
2231n/a (reprfunc)set_repr, /* tp_repr */
2232n/a &frozenset_as_number, /* tp_as_number */
2233n/a &set_as_sequence, /* tp_as_sequence */
2234n/a 0, /* tp_as_mapping */
2235n/a frozenset_hash, /* tp_hash */
2236n/a 0, /* tp_call */
2237n/a 0, /* tp_str */
2238n/a PyObject_GenericGetAttr, /* tp_getattro */
2239n/a 0, /* tp_setattro */
2240n/a 0, /* tp_as_buffer */
2241n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2242n/a Py_TPFLAGS_BASETYPE, /* tp_flags */
2243n/a frozenset_doc, /* tp_doc */
2244n/a (traverseproc)set_traverse, /* tp_traverse */
2245n/a (inquiry)set_clear_internal, /* tp_clear */
2246n/a (richcmpfunc)set_richcompare, /* tp_richcompare */
2247n/a offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2248n/a (getiterfunc)set_iter, /* tp_iter */
2249n/a 0, /* tp_iternext */
2250n/a frozenset_methods, /* tp_methods */
2251n/a 0, /* tp_members */
2252n/a 0, /* tp_getset */
2253n/a 0, /* tp_base */
2254n/a 0, /* tp_dict */
2255n/a 0, /* tp_descr_get */
2256n/a 0, /* tp_descr_set */
2257n/a 0, /* tp_dictoffset */
2258n/a 0, /* tp_init */
2259n/a PyType_GenericAlloc, /* tp_alloc */
2260n/a frozenset_new, /* tp_new */
2261n/a PyObject_GC_Del, /* tp_free */
2262n/a};
2263n/a
2264n/a
2265n/a/***** C API functions *************************************************/
2266n/a
2267n/aPyObject *
2268n/aPySet_New(PyObject *iterable)
2269n/a{
2270n/a return make_new_set(&PySet_Type, iterable);
2271n/a}
2272n/a
2273n/aPyObject *
2274n/aPyFrozenSet_New(PyObject *iterable)
2275n/a{
2276n/a return make_new_set(&PyFrozenSet_Type, iterable);
2277n/a}
2278n/a
2279n/aPy_ssize_t
2280n/aPySet_Size(PyObject *anyset)
2281n/a{
2282n/a if (!PyAnySet_Check(anyset)) {
2283n/a PyErr_BadInternalCall();
2284n/a return -1;
2285n/a }
2286n/a return PySet_GET_SIZE(anyset);
2287n/a}
2288n/a
2289n/aint
2290n/aPySet_Clear(PyObject *set)
2291n/a{
2292n/a if (!PySet_Check(set)) {
2293n/a PyErr_BadInternalCall();
2294n/a return -1;
2295n/a }
2296n/a return set_clear_internal((PySetObject *)set);
2297n/a}
2298n/a
2299n/aint
2300n/aPySet_Contains(PyObject *anyset, PyObject *key)
2301n/a{
2302n/a if (!PyAnySet_Check(anyset)) {
2303n/a PyErr_BadInternalCall();
2304n/a return -1;
2305n/a }
2306n/a return set_contains_key((PySetObject *)anyset, key);
2307n/a}
2308n/a
2309n/aint
2310n/aPySet_Discard(PyObject *set, PyObject *key)
2311n/a{
2312n/a if (!PySet_Check(set)) {
2313n/a PyErr_BadInternalCall();
2314n/a return -1;
2315n/a }
2316n/a return set_discard_key((PySetObject *)set, key);
2317n/a}
2318n/a
2319n/aint
2320n/aPySet_Add(PyObject *anyset, PyObject *key)
2321n/a{
2322n/a if (!PySet_Check(anyset) &&
2323n/a (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2324n/a PyErr_BadInternalCall();
2325n/a return -1;
2326n/a }
2327n/a return set_add_key((PySetObject *)anyset, key);
2328n/a}
2329n/a
2330n/aint
2331n/aPySet_ClearFreeList(void)
2332n/a{
2333n/a return 0;
2334n/a}
2335n/a
2336n/avoid
2337n/aPySet_Fini(void)
2338n/a{
2339n/a Py_CLEAR(emptyfrozenset);
2340n/a}
2341n/a
2342n/aint
2343n/a_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
2344n/a{
2345n/a setentry *entry;
2346n/a
2347n/a if (!PyAnySet_Check(set)) {
2348n/a PyErr_BadInternalCall();
2349n/a return -1;
2350n/a }
2351n/a if (set_next((PySetObject *)set, pos, &entry) == 0)
2352n/a return 0;
2353n/a *key = entry->key;
2354n/a *hash = entry->hash;
2355n/a return 1;
2356n/a}
2357n/a
2358n/aPyObject *
2359n/aPySet_Pop(PyObject *set)
2360n/a{
2361n/a if (!PySet_Check(set)) {
2362n/a PyErr_BadInternalCall();
2363n/a return NULL;
2364n/a }
2365n/a return set_pop((PySetObject *)set);
2366n/a}
2367n/a
2368n/aint
2369n/a_PySet_Update(PyObject *set, PyObject *iterable)
2370n/a{
2371n/a if (!PySet_Check(set)) {
2372n/a PyErr_BadInternalCall();
2373n/a return -1;
2374n/a }
2375n/a return set_update_internal((PySetObject *)set, iterable);
2376n/a}
2377n/a
2378n/a/* Exported for the gdb plugin's benefit. */
2379n/aPyObject *_PySet_Dummy = dummy;
2380n/a
2381n/a#ifdef Py_DEBUG
2382n/a
2383n/a/* Test code to be called with any three element set.
2384n/a Returns True and original set is restored. */
2385n/a
2386n/a#define assertRaises(call_return_value, exception) \
2387n/a do { \
2388n/a assert(call_return_value); \
2389n/a assert(PyErr_ExceptionMatches(exception)); \
2390n/a PyErr_Clear(); \
2391n/a } while(0)
2392n/a
2393n/astatic PyObject *
2394n/atest_c_api(PySetObject *so)
2395n/a{
2396n/a Py_ssize_t count;
2397n/a const char *s;
2398n/a Py_ssize_t i;
2399n/a PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
2400n/a PyObject *ob = (PyObject *)so;
2401n/a Py_hash_t hash;
2402n/a PyObject *str;
2403n/a
2404n/a /* Verify preconditions */
2405n/a assert(PyAnySet_Check(ob));
2406n/a assert(PyAnySet_CheckExact(ob));
2407n/a assert(!PyFrozenSet_CheckExact(ob));
2408n/a
2409n/a /* so.clear(); so |= set("abc"); */
2410n/a str = PyUnicode_FromString("abc");
2411n/a if (str == NULL)
2412n/a return NULL;
2413n/a set_clear_internal(so);
2414n/a if (set_update_internal(so, str)) {
2415n/a Py_DECREF(str);
2416n/a return NULL;
2417n/a }
2418n/a Py_DECREF(str);
2419n/a
2420n/a /* Exercise type/size checks */
2421n/a assert(PySet_Size(ob) == 3);
2422n/a assert(PySet_GET_SIZE(ob) == 3);
2423n/a
2424n/a /* Raise TypeError for non-iterable constructor arguments */
2425n/a assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2426n/a assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2427n/a
2428n/a /* Raise TypeError for unhashable key */
2429n/a dup = PySet_New(ob);
2430n/a assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2431n/a assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2432n/a assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2433n/a
2434n/a /* Exercise successful pop, contains, add, and discard */
2435n/a elem = PySet_Pop(ob);
2436n/a assert(PySet_Contains(ob, elem) == 0);
2437n/a assert(PySet_GET_SIZE(ob) == 2);
2438n/a assert(PySet_Add(ob, elem) == 0);
2439n/a assert(PySet_Contains(ob, elem) == 1);
2440n/a assert(PySet_GET_SIZE(ob) == 3);
2441n/a assert(PySet_Discard(ob, elem) == 1);
2442n/a assert(PySet_GET_SIZE(ob) == 2);
2443n/a assert(PySet_Discard(ob, elem) == 0);
2444n/a assert(PySet_GET_SIZE(ob) == 2);
2445n/a
2446n/a /* Exercise clear */
2447n/a dup2 = PySet_New(dup);
2448n/a assert(PySet_Clear(dup2) == 0);
2449n/a assert(PySet_Size(dup2) == 0);
2450n/a Py_DECREF(dup2);
2451n/a
2452n/a /* Raise SystemError on clear or update of frozen set */
2453n/a f = PyFrozenSet_New(dup);
2454n/a assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2455n/a assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2456n/a assert(PySet_Add(f, elem) == 0);
2457n/a Py_INCREF(f);
2458n/a assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2459n/a Py_DECREF(f);
2460n/a Py_DECREF(f);
2461n/a
2462n/a /* Exercise direct iteration */
2463n/a i = 0, count = 0;
2464n/a while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2465n/a s = PyUnicode_AsUTF8(x);
2466n/a assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2467n/a count++;
2468n/a }
2469n/a assert(count == 3);
2470n/a
2471n/a /* Exercise updates */
2472n/a dup2 = PySet_New(NULL);
2473n/a assert(_PySet_Update(dup2, dup) == 0);
2474n/a assert(PySet_Size(dup2) == 3);
2475n/a assert(_PySet_Update(dup2, dup) == 0);
2476n/a assert(PySet_Size(dup2) == 3);
2477n/a Py_DECREF(dup2);
2478n/a
2479n/a /* Raise SystemError when self argument is not a set or frozenset. */
2480n/a t = PyTuple_New(0);
2481n/a assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2482n/a assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2483n/a Py_DECREF(t);
2484n/a
2485n/a /* Raise SystemError when self argument is not a set. */
2486n/a f = PyFrozenSet_New(dup);
2487n/a assert(PySet_Size(f) == 3);
2488n/a assert(PyFrozenSet_CheckExact(f));
2489n/a assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2490n/a assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2491n/a Py_DECREF(f);
2492n/a
2493n/a /* Raise KeyError when popping from an empty set */
2494n/a assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2495n/a Py_DECREF(ob);
2496n/a assert(PySet_GET_SIZE(ob) == 0);
2497n/a assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2498n/a
2499n/a /* Restore the set from the copy using the PyNumber API */
2500n/a assert(PyNumber_InPlaceOr(ob, dup) == ob);
2501n/a Py_DECREF(ob);
2502n/a
2503n/a /* Verify constructors accept NULL arguments */
2504n/a f = PySet_New(NULL);
2505n/a assert(f != NULL);
2506n/a assert(PySet_GET_SIZE(f) == 0);
2507n/a Py_DECREF(f);
2508n/a f = PyFrozenSet_New(NULL);
2509n/a assert(f != NULL);
2510n/a assert(PyFrozenSet_CheckExact(f));
2511n/a assert(PySet_GET_SIZE(f) == 0);
2512n/a Py_DECREF(f);
2513n/a
2514n/a Py_DECREF(elem);
2515n/a Py_DECREF(dup);
2516n/a Py_RETURN_TRUE;
2517n/a}
2518n/a
2519n/a#undef assertRaises
2520n/a
2521n/a#endif
2522n/a
2523n/a/***** Dummy Struct *************************************************/
2524n/a
2525n/astatic PyObject *
2526n/adummy_repr(PyObject *op)
2527n/a{
2528n/a return PyUnicode_FromString("<dummy key>");
2529n/a}
2530n/a
2531n/astatic void
2532n/adummy_dealloc(PyObject* ignore)
2533n/a{
2534n/a Py_FatalError("deallocating <dummy key>");
2535n/a}
2536n/a
2537n/astatic PyTypeObject _PySetDummy_Type = {
2538n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
2539n/a "<dummy key> type",
2540n/a 0,
2541n/a 0,
2542n/a dummy_dealloc, /*tp_dealloc*/ /*never called*/
2543n/a 0, /*tp_print*/
2544n/a 0, /*tp_getattr*/
2545n/a 0, /*tp_setattr*/
2546n/a 0, /*tp_reserved*/
2547n/a dummy_repr, /*tp_repr*/
2548n/a 0, /*tp_as_number*/
2549n/a 0, /*tp_as_sequence*/
2550n/a 0, /*tp_as_mapping*/
2551n/a 0, /*tp_hash */
2552n/a 0, /*tp_call */
2553n/a 0, /*tp_str */
2554n/a 0, /*tp_getattro */
2555n/a 0, /*tp_setattro */
2556n/a 0, /*tp_as_buffer */
2557n/a Py_TPFLAGS_DEFAULT, /*tp_flags */
2558n/a};
2559n/a
2560n/astatic PyObject _dummy_struct = {
2561n/a _PyObject_EXTRA_INIT
2562n/a 2, &_PySetDummy_Type
2563n/a};
2564n/a