Python code coverage for Objects/setobject.c

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