diff options
Diffstat (limited to 'Objects/setobject.c')
| -rw-r--r-- | Objects/setobject.c | 546 |
1 files changed, 280 insertions, 266 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c index fc17fa5..61f1d94 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -1,151 +1,115 @@ /* set object implementation + Written and maintained by Raymond D. Hettinger <python@rcn.com> Derived from Lib/sets.py and Objects/dictobject.c. + + The basic lookup function used by all operations. + This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. + + The initial probe index is computed as hash mod the table size. + Subsequent probe indices are computed as explained in Objects/dictobject.c. + + To improve cache locality, each probe inspects a series of consecutive + nearby entries before moving on to probes elsewhere in memory. This leaves + us with a hybrid of linear probing and open addressing. The linear probing + reduces the cost of hash collisions because consecutive memory accesses + tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, + we then use open addressing with the upper bits from the hash value. This + helps break-up long chains of collisions. + + All arithmetic on hash should ignore overflow. + + Unlike the dictionary implementation, the lookkey functions can return + NULL if the rich comparison returns an error. */ #include "Python.h" #include "structmember.h" #include "stringlib/eq.h" -/* Set a key error with the specified argument, wrapping it in a - * tuple automatically so that tuple keys are not unpacked as the - * exception arguments. */ -static void -set_key_error(PyObject *arg) -{ - PyObject *tup; - tup = PyTuple_Pack(1, arg); - if (!tup) - return; /* caller will expect error to be set anyway */ - PyErr_SetObject(PyExc_KeyError, tup); - Py_DECREF(tup); -} - -/* This must be >= 1. */ -#define PERTURB_SHIFT 5 - /* Object used as dummy key to fill deleted entries */ -static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */ +static PyObject _dummy_struct; -#ifdef Py_REF_DEBUG -PyObject * -_PySet_Dummy(void) -{ - return dummy; -} -#endif +#define dummy (&_dummy_struct) -#define INIT_NONZERO_SET_SLOTS(so) do { \ - (so)->table = (so)->smalltable; \ - (so)->mask = PySet_MINSIZE - 1; \ - (so)->hash = -1; \ - } while(0) -#define EMPTY_TO_MINSIZE(so) do { \ - memset((so)->smalltable, 0, sizeof((so)->smalltable)); \ - (so)->used = (so)->fill = 0; \ - INIT_NONZERO_SET_SLOTS(so); \ - } while(0) +/* ======================================================================== */ +/* ======= Begin logic for probing the hash table ========================= */ -/* Reuse scheme to save calls to malloc, free, and memset */ -#ifndef PySet_MAXFREELIST -#define PySet_MAXFREELIST 80 +/* Set this to zero to turn-off linear probing */ +#ifndef LINEAR_PROBES +#define LINEAR_PROBES 9 #endif -static PySetObject *free_list[PySet_MAXFREELIST]; -static int numfree = 0; - - -/* -The basic lookup function used by all operations. -This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. -Open addressing is preferred over chaining since the link overhead for -chaining would be substantial (100% with typical malloc overhead). - -The initial probe index is computed as hash mod the table size. Subsequent -probe indices are computed as explained in Objects/dictobject.c. - -All arithmetic on hash should ignore overflow. -Unlike the dictionary implementation, the lookkey functions can return -NULL if the rich comparison returns an error. -*/ +/* This must be >= 1 */ +#define PERTURB_SHIFT 5 static setentry * -set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) +set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { - register size_t i; /* Unsigned for defined overflow behavior. */ - register size_t perturb; - register setentry *freeslot; - register size_t mask = so->mask; setentry *table = so->table; - register setentry *entry; - register int cmp; - PyObject *startkey; - - i = (size_t)hash & mask; - entry = &table[i]; - if (entry->key == NULL || entry->key == key) + setentry *freeslot = NULL; + setentry *entry; + size_t perturb = hash; + size_t mask = so->mask; + size_t i = (size_t)hash; /* Unsigned for defined overflow behavior. */ + size_t j; + int cmp; + + entry = &table[i & mask]; + if (entry->key == NULL) return entry; - if (entry->key == dummy) - freeslot = entry; - else { - if (entry->hash == hash) { - startkey = entry->key; + while (1) { + if (entry->key == key) + return entry; + if (entry->hash == hash && entry->key != dummy) { + PyObject *startkey = entry->key; Py_INCREF(startkey); cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); Py_DECREF(startkey); if (cmp < 0) return NULL; - if (table == so->table && entry->key == startkey) { - if (cmp > 0) - return entry; - } - else { - /* The compare did major nasty stuff to the - * set: start over. - */ + if (table != so->table || entry->key != startkey) return set_lookkey(so, key, hash); - } + if (cmp > 0) + return entry; } - freeslot = NULL; - } + if (entry->key == dummy && freeslot == NULL) + freeslot = entry; - /* In the loop, key == dummy is by far (factor of 100s) the - least likely outcome, so test for that last. */ - for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; - entry = &table[i & mask]; - if (entry->key == NULL) { - if (freeslot != NULL) - entry = freeslot; - break; - } - if (entry->key == key) - break; - if (entry->hash == hash && entry->key != dummy) { - startkey = entry->key; - Py_INCREF(startkey); - cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) - return NULL; - if (table == so->table && entry->key == startkey) { + for (j = 1 ; j <= LINEAR_PROBES ; j++) { + entry = &table[(i + j) & mask]; + if (entry->key == NULL) + goto found_null; + if (entry->key == key) + return entry; + if (entry->hash == hash && entry->key != dummy) { + PyObject *startkey = entry->key; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) + return NULL; + if (table != so->table || entry->key != startkey) + return set_lookkey(so, key, hash); if (cmp > 0) - break; - } - else { - /* The compare did major nasty stuff to the - * set: start over. - */ - return set_lookkey(so, key, hash); + return entry; } + if (entry->key == dummy && freeslot == NULL) + freeslot = entry; } - else if (entry->key == dummy && freeslot == NULL) - freeslot = entry; + + perturb >>= PERTURB_SHIFT; + i = i * 5 + 1 + perturb; + + entry = &table[i & mask]; + if (entry->key == NULL) + goto found_null; } - return entry; + found_null: + return freeslot == NULL ? entry : freeslot; } /* @@ -154,14 +118,15 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) * see if the comparison altered the table. */ static setentry * -set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash) +set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash) { - register size_t i; /* Unsigned for defined overflow behavior. */ - register size_t perturb; - register setentry *freeslot; - register size_t mask = so->mask; setentry *table = so->table; - register setentry *entry; + setentry *freeslot = NULL; + setentry *entry; + size_t perturb = hash; + size_t mask = so->mask; + size_t i = (size_t)hash; + size_t j; /* Make sure this function doesn't have to handle non-unicode keys, including subclasses of str; e.g., one reason to subclass @@ -171,46 +136,94 @@ set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash) so->lookup = set_lookkey; return set_lookkey(so, key, hash); } - i = (size_t)hash & mask; - entry = &table[i]; - if (entry->key == NULL || entry->key == key) + + entry = &table[i & mask]; + if (entry->key == NULL) return entry; - if (entry->key == dummy) - freeslot = entry; - else { - if (entry->hash == hash && unicode_eq(entry->key, key)) - return entry; - freeslot = NULL; - } - /* In the loop, key == dummy is by far (factor of 100s) the - least likely outcome, so test for that last. */ - for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; - entry = &table[i & mask]; - if (entry->key == NULL) - return freeslot == NULL ? entry : freeslot; + while (1) { if (entry->key == key || (entry->hash == hash - && entry->key != dummy - && unicode_eq(entry->key, key))) + && entry->key != dummy + && unicode_eq(entry->key, key))) return entry; if (entry->key == dummy && freeslot == NULL) freeslot = entry; + + for (j = 1 ; j <= LINEAR_PROBES ; j++) { + entry = &table[(i + j) & mask]; + if (entry->key == NULL) + goto found_null; + if (entry->key == key + || (entry->hash == hash + && entry->key != dummy + && unicode_eq(entry->key, key))) + return entry; + if (entry->key == dummy && freeslot == NULL) + freeslot = entry; + } + + perturb >>= PERTURB_SHIFT; + i = i * 5 + 1 + perturb; + + entry = &table[i & mask]; + if (entry->key == NULL) + goto found_null; } - assert(0); /* NOT REACHED */ - return 0; + found_null: + return freeslot == NULL ? entry : freeslot; +} + +/* +Internal routine used by set_table_resize() to insert an item which is +known to be absent from the set. This routine also assumes that +the set contains no deleted entries. Besides the performance benefit, +using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209). +Note that no refcounts are changed by this routine; if needed, the caller +is responsible for incref'ing `key`. +*/ +static void +set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) +{ + setentry *table = so->table; + setentry *entry; + size_t perturb = hash; + size_t mask = (size_t)so->mask; + size_t i = (size_t)hash; + size_t j; + + while (1) { + entry = &table[i & mask]; + if (entry->key == NULL) + goto found_null; + for (j = 1 ; j <= LINEAR_PROBES ; j++) { + entry = &table[(i + j) & mask]; + if (entry->key == NULL) + goto found_null; + } + perturb >>= PERTURB_SHIFT; + i = i * 5 + 1 + perturb; + } + found_null: + entry->key = key; + entry->hash = hash; + so->fill++; + so->used++; } +/* ======== End logic for probing the hash table ========================== */ +/* ======================================================================== */ + + /* Internal routine to insert a new key into the table. Used by the public insert routine. Eats a reference to key. */ static int -set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash) +set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) { - register setentry *entry; + setentry *entry; assert(so->lookup != NULL); entry = so->lookup(so, key, hash); @@ -227,7 +240,6 @@ set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash) entry->key = key; entry->hash = hash; so->used++; - Py_DECREF(dummy); } else { /* ACTIVE */ Py_DECREF(key); @@ -236,35 +248,6 @@ set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash) } /* -Internal routine used by set_table_resize() to insert an item which is -known to be absent from the set. This routine also assumes that -the set contains no deleted entries. Besides the performance benefit, -using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209). -Note that no refcounts are changed by this routine; if needed, the caller -is responsible for incref'ing `key`. -*/ -static void -set_insert_clean(register PySetObject *so, PyObject *key, Py_hash_t hash) -{ - register size_t i; - register size_t perturb; - register size_t mask = (size_t)so->mask; - setentry *table = so->table; - register setentry *entry; - - i = (size_t)hash & mask; - entry = &table[i]; - for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; - entry = &table[i & mask]; - } - so->fill++; - entry->key = key; - entry->hash = hash; - so->used++; -} - -/* Restructure the table by allocating a new table and reinserting all keys again. When entries have been deleted, the new table may actually be smaller than the old one. @@ -327,23 +310,14 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) so->table = newtable; so->mask = newsize - 1; memset(newtable, 0, sizeof(setentry) * newsize); + i = so->used; so->used = 0; - i = so->fill; so->fill = 0; /* Copy the data over; this is refcount-neutral for active entries; dummy entries aren't copied over, of course */ for (entry = oldtable; i > 0; entry++) { - if (entry->key == NULL) { - /* UNUSED */ - ; - } else if (entry->key == dummy) { - /* DUMMY */ - --i; - assert(entry->key == dummy); - Py_DECREF(entry->key); - } else { - /* ACTIVE */ + if (entry->key != NULL && entry->key != dummy) { --i; set_insert_clean(so, entry->key, entry->hash); } @@ -357,9 +331,9 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */ static int -set_add_entry(register PySetObject *so, setentry *entry) +set_add_entry(PySetObject *so, setentry *entry) { - register Py_ssize_t n_used; + Py_ssize_t n_used; PyObject *key = entry->key; Py_hash_t hash = entry->hash; @@ -376,10 +350,10 @@ set_add_entry(register PySetObject *so, setentry *entry) } static int -set_add_key(register PySetObject *so, PyObject *key) +set_add_key(PySetObject *so, PyObject *key) { - register Py_hash_t hash; - register Py_ssize_t n_used; + Py_hash_t hash; + Py_ssize_t n_used; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -404,7 +378,7 @@ set_add_key(register PySetObject *so, PyObject *key) static int set_discard_entry(PySetObject *so, setentry *oldentry) -{ register setentry *entry; +{ setentry *entry; PyObject *old_key; entry = (so->lookup)(so, oldentry->key, oldentry->hash); @@ -413,7 +387,6 @@ set_discard_entry(PySetObject *so, setentry *oldentry) if (entry->key == NULL || entry->key == dummy) return DISCARD_NOTFOUND; old_key = entry->key; - Py_INCREF(dummy); entry->key = dummy; so->used--; Py_DECREF(old_key); @@ -423,8 +396,8 @@ set_discard_entry(PySetObject *so, setentry *oldentry) static int set_discard_key(PySetObject *so, PyObject *key) { - register Py_hash_t hash; - register setentry *entry; + Py_hash_t hash; + setentry *entry; PyObject *old_key; assert (PyAnySet_Check(so)); @@ -441,13 +414,23 @@ set_discard_key(PySetObject *so, PyObject *key) if (entry->key == NULL || entry->key == dummy) return DISCARD_NOTFOUND; old_key = entry->key; - Py_INCREF(dummy); entry->key = dummy; so->used--; Py_DECREF(old_key); return DISCARD_FOUND; } +static void +set_empty_to_minsize(PySetObject *so) +{ + memset(so->smalltable, 0, sizeof(so->smalltable)); + so->fill = 0; + so->used = 0; + so->mask = PySet_MINSIZE - 1; + so->table = so->smalltable; + so->hash = -1; +} + static int set_clear_internal(PySetObject *so) { @@ -455,14 +438,13 @@ set_clear_internal(PySetObject *so) int table_is_malloced; Py_ssize_t fill; setentry small_copy[PySet_MINSIZE]; -#ifdef Py_DEBUG - Py_ssize_t i, n; - assert (PyAnySet_Check(so)); - n = so->mask + 1; - i = 0; +#ifdef Py_DEBUG + Py_ssize_t i = 0; + Py_ssize_t n = so->mask + 1; #endif + assert (PyAnySet_Check(so)); table = so->table; assert(table != NULL); table_is_malloced = table != so->smalltable; @@ -475,7 +457,7 @@ set_clear_internal(PySetObject *so) */ fill = so->fill; if (table_is_malloced) - EMPTY_TO_MINSIZE(so); + set_empty_to_minsize(so); else if (fill > 0) { /* It's a small table with something that needs to be cleared. @@ -484,7 +466,7 @@ set_clear_internal(PySetObject *so) */ memcpy(small_copy, table, sizeof(small_copy)); table = small_copy; - EMPTY_TO_MINSIZE(so); + set_empty_to_minsize(so); } /* else it's a small table that's already empty */ @@ -499,7 +481,8 @@ set_clear_internal(PySetObject *so) #endif if (entry->key) { --fill; - Py_DECREF(entry->key); + if (entry->key != dummy) + Py_DECREF(entry->key); } #ifdef Py_DEBUG else @@ -530,7 +513,7 @@ set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) { Py_ssize_t i; Py_ssize_t mask; - register setentry *table; + setentry *table; assert (PyAnySet_Check(so)); i = *pos_ptr; @@ -550,7 +533,7 @@ set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) static void set_dealloc(PySetObject *so) { - register setentry *entry; + setentry *entry; Py_ssize_t fill = so->fill; PyObject_GC_UnTrack(so); Py_TRASHCAN_SAFE_BEGIN(so) @@ -560,15 +543,13 @@ set_dealloc(PySetObject *so) for (entry = so->table; fill > 0; entry++) { if (entry->key) { --fill; - Py_DECREF(entry->key); + if (entry->key != dummy) + Py_DECREF(entry->key); } } if (so->table != so->smalltable) PyMem_DEL(so->table); - if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so)) - free_list[numfree++] = so; - else - Py_TYPE(so)->tp_free(so); + Py_TYPE(so)->tp_free(so); Py_TRASHCAN_SAFE_END(so) } @@ -629,8 +610,8 @@ set_merge(PySetObject *so, PyObject *otherset) PySetObject *other; PyObject *key; Py_hash_t hash; - register Py_ssize_t i; - register setentry *entry; + Py_ssize_t i; + setentry *entry; assert (PyAnySet_Check(so)); assert (PyAnySet_Check(otherset)); @@ -698,8 +679,8 @@ set_contains_entry(PySetObject *so, setentry *entry) static PyObject * set_pop(PySetObject *so) { - register Py_ssize_t i = 0; - register setentry *entry; + Py_ssize_t i = 0; + setentry *entry; PyObject *key; assert (PyAnySet_Check(so)); @@ -731,7 +712,6 @@ set_pop(PySetObject *so) } } key = entry->key; - Py_INCREF(dummy); entry->key = dummy; so->used--; so->table[0].hash = i + 1; /* next place to start */ @@ -755,6 +735,17 @@ set_traverse(PySetObject *so, visitproc visit, void *arg) static Py_hash_t frozenset_hash(PyObject *self) { + /* Most of the constants in this hash algorithm are randomly choosen + large primes with "interesting bit patterns" and that passed + tests for good collision statistics on a variety of problematic + datasets such as: + + ps = [] + for r in range(21): + ps += itertools.combinations(range(20), r) + num_distinct_hashes = len({hash(frozenset(s)) for s in ps}) + + */ PySetObject *so = (PySetObject *)self; Py_uhash_t h, hash = 1927868237UL; setentry *entry; @@ -771,8 +762,10 @@ frozenset_hash(PyObject *self) hashes so that many distinct combinations collapse to only a handful of distinct hash values. */ h = entry->hash; - hash ^= (h ^ (h << 16) ^ 89869747UL) * 3644798167UL; + hash ^= ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL; } + /* Make the final result spread-out in a different pattern + than the algorithm for tuples or other python objects. */ hash = hash * 69069U + 907133923UL; if (hash == -1) hash = 590923713UL; @@ -866,8 +859,8 @@ static PyMethodDef setiter_methods[] = { static PyObject *setiter_iternext(setiterobject *si) { PyObject *key; - register Py_ssize_t i, mask; - register setentry *entry; + Py_ssize_t i, mask; + setentry *entry; PySetObject *so = si->si_set; if (so == NULL) @@ -1021,33 +1014,19 @@ PyDoc_STRVAR(update_doc, static PyObject * make_new_set(PyTypeObject *type, PyObject *iterable) { - register PySetObject *so = NULL; - - if (dummy == NULL) { /* Auto-initialize dummy */ - dummy = PyUnicode_FromString("<dummy key>"); - if (dummy == NULL) - return NULL; - } + PySetObject *so = NULL; /* create PySetObject structure */ - if (numfree && - (type == &PySet_Type || type == &PyFrozenSet_Type)) { - so = free_list[--numfree]; - assert (so != NULL && PyAnySet_CheckExact(so)); - Py_TYPE(so) = type; - _Py_NewReference((PyObject *)so); - EMPTY_TO_MINSIZE(so); - PyObject_GC_Track(so); - } else { - so = (PySetObject *)type->tp_alloc(type, 0); - if (so == NULL) - return NULL; - /* tp_alloc has already zeroed the structure */ - assert(so->table == NULL && so->fill == 0 && so->used == 0); - INIT_NONZERO_SET_SLOTS(so); - } + so = (PySetObject *)type->tp_alloc(type, 0); + if (so == NULL) + return NULL; + so->fill = 0; + so->used = 0; + so->mask = PySet_MINSIZE - 1; + so->table = so->smalltable; so->lookup = set_lookkey_unicode; + so->hash = -1; so->weakreflist = NULL; if (iterable != NULL) { @@ -1110,35 +1089,15 @@ frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) int PySet_ClearFreeList(void) { - int freelist_size = numfree; - PySetObject *so; - - while (numfree) { - numfree--; - so = free_list[numfree]; - PyObject_GC_Del(so); - } - return freelist_size; + return 0; } void PySet_Fini(void) { - PySet_ClearFreeList(); - Py_CLEAR(dummy); Py_CLEAR(emptyfrozenset); } -/* Print summary info about the state of the optimized allocator */ -void -_PySet_DebugMallocStats(FILE *out) -{ - _PyDebugAllocatorStats(out, - "free PySetObject", - numfree, sizeof(PySetObject)); -} - - static PyObject * set_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { @@ -1607,9 +1566,15 @@ set_difference(PySetObject *so, PyObject *other) if (PyDict_CheckExact(other)) { while (set_next(so, &pos, &entry)) { setentry entrycopy; + int rv; entrycopy.hash = entry->hash; entrycopy.key = entry->key; - if (!_PyDict_Contains(other, entry->key, entry->hash)) { + rv = _PyDict_Contains(other, entry->key, entry->hash); + if (rv < 0) { + Py_DECREF(result); + return NULL; + } + if (!rv) { if (set_add_entry((PySetObject *)result, &entrycopy) == -1) { Py_DECREF(result); return NULL; @@ -1845,7 +1810,8 @@ PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set."); static PyObject * set_richcompare(PySetObject *v, PyObject *w, int op) { - PyObject *r1, *r2; + PyObject *r1; + int r2; if(!PyAnySet_Check(w)) Py_RETURN_NOTIMPLEMENTED; @@ -1863,9 +1829,11 @@ set_richcompare(PySetObject *v, PyObject *w, int op) r1 = set_richcompare(v, w, Py_EQ); if (r1 == NULL) return NULL; - r2 = PyBool_FromLong(PyObject_Not(r1)); + r2 = PyObject_IsTrue(r1); Py_DECREF(r1); - return r2; + if (r2 < 0) + return NULL; + return PyBool_FromLong(!r2); case Py_LE: return set_issubset(v, w); case Py_GE: @@ -1949,7 +1917,7 @@ set_remove(PySetObject *so, PyObject *key) } if (rv == DISCARD_NOTFOUND) { - set_key_error(key); + _PyErr_SetKeyError(key); return NULL; } Py_RETURN_NONE; @@ -2393,6 +2361,9 @@ _PySet_Update(PyObject *set, PyObject *iterable) return set_update_internal((PySetObject *)set, iterable); } +/* Exported for the gdb plugin's benefit. */ +PyObject *_PySet_Dummy = dummy; + #ifdef Py_DEBUG /* Test code to be called with any three element set. @@ -2411,7 +2382,7 @@ test_c_api(PySetObject *so) Py_ssize_t count; char *s; Py_ssize_t i; - PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x; + PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL; PyObject *ob = (PyObject *)so; Py_hash_t hash; PyObject *str; @@ -2534,3 +2505,46 @@ test_c_api(PySetObject *so) #undef assertRaises #endif + +/***** Dummy Struct *************************************************/ + +static PyObject * +dummy_repr(PyObject *op) +{ + return PyUnicode_FromString("<dummy key>"); +} + +static void +dummy_dealloc(PyObject* ignore) +{ + Py_FatalError("deallocating <dummy key>"); +} + +static PyTypeObject _PySetDummy_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "<dummy key> type", + 0, + 0, + dummy_dealloc, /*tp_dealloc*/ /*never called*/ + 0, /*tp_print*/ + 0, /*tp_getattr*/ + 0, /*tp_setattr*/ + 0, /*tp_reserved*/ + dummy_repr, /*tp_repr*/ + 0, /*tp_as_number*/ + 0, /*tp_as_sequence*/ + 0, /*tp_as_mapping*/ + 0, /*tp_hash */ + 0, /*tp_call */ + 0, /*tp_str */ + 0, /*tp_getattro */ + 0, /*tp_setattro */ + 0, /*tp_as_buffer */ + Py_TPFLAGS_DEFAULT, /*tp_flags */ +}; + +static PyObject _dummy_struct = { + _PyObject_EXTRA_INIT + 2, &_PySetDummy_Type +}; + |