diff options
| -rw-r--r-- | Include/setobject.h | 5 | ||||
| -rw-r--r-- | Lib/test/test_sys.py | 2 | ||||
| -rw-r--r-- | Objects/setobject.c | 33 |
3 files changed, 15 insertions, 25 deletions
diff --git a/Include/setobject.h b/Include/setobject.h index 8f8e34f..79124d0 100644 --- a/Include/setobject.h +++ b/Include/setobject.h @@ -14,9 +14,7 @@ extern "C" { 2. Active: key != NULL and key != dummy 3. Dummy: key == dummy -Note: .pop() abuses the hash field of an Unused or Dummy slot to -hold a search finger. The hash field of Unused or Dummy slots has -no meaning otherwise. +The hash field of Unused or Dummy slots have no meaning. */ #define PySet_MINSIZE 8 @@ -59,6 +57,7 @@ typedef struct _setobject { Py_hash_t hash; /* Only used by frozenset objects */ setentry smalltable[PySet_MINSIZE]; + Py_ssize_t finger; /* Search finger for pop() */ PyObject *weakreflist; /* List of weak references */ } PySetObject; diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py index ec2eaf3..2da987f 100644 --- a/Lib/test/test_sys.py +++ b/Lib/test/test_sys.py @@ -994,7 +994,7 @@ class SizeofTest(unittest.TestCase): # frozenset PySet_MINSIZE = 8 samples = [[], range(10), range(50)] - s = size('3n2P' + PySet_MINSIZE*'nP' + 'nP') + s = size('3n2P' + PySet_MINSIZE*'nP' + '2nP') for sample in samples: minused = len(sample) if minused == 0: tmp = 1 diff --git a/Objects/setobject.c b/Objects/setobject.c index 4fba897..9dc88c8 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -668,32 +668,22 @@ set_pop(PySetObject *so) return NULL; } - /* Set entry to "the first" unused or dummy set entry. We abuse - * the hash field of slot 0 to hold a search finger: - * If slot 0 has a value, use slot 0. - * Else slot 0 is being used to hold a search finger, - * and we use its hash value as the first index to look. + i = so->finger; + /* This may be a legit search finger, or it may be a once legit + * search finger that's out of bounds now (due to wrapping or + * resizing). We simply make sure it's in bounds now. */ - entry = &so->table[0]; - if (entry->key == NULL || entry->key == dummy) { - i = entry->hash; - /* The hash field may be a real hash value, or it may be a - * legit search finger, or it may be a once-legit search - * finger that's out of bounds now because it wrapped around - * or the table shrunk -- simply make sure it's in bounds now. - */ - if (i > so->mask || i < 1) - i = 1; /* skip slot 0 */ - while ((entry = &so->table[i])->key == NULL || entry->key==dummy) { - i++; - if (i > so->mask) - i = 1; - } + if (i > so->mask) + i = 0; + while ((entry = &so->table[i])->key == NULL || entry->key==dummy) { + i++; + if (i > so->mask) + i = 0; } key = entry->key; entry->key = dummy; so->used--; - so->table[0].hash = i + 1; /* next place to start */ + so->finger = i + 1; /* next place to start */ return key; } @@ -1012,6 +1002,7 @@ make_new_set(PyTypeObject *type, PyObject *iterable) so->table = so->smalltable; so->lookup = set_lookkey_unicode; so->hash = -1; + so->finger = 0; so->weakreflist = NULL; if (iterable != NULL) { |