summaryrefslogtreecommitdiffstats
path: root/Objects
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2013-09-07 22:05:00 (GMT)
committerRaymond Hettinger <python@rcn.com>2013-09-07 22:05:00 (GMT)
commitae7b00e2d3b92991ef1d7685f2bd4b15e5263b84 (patch)
tree62708ef65642e499e1bd44a2a78c57de4c7c862e /Objects
parent7b4769937fb612d576b6829c3b834f3dd31752f1 (diff)
downloadcpython-ae7b00e2d3b92991ef1d7685f2bd4b15e5263b84.zip
cpython-ae7b00e2d3b92991ef1d7685f2bd4b15e5263b84.tar.gz
cpython-ae7b00e2d3b92991ef1d7685f2bd4b15e5263b84.tar.bz2
Move the overview comment to the top of the file.
Diffstat (limited to 'Objects')
-rw-r--r--Objects/setobject.c42
1 files changed, 20 insertions, 22 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 0aec100..b63a966 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -1,10 +1,30 @@
/* set object implementation
+
Written and maintained by Raymond D. Hettinger <python@rcn.com>
Derived from Lib/sets.py and Objects/dictobject.c.
Copyright (c) 2003-2013 Python Software Foundation.
All rights reserved.
+
+ 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"
@@ -44,28 +64,6 @@ PyObject *_PySet_Dummy = dummy;
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.
-
-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.
-*/
-
static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{