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