/* Replacement code for popitem in dictobject.c */

static PyObject *
dict_popitem(dictobject *mp, PyObject *args)
{
        int i = 0;
        long hash;
        dictentry *ep;
        PyObject *res;
        PyObject *key = NULL;

        /* Allocate the result tuple before checking the size.  Believe it
         * or not, this allocation could trigger a garbage collection which
         * could empty the dict, so if we checked the size first and that
         * happened, the result would be an infinite loop (searching for an
         * entry that no longer exists).  Note that the usual popitem()
         * idiom is "while d: k, v = d.popitem()". so needing to throw the
         * tuple away  if the dict *is* empty isn't a significant
         * inefficiency -- possible, but unlikely in practice.
         */
        res = PyTuple_New(2);
        if (res == NULL)
                return NULL;
        if (mp->ma_used == 0) {
                Py_DECREF(res);
                PyErr_SetString(PyExc_KeyError,
                                "popitem(): dictionary is empty");
                return NULL;
        }

        if (!PyArg_ParseTuple(args, "|O:popitem", &key))
                return NULL;
        if (key != NULL) {
                if (!PyString_CheckExact(key) ||
                    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
                        hash = PyObject_Hash(key);
                        if (hash == -1)
                                return NULL;
                }
                ep = (mp->ma_lookup)(mp, key, hash);
                if (ep->me_value == NULL) {
                        PyErr_SetObject(PyExc_KeyError, key);
                        return NULL;
                }
		PyTuple_SET_ITEM(res, 0, ep->me_key);
		PyTuple_SET_ITEM(res, 1, ep->me_value);
                Py_INCREF(dummy);
                ep->me_key = dummy;
                ep->me_value = NULL;
                mp->ma_used--;
                return res;
        }

        /* Set ep to "the first" dict entry with a value.  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.
         */

        ep = &mp->ma_table[0];
        if (ep->me_value == NULL) {
                i = (int)ep->me_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 > mp->ma_mask || i < 1)
                        i = 1;  /* skip slot 0 */
                while ((ep = &mp->ma_table[i])->me_value == NULL) {
                        i++;
                        if (i > mp->ma_mask)
                                i = 1;
                }
        }
        PyTuple_SET_ITEM(res, 0, ep->me_key);
        PyTuple_SET_ITEM(res, 1, ep->me_value);
        Py_INCREF(dummy);
        ep->me_key = dummy;
        ep->me_value = NULL;
        mp->ma_used--;
        assert(mp->ma_table[0].me_value == NULL);
        mp->ma_table[0].me_hash = i + 1;  /* next place to start */
        return res;
}


/* Replacement docstring in dictobject.c */

static char popitem__doc__[] =
"D.popitem([k]) -> (k, v), remove and return an arbitrary or specified\n\
(key, value) pair as a 2-tuple; but raise KeyError if D is empty or if\n\
when k is specified and not D.has_key(k)";


/* Replacement registration code in dictobject.c */

        {"popitem",     (PyCFunction)dict_popitem,      METH_VARARGS,
         popitem__doc__},


/* Python test code */

## Basic demonstration of dict.popitem()

d = { 'a':'ay', 'b':'be', 'c':'cee' }
for k in d.keys():
        print len(d), d
        print d.popitem(k)
try:
        print d.popitem('d')
        print 'This line should not be reached'
except KeyError:
        print 'Dict Empty'


e = { 'a':'ay', 'b':'be', 'c':'cee' }
try:
        print e.popitem('nf')
        print 'This line should not be reached'
except KeyError:
        print 'Attempted retrieval of non-existant key'

try:
        print e[ ['a'] ]
        print 'This line should not be reached'
except TypeError:
        print 'Caught exception for unhashable object'


## More thorough exercise

import random
def tochar(x):  return '%c' % (32+x)
scope = 92

print 'Basic Check that new popitem works'
d = dict([ (tochar(i),i) for i in range(scope) ])
keys = d.keys()
random.shuffle(keys)

cnt = scope
for key in keys:
    assert cnt == len(d)
    #k, v = d.popitem(key)
    print k, v, len(d)
    assert k is key
    assert k == '%c' % (32+v)
    cnt -= 1
assert len(d) == 0
print 'Random element deletion check complete'