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 	typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);

   216 

   217 	assert(so->lookup != NULL);

   218 	entry = so->lookup(so, key, hash);

   219 	if (entry == NULL)

   220 		return -1;

   221 	if (entry->key == NULL) {

   222 		/* UNUSED */

   223 		so->fill++; 

   224 		entry->key = key;

   225 		entry->hash = hash;

   226 		so->used++;

   227 	} else if (entry->key == dummy) {

   228 		/* DUMMY */

   229 		entry->key = key;

   230 		entry->hash = hash;

   231 		so->used++;

   232 		Py_DECREF(dummy);

   233 	} else {

   234 		/* ACTIVE */

   235 		Py_DECREF(key);

   236 	}

   237 	return 0;

   238 }

   239 

   240 /*

   241 Internal routine used by set_table_resize() to insert an item which is

   242 known to be absent from the set.  This routine also assumes that

   243 the set contains no deleted entries.  Besides the performance benefit,

   244 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).

   245 Note that no refcounts are changed by this routine; if needed, the caller

   246 is responsible for incref'ing `key`.

   247 */

   248 static void

   249 set_insert_clean(register PySetObject *so, PyObject *key, long hash)

   250 {

   251 	register size_t i;

   252 	register size_t perturb;

   253 	register size_t mask = (size_t)so->mask;

   254 	setentry *table = so->table;

   255 	register setentry *entry;

   256 

   257 	i = hash & mask;

   258 	entry = &table[i];

   259 	for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {

   260 		i = (i << 2) + i + perturb + 1;

   261 		entry = &table[i & mask];

   262 	}

   263 	so->fill++;

   264 	entry->key = key;

   265 	entry->hash = hash;

   266 	so->used++;

   267 }

   268 

   269 /*

   270 Restructure the table by allocating a new table and reinserting all

   271 keys again.  When entries have been deleted, the new table may

   272 actually be smaller than the old one.

   273 */

   274 static int

   275 set_table_resize(PySetObject *so, Py_ssize_t minused)

   276 {

   277 	Py_ssize_t newsize;

   278 	setentry *oldtable, *newtable, *entry;

   279 	Py_ssize_t i;

   280 	int is_oldtable_malloced;

   281 	setentry small_copy[PySet_MINSIZE];

   282 

   283 	assert(minused >= 0);

   284 

   285 	/* Find the smallest table size > minused. */

   286 	for (newsize = PySet_MINSIZE;

   287 	     newsize <= minused && newsize > 0;

   288 	     newsize <<= 1)

   289 		;

   290 	if (newsize <= 0) {

   291 		PyErr_NoMemory();

   292 		return -1;

   293 	}

   294 

   295 	/* Get space for a new table. */

   296 	oldtable = so->table;

   297 	assert(oldtable != NULL);

   298 	is_oldtable_malloced = oldtable != so->smalltable;

   299 

   300 	if (newsize == PySet_MINSIZE) {

   301 		/* A large table is shrinking, or we can't get any smaller. */

   302 		newtable = so->smalltable;

   303 		if (newtable == oldtable) {

   304 			if (so->fill == so->used) {

   305 				/* No dummies, so no point doing anything. */

   306 				return 0;

   307 			}

   308 			/* We're not going to resize it, but rebuild the

   309 			   table anyway to purge old dummy entries.

   310 			   Subtle:  This is *necessary* if fill==size,

   311 			   as set_lookkey needs at least one virgin slot to

   312 			   terminate failing searches.  If fill < size, it's

   313 			   merely desirable, as dummies slow searches. */

   314 			assert(so->fill > so->used);

   315 			memcpy(small_copy, oldtable, sizeof(small_copy));

   316 			oldtable = small_copy;

   317 		}

   318 	}

   319 	else {

   320 		newtable = PyMem_NEW(setentry, newsize);

   321 		if (newtable == NULL) {

   322 			PyErr_NoMemory();

   323 			return -1;

   324 		}

   325 	}

   326 

   327 	/* Make the set empty, using the new table. */

   328 	assert(newtable != oldtable);

   329 	so->table = newtable;

   330 	so->mask = newsize - 1;

   331 	memset(newtable, 0, sizeof(setentry) * newsize);

   332 	so->used = 0;

   333 	i = so->fill;

   334 	so->fill = 0;

   335 

   336 	/* Copy the data over; this is refcount-neutral for active entries;

   337 	   dummy entries aren't copied over, of course */

   338 	for (entry = oldtable; i > 0; entry++) {

   339 		if (entry->key == NULL) {

   340 			/* UNUSED */

   341 			;

   342 		} else if (entry->key == dummy) {

   343 			/* DUMMY */

   344 			--i;

   345 			assert(entry->key == dummy);

   346 			Py_DECREF(entry->key);

   347 		} else {

   348 			/* ACTIVE */

   349 			--i;

   350 			set_insert_clean(so, entry->key, entry->hash);

   351 		}

   352 	}

   353 

   354 	if (is_oldtable_malloced)

   355 		PyMem_DEL(oldtable);

   356 	return 0;

   357 }

   358 

   359 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */

   360 

   361 static int

   362 set_add_entry(register PySetObject *so, setentry *entry)

   363 {

   364 	register Py_ssize_t n_used;

   365 

   366 	assert(so->fill <= so->mask);  /* at least one empty slot */

   367 	n_used = so->used;

   368 	Py_INCREF(entry->key);

   369 	if (set_insert_key(so, entry->key, entry->hash) == -1) {

   370 		Py_DECREF(entry->key);

   371 		return -1;

   372 	}

   373 	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))

   374 		return 0;

   375 	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

   376 }

   377 

   378 static int

   379 set_add_key(register PySetObject *so, PyObject *key)

   380 {

   381 	register long hash;

   382 	register Py_ssize_t n_used;

   383 

   384 	if (!PyString_CheckExact(key) ||

   385 	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {

   386 		hash = PyObject_Hash(key);

   387 		if (hash == -1)

   388 			return -1;

   389 	}

   390 	assert(so->fill <= so->mask);  /* at least one empty slot */

   391 	n_used = so->used;

   392 	Py_INCREF(key);

   393 	if (set_insert_key(so, key, hash) == -1) {

   394 		Py_DECREF(key);

   395 		return -1;

   396 	}

   397 	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))

   398 		return 0;

   399 	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

   400 }

   401 

   402 #define DISCARD_NOTFOUND 0

   403 #define DISCARD_FOUND 1

   404 

   405 static int

   406 set_discard_entry(PySetObject *so, setentry *oldentry)

   407 {	register setentry *entry;

   408 	PyObject *old_key;

   409 

   410 	entry = (so->lookup)(so, oldentry->key, oldentry->hash);

   411 	if (entry == NULL)

   412 		return -1;

   413 	if (entry->key == NULL  ||  entry->key == dummy)

   414 		return DISCARD_NOTFOUND;

   415 	old_key = entry->key;

   416 	Py_INCREF(dummy);

   417 	entry->key = dummy;

   418 	so->used--;

   419 	Py_DECREF(old_key);

   420 	return DISCARD_FOUND;

   421 }

   422 

   423 static int

   424 set_discard_key(PySetObject *so, PyObject *key)

   425 {

   426 	register long hash;

   427 	register setentry *entry;

   428 	PyObject *old_key;

   429 

   430 	assert (PyAnySet_Check(so));

   431 	if (!PyString_CheckExact(key) ||

   432 	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {

   433 		hash = PyObject_Hash(key);

   434 		if (hash == -1)

   435 			return -1;

   436 	}

   437 	entry = (so->lookup)(so, key, hash);

   438 	if (entry == NULL)

   439 		return -1;

   440 	if (entry->key == NULL  ||  entry->key == dummy)

   441 		return DISCARD_NOTFOUND;

   442 	old_key = entry->key;

   443 	Py_INCREF(dummy);

   444 	entry->key = dummy;

   445 	so->used--;

   446 	Py_DECREF(old_key);

   447 	return DISCARD_FOUND;

   448 }

   449 

   450 static int

   451 set_clear_internal(PySetObject *so)

   452 {

   453 	setentry *entry, *table;

   454 	int table_is_malloced;

   455 	Py_ssize_t fill;

   456 	setentry small_copy[PySet_MINSIZE];

   457 #ifdef Py_DEBUG

   458 	Py_ssize_t i, n;

   459 	assert (PyAnySet_Check(so));

   460 

   461 	n = so->mask + 1;

   462 	i = 0;

   463 #endif

   464 

   465 	table = so->table;

   466 	assert(table != NULL);

   467 	table_is_malloced = table != so->smalltable;

   468 

   469 	/* This is delicate.  During the process of clearing the set,

   470 	 * decrefs can cause the set to mutate.  To avoid fatal confusion

   471 	 * (voice of experience), we have to make the set empty before

   472 	 * clearing the slots, and never refer to anything via so->ref while

   473 	 * clearing.

   474 	 */

   475 	fill = so->fill;

   476 	if (table_is_malloced)

   477 		EMPTY_TO_MINSIZE(so);

   478 

   479 	else if (fill > 0) {

   480 		/* It's a small table with something that needs to be cleared.

   481 		 * Afraid the only safe way is to copy the set entries into

   482 		 * another small table first.

   483 		 */

   484 		memcpy(small_copy, table, sizeof(small_copy));

   485 		table = small_copy;

   486 		EMPTY_TO_MINSIZE(so);

   487 	}

   488 	/* else it's a small table that's already empty */

   489 

   490 	/* Now we can finally clear things.  If C had refcounts, we could

   491 	 * assert that the refcount on table is 1 now, i.e. that this function

   492 	 * has unique access to it, so decref side-effects can't alter it.

   493 	 */

   494 	for (entry = table; fill > 0; ++entry) {

   495 #ifdef Py_DEBUG

   496 		assert(i < n);

   497 		++i;

   498 #endif

   499 		if (entry->key) {

   500 			--fill;

   501 			Py_DECREF(entry->key);

   502 		}

   503 #ifdef Py_DEBUG

   504 		else

   505 			assert(entry->key == NULL);

   506 #endif

   507 	}

   508 

   509 	if (table_is_malloced)

   510 		PyMem_DEL(table);

   511 	return 0;

   512 }

   513 

   514 /*

   515  * Iterate over a set table.  Use like so:

   516  *

   517  *     Py_ssize_t pos;

   518  *     setentry *entry;

   519  *     pos = 0;   # important!  pos should not otherwise be changed by you

   520  *     while (set_next(yourset, &pos, &entry)) {

   521  *              Refer to borrowed reference in entry->key.

   522  *     }

   523  *

   524  * CAUTION:  In general, it isn't safe to use set_next in a loop that

   525  * mutates the table.  

   526  */

   527 static int

   528 set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)

   529 {

   530 	Py_ssize_t i;

   531 	Py_ssize_t mask;

   532 	register setentry *table;

   533 

   534 	assert (PyAnySet_Check(so));

   535 	i = *pos_ptr;

   536 	assert(i >= 0);

   537 	table = so->table;

   538 	mask = so->mask;

   539 	while (i <= mask && (table[i].key == NULL || table[i].key == dummy))

   540 		i++;

   541 	*pos_ptr = i+1;

   542 	if (i > mask)

   543 		return 0;

   544 	assert(table[i].key != NULL);

   545 	*entry_ptr = &table[i];

   546 	return 1;

   547 }

   548 

   549 static void

   550 set_dealloc(PySetObject *so)

   551 {

   552 	register setentry *entry;

   553 	Py_ssize_t fill = so->fill;

   554 	PyObject_GC_UnTrack(so);

   555 	Py_TRASHCAN_SAFE_BEGIN(so)

   556 	if (so->weakreflist != NULL)

   557 		PyObject_ClearWeakRefs((PyObject *) so);

   558 

   559 	for (entry = so->table; fill > 0; entry++) {

   560 		if (entry->key) {

   561 			--fill;

   562 			Py_DECREF(entry->key);

   563 		}

   564 	}

   565 	if (so->table != so->smalltable)

   566 		PyMem_DEL(so->table);

   567 	if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))

   568 		free_list[numfree++] = so;

   569 	else 

   570 		Py_TYPE(so)->tp_free(so);

   571 	Py_TRASHCAN_SAFE_END(so)

   572 }

   573 

   574 static int

   575 set_tp_print(PySetObject *so, FILE *fp, int flags)

   576 {

   577 	setentry *entry;

   578 	Py_ssize_t pos=0;

   579 	char *emit = "";	/* No separator emitted on first pass */

   580 	char *separator = ", ";

   581 	int status = Py_ReprEnter((PyObject*)so);

   582 

   583 	if (status != 0) {

   584 		if (status < 0)

   585 			return status;

   586 		Py_BEGIN_ALLOW_THREADS

   587 		fprintf(fp, "%s(...)", so->ob_type->tp_name);

   588 		Py_END_ALLOW_THREADS

   589 		return 0;

   590 	}        

   591 

   592 	Py_BEGIN_ALLOW_THREADS

   593 	fprintf(fp, "%s([", so->ob_type->tp_name);

   594 	Py_END_ALLOW_THREADS

   595 	while (set_next(so, &pos, &entry)) {

   596 		Py_BEGIN_ALLOW_THREADS

   597 		fputs(emit, fp);

   598 		Py_END_ALLOW_THREADS

   599 		emit = separator;

   600 		if (PyObject_Print(entry->key, fp, 0) != 0) {

   601 			Py_ReprLeave((PyObject*)so);

   602 			return -1;

   603 		}

   604 	}

   605 	Py_BEGIN_ALLOW_THREADS

   606 	fputs("])", fp);

   607 	Py_END_ALLOW_THREADS

   608 	Py_ReprLeave((PyObject*)so);        

   609 	return 0;

   610 }

   611 

   612 static PyObject *

   613 set_repr(PySetObject *so)

   614 {

   615 	PyObject *keys, *result=NULL, *listrepr;

   616 	int status = Py_ReprEnter((PyObject*)so);

   617 

   618 	if (status != 0) {

   619 		if (status < 0)

   620 			return NULL;

   621 		return PyString_FromFormat("%s(...)", so->ob_type->tp_name);

   622 	}

   623 

   624 	keys = PySequence_List((PyObject *)so);

   625 	if (keys == NULL)

   626 		goto done;

   627 	listrepr = PyObject_Repr(keys);

   628 	Py_DECREF(keys);

   629 	if (listrepr == NULL)

   630 		goto done;

   631 

   632 	result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,

   633 		PyString_AS_STRING(listrepr));

   634 	Py_DECREF(listrepr);

   635 done:

   636 	Py_ReprLeave((PyObject*)so);

   637 	return result;

   638 }

   639 

   640 static Py_ssize_t

   641 set_len(PyObject *so)

   642 {

   643 	return ((PySetObject *)so)->used;

   644 }

   645 

   646 static int

   647 set_merge(PySetObject *so, PyObject *otherset)

   648 {

   649 	PySetObject *other;

   650 	register Py_ssize_t i;

   651 	register setentry *entry;

   652 

   653 	assert (PyAnySet_Check(so));

   654 	assert (PyAnySet_Check(otherset));

   655 

   656 	other = (PySetObject*)otherset;

   657 	if (other == so || other->used == 0)

   658 		/* a.update(a) or a.update({}); nothing to do */

   659 		return 0;

   660 	/* Do one big resize at the start, rather than

   661 	 * incrementally resizing as we insert new keys.  Expect

   662 	 * that there will be no (or few) overlapping keys.

   663 	 */

   664 	if ((so->fill + other->used)*3 >= (so->mask+1)*2) {

   665 	   if (set_table_resize(so, (so->used + other->used)*2) != 0)

   666 		   return -1;

   667 	}

   668 	for (i = 0; i <= other->mask; i++) {

   669 		entry = &other->table[i];

   670 		if (entry->key != NULL && 

   671 		    entry->key != dummy) {

   672 			Py_INCREF(entry->key);

   673 			if (set_insert_key(so, entry->key, entry->hash) == -1) {

   674 				Py_DECREF(entry->key);

   675 				return -1;

   676 			}

   677 		}

   678 	}

   679 	return 0;

   680 }

   681 

   682 static int

   683 set_contains_key(PySetObject *so, PyObject *key)

   684 {

   685 	long hash;

   686 	setentry *entry;

   687 

   688 	if (!PyString_CheckExact(key) ||

   689 	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {

   690 		hash = PyObject_Hash(key);

   691 		if (hash == -1)

   692 			return -1;

   693 	}

   694 	entry = (so->lookup)(so, key, hash);

   695 	if (entry == NULL)

   696 		return -1;

   697 	key = entry->key;

   698 	return key != NULL && key != dummy;

   699 }

   700 

   701 static int

   702 set_contains_entry(PySetObject *so, setentry *entry)

   703 {

   704 	PyObject *key;

   705 	setentry *lu_entry;

   706 

   707 	lu_entry = (so->lookup)(so, entry->key, entry->hash);

   708 	if (lu_entry == NULL)

   709 		return -1;

   710 	key = lu_entry->key; 

   711 	return key != NULL && key != dummy;

   712 }

   713 

   714 static PyObject *

   715 set_pop(PySetObject *so)

   716 {

   717 	register Py_ssize_t i = 0;

   718 	register setentry *entry;

   719 	PyObject *key;

   720 

   721 	assert (PyAnySet_Check(so));

   722 	if (so->used == 0) {

   723 		PyErr_SetString(PyExc_KeyError, "pop from an empty set");

   724 		return NULL;

   725 	}

   726 

   727 	/* Set entry to "the first" unused or dummy set entry.  We abuse

   728 	 * the hash field of slot 0 to hold a search finger:

   729 	 * If slot 0 has a value, use slot 0.

   730 	 * Else slot 0 is being used to hold a search finger,

   731 	 * and we use its hash value as the first index to look.

   732 	 */

   733 	entry = &so->table[0];

   734 	if (entry->key == NULL || entry->key == dummy) {

   735 		i = entry->hash;

   736 		/* The hash field may be a real hash value, or it may be a

   737 		 * legit search finger, or it may be a once-legit search

   738 		 * finger that's out of bounds now because it wrapped around

   739 		 * or the table shrunk -- simply make sure it's in bounds now.

   740 		 */

   741 		if (i > so->mask || i < 1)

   742 			i = 1;	/* skip slot 0 */

   743 		while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {

   744 			i++;

   745 			if (i > so->mask)

   746 				i = 1;

   747 		}

   748 	}

   749 	key = entry->key;

   750 	Py_INCREF(dummy);

   751 	entry->key = dummy;

   752 	so->used--;

   753 	so->table[0].hash = i + 1;  /* next place to start */

   754 	return key;

   755 }

   756 

   757 PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\

   758 Raises KeyError if the set is empty.");

   759 

   760 static int

   761 set_traverse(PySetObject *so, visitproc visit, void *arg)

   762 {

   763 	Py_ssize_t pos = 0;

   764 	setentry *entry;

   765 

   766 	while (set_next(so, &pos, &entry))

   767 		Py_VISIT(entry->key);

   768 	return 0;

   769 }

   770 

   771 static long

   772 frozenset_hash(PyObject *self)

   773 {

   774 	PySetObject *so = (PySetObject *)self;

   775 	long h, hash = 1927868237L;

   776 	setentry *entry;

   777 	Py_ssize_t pos = 0;

   778 

   779 	if (so->hash != -1)

   780 		return so->hash;

   781 

   782 	hash *= PySet_GET_SIZE(self) + 1;

   783 	while (set_next(so, &pos, &entry)) {

   784 		/* Work to increase the bit dispersion for closely spaced hash

   785 		   values.  The is important because some use cases have many 

   786 		   combinations of a small number of elements with nearby 

   787 		   hashes so that many distinct combinations collapse to only 

   788 		   a handful of distinct hash values. */

   789 		h = entry->hash;

   790 		hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;

   791 	}

   792 	hash = hash * 69069L + 907133923L;

   793 	if (hash == -1)

   794 		hash = 590923713L;

   795 	so->hash = hash;

   796 	return hash;

   797 }

   798 

   799 /***** Set iterator type ***********************************************/

   800 

   801 typedef struct {

   802 	PyObject_HEAD

   803 	PySetObject *si_set; /* Set to NULL when iterator is exhausted */

   804 	Py_ssize_t si_used;

   805 	Py_ssize_t si_pos;

   806 	Py_ssize_t len;

   807 } setiterobject;

   808 

   809 static void

   810 setiter_dealloc(setiterobject *si)

   811 {

   812 	Py_XDECREF(si->si_set);

   813 	PyObject_Del(si);

   814 }

   815 

   816 static PyObject *

   817 setiter_len(setiterobject *si)

   818 {

   819 	Py_ssize_t len = 0;

   820 	if (si->si_set != NULL && si->si_used == si->si_set->used)

   821 		len = si->len;

   822 	return PyInt_FromLong(len);

   823 }

   824 

   825 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

   826 

   827 static PyMethodDef setiter_methods[] = {

   828 	{"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},

   829  	{NULL,		NULL}		/* sentinel */

   830 };

   831 

   832 static PyObject *setiter_iternext(setiterobject *si)

   833 {

   834 	PyObject *key;

   835 	register Py_ssize_t i, mask;

   836 	register setentry *entry;

   837 	PySetObject *so = si->si_set;

   838 

   839 	if (so == NULL)

   840 		return NULL;

   841 	assert (PyAnySet_Check(so));

   842 

   843 	if (si->si_used != so->used) {

   844 		PyErr_SetString(PyExc_RuntimeError,

   845 				"Set changed size during iteration");

   846 		si->si_used = -1; /* Make this state sticky */

   847 		return NULL;

   848 	}

   849 

   850 	i = si->si_pos;

   851 	assert(i>=0);

   852 	entry = so->table;

   853 	mask = so->mask;

   854 	while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))

   855 		i++;

   856 	si->si_pos = i+1;

   857 	if (i > mask)

   858 		goto fail;

   859 	si->len--;

   860 	key = entry[i].key;

   861 	Py_INCREF(key);

   862 	return key;

   863 

   864 fail:

   865 	Py_DECREF(so);

   866 	si->si_set = NULL;

   867 	return NULL;

   868 }

   869 

   870 static PyTypeObject PySetIter_Type = {

   871 	PyVarObject_HEAD_INIT(&PyType_Type, 0)

   872 	"setiterator",				/* tp_name */

   873 	sizeof(setiterobject),			/* tp_basicsize */

   874 	0,					/* tp_itemsize */

   875 	/* methods */

   876 	(destructor)setiter_dealloc, 		/* tp_dealloc */

   877 	0,					/* tp_print */

   878 	0,					/* tp_getattr */

   879 	0,					/* tp_setattr */

   880 	0,					/* tp_compare */

   881 	0,					/* tp_repr */

   882 	0,					/* tp_as_number */

   883 	0,					/* tp_as_sequence */

   884 	0,					/* tp_as_mapping */

   885 	0,					/* tp_hash */

   886 	0,					/* tp_call */

   887 	0,					/* tp_str */

   888 	PyObject_GenericGetAttr,		/* tp_getattro */

   889 	0,					/* tp_setattro */

   890 	0,					/* tp_as_buffer */

   891 	Py_TPFLAGS_DEFAULT,			/* tp_flags */

   892  	0,					/* tp_doc */

   893  	0,					/* tp_traverse */

   894  	0,					/* tp_clear */

   895 	0,					/* tp_richcompare */

   896 	0,					/* tp_weaklistoffset */

   897 	PyObject_SelfIter,			/* tp_iter */

   898 	(iternextfunc)setiter_iternext,		/* tp_iternext */

   899 	setiter_methods,			/* tp_methods */

   900 	0,

   901 };

   902 

   903 static PyObject *

   904 set_iter(PySetObject *so)

   905 {

   906 	setiterobject *si = PyObject_New(setiterobject, &PySetIter_Type);

   907 	if (si == NULL)

   908 		return NULL;

   909 	Py_INCREF(so);

   910 	si->si_set = so;

   911 	si->si_used = so->used;

   912 	si->si_pos = 0;

   913 	si->len = so->used;

   914 	return (PyObject *)si;

   915 }

   916 

   917 static int

   918 set_update_internal(PySetObject *so, PyObject *other)

   919 {

   920 	PyObject *key, *it;

   921 

   922 	if (PyAnySet_Check(other))

   923 		return set_merge(so, other);

   924 

   925 	if (PyDict_CheckExact(other)) {

   926 		PyObject *value;

   927 		Py_ssize_t pos = 0;

   928 		long hash;

   929 		Py_ssize_t dictsize = PyDict_Size(other);

   930 

   931 		/* Do one big resize at the start, rather than

   932 		* incrementally resizing as we insert new keys.  Expect

   933 		* that there will be no (or few) overlapping keys.

   934 		*/

   935 		if (dictsize == -1)

   936 			return -1;

   937 		if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {

   938 			if (set_table_resize(so, (so->used + dictsize)*2) != 0)

   939 				return -1;

   940 		}

   941 		while (_PyDict_Next(other, &pos, &key, &value, &hash)) {

   942 			setentry an_entry;

   943 

   944 			an_entry.hash = hash;

   945 			an_entry.key = key;

   946 			if (set_add_entry(so, &an_entry) == -1)

   947 				return -1;

   948 		}

   949 		return 0;

   950 	}

   951 

   952 	it = PyObject_GetIter(other);

   953 	if (it == NULL)

   954 		return -1;

   955 

   956 	while ((key = PyIter_Next(it)) != NULL) {

   957                 if (set_add_key(so, key) == -1) {

   958 			Py_DECREF(it);

   959 			Py_DECREF(key);

   960 			return -1;

   961                 } 

   962 		Py_DECREF(key);

   963 	}

   964 	Py_DECREF(it);

   965 	if (PyErr_Occurred())

   966 		return -1;

   967 	return 0;

   968 }

   969 

   970 static PyObject *

   971 set_update(PySetObject *so, PyObject *args)

   972 {

   973 	Py_ssize_t i;

   974 

   975 	for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {

   976 		PyObject *other = PyTuple_GET_ITEM(args, i);

   977 		if (set_update_internal(so, other) == -1)

   978 			return NULL;

   979 	}

   980 	Py_RETURN_NONE;

   981 }

   982 

   983 PyDoc_STRVAR(update_doc, 

   984 "Update a set with the union of itself and others.");

   985 

   986 static PyObject *

   987 make_new_set(PyTypeObject *type, PyObject *iterable)

   988 {

   989 	register PySetObject *so = NULL;

   990 

   991 	if (dummy == NULL) { /* Auto-initialize dummy */

   992 		dummy = PyString_FromString("<dummy key>");

   993 		if (dummy == NULL)

   994 			return NULL;

   995 	}

   996 

   997 	/* create PySetObject structure */

   998 	if (numfree &&

   999 	    (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {

  1000 		so = free_list[--numfree];

  1001 		assert (so != NULL && PyAnySet_CheckExact(so));

  1002 		Py_TYPE(so) = type;

  1003 		_Py_NewReference((PyObject *)so);

  1004 		EMPTY_TO_MINSIZE(so);

  1005 		PyObject_GC_Track(so);

  1006 	} else {

  1007 		so = (PySetObject *)type->tp_alloc(type, 0);

  1008 		if (so == NULL)

  1009 			return NULL;

  1010 		/* tp_alloc has already zeroed the structure */

  1011 		assert(so->table == NULL && so->fill == 0 && so->used == 0);

  1012 		INIT_NONZERO_SET_SLOTS(so);

  1013 	}

  1014 

  1015 	so->lookup = set_lookkey_string;

  1016 	so->weakreflist = NULL;

  1017 

  1018 	if (iterable != NULL) {

  1019 		if (set_update_internal(so, iterable) == -1) {

  1020 			Py_DECREF(so);

  1021 			return NULL;

  1022 		}

  1023 	}

  1024 

  1025 	return (PyObject *)so;

  1026 }

  1027 

  1028 /* The empty frozenset is a singleton */

  1029 static PyObject *emptyfrozenset = NULL;

  1030 

  1031 static PyObject *

  1032 frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

  1033 {

  1034 	PyObject *iterable = NULL, *result;

  1035 

  1036 	if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))

  1037 		return NULL;

  1038 

  1039 	if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))

  1040 		return NULL;

  1041 

  1042 	if (type != &PyFrozenSet_Type)

  1043 		return make_new_set(type, iterable);

  1044 

  1045 	if (iterable != NULL) {

  1046 		/* frozenset(f) is idempotent */

  1047 		if (PyFrozenSet_CheckExact(iterable)) {

  1048 			Py_INCREF(iterable);

  1049 			return iterable;

  1050 		}

  1051 		result = make_new_set(type, iterable);

  1052 		if (result == NULL || PySet_GET_SIZE(result))

  1053 			return result;

  1054 		Py_DECREF(result);

  1055 	}

  1056 	/* The empty frozenset is a singleton */

  1057 	if (emptyfrozenset == NULL)

  1058 		emptyfrozenset = make_new_set(type, NULL);

  1059 	Py_XINCREF(emptyfrozenset);

  1060 	return emptyfrozenset;

  1061 }

  1062 

  1063 void

  1064 PySet_Fini(void)

  1065 {

  1066 	PySetObject *so;

  1067 

  1068 	while (numfree) {

  1069 		numfree--;

  1070 		so = free_list[numfree];

  1071 		PyObject_GC_Del(so);

  1072 	}

  1073 	Py_CLEAR(dummy);

  1074 	Py_CLEAR(emptyfrozenset);

  1075 }

  1076 

  1077 static PyObject *

  1078 set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

  1079 {

  1080 	if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))

  1081 		return NULL;

  1082 	

  1083 	return make_new_set(type, NULL);

  1084 }

  1085 

  1086 /* set_swap_bodies() switches the contents of any two sets by moving their

  1087    internal data pointers and, if needed, copying the internal smalltables.

  1088    Semantically equivalent to:

  1089 

  1090      t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t

  1091 

  1092    The function always succeeds and it leaves both objects in a stable state.

  1093    Useful for creating temporary frozensets from sets for membership testing 

  1094    in __contains__(), discard(), and remove().  Also useful for operations

  1095    that update in-place (by allowing an intermediate result to be swapped 

  1096    into one of the original inputs).

  1097 */

  1098 

  1099 static void

  1100 set_swap_bodies(PySetObject *a, PySetObject *b)

  1101 {

  1102 	Py_ssize_t t;

  1103 	setentry *u;

  1104 	setentry *(*f)(PySetObject *so, PyObject *key, long hash);

  1105 	setentry tab[PySet_MINSIZE];

  1106 	long h;

  1107 

  1108 	t = a->fill;     a->fill   = b->fill;        b->fill  = t;

  1109 	t = a->used;     a->used   = b->used;        b->used  = t;

  1110 	t = a->mask;     a->mask   = b->mask;        b->mask  = t;

  1111 

  1112 	u = a->table;

  1113 	if (a->table == a->smalltable)

  1114 		u = b->smalltable;

  1115 	a->table  = b->table;

  1116 	if (b->table == b->smalltable)

  1117 		a->table = a->smalltable;

  1118 	b->table = u;

  1119 

  1120 	f = a->lookup;   a->lookup = b->lookup;      b->lookup = f;

  1121 

  1122 	if (a->table == a->smalltable || b->table == b->smalltable) {

  1123 		memcpy(tab, a->smalltable, sizeof(tab));

  1124 		memcpy(a->smalltable, b->smalltable, sizeof(tab));

  1125 		memcpy(b->smalltable, tab, sizeof(tab));

  1126 	}

  1127 

  1128 	if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type)  &&

  1129 	    PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {

  1130 		h = a->hash;     a->hash = b->hash;  b->hash = h;

  1131 	} else {

  1132 		a->hash = -1;

  1133 		b->hash = -1;

  1134 	}

  1135 }