/** \ingroup python_interface_edge
 * \brief Returns the hash code of the edge
 */
Py_hash_t igraphmodule_Edge_hash(igraphmodule_EdgeObject* self) {
  Py_hash_t hash_graph;
  Py_hash_t hash_index;
  Py_hash_t result;
  PyObject* index_o;

  if (self->hash != -1)
    return self->hash;

  index_o = PyInt_FromLong((long int)self->idx);
  if (index_o == 0)
    return -1;

  hash_index = PyObject_Hash(index_o);
  Py_DECREF(index_o);

  if (hash_index == -1)
    return -1;

  /* Graph objects are unhashable from Python so we cannot call PyObject_Hash
   * directly. */
  hash_graph = igraphmodule_Py_HashPointer(self->gref);
  if (hash_graph == -1)
    return -1;

  result = hash_graph ^ hash_index;
  if (result == -1)
    result = 590923713U;

  self->hash = result;

  return result;
}

static Py_hash_t
contextvar_generate_hash(void *addr, PyObject *name)
{
    /* Take hash of `name` and XOR it with the object's addr.

       The structure of the tree is encoded in objects' hashes, which
       means that sufficiently similar hashes would result in tall trees
       with many Collision nodes.  Which would, in turn, result in slower
       get and set operations.

       The XORing helps to ensure that:

       (1) sequentially allocated ContextVar objects have
           different hashes;

       (2) context variables with equal names have
           different hashes.
    */

    Py_hash_t name_hash = PyObject_Hash(name);
    if (name_hash == -1) {
        return -1;
    }

    Py_hash_t res = _Py_HashPointer(addr) ^ name_hash;
    return res == -1 ? -2 : res;
}

Py_hash_t
Oid_hash(PyObject *oid)
{
    PyObject *py_oid = git_oid_to_py_str(&((Oid *)oid)->oid);
    Py_hash_t ret = PyObject_Hash(py_oid);
    Py_DECREF(py_oid);
    return ret;
}

static int t_tzinfo_hash(t_tzinfo *self)
{
    PyObject *str = PyObject_Str((PyObject *) self->tz);
    int hash = PyObject_Hash(str);

    Py_DECREF(str);
    return hash;
}

static PyObject *t_jccenv_strhash(PyObject *self, PyObject *arg)
{
    int hash = PyObject_Hash(arg);
    char buffer[10];

    sprintf(buffer, "%08x", (unsigned int) hash);
    return PyString_FromStringAndSize(buffer, 8);
}

static Py_hash_t
Pympq_hash(PympqObject *self)
{
#ifdef _PyHASH_MODULUS
    Py_hash_t hash = 0;
    mpz_t temp, temp1, mask;

    if (self->hash_cache != -1)
        return self->hash_cache;

    mpz_inoc(temp);
    mpz_inoc(temp1);
    mpz_inoc(mask);
    mpz_set_si(mask, 1);
    mpz_mul_2exp(mask, mask, _PyHASH_BITS);
    mpz_sub_ui(mask, mask, 1);

    if (!mpz_invert(temp, mpq_denref(self->q), mask)) {
        mpz_cloc(temp);
        mpz_cloc(temp1);
        mpz_cloc(mask);
        hash = _PyHASH_INF;
        if (mpz_sgn(mpq_numref(self->q))<0)
            hash = -hash;
        self->hash_cache = hash;
        return hash;
    }
    mpz_set(temp1, mask);
    mpz_sub_ui(temp1, temp1, 2);
    mpz_powm(temp, mpq_denref(self->q), temp1, mask);

    mpz_tdiv_r(temp1, mpq_numref(self->q), mask);
    mpz_mul(temp, temp, temp1);
    hash = (Py_hash_t)mpn_mod_1(temp->_mp_d, mpz_size(temp), _PyHASH_MODULUS);

    if (mpz_sgn(mpq_numref(self->q))<0)
        hash = -hash;
    if (hash==-1) hash = -2;
    mpz_cloc(temp);
    mpz_cloc(temp1);
    mpz_cloc(mask);
    self->hash_cache = hash;
    return hash;
#else
    PyObject *temp;

    if (self->hash_cache != -1)
        return self->hash_cache;

    if (!(temp = Pympq_To_PyFloat(self))) {
        SYSTEM_ERROR("Could not convert 'mpq' to float.");
        return -1;
    }
    self->hash_cache = PyObject_Hash(temp);
    Py_DECREF(temp);
    return self->hash_cache;
#endif
}

Py_hash_t
Object_hash(Object *object)
{
    const git_oid *oid = git_object_id(object->obj);
    PyObject *py_oid = git_oid_to_py_str(oid);
    Py_hash_t ret = PyObject_Hash(py_oid);
    Py_DECREF(py_oid);
    return ret;
}

static Py_hash_t
method_hash(PyMethodObject *a)
{
    Py_hash_t x, y;
    if (a->im_self == NULL)
        x = PyObject_Hash(Py_None);
    else
        x = PyObject_Hash(a->im_self);
    if (x == -1)
        return -1;
    y = PyObject_Hash(a->im_func);
    if (y == -1)
        return -1;
    x = x ^ y;
    if (x == -1)
        x = -2;
    return x;
}

static long struct_hash(PyObject *self)
{
	StructObject * const that = (StructObject*) self;

	if(that->repr == NULL) {
		_struct_build_repr(that);
	}

	return PyObject_Hash(that->repr);
}

static long
structseq_hash(PyObject *obj)
{
	PyObject *tup;
	long result;
	tup = make_tuple((PyStructSequence*) obj);
	result = PyObject_Hash(tup);
	Py_DECREF(tup);
	return result;
}

long
_Py_HashDouble(double v)
{
	double intpart, fractpart;
	int expo;
	long hipart;
	long x;		/* the final hash value */
	/* This is designed so that Python numbers of different types
	 * that compare equal hash to the same value; otherwise comparisons
	 * of mapping keys will turn out weird.
	 */

	fractpart = modf(v, &intpart);
	if (fractpart == 0.0) {
		/* This must return the same hash as an equal int or long. */
		if (intpart > LONG_MAX || -intpart > LONG_MAX) {
			/* Convert to long and use its hash. */
			PyObject *plong;	/* converted to Python long */
			if (Py_IS_INFINITY(intpart))
				/* can't convert to long int -- arbitrary */
				v = v < 0 ? -271828.0 : 314159.0;
			plong = PyLong_FromDouble(v);
			if (plong == NULL)
				return -1;
			x = PyObject_Hash(plong);
			Py_DECREF(plong);
			return x;
		}
		/* Fits in a C long == a Python int, so is its own hash. */
		x = (long)intpart;
		if (x == -1)
			x = -2;
		return x;
	}
	/* The fractional part is non-zero, so we don't have to worry about
	 * making this match the hash of some other type.
	 * Use frexp to get at the bits in the double.
	 * Since the VAX D double format has 56 mantissa bits, which is the
	 * most of any double format in use, each of these parts may have as
	 * many as (but no more than) 56 significant bits.
	 * So, assuming sizeof(long) >= 4, each part can be broken into two
	 * longs; frexp and multiplication are used to do that.
	 * Also, since the Cray double format has 15 exponent bits, which is
	 * the most of any double format in use, shifting the exponent field
	 * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).
	 */
	v = frexp(v, &expo);
	v *= 2147483648.0;	/* 2**31 */
	hipart = (long)v;	/* take the top 32 bits */
	v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */
	x = hipart + (long)v + (expo << 15);
	if (x == -1)
		x = -2;
	return x;
}

static Py_hash_t
thunk_hash(PyObject *self)
{
    PyObject *normal;

    if (!(normal = _strict_eval_borrowed(self))) {
        return -1;
    }

    return PyObject_Hash(normal);
}

static long
weakref_hash(PyWeakReference *self)
{
    if (self->hash != -1)
        return self->hash;
    if (PyWeakref_GET_OBJECT(self) == Py_None) {
        PyErr_SetString(PyExc_TypeError, "weak object has gone away");
        return -1;
    }
    self->hash = PyObject_Hash(PyWeakref_GET_OBJECT(self));
    return self->hash;
}

static long
func_hash(PyFunctionObject *f)
{
	long h,x;
	h = PyObject_Hash(f->func_code);
	if (h == -1) return h;
	x = _Py_HashPointer(f->func_globals);
	if (x == -1) return x;
	h ^= x;
	if (h == -1) h = -2;
	return h;
}

/*
 * Return 0 if successfull
 */
static int _PyArray_DescrHashImp(PyArray_Descr *descr, long *hash)
{
    PyObject *l, *tl, *item;
    Py_ssize_t i;
    int st;

    l = PyList_New(0);
    if (l == NULL) {
        return -1;
    }

    st = _array_descr_walk(descr, l);
    if (st) {
        goto clean_l;
    }

    /*
     * Convert the list to tuple and compute the tuple hash using python
     * builtin function
     */
    tl = PyTuple_New(PyList_Size(l));
    for(i = 0; i < PyList_Size(l); ++i) {
        item = PyList_GetItem(l, i);
        if (item == NULL) {
            PyErr_SetString(PyExc_SystemError,
                    "(Hash) Error while translating the list into a tuple " \
                    "(NULL item)");
            goto clean_tl;
        }
        PyTuple_SetItem(tl, i, item);
    }

    *hash = PyObject_Hash(tl);
    if (*hash == -1) {
        /* XXX: does PyObject_Hash set an exception on failure ? */
#if 0
        PyErr_SetString(PyExc_SystemError,
                "(Hash) Error while hashing final tuple");
#endif
        goto clean_tl;
    }
    Py_DECREF(tl);
    Py_DECREF(l);

    return 0;

clean_tl:
    Py_DECREF(tl);
clean_l:
    Py_DECREF(l);
    return -1;
}

static Py_hash_t
notify_hash(notifyObject *self)
{
    Py_hash_t rv = -1L;
    PyObject *tself = NULL;

    /* if self == a tuple, then their hashes are the same. */
    int has_payload = PyObject_IsTrue(self->payload);
    if (!(tself = notify_astuple(self, has_payload))) { goto exit; }
    rv = PyObject_Hash(tself);

exit:
    Py_XDECREF(tself);
    return rv;
}

static long
wrapper_hash(wrapperobject *wp)
{
	int x, y;
	x = _Py_HashPointer(wp->descr);
	if (x == -1)
		return -1;
	y = PyObject_Hash(wp->self);
	if (y == -1)
		return -1;
	x = x ^ y;
	if (x == -1)
		x = -2;
	return x;
}

static PyObject * AtTime_call( AtTime* self, PyObject* args, PyObject* kwds )
{
	if( !PyTuple_Check(args) || (PyTuple_Size(args) != 1) || (!PyNumber_Check(PyTuple_GetItem(args,0))) ) {
		PyErr_SetString( PyExc_AttributeError, "Calling AtTime instances require a single time(int) argument" );
		return 0;
	}
	
	int timeValue = PyInt_AsLong(PyTuple_GetItem(args,0));
	if( PyErr_Occurred() )
		return 0;
	
	PyObject * tsd = PyThreadState_GetDict();
	PyObject * atd = PyDict_GetItemString(tsd, "_AtTime" );
	
	// New reference is either transfered to a list, or decremented below
	PyObject * hashKey = PyLong_FromLong( PyObject_Hash((PyObject*)self) );
	
	if( !atd ) {
		
		// New ref
		atd = PyDict_New();
		
		PyDict_SetItemString( tsd, "_AtTime", atd );
		// tsd now has a ref to atd
		Py_DECREF(atd);
		
		// New refs
		PyObject * time_stack = PyList_New(1), * cur_stack = PyList_New(1);
		
		// PyList_SetItem steals a reference
		PyList_SetItem( time_stack, 0, PyLong_FromLong(thread_local(current_time)) );
		// Give our hashKey reference to cur_stack
		PyList_SetItem( cur_stack, 0, hashKey );
		
		// Dicts take their own reference, so we release ours after this
		PyDict_SetItemString( atd, "time_stack", time_stack );
		PyDict_SetItemString( atd, "current_stack", cur_stack );
		Py_DECREF(time_stack);
		Py_DECREF(cur_stack);
		
		PyObject * utl = PyBool_FromLong( thread_local(use_time_context) );
		// takes it's own ref, so we release ours
		PyDict_SetItemString( atd, "restore_use_time_context", utl );
		Py_DECREF(utl);
		
		thread_local(use_time_context) = TRUE;
		//PySys_WriteStdout( "First AtTime struct activated, setting thread_local(use_time_context) to TRUE\n" );
	} else {

/* Hash function for range objects.  Rough C equivalent of

   if not len(r):
       return hash((len(r), None, None))
   if len(r) == 1:
       return hash((len(r), r.start, None))
   return hash((len(r), r.start, r.step))
*/
static Py_hash_t
range_hash(rangeobject *r)
{
    PyObject *t;
    Py_hash_t result = -1;
    int cmp_result;

    t = PyTuple_New(3);
    if (!t)
        return -1;
    Py_INCREF(r->length);
    PyTuple_SET_ITEM(t, 0, r->length);
    cmp_result = PyObject_Not(r->length);
    if (cmp_result == -1)
        goto end;
    if (cmp_result == 1) {
        Py_INCREF(Py_None);
        Py_INCREF(Py_None);
        PyTuple_SET_ITEM(t, 1, Py_None);
        PyTuple_SET_ITEM(t, 2, Py_None);
    }
    else {
        PyObject *one;
        Py_INCREF(r->start);
        PyTuple_SET_ITEM(t, 1, r->start);
        one = PyLong_FromLong(1);
        if (!one)
            goto end;
        cmp_result = PyObject_RichCompareBool(r->length, one, Py_EQ);
        Py_DECREF(one);
        if (cmp_result == -1)
            goto end;
        if (cmp_result == 1) {
            Py_INCREF(Py_None);
            PyTuple_SET_ITEM(t, 2, Py_None);
        }
        else {
            Py_INCREF(r->step);
            PyTuple_SET_ITEM(t, 2, r->step);
        }
    }
    result = PyObject_Hash(t);
  end:
    Py_DECREF(t);
    return result;
}

static long node_hash(NodeObject *self)
{
#if SIZEOF_LONG >= SIZEOF_VOID_P
  return (long)self;
#else
  /* convert to a Python long and hash that */
  PyObject *longobj;
  long hash;

  if ((longobj = PyLong_FromVoidPtr(self)) == NULL) {
    return -1;
  }

  hash = PyObject_Hash(longobj);
  Py_DECREF(longobj);
  return hash;
#endif
}