path: root/python/sip/siplib/objmap.c

/*
 * This module implements a hash table class for mapping C/C++ addresses to the
 * corresponding wrapped Python object.
 *
 * Copyright (c) 2007
 * 	Riverbank Computing Limited <info@riverbankcomputing.co.uk>
 * 
 * This file is part of SIP.
 * 
 * This copy of SIP is licensed for use under the terms of the SIP License
 * Agreement.  See the file LICENSE for more details.
 * 
 * SIP is supplied WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 */


#include <string.h>

#include "sip.h"
#include "sipint.h"


#define hash_1(k,s) (((unsigned long)(k)) % (s))
#define hash_2(k,s) ((s) - 2 - (hash_1((k),(s)) % ((s) - 2)))


/* Prime numbers to use as hash table sizes. */
static unsigned long hash_primes[] = {
    521,        1031,       2053,       4099,
    8209,       16411,      32771,      65537,      131101,     262147,
    524309,     1048583,    2097169,    4194319,    8388617,    16777259,
    33554467,   67108879,   134217757,  268435459,  536870923,  1073741827,
    2147483659U,0
};


static sipHashEntry *newHashTable(unsigned long);
static sipHashEntry *findHashEntry(sipObjectMap *,void *);
static void reorganiseMap(sipObjectMap *om);


/*
 * Initialise an object map.
 */
void sipOMInit(sipObjectMap *om)
{
    om -> primeIdx = 0;
    om -> unused = om -> size = hash_primes[om -> primeIdx];
    om -> stale = 0;
    om -> hash_array = newHashTable(om -> size);
}


/*
 * Finalise an object map.
 */
void sipOMFinalise(sipObjectMap *om)
{
    sip_api_free(om -> hash_array);
}


/*
 * Allocate and initialise a new hash table.
 */
static sipHashEntry *newHashTable(unsigned long size)
{
    size_t nbytes;
    sipHashEntry *hashtab;

    nbytes = sizeof (sipHashEntry) * size;

    if ((hashtab = (sipHashEntry *)sip_api_malloc(nbytes)) != NULL)
        memset(hashtab,0,nbytes);

    return hashtab;
}


/*
 * Return a pointer to the hash entry that is used, or should be used, for the
 * given C/C++ address.
 */
static sipHashEntry *findHashEntry(sipObjectMap *om,void *key)
{
    unsigned long hash, inc;
    void *hek;

    hash = hash_1(key,om -> size);
    inc = hash_2(key,om -> size);

    while ((hek = om -> hash_array[hash].key) != NULL && hek != key)
        hash = (hash + inc) % om -> size;

    return &om -> hash_array[hash];
}


/*
 * Return the wrapped Python object of a specific type for a C/C++ address or
 * NULL if it wasn't found.
 */
sipWrapper *sipOMFindObject(sipObjectMap *om,void *key, sipWrapperType *type)
{
    sipHashEntry *he = findHashEntry(om, key);
    sipWrapper *w;

    /* Go through each wrapped object at this address. */
    for (w = he->first; w != NULL; w = w->next)
    {
        /*
         * If this wrapped object is of the given type, or a sub-type
         * of it, or vice versa, then we assume it is the same C++
         * object.
         */
        if (PyObject_TypeCheck(w, (PyTypeObject *)type) ||
                PyType_IsSubtype((PyTypeObject *)type, w->ob_type))
            return w;
    }

    return NULL;
}


/*
 * Add a C/C++ address and the corresponding wrapped Python object to the map.
 */
void sipOMAddObject(sipObjectMap *om,sipWrapper *val)
{
    sipHashEntry *he = findHashEntry(om,val -> u.cppPtr);

    /*
     * If the bucket is in use then we appear to have several objects at
     * the same address.
     */
    if (he -> first != NULL)
    {
        /*
         * This can happen for three reasons.  A variable of one class
         * can be declared at the start of another class.  Therefore
         * there are two objects, of different classes, with the same
         * address.  The second reason is that the old C/C++ object has
         * been deleted by C/C++ but we didn't get to find out for some
         * reason, and a new C/C++ instance has been created at the
         * same address.  The third reason is if we are in the process
         * of deleting a Python object but the C++ object gets wrapped
         * again because the C++ dtor called a method that has been
         * re-implemented in Python.  The absence of the SIP_SHARE_MAP
         * flag tells us that a new C++ instance has just been created
         * and so we know the second reason is the correct one so we
         * mark the old pointers as invalid and reuse the entry.
         * Otherwise we just add this one to the existing list of
         * objects at this address.
         */
        if (!(val -> flags & SIP_SHARE_MAP))
        {
            sipWrapper *w;

            for (w = he -> first; w != NULL; w = w -> next)
                w -> u.cppPtr = NULL;

            he -> first = NULL;
        }

        val -> next = he -> first;
        he -> first = val;

        return;
    }

    /* See if the bucket was unused or stale. */
    if (he -> key == NULL)
    {
        he -> key = val -> u.cppPtr;
        om -> unused--;
    }
    else
        om -> stale--;

    /* Add the rest of the new value. */
    he -> first = val;
    val -> next = NULL;

    reorganiseMap(om);
}


/*
 * Reorganise a map if it is running short of space.
 */
static void reorganiseMap(sipObjectMap *om)
{
    unsigned long old_size, i;
    sipHashEntry *ohe, *old_tab;

    /* Don't bother if it still has more than 12% available. */
    if (om -> unused > om -> size >> 3)
        return;

    /*
     * If reorganising (ie. making the stale buckets unused) using the same
     * sized table would make 25% available then do that.  Otherwise use a
     * bigger table (if possible).
     */
    if (om -> unused + om -> stale < om -> size >> 2 && hash_primes[om -> primeIdx + 1] != 0)
        om -> primeIdx++;

    old_size = om -> size;
    old_tab = om -> hash_array;

    om -> unused = om -> size = hash_primes[om -> primeIdx];
    om -> stale = 0;
    om -> hash_array = newHashTable(om -> size);

    /* Transfer the entries from the old table to the new one. */
    ohe = old_tab;

    for (i = 0; i < old_size; ++i)
    {
        if (ohe -> key != NULL && ohe -> first != NULL)
        {
            *findHashEntry(om,ohe -> key) = *ohe;
            om -> unused--;
        }

        ++ohe;
    }

    sip_api_free(old_tab);
}


/*
 * Remove a C/C++ object from the table.  Return 0 if it was removed
 * successfully.
 */
int sipOMRemoveObject(sipObjectMap *om,sipWrapper *val)
{
    sipHashEntry *he = findHashEntry(om,val -> u.cppPtr);
    sipWrapper **wp;

    for (wp = &he -> first; *wp != NULL; wp = &(*wp) -> next)
        if (*wp == val)
        {
            *wp = val -> next;

            /*
             * If the bucket is now empty then count it as stale.
             * Note that we do not NULL the key and count it as
             * unused because that might throw out the search for
             * another entry that wanted to go here, found it
             * already occupied, and was put somewhere else.  In
             * other words, searches must be repeatable until we
             * reorganise the table.
             */
            if (he -> first == NULL)
                om -> stale++;

            return 0;
        }

    return -1;
}