1 

     2 /* Dictionary object implementation using a hash table */

     3 

     4 /* The distribution includes a separate file, Objects/dictnotes.txt,

     5    describing explorations into dictionary design and optimization.

     6    It covers typical dictionary use patterns, the parameters for

     7    tuning dictionaries, and several ideas for possible optimizations.

     8 */

     9 

    10 #include "Python.h"

    11 

    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 /* Define this out if you don't want conversion statistics on exit. */

    28 #undef SHOW_CONVERSION_COUNTS

    29 

    30 /* See large comment block below.  This must be >= 1. */

    31 #define PERTURB_SHIFT 5

    32 

    33 /*

    34 Major subtleties ahead:  Most hash schemes depend on having a "good" hash

    35 function, in the sense of simulating randomness.  Python doesn't:  its most

    36 important hash functions (for strings and ints) are very regular in common

    37 cases:

    38 

    39 >>> map(hash, (0, 1, 2, 3))

    40 [0, 1, 2, 3]

    41 >>> map(hash, ("namea", "nameb", "namec", "named"))

    42 [-1658398457, -1658398460, -1658398459, -1658398462]

    43 >>>

    44 

    45 This isn't necessarily bad!  To the contrary, in a table of size 2**i, taking

    46 the low-order i bits as the initial table index is extremely fast, and there

    47 are no collisions at all for dicts indexed by a contiguous range of ints.

    48 The same is approximately true when keys are "consecutive" strings.  So this

    49 gives better-than-random behavior in common cases, and that's very desirable.

    50 

    51 OTOH, when collisions occur, the tendency to fill contiguous slices of the

    52 hash table makes a good collision resolution strategy crucial.  Taking only

    53 the last i bits of the hash code is also vulnerable:  for example, consider

    54 [i << 16 for i in range(20000)] as a set of keys.  Since ints are their own

    55 hash codes, and this fits in a dict of size 2**15, the last 15 bits of every

    56 hash code are all 0:  they *all* map to the same table index.

    57 

    58 But catering to unusual cases should not slow the usual ones, so we just take

    59 the last i bits anyway.  It's up to collision resolution to do the rest.  If

    60 we *usually* find the key we're looking for on the first try (and, it turns

    61 out, we usually do -- the table load factor is kept under 2/3, so the odds

    62 are solidly in our favor), then it makes best sense to keep the initial index

    63 computation dirt cheap.

    64 

    65 The first half of collision resolution is to visit table indices via this

    66 recurrence:

    67 

    68     j = ((5*j) + 1) mod 2**i

    69 

    70 For any initial j in range(2**i), repeating that 2**i times generates each

    71 int in range(2**i) exactly once (see any text on random-number generation for

    72 proof).  By itself, this doesn't help much:  like linear probing (setting

    73 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed

    74 order.  This would be bad, except that's not the only thing we do, and it's

    75 actually *good* in the common cases where hash keys are consecutive.  In an

    76 example that's really too small to make this entirely clear, for a table of

    77 size 2**3 the order of indices is:

    78 

    79     0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]

    80 

    81 If two things come in at index 5, the first place we look after is index 2,

    82 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.

    83 Linear probing is deadly in this case because there the fixed probe order

    84 is the *same* as the order consecutive keys are likely to arrive.  But it's

    85 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,

    86 and certain that consecutive hash codes do not.

    87 

    88 The other half of the strategy is to get the other bits of the hash code

    89 into play.  This is done by initializing a (unsigned) vrbl "perturb" to the

    90 full hash code, and changing the recurrence to:

    91 

    92     j = (5*j) + 1 + perturb;

    93     perturb >>= PERTURB_SHIFT;

    94     use j % 2**i as the next table index;

    95 

    96 Now the probe sequence depends (eventually) on every bit in the hash code,

    97 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,

    98 because it quickly magnifies small differences in the bits that didn't affect

    99 the initial index.  Note that because perturb is unsigned, if the recurrence

   100 is executed often enough perturb eventually becomes and remains 0.  At that

   101 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and

   102 that's certain to find an empty slot eventually (since it generates every int

   103 in range(2**i), and we make sure there's always at least one empty slot).

   104 

   105 Selecting a good value for PERTURB_SHIFT is a balancing act.  You want it

   106 small so that the high bits of the hash code continue to affect the probe

   107 sequence across iterations; but you want it large so that in really bad cases

   108 the high-order hash bits have an effect on early iterations.  5 was "the

   109 best" in minimizing total collisions across experiments Tim Peters ran (on

   110 both normal and pathological cases), but 4 and 6 weren't significantly worse.

   111 

   112 Historical:  Reimer Behrends contributed the idea of using a polynomial-based

   113 approach, using repeated multiplication by x in GF(2**n) where an irreducible

   114 polynomial for each table size was chosen such that x was a primitive root.

   115 Christian Tismer later extended that to use division by x instead, as an

   116 efficient way to get the high bits of the hash code into play.  This scheme

   117 also gave excellent collision statistics, but was more expensive:  two

   118 if-tests were required inside the loop; computing "the next" index took about

   119 the same number of operations but without as much potential parallelism

   120 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the

   121 above, and then shifting perturb can be done while the table index is being

   122 masked); and the PyDictObject struct required a member to hold the table's

   123 polynomial.  In Tim's experiments the current scheme ran faster, produced

   124 equally good collision statistics, needed less code & used less memory.

   125 

   126 Theoretical Python 2.5 headache:  hash codes are only C "long", but

   127 sizeof(Py_ssize_t) > sizeof(long) may be possible.  In that case, and if a

   128 dict is genuinely huge, then only the slots directly reachable via indexing

   129 by a C long can be the first slot in a probe sequence.  The probe sequence

   130 will still eventually reach every slot in the table, but the collision rate

   131 on initial probes may be much higher than this scheme was designed for.

   132 Getting a hash code as fat as Py_ssize_t is the only real cure.  But in

   133 practice, this probably won't make a lick of difference for many years (at

   134 which point everyone will have terabytes of RAM on 64-bit boxes).

   135 */

   136 

   137 /* Object used as dummy key to fill deleted entries */

   138 static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */

   139 

   140 #ifdef Py_REF_DEBUG

   141 PyObject *

   142 _PyDict_Dummy(void)

   143 {

   144 	return dummy;

   145 }

   146 #endif

   147 

   148 /* forward declarations */

   149 static PyDictEntry *

   150 lookdict_string(PyDictObject *mp, PyObject *key, long hash);

   151 

   152 #ifdef SHOW_CONVERSION_COUNTS

   153 static long created = 0L;

   154 static long converted = 0L;

   155 

   156 static void

   157 show_counts(void)

   158 {

   159 	fprintf(stderr, "created %ld string dicts\n", created);

   160 	fprintf(stderr, "converted %ld to normal dicts\n", converted);

   161 	fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);

   162 }

   163 #endif

   164 

   165 /* Debug statistic to compare allocations with reuse through the free list */

   166 #undef SHOW_ALLOC_COUNT

   167 #ifdef SHOW_ALLOC_COUNT

   168 static size_t count_alloc = 0;

   169 static size_t count_reuse = 0;

   170 

   171 static void

   172 show_alloc(void)

   173 {

   174 	fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",

   175 		count_alloc);

   176 	fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T

   177 		"d\n", count_reuse);

   178 	fprintf(stderr, "%.2f%% reuse rate\n\n",

   179 		(100.0*count_reuse/(count_alloc+count_reuse)));

   180 }

   181 #endif

   182 

   183 /* Initialization macros.

   184    There are two ways to create a dict:  PyDict_New() is the main C API

   185    function, and the tp_new slot maps to dict_new().  In the latter case we

   186    can save a little time over what PyDict_New does because it's guaranteed

   187    that the PyDictObject struct is already zeroed out.

   188    Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have

   189    an excellent reason not to).

   190 */

   191 

   192 #define INIT_NONZERO_DICT_SLOTS(mp) do {				\

   193 	(mp)->ma_table = (mp)->ma_smalltable;				\

   194 	(mp)->ma_mask = PyDict_MINSIZE - 1;				\

   195     } while(0)

   196 

   197 #define EMPTY_TO_MINSIZE(mp) do {					\

   198 	memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable));	\

   199 	(mp)->ma_used = (mp)->ma_fill = 0;				\

   200 	INIT_NONZERO_DICT_SLOTS(mp);					\

   201     } while(0)

   202 

   203 /* Dictionary reuse scheme to save calls to malloc, free, and memset */

   204 #ifndef PyDict_MAXFREELIST

   205 #define PyDict_MAXFREELIST 80

   206 #endif

   207 static PyDictObject *free_list[PyDict_MAXFREELIST];

   208 static int numfree = 0;

   209 

   210 void

   211 PyDict_Fini(void)

   212 {

   213 	PyDictObject *op;

   214 

   215 	while (numfree) {

   216 		op = free_list[--numfree];

   217 		assert(PyDict_CheckExact(op));

   218 		PyObject_GC_Del(op);

   219 	}

   220 }

   221 

   222 PyObject *

   223 PyDict_New(void)

   224 {

   225 	register PyDictObject *mp;

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

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

   228 		if (dummy == NULL)

   229 			return NULL;

   230 #ifdef SHOW_CONVERSION_COUNTS

   231 		Py_AtExit(show_counts);

   232 #endif

   233 #ifdef SHOW_ALLOC_COUNT

   234 		Py_AtExit(show_alloc);

   235 #endif

   236 	}

   237 	if (numfree) {

   238 		mp = free_list[--numfree];

   239 		assert (mp != NULL);

   240 		assert (Py_TYPE(mp) == &PyDict_Type);

   241 		_Py_NewReference((PyObject *)mp);

   242 		if (mp->ma_fill) {

   243 			EMPTY_TO_MINSIZE(mp);

   244 		} else {

   245 			/* At least set ma_table and ma_mask; these are wrong

   246 			   if an empty but presized dict is added to freelist */

   247 			INIT_NONZERO_DICT_SLOTS(mp);

   248 		}

   249 		assert (mp->ma_used == 0);

   250 		assert (mp->ma_table == mp->ma_smalltable);

   251 		assert (mp->ma_mask == PyDict_MINSIZE - 1);

   252 #ifdef SHOW_ALLOC_COUNT

   253 		count_reuse++;

   254 #endif

   255 	} else {

   256 		mp = PyObject_GC_New(PyDictObject, &PyDict_Type);

   257 		if (mp == NULL)

   258 			return NULL;

   259 		EMPTY_TO_MINSIZE(mp);

   260 #ifdef SHOW_ALLOC_COUNT

   261 		count_alloc++;

   262 #endif

   263 	}

   264 	mp->ma_lookup = lookdict_string;

   265 #ifdef SHOW_CONVERSION_COUNTS

   266 	++created;

   267 #endif

   268 	_PyObject_GC_TRACK(mp);

   269 	return (PyObject *)mp;

   270 }

   271 

   272 /*

   273 The basic lookup function used by all operations.

   274 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.

   275 Open addressing is preferred over chaining since the link overhead for

   276 chaining would be substantial (100% with typical malloc overhead).

   277 

   278 The initial probe index is computed as hash mod the table size. Subsequent

   279 probe indices are computed as explained earlier.

   280 

   281 All arithmetic on hash should ignore overflow.

   282 

   283 (The details in this version are due to Tim Peters, building on many past

   284 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and

   285 Christian Tismer).

   286 

   287 lookdict() is general-purpose, and may return NULL if (and only if) a

   288 comparison raises an exception (this was new in Python 2.5).

   289 lookdict_string() below is specialized to string keys, comparison of which can

   290 never raise an exception; that function can never return NULL.  For both, when

   291 the key isn't found a PyDictEntry* is returned for which the me_value field is

   292 NULL; this is the slot in the dict at which the key would have been found, and

   293 the caller can (if it wishes) add the <key, value> pair to the returned

   294 PyDictEntry*.

   295 */

   296 static PyDictEntry *

   297 lookdict(PyDictObject *mp, PyObject *key, register long hash)

   298 {

   299 	register size_t i;

   300 	register size_t perturb;

   301 	register PyDictEntry *freeslot;

   302 	register size_t mask = (size_t)mp->ma_mask;

   303 	PyDictEntry *ep0 = mp->ma_table;

   304 	register PyDictEntry *ep;

   305 	register int cmp;

   306 	PyObject *startkey;

   307 

   308 	i = (size_t)hash & mask;

   309 	ep = &ep0[i];

   310 	if (ep->me_key == NULL || ep->me_key == key)

   311 		return ep;

   312 

   313 	if (ep->me_key == dummy)

   314 		freeslot = ep;

   315 	else {

   316 		if (ep->me_hash == hash) {

   317 			startkey = ep->me_key;

   318 			Py_INCREF(startkey);

   319 			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

   320 			Py_DECREF(startkey);

   321 			if (cmp < 0)

   322 				return NULL;

   323 			if (ep0 == mp->ma_table && ep->me_key == startkey) {

   324 				if (cmp > 0)

   325 					return ep;

   326 			}

   327 			else {

   328 				/* The compare did major nasty stuff to the

   329 				 * dict:  start over.

   330 				 * XXX A clever adversary could prevent this

   331 				 * XXX from terminating.

   332  				 */

   333  				return lookdict(mp, key, hash);

   334  			}

   335 		}

   336 		freeslot = NULL;

   337 	}

   338 

   339 	/* In the loop, me_key == dummy is by far (factor of 100s) the

   340 	   least likely outcome, so test for that last. */

   341 	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {

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

   343 		ep = &ep0[i & mask];

   344 		if (ep->me_key == NULL)

   345 			return freeslot == NULL ? ep : freeslot;

   346 		if (ep->me_key == key)

   347 			return ep;

   348 		if (ep->me_hash == hash && ep->me_key != dummy) {

   349 			startkey = ep->me_key;

   350 			Py_INCREF(startkey);

   351 			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

   352 			Py_DECREF(startkey);

   353 			if (cmp < 0)

   354 				return NULL;

   355 			if (ep0 == mp->ma_table && ep->me_key == startkey) {

   356 				if (cmp > 0)

   357 					return ep;

   358 			}

   359 			else {

   360 				/* The compare did major nasty stuff to the

   361 				 * dict:  start over.

   362 				 * XXX A clever adversary could prevent this

   363 				 * XXX from terminating.

   364  				 */

   365  				return lookdict(mp, key, hash);

   366  			}

   367 		}

   368 		else if (ep->me_key == dummy && freeslot == NULL)

   369 			freeslot = ep;

   370 	}

   371 	assert(0);	/* NOT REACHED */

   372 	return 0;

   373 }

   374 

   375 /*

   376  * Hacked up version of lookdict which can assume keys are always strings;

   377  * this assumption allows testing for errors during PyObject_RichCompareBool()

   378  * to be dropped; string-string comparisons never raise exceptions.  This also

   379  * means we don't need to go through PyObject_RichCompareBool(); we can always

   380  * use _PyString_Eq() directly.

   381  *

   382  * This is valuable because dicts with only string keys are very common.

   383  */

   384 static PyDictEntry *

   385 lookdict_string(PyDictObject *mp, PyObject *key, register long hash)

   386 {

   387 	register size_t i;

   388 	register size_t perturb;

   389 	register PyDictEntry *freeslot;

   390 	register size_t mask = (size_t)mp->ma_mask;

   391 	PyDictEntry *ep0 = mp->ma_table;

   392 	register PyDictEntry *ep;

   393 

   394 	/* Make sure this function doesn't have to handle non-string keys,

   395 	   including subclasses of str; e.g., one reason to subclass

   396 	   strings is to override __eq__, and for speed we don't cater to

   397 	   that here. */

   398 	if (!PyString_CheckExact(key)) {

   399 #ifdef SHOW_CONVERSION_COUNTS

   400 		++converted;

   401 #endif

   402 		mp->ma_lookup = lookdict;

   403 		return lookdict(mp, key, hash);

   404 	}

   405 	i = hash & mask;

   406 	ep = &ep0[i];

   407 	if (ep->me_key == NULL || ep->me_key == key)

   408 		return ep;

   409 	if (ep->me_key == dummy)

   410 		freeslot = ep;

   411 	else {

   412 		if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))

   413 			return ep;

   414 		freeslot = NULL;

   415 	}

   416 

   417 	/* In the loop, me_key == dummy is by far (factor of 100s) the

   418 	   least likely outcome, so test for that last. */

   419 	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {

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

   421 		ep = &ep0[i & mask];

   422 		if (ep->me_key == NULL)

   423 			return freeslot == NULL ? ep : freeslot;

   424 		if (ep->me_key == key

   425 		    || (ep->me_hash == hash

   426 		        && ep->me_key != dummy

   427 			&& _PyString_Eq(ep->me_key, key)))

   428 			return ep;

   429 		if (ep->me_key == dummy && freeslot == NULL)

   430 			freeslot = ep;

   431 	}

   432 	assert(0);	/* NOT REACHED */

   433 	return 0;

   434 }

   435 

   436 /*

   437 Internal routine to insert a new item into the table.

   438 Used both by the internal resize routine and by the public insert routine.

   439 Eats a reference to key and one to value.

   440 Returns -1 if an error occurred, or 0 on success.

   441 */

   442 static int

   443 insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)

   444 {

   445 	PyObject *old_value;

   446 	register PyDictEntry *ep;

   447 	typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);

   448 

   449 	assert(mp->ma_lookup != NULL);

   450 	ep = mp->ma_lookup(mp, key, hash);

   451 	if (ep == NULL) {

   452 		Py_DECREF(key);

   453 		Py_DECREF(value);

   454 		return -1;

   455 	}

   456 	if (ep->me_value != NULL) {

   457 		old_value = ep->me_value;

   458 		ep->me_value = value;

   459 		Py_DECREF(old_value); /* which **CAN** re-enter */

   460 		Py_DECREF(key);

   461 	}

   462 	else {

   463 		if (ep->me_key == NULL)

   464 			mp->ma_fill++;

   465 		else {

   466 			assert(ep->me_key == dummy);

   467 			Py_DECREF(dummy);

   468 		}

   469 		ep->me_key = key;

   470 		ep->me_hash = (Py_ssize_t)hash;

   471 		ep->me_value = value;

   472 		mp->ma_used++;

   473 	}

   474 	return 0;

   475 }

   476 

   477 /*

   478 Internal routine used by dictresize() to insert an item which is

   479 known to be absent from the dict.  This routine also assumes that

   480 the dict contains no deleted entries.  Besides the performance benefit,

   481 using insertdict() in dictresize() is dangerous (SF bug #1456209).

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

   483 is responsible for incref'ing `key` and `value`.

   484 */

   485 static void

   486 insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,

   487 		 PyObject *value)

   488 {

   489 	register size_t i;

   490 	register size_t perturb;

   491 	register size_t mask = (size_t)mp->ma_mask;

   492 	PyDictEntry *ep0 = mp->ma_table;

   493 	register PyDictEntry *ep;

   494 

   495 	i = hash & mask;

   496 	ep = &ep0[i];

   497 	for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {

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

   499 		ep = &ep0[i & mask];

   500 	}

   501 	assert(ep->me_value == NULL);

   502 	mp->ma_fill++;

   503 	ep->me_key = key;

   504 	ep->me_hash = (Py_ssize_t)hash;

   505 	ep->me_value = value;

   506 	mp->ma_used++;

   507 }

   508 

   509 /*

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

   511 items again.  When entries have been deleted, the new table may

   512 actually be smaller than the old one.

   513 */

   514 static int

   515 dictresize(PyDictObject *mp, Py_ssize_t minused)

   516 {

   517 	Py_ssize_t newsize;

   518 	PyDictEntry *oldtable, *newtable, *ep;

   519 	Py_ssize_t i;

   520 	int is_oldtable_malloced;

   521 	PyDictEntry small_copy[PyDict_MINSIZE];

   522 

   523 	assert(minused >= 0);

   524 

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

   526 	for (newsize = PyDict_MINSIZE;

   527 	     newsize <= minused && newsize > 0;

   528 	     newsize <<= 1)

   529 		;

   530 	if (newsize <= 0) {

   531 		PyErr_NoMemory();

   532 		return -1;

   533 	}

   534 

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

   536 	oldtable = mp->ma_table;

   537 	assert(oldtable != NULL);

   538 	is_oldtable_malloced = oldtable != mp->ma_smalltable;

   539 

   540 	if (newsize == PyDict_MINSIZE) {

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

   542 		newtable = mp->ma_smalltable;

   543 		if (newtable == oldtable) {

   544 			if (mp->ma_fill == mp->ma_used) {

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

   546 				return 0;

   547 			}

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

   549 			   table anyway to purge old dummy entries.

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

   551 			   as lookdict needs at least one virgin slot to

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

   553 			   merely desirable, as dummies slow searches. */

   554 			assert(mp->ma_fill > mp->ma_used);

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

   556 			oldtable = small_copy;

   557 		}

   558 	}

   559 	else {

   560 		newtable = PyMem_NEW(PyDictEntry, newsize);

   561 		if (newtable == NULL) {

   562 			PyErr_NoMemory();

   563 			return -1;

   564 		}

   565 	}

   566 

   567 	/* Make the dict empty, using the new table. */

   568 	assert(newtable != oldtable);

   569 	mp->ma_table = newtable;

   570 	mp->ma_mask = newsize - 1;

   571 	memset(newtable, 0, sizeof(PyDictEntry) * newsize);

   572 	mp->ma_used = 0;

   573 	i = mp->ma_fill;

   574 	mp->ma_fill = 0;

   575 

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

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

   578 	for (ep = oldtable; i > 0; ep++) {

   579 		if (ep->me_value != NULL) {	/* active entry */

   580 			--i;

   581 			insertdict_clean(mp, ep->me_key, (long)ep->me_hash,

   582 					 ep->me_value);

   583 		}

   584 		else if (ep->me_key != NULL) {	/* dummy entry */

   585 			--i;

   586 			assert(ep->me_key == dummy);

   587 			Py_DECREF(ep->me_key);

   588 		}

   589 		/* else key == value == NULL:  nothing to do */

   590 	}

   591 

   592 	if (is_oldtable_malloced)

   593 		PyMem_DEL(oldtable);

   594 	return 0;

   595 }

   596 

   597 /* Create a new dictionary pre-sized to hold an estimated number of elements.

   598    Underestimates are okay because the dictionary will resize as necessary.

   599    Overestimates just mean the dictionary will be more sparse than usual.

   600 */

   601 

   602 PyObject *

   603 _PyDict_NewPresized(Py_ssize_t minused)

   604 {

   605 	PyObject *op = PyDict_New();

   606 

   607 	if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {

   608 		Py_DECREF(op);

   609 		return NULL;

   610 	}

   611 	return op;

   612 }

   613 

   614 /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors

   615  * that may occur (originally dicts supported only string keys, and exceptions

   616  * weren't possible).  So, while the original intent was that a NULL return

   617  * meant the key wasn't present, in reality it can mean that, or that an error

   618  * (suppressed) occurred while computing the key's hash, or that some error

   619  * (suppressed) occurred when comparing keys in the dict's internal probe

   620  * sequence.  A nasty example of the latter is when a Python-coded comparison

   621  * function hits a stack-depth error, which can cause this to return NULL

   622  * even if the key is present.

   623  */

   624 PyObject *

   625 PyDict_GetItem(PyObject *op, PyObject *key)

   626 {

   627 	long hash;

   628 	PyDictObject *mp = (PyDictObject *)op;

   629 	PyDictEntry *ep;

   630 	PyThreadState *tstate;

   631 	if (!PyDict_Check(op))

   632 		return NULL;

   633 	if (!PyString_CheckExact(key) ||

   634 	    (hash = ((PyStringObject *) key)->ob_shash) == -1)

   635 	{

   636 		hash = PyObject_Hash(key);

   637 		if (hash == -1) {

   638 			PyErr_Clear();

   639 			return NULL;

   640 		}

   641 	}

   642 

   643 	/* We can arrive here with a NULL tstate during initialization:

   644 	   try running "python -Wi" for an example related to string

   645 	   interning.  Let's just hope that no exception occurs then... */

   646 	tstate = _PyThreadState_Current;

   647 	if (tstate != NULL && tstate->curexc_type != NULL) {

   648 		/* preserve the existing exception */

   649 		PyObject *err_type, *err_value, *err_tb;

   650 		PyErr_Fetch(&err_type, &err_value, &err_tb);

   651 		ep = (mp->ma_lookup)(mp, key, hash);

   652 		/* ignore errors */

   653 		PyErr_Restore(err_type, err_value, err_tb);

   654 		if (ep == NULL)

   655 			return NULL;

   656 	}

   657 	else {

   658 		ep = (mp->ma_lookup)(mp, key, hash);

   659 		if (ep == NULL) {

   660 			PyErr_Clear();

   661 			return NULL;

   662 		}

   663 	}

   664 	return ep->me_value;

   665 }

   666 

   667 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the

   668  * dictionary if it's merely replacing the value for an existing key.

   669  * This means that it's safe to loop over a dictionary with PyDict_Next()

   670  * and occasionally replace a value -- but you can't insert new keys or

   671  * remove them.

   672  */

   673 int

   674 PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)

   675 {

   676 	register PyDictObject *mp;

   677 	register long hash;

   678 	register Py_ssize_t n_used;

   679 

   680 	if (!PyDict_Check(op)) {

   681 		PyErr_BadInternalCall();

   682 		return -1;

   683 	}

   684 	assert(key);

   685 	assert(value);

   686 	mp = (PyDictObject *)op;

   687 	if (PyString_CheckExact(key)) {

   688 		hash = ((PyStringObject *)key)->ob_shash;

   689 		if (hash == -1)

   690 			hash = PyObject_Hash(key);

   691 	}

   692 	else {

   693 		hash = PyObject_Hash(key);

   694 		if (hash == -1)

   695 			return -1;

   696 	}

   697 	assert(mp->ma_fill <= mp->ma_mask);  /* at least one empty slot */

   698 	n_used = mp->ma_used;

   699 	Py_INCREF(value);

   700 	Py_INCREF(key);

   701 	if (insertdict(mp, key, hash, value) != 0)

   702 		return -1;

   703 	/* If we added a key, we can safely resize.  Otherwise just return!

   704 	 * If fill >= 2/3 size, adjust size.  Normally, this doubles or

   705 	 * quaduples the size, but it's also possible for the dict to shrink

   706 	 * (if ma_fill is much larger than ma_used, meaning a lot of dict

   707 	 * keys have been * deleted).

   708 	 *

   709 	 * Quadrupling the size improves average dictionary sparseness

   710 	 * (reducing collisions) at the cost of some memory and iteration

   711 	 * speed (which loops over every possible entry).  It also halves

   712 	 * the number of expensive resize operations in a growing dictionary.

   713 	 *

   714 	 * Very large dictionaries (over 50K items) use doubling instead.

   715 	 * This may help applications with severe memory constraints.

   716 	 */

   717 	if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))

   718 		return 0;

   719 	return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

   720 }

   721 

   722 int

   723 PyDict_DelItem(PyObject *op, PyObject *key)

   724 {

   725 	register PyDictObject *mp;

   726 	register long hash;

   727 	register PyDictEntry *ep;

   728 	PyObject *old_value, *old_key;

   729 

   730 	if (!PyDict_Check(op)) {

   731 		PyErr_BadInternalCall();

   732 		return -1;

   733 	}

   734 	assert(key);

   735 	if (!PyString_CheckExact(key) ||

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

   737 		hash = PyObject_Hash(key);

   738 		if (hash == -1)

   739 			return -1;

   740 	}

   741 	mp = (PyDictObject *)op;

   742 	ep = (mp->ma_lookup)(mp, key, hash);

   743 	if (ep == NULL)

   744 		return -1;

   745 	if (ep->me_value == NULL) {

   746 		set_key_error(key);

   747 		return -1;

   748 	}

   749 	old_key = ep->me_key;

   750 	Py_INCREF(dummy);

   751 	ep->me_key = dummy;

   752 	old_value = ep->me_value;

   753 	ep->me_value = NULL;

   754 	mp->ma_used--;

   755 	Py_DECREF(old_value);

   756 	Py_DECREF(old_key);

   757 	return 0;

   758 }

   759 

   760 void

   761 PyDict_Clear(PyObject *op)

   762 {

   763 	PyDictObject *mp;

   764 	PyDictEntry *ep, *table;

   765 	int table_is_malloced;

   766 	Py_ssize_t fill;

   767 	PyDictEntry small_copy[PyDict_MINSIZE];

   768 #ifdef Py_DEBUG

   769 	Py_ssize_t i, n;

   770 #endif

   771 

   772 	if (!PyDict_Check(op))

   773 		return;

   774 	mp = (PyDictObject *)op;

   775 #ifdef Py_DEBUG

   776 	n = mp->ma_mask + 1;

   777 	i = 0;

   778 #endif

   779 

   780 	table = mp->ma_table;

   781 	assert(table != NULL);

   782 	table_is_malloced = table != mp->ma_smalltable;

   783 

   784 	/* This is delicate.  During the process of clearing the dict,

   785 	 * decrefs can cause the dict to mutate.  To avoid fatal confusion

   786 	 * (voice of experience), we have to make the dict empty before

   787 	 * clearing the slots, and never refer to anything via mp->xxx while

   788 	 * clearing.

   789 	 */

   790 	fill = mp->ma_fill;

   791 	if (table_is_malloced)

   792 		EMPTY_TO_MINSIZE(mp);

   793 

   794 	else if (fill > 0) {

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

   796 		 * Afraid the only safe way is to copy the dict entries into

   797 		 * another small table first.

   798 		 */

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

   800 		table = small_copy;

   801 		EMPTY_TO_MINSIZE(mp);

   802 	}

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

   804 

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

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

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

   808 	 */

   809 	for (ep = table; fill > 0; ++ep) {

   810 #ifdef Py_DEBUG

   811 		assert(i < n);

   812 		++i;

   813 #endif

   814 		if (ep->me_key) {

   815 			--fill;

   816 			Py_DECREF(ep->me_key);

   817 			Py_XDECREF(ep->me_value);

   818 		}

   819 #ifdef Py_DEBUG

   820 		else

   821 			assert(ep->me_value == NULL);

   822 #endif

   823 	}

   824 

   825 	if (table_is_malloced)

   826 		PyMem_DEL(table);

   827 }

   828 

   829 /*

   830  * Iterate over a dict.  Use like so:

   831  *

   832  *     Py_ssize_t i;

   833  *     PyObject *key, *value;

   834  *     i = 0;   # important!  i should not otherwise be changed by you

   835  *     while (PyDict_Next(yourdict, &i, &key, &value)) {

   836  *              Refer to borrowed references in key and value.

   837  *     }

   838  *

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

   840  * mutates the dict.  One exception:  it is safe if the loop merely changes

   841  * the values associated with the keys (but doesn't insert new keys or

   842  * delete keys), via PyDict_SetItem().

   843  */

   844 int

   845 PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)

   846 {

   847 	register Py_ssize_t i;

   848 	register Py_ssize_t mask;

   849 	register PyDictEntry *ep;

   850 

   851 	if (!PyDict_Check(op))

   852 		return 0;

   853 	i = *ppos;

   854 	if (i < 0)

   855 		return 0;

   856 	ep = ((PyDictObject *)op)->ma_table;

   857 	mask = ((PyDictObject *)op)->ma_mask;

   858 	while (i <= mask && ep[i].me_value == NULL)

   859 		i++;

   860 	*ppos = i+1;

   861 	if (i > mask)

   862 		return 0;

   863 	if (pkey)

   864 		*pkey = ep[i].me_key;

   865 	if (pvalue)

   866 		*pvalue = ep[i].me_value;

   867 	return 1;

   868 }

   869 

   870 /* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/

   871 int

   872 _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)

   873 {

   874 	register Py_ssize_t i;

   875 	register Py_ssize_t mask;

   876 	register PyDictEntry *ep;

   877 

   878 	if (!PyDict_Check(op))

   879 		return 0;

   880 	i = *ppos;

   881 	if (i < 0)

   882 		return 0;

   883 	ep = ((PyDictObject *)op)->ma_table;

   884 	mask = ((PyDictObject *)op)->ma_mask;

   885 	while (i <= mask && ep[i].me_value == NULL)

   886 		i++;

   887 	*ppos = i+1;

   888 	if (i > mask)

   889 		return 0;

   890         *phash = (long)(ep[i].me_hash);

   891 	if (pkey)

   892 		*pkey = ep[i].me_key;

   893 	if (pvalue)

   894 		*pvalue = ep[i].me_value;

   895 	return 1;

   896 }

   897 

   898 /* Methods */

   899 

   900 static void

   901 dict_dealloc(register PyDictObject *mp)

   902 {

   903 	register PyDictEntry *ep;

   904 	Py_ssize_t fill = mp->ma_fill;

   905  	PyObject_GC_UnTrack(mp);

   906 	Py_TRASHCAN_SAFE_BEGIN(mp)

   907 	for (ep = mp->ma_table; fill > 0; ep++) {

   908 		if (ep->me_key) {

   909 			--fill;

   910 			Py_DECREF(ep->me_key);

   911 			Py_XDECREF(ep->me_value);

   912 		}

   913 	}

   914 	if (mp->ma_table != mp->ma_smalltable)

   915 		PyMem_DEL(mp->ma_table);

   916 	if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)

   917 		free_list[numfree++] = mp;

   918 	else

   919 		Py_TYPE(mp)->tp_free((PyObject *)mp);

   920 	Py_TRASHCAN_SAFE_END(mp)

   921 }

   922 

   923 static int

   924 dict_print(register PyDictObject *mp, register FILE *fp, register int flags)

   925 {

   926 	register Py_ssize_t i;

   927 	register Py_ssize_t any;

   928 	int status;

   929 

   930 	status = Py_ReprEnter((PyObject*)mp);

   931 	if (status != 0) {

   932 		if (status < 0)

   933 			return status;

   934 		Py_BEGIN_ALLOW_THREADS

   935 		fprintf(fp, "{...}");

   936 		Py_END_ALLOW_THREADS

   937 		return 0;

   938 	}

   939 

   940 	Py_BEGIN_ALLOW_THREADS

   941 	fprintf(fp, "{");

   942 	Py_END_ALLOW_THREADS

   943 	any = 0;

   944 	for (i = 0; i <= mp->ma_mask; i++) {

   945 		PyDictEntry *ep = mp->ma_table + i;

   946 		PyObject *pvalue = ep->me_value;

   947 		if (pvalue != NULL) {

   948 			/* Prevent PyObject_Repr from deleting value during

   949 			   key format */

   950 			Py_INCREF(pvalue);

   951 			if (any++ > 0) {

   952 				Py_BEGIN_ALLOW_THREADS

   953 				fprintf(fp, ", ");

   954 				Py_END_ALLOW_THREADS

   955 			}

   956 			if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {

   957 				Py_DECREF(pvalue);

   958 				Py_ReprLeave((PyObject*)mp);

   959 				return -1;

   960 			}

   961 			Py_BEGIN_ALLOW_THREADS

   962 			fprintf(fp, ": ");

   963 			Py_END_ALLOW_THREADS

   964 			if (PyObject_Print(pvalue, fp, 0) != 0) {

   965 				Py_DECREF(pvalue);

   966 				Py_ReprLeave((PyObject*)mp);

   967 				return -1;

   968 			}

   969 			Py_DECREF(pvalue);

   970 		}

   971 	}

   972 	Py_BEGIN_ALLOW_THREADS

   973 	fprintf(fp, "}");

   974 	Py_END_ALLOW_THREADS

   975 	Py_ReprLeave((PyObject*)mp);

   976 	return 0;

   977 }

   978 

   979 static PyObject *

   980 dict_repr(PyDictObject *mp)

   981 {

   982 	Py_ssize_t i;

   983 	PyObject *s, *temp, *colon = NULL;

   984 	PyObject *pieces = NULL, *result = NULL;

   985 	PyObject *key, *value;

   986 

   987 	i = Py_ReprEnter((PyObject *)mp);

   988 	if (i != 0) {

   989 		return i > 0 ? PyString_FromString("{...}") : NULL;

   990 	}

   991 

   992 	if (mp->ma_used == 0) {

   993 		result = PyString_FromString("{}");

   994 		goto Done;

   995 	}

   996 

   997 	pieces = PyList_New(0);

   998 	if (pieces == NULL)

   999 		goto Done;

  1000 

  1001 	colon = PyString_FromString(": ");

  1002 	if (colon == NULL)

  1003 		goto Done;

  1004 

  1005 	/* Do repr() on each key+value pair, and insert ": " between them.

  1006 	   Note that repr may mutate the dict. */

  1007 	i = 0;

  1008 	while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {

  1009 		int status;

  1010 		/* Prevent repr from deleting value during key format. */

  1011 		Py_INCREF(value);

  1012 		s = PyObject_Repr(key);

  1013 		PyString_Concat(&s, colon);

  1014 		PyString_ConcatAndDel(&s, PyObject_Repr(value));

  1015 		Py_DECREF(value);

  1016 		if (s == NULL)

  1017 			goto Done;

  1018 		status = PyList_Append(pieces, s);

  1019 		Py_DECREF(s);  /* append created a new ref */

  1020 		if (status < 0)

  1021 			goto Done;

  1022 	}

  1023 

  1024 	/* Add "{}" decorations to the first and last items. */

  1025 	assert(PyList_GET_SIZE(pieces) > 0);

  1026 	s = PyString_FromString("{");

  1027 	if (s == NULL)

  1028 		goto Done;

  1029 	temp = PyList_GET_ITEM(pieces, 0);

  1030 	PyString_ConcatAndDel(&s, temp);

  1031 	PyList_SET_ITEM(pieces, 0, s);

  1032 	if (s == NULL)

  1033 		goto Done;

  1034 

  1035 	s = PyString_FromString("}");

  1036 	if (s == NULL)

  1037 		goto Done;

  1038 	temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);

  1039 	PyString_ConcatAndDel(&temp, s);

  1040 	PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);

  1041 	if (temp == NULL)

  1042 		goto Done;

  1043 

  1044 	/* Paste them all together with ", " between. */

  1045 	s = PyString_FromString(", ");

  1046 	if (s == NULL)

  1047 		goto Done;

  1048 	result = _PyString_Join(s, pieces);

  1049 	Py_DECREF(s);

  1050 

  1051 Done:

  1052 	Py_XDECREF(pieces);

  1053 	Py_XDECREF(colon);

  1054 	Py_ReprLeave((PyObject *)mp);

  1055 	return result;

  1056 }

  1057 

  1058 static Py_ssize_t

  1059 dict_length(PyDictObject *mp)

  1060 {

  1061 	return mp->ma_used;

  1062 }

  1063 

  1064 static PyObject *

  1065 dict_subscript(PyDictObject *mp, register PyObject *key)

  1066 {

  1067 	PyObject *v;

  1068 	long hash;

  1069 	PyDictEntry *ep;

  1070 	assert(mp->ma_table != NULL);

  1071 	if (!PyString_CheckExact(key) ||

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

  1073 		hash = PyObject_Hash(key);

  1074 		if (hash == -1)

  1075 			return NULL;

  1076 	}

  1077 	ep = (mp->ma_lookup)(mp, key, hash);

  1078 	if (ep == NULL)

  1079 		return NULL;

  1080 	v = ep->me_value;

  1081 	if (v == NULL) {

  1082 		if (!PyDict_CheckExact(mp)) {

  1083 			/* Look up __missing__ method if we're a subclass. */

  1084 		    	PyObject *missing;

  1085 			static PyObject *missing_str = NULL;

  1086 			if (missing_str == NULL)

  1087 				missing_str =

  1088 				  PyString_InternFromString("__missing__");

  1089 			missing = _PyType_Lookup(Py_TYPE(mp), missing_str);

  1090 			if (missing != NULL)

  1091 				return PyObject_CallFunctionObjArgs(missing,

  1092 					(PyObject *)mp, key, NULL);

  1093 		}

  1094 		set_key_error(key);

  1095 		return NULL;

  1096 	}

  1097 	else

  1098 		Py_INCREF(v);

  1099 	return v;

  1100 }

  1101 

  1102 static int

  1103 dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)

  1104 {

  1105 	if (w == NULL)

  1106 		return PyDict_DelItem((PyObject *)mp, v);

  1107 	else

  1108 		return PyDict_SetItem((PyObject *)mp, v, w);

  1109 }

  1110 

  1111 static PyMappingMethods dict_as_mapping = {

  1112 	(lenfunc)dict_length, /*mp_length*/

  1113 	(binaryfunc)dict_subscript, /*mp_subscript*/

  1114 	(objobjargproc)dict_ass_sub, /*mp_ass_subscript*/

  1115 };

  1116 

  1117 static PyObject *

  1118 dict_keys(register PyDictObject *mp)

  1119 {

  1120 	register PyObject *v;

  1121 	register Py_ssize_t i, j;

  1122 	PyDictEntry *ep;

  1123 	Py_ssize_t mask, n;

  1124 

  1125   again:

  1126 	n = mp->ma_used;

  1127 	v = PyList_New(n);

  1128 	if (v == NULL)

  1129 		return NULL;

  1130 	if (n != mp->ma_used) {

  1131 		/* Durnit.  The allocations caused the dict to resize.

  1132 		 * Just start over, this shouldn't normally happen.

  1133 		 */

  1134 		Py_DECREF(v);

  1135 		goto again;