dictobject.c

python s60 1.4.5版本的源代码

	assert(PyDict_Check(d));
	assert(seq2 != NULL);

	it = PyObject_GetIter(seq2);
	if (it == NULL)
		return -1;

	for (i = 0; ; ++i) {
		PyObject *key, *value;
		int n;

		fast = NULL;
		item = PyIter_Next(it);
		if (item == NULL) {
			if (PyErr_Occurred())
				goto Fail;
			break;
		}

		/* Convert item to sequence, and verify length 2. */
		fast = PySequence_Fast(item, "");
		if (fast == NULL) {
			if (PyErr_ExceptionMatches(PyExc_TypeError))
				PyErr_Format(PyExc_TypeError,
					"cannot convert dictionary update "
					"sequence element #%d to a sequence",
					i);
			goto Fail;
		}
		n = PySequence_Fast_GET_SIZE(fast);
		if (n != 2) {
			PyErr_Format(PyExc_ValueError,
				     "dictionary update sequence element #%d "
				     "has length %d; 2 is required",
				     i, n);
			goto Fail;
		}

		/* Update/merge with this (key, value) pair. */
		key = PySequence_Fast_GET_ITEM(fast, 0);
		value = PySequence_Fast_GET_ITEM(fast, 1);
		if (override || PyDict_GetItem(d, key) == NULL) {
			int status = PyDict_SetItem(d, key, value);
			if (status < 0)
				goto Fail;
		}
		Py_DECREF(fast);
		Py_DECREF(item);
	}

	i = 0;
	goto Return;
Fail:
	Py_XDECREF(item);
	Py_XDECREF(fast);
	i = -1;
Return:
	Py_DECREF(it);
	return i;
}

DL_EXPORT(int)
PyDict_Update(PyObject *a, PyObject *b)
{
	return PyDict_Merge(a, b, 1);
}

DL_EXPORT(int)
PyDict_Merge(PyObject *a, PyObject *b, int override)
{
	register PyDictObject *mp, *other;
	register int i;
	dictentry *entry;

	/* We accept for the argument either a concrete dictionary object,
	 * or an abstract "mapping" object.  For the former, we can do
	 * things quite efficiently.  For the latter, we only require that
	 * PyMapping_Keys() and PyObject_GetItem() be supported.
	 */
	if (a == NULL || !PyDict_Check(a) || b == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}
	mp = (dictobject*)a;
	if (PyDict_Check(b)) {
		other = (dictobject*)b;
		if (other == mp || other->ma_used == 0)
			/* a.update(a) or a.update({}); nothing to do */
			return 0;
		/* Do one big resize at the start, rather than
		 * incrementally resizing as we insert new items.  Expect
		 * that there will be no (or few) overlapping keys.
		 */
		if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
		   if (dictresize(mp, (mp->ma_used + other->ma_used)*3/2) != 0)
			   return -1;
		}
		for (i = 0; i <= other->ma_mask; i++) {
			entry = &other->ma_table[i];
			if (entry->me_value != NULL &&
			    (override ||
			     PyDict_GetItem(a, entry->me_key) == NULL)) {
				Py_INCREF(entry->me_key);
				Py_INCREF(entry->me_value);
				insertdict(mp, entry->me_key, entry->me_hash,
					   entry->me_value);
			}
		}
	}
	else {
		/* Do it the generic, slower way */
		PyObject *keys = PyMapping_Keys(b);
		PyObject *iter;
		PyObject *key, *value;
		int status;

		if (keys == NULL)
			/* Docstring says this is equivalent to E.keys() so
			 * if E doesn't have a .keys() method we want
			 * AttributeError to percolate up.  Might as well
			 * do the same for any other error.
			 */
			return -1;

		iter = PyObject_GetIter(keys);
		Py_DECREF(keys);
		if (iter == NULL)
			return -1;

		for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
			if (!override && PyDict_GetItem(a, key) != NULL) {
				Py_DECREF(key);
				continue;
			}
			value = PyObject_GetItem(b, key);
			if (value == NULL) {
				Py_DECREF(iter);
				Py_DECREF(key);
				return -1;
			}
			status = PyDict_SetItem(a, key, value);
			Py_DECREF(key);
			Py_DECREF(value);
			if (status < 0) {
				Py_DECREF(iter);
				return -1;
			}
		}
		Py_DECREF(iter);
		if (PyErr_Occurred())
			/* Iterator completed, via error */
			return -1;
	}
	return 0;
}

static PyObject *
dict_copy(register dictobject *mp)
{
	return PyDict_Copy((PyObject*)mp);
}

DL_EXPORT(PyObject *)
PyDict_Copy(PyObject *o)
{
	register dictobject *mp;
	register int i;
	dictobject *copy;
	dictentry *entry;

	if (o == NULL || !PyDict_Check(o)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	mp = (dictobject *)o;
	copy = (dictobject *)PyDict_New();
	if (copy == NULL)
		return NULL;
	if (mp->ma_used > 0) {
		if (dictresize(copy, mp->ma_used*3/2) != 0)
			return NULL;
		for (i = 0; i <= mp->ma_mask; i++) {
			entry = &mp->ma_table[i];
			if (entry->me_value != NULL) {
				Py_INCREF(entry->me_key);
				Py_INCREF(entry->me_value);
				insertdict(copy, entry->me_key, entry->me_hash,
					   entry->me_value);
			}
		}
	}
	return (PyObject *)copy;
}

DL_EXPORT(int)
PyDict_Size(PyObject *mp)
{
	if (mp == NULL || !PyDict_Check(mp)) {
		PyErr_BadInternalCall();
		return 0;
	}
	return ((dictobject *)mp)->ma_used;
}

DL_EXPORT(PyObject *)
PyDict_Keys(PyObject *mp)
{
	if (mp == NULL || !PyDict_Check(mp)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	return dict_keys((dictobject *)mp);
}

DL_EXPORT(PyObject *)
PyDict_Values(PyObject *mp)
{
	if (mp == NULL || !PyDict_Check(mp)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	return dict_values((dictobject *)mp);
}

DL_EXPORT(PyObject *)
PyDict_Items(PyObject *mp)
{
	if (mp == NULL || !PyDict_Check(mp)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	return dict_items((dictobject *)mp);
}

/* Subroutine which returns the smallest key in a for which b's value
   is different or absent.  The value is returned too, through the
   pval argument.  Both are NULL if no key in a is found for which b's status
   differs.  The refcounts on (and only on) non-NULL *pval and function return
   values must be decremented by the caller (characterize() increments them
   to ensure that mutating comparison and PyDict_GetItem calls can't delete
   them before the caller is done looking at them). */

static PyObject *
characterize(dictobject *a, dictobject *b, PyObject **pval)
{
	PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
	PyObject *aval = NULL; /* a[akey] */
	int i, cmp;

	for (i = 0; i <= a->ma_mask; i++) {
		PyObject *thiskey, *thisaval, *thisbval;
		if (a->ma_table[i].me_value == NULL)
			continue;
		thiskey = a->ma_table[i].me_key;
		Py_INCREF(thiskey);  /* keep alive across compares */
		if (akey != NULL) {
			cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
			if (cmp < 0) {
				Py_DECREF(thiskey);
				goto Fail;
			}
			if (cmp > 0 ||
			    i > a->ma_mask ||
			    a->ma_table[i].me_value == NULL)
			{
				/* Not the *smallest* a key; or maybe it is
				 * but the compare shrunk the dict so we can't
				 * find its associated value anymore; or
				 * maybe it is but the compare deleted the
				 * a[thiskey] entry.
				 */
				Py_DECREF(thiskey);
				continue;
			}
		}

		/* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
		thisaval = a->ma_table[i].me_value;
		assert(thisaval);
		Py_INCREF(thisaval);   /* keep alive */
		thisbval = PyDict_GetItem((PyObject *)b, thiskey);
		if (thisbval == NULL)
			cmp = 0;
		else {
			/* both dicts have thiskey:  same values? */
			cmp = PyObject_RichCompareBool(
						thisaval, thisbval, Py_EQ);
			if (cmp < 0) {
		    		Py_DECREF(thiskey);
		    		Py_DECREF(thisaval);
		    		goto Fail;
			}
		}
		if (cmp == 0) {
			/* New winner. */
			Py_XDECREF(akey);
			Py_XDECREF(aval);
			akey = thiskey;
			aval = thisaval;
		}
		else {
			Py_DECREF(thiskey);
			Py_DECREF(thisaval);
		}
	}
	*pval = aval;
	return akey;

Fail:
	Py_XDECREF(akey);
	Py_XDECREF(aval);
	*pval = NULL;
	return NULL;
}

static int
dict_compare(dictobject *a, dictobject *b)
{
	PyObject *adiff, *bdiff, *aval, *bval;
	int res;

	/* Compare lengths first */
	if (a->ma_used < b->ma_used)
		return -1;	/* a is shorter */
	else if (a->ma_used > b->ma_used)
		return 1;	/* b is shorter */

	/* Same length -- check all keys */
	bdiff = bval = NULL;
	adiff = characterize(a, b, &aval);
	if (adiff == NULL) {
		assert(!aval);
		/* Either an error, or a is a subset with the same length so
		 * must be equal.
		 */
		res = PyErr_Occurred() ? -1 : 0;
		goto Finished;
	}
	bdiff = characterize(b, a, &bval);
	if (bdiff == NULL && PyErr_Occurred()) {
		assert(!bval);
		res = -1;
		goto Finished;
	}
	res = 0;
	if (bdiff) {
		/* bdiff == NULL "should be" impossible now, but perhaps
		 * the last comparison done by the characterize() on a had
		 * the side effect of making the dicts equal!
		 */
		res = PyObject_Compare(adiff, bdiff);
	}
	if (res == 0 && bval != NULL)
		res = PyObject_Compare(aval, bval);

Finished:
	Py_XDECREF(adiff);
	Py_XDECREF(bdiff);
	Py_XDECREF(aval);
	Py_XDECREF(bval);
	return res;
}

/* Return 1 if dicts equal, 0 if not, -1 if error.
 * Gets out as soon as any difference is detected.
 * Uses only Py_EQ comparison.
 */
static int
dict_equal(dictobject *a, dictobject *b)
{
	int i;

	if (a->ma_used != b->ma_used)
		/* can't be equal if # of entries differ */
		return 0;

	/* Same # of entries -- check all of 'em.  Exit early on any diff. */
	for (i = 0; i <= a->ma_mask; i++) {
		PyObject *aval = a->ma_table[i].me_value;
		if (aval != NULL) {
			int cmp;
			PyObject *bval;
			PyObject *key = a->ma_table[i].me_key;
			/* temporarily bump aval's refcount to ensure it stays
			   alive until we're done with it */
			Py_INCREF(aval);
			bval = PyDict_GetItem((PyObject *)b, key);
			if (bval == NULL) {
				Py_DECREF(aval);
				return 0;
			}
			cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
			Py_DECREF(aval);
			if (cmp <= 0)  /* error or not equal */
				return cmp;
 		}
	}
	return 1;
 }

static PyObject *
dict_richcompare(PyObject *v, PyObject *w, int op)
{
	int cmp;
	PyObject *res;

	if (!PyDict_Check(v) || !PyDict_Check(w)) {
		res = Py_NotImplemented;
	}
	else if (op == Py_EQ || op == Py_NE) {
		cmp = dict_equal((dictobject *)v, (dictobject *)w);
		if (cmp < 0)
			return NULL;
		res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
	}
	else
		res = Py_NotImplemented;
	Py_INCREF(res);
	return res;
 }

static PyObject *
dict_has_key(register dictobject *mp, PyObject *key)
{
	long hash;
	register long ok;
#ifdef CACHE_HASH
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1)
#endif
	{
		hash = PyObject_Hash(key);
		if (hash == -1)
			return NULL;
	}
	ok = (mp->ma_lookup)(mp, key, hash)->me_value != NULL;
	return PyInt_FromLong(ok);
}

static PyObject *
dict_get(register dictobject *mp, PyObject *args)
{
	PyObject *key;
	PyObject *failobj = Py_None;
	PyObject *val = NULL;
	long hash;

	if (!PyArg_ParseTuple(args, "O|O:get", &key, &failobj))
		return NULL;

#ifdef CACHE_HASH
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1)
#endif
	{
		hash = PyObject_Hash(key);
		if (hash == -1)
			return NULL;
	}
	val = (mp->ma_lookup)(mp, key, hash)->me_value;

	if (val == NULL)
		val = failobj;
	Py_INCREF(val);
	return val;
}


static PyObject *
dict_setdefault(register dictobject *mp, PyObject *args)
{
	PyObject *key;
	PyObject *failobj = Py_None;
	PyObject *val = NULL;
	long hash;

	if (!PyArg_ParseTuple(args, "O|O:setdefault", &key, &failobj))
		return NULL;

#ifdef CACHE_HASH
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1)
#endif
	{
		hash = PyObject_Hash(key);
		if (hash == -1)
			return NULL;
	}
	val = (mp->ma_lookup)(mp, key, hash)->me_value;
	if (val == NULL) {
		val = failobj;
		if (PyDict_SetItem((PyObject*)mp, key, failobj))
			val = NULL;
	}
	Py_XINCREF(val);
	return val;
}


static PyObject *
dict_clear(register dictobject *mp)
{
	PyDict_Clear((PyObject *)mp);
	Py_INCREF(Py_None);
	return Py_None;
}

static PyObject *
dict_popitem(dictobject *mp)
{
	int i = 0;
	dictentry *ep;
	PyObject *res;