Index: Objects/setobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/setobject.c,v
retrieving revision 1.56
diff -C2 -r1.56 setobject.c
*** Objects/setobject.c	26 Aug 2005 06:42:30 -0000	1.56
--- Objects/setobject.c	3 Sep 2005 02:37:12 -0000
***************
*** 211,214 ****
--- 211,410 ----
  Eats a reference to key.
  */
+ 
+ /* <AP> */
+ #define BRENT 1
+ 
+ static void
+ set_lookup_insert_key(PySetObject *so, PyObject *key, register long hash)
+ {
+ 	register int i;
+ 	register unsigned int perturb;
+ 	register setentry *freeslot;
+ 	register unsigned int mask = so->mask;
+ 	setentry *table = so->table;
+ 	register setentry *entry;
+ 	register int restore_error;
+ 	register int checked_error;
+ 	register int cmp;
+ 	PyObject *err_type, *err_value, *err_tb;
+ 	PyObject *startkey;
+ 
+ #if BRENT
+ 	/* Brent's variation */
+ 	register int len, alt_len, freeslot_len;
+ 	register int j, k, alt;
+ 	register unsigned int alt_perturb;
+ 	register setentry *alt_entry, *opt_entry, *opt_alt_entry;
+ #endif
+ 
+ 	i = hash & mask;
+ 	entry = &table[i];
+ 	restore_error = checked_error = 0;
+ #if BRENT
+ 	len = 0;
+ #endif
+ 	if (entry->key == NULL)
+ 		goto NotFound;
+ 	if (entry->key == key)
+ 		goto Found;
+ 
+ 	if (entry->key == dummy) {
+ 		freeslot = entry;
+ #if BRENT
+ 		freeslot_len = len;
+ #endif
+ 	}
+ 	else {
+ 		if (entry->hash == hash) {
+ 			/* error can't have been checked yet */
+ 			checked_error = 1;
+ 			if (_PyErr_OCCURRED()) {
+ 				restore_error = 1;
+ 				PyErr_Fetch(&err_type, &err_value, &err_tb);
+ 			}
+ 			startkey = entry->key;
+ 			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+ 			if (cmp < 0)
+ 				PyErr_Clear();
+ 			if (table == so->table && entry->key == startkey) {
+ 				if (cmp > 0)
+ 					goto Found;
+ 			}
+ 			else {
+ 				/* The compare did major nasty stuff to the
+ 				 * set:  start over.
+  				 */
+  				set_lookup_insert_key(so, key, hash);
+  				goto Done;
+  			}
+ 		}
+ #if BRENT
+ 		freeslot_len = 0;
+ #endif
+ 		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) {
+ #if BRENT
+ 		len++;
+ #endif
+ 		i = (i << 2) + i + perturb + 1;
+ 		entry = &table[i & mask];
+ 		if (entry->key == NULL) {
+ 			if (freeslot != NULL) {
+ #if BRENT
+ 				len = freeslot_len;
+ #endif
+ 				entry = freeslot;
+ 			}
+ 			goto NotFound;
+ 		}
+ 		if (entry->key == key)
+ 			goto Found;
+ 		if (entry->hash == hash && entry->key != dummy) {
+ 			if (!checked_error) {
+ 				checked_error = 1;
+ 				if (_PyErr_OCCURRED()) {
+ 					restore_error = 1;
+ 					PyErr_Fetch(&err_type, &err_value,
+ 						    &err_tb);
+ 				}
+ 			}
+ 			startkey = entry->key;
+ 			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+ 			if (cmp < 0)
+ 				PyErr_Clear();
+ 			if (table == so->table && entry->key == startkey) {
+ 				if (cmp > 0)
+ 					goto Found;
+ 			}
+ 			else {
+ 				/* The compare did major nasty stuff to the
+ 				 * set:  start over.
+  				 */
+  				set_lookup_insert_key(so, key, hash);
+  				goto Done;
+  			}
+ 		}
+ 		else if (entry->key == dummy && freeslot == NULL) {
+ #if BRENT
+ 			freeslot_len = len;
+ #endif
+ 			freeslot = entry;
+ 		}
+ 	}
+ 
+ Found:
+ 	/* ACTIVE */
+ 	Py_DECREF(key);
+ 	goto Done;
+ NotFound:
+ #if BRENT
+ 	if (len >= 2) {
+ 		alt_len = len;
+ 		opt_entry = opt_alt_entry = entry;
+ 		/* First slot in main branch */
+ 		/* Traverse main branch */
+ 		i = hash & mask;
+ 		perturb = hash;
+ 		for (j = 0; j < alt_len; j++, perturb >>= PERTURB_SHIFT) {
+ 			entry = &table[i & mask];
+ 			i = (i << 2) + i + perturb + 1;
+ 			assert(entry->key != NULL && entry->key != dummy);
+ 			/* Traverse alternate branch */
+ 			alt_perturb = entry->hash;
+ 			alt = entry->hash & mask;
+ 			for (k = 0; k < alt_len; k++, alt_perturb >>= PERTURB_SHIFT) {
+ 				alt_entry = &table[alt & mask];
+ 				alt = (alt << 2) + alt + alt_perturb + 1;
+ 				if (alt_entry->key == NULL || alt_entry->key == dummy) {
+ 					alt_len = k;
+ 					opt_entry = entry;
+ 					opt_alt_entry = alt_entry;
+ 					break;
+ 				}
+ 			}
+ 		}
+ 		/* An alternate was found ? */
+ 		if (opt_entry != opt_alt_entry) {
+ 			if (opt_alt_entry->key != NULL) {
+ 				/* Alternate was DUMMY */
+ 				so->used++;
+ 				Py_DECREF(dummy);
+ 			}
+ 			else {
+ 				/* Alternate was UNUSED */
+ 				so->used++;
+ 				so->fill++;
+ 			}
+ 			opt_alt_entry->key = opt_entry->key;
+ 			opt_alt_entry->hash = opt_entry->hash;
+ 			opt_entry->key = key;
+ 			opt_entry->hash = hash;
+ 			goto Done;
+ 		}
+ 		entry = opt_entry;
+ 	}
+ #endif
+ 	if (entry->key != NULL) {
+ 		/* DUMMY */
+ 		so->used++;
+ 		Py_DECREF(dummy);
+ 	}
+ 	else {
+ 		/* UNUSED */
+ 		so->fill++;
+ 		so->used++;
+ 	}
+ 	entry->key = key;
+ 	entry->hash = hash;
+ Done:
+ 	if (restore_error)
+ 		PyErr_Restore(err_type, err_value, err_tb);
+ }
+ /* </AP> */
+ 
  static void
  set_insert_key(register PySetObject *so, PyObject *key, long hash)
***************
*** 218,221 ****
--- 414,423 ----
  
  	assert(so->lookup != NULL);
+ 	/* <AP> */
+ 	if (so->lookup == set_lookkey) {
+ 		set_lookup_insert_key(so, key, hash);
+ 		return;
+ 	}
+ 	/* </AP> */
  	entry = so->lookup(so, key, hash);
  	if (entry->key == NULL) {
***************
*** 237,240 ****
--- 439,443 ----
  }
  
+ 
  /*
  Restructure the table by allocating a new table and reinserting all