summaryrefslogtreecommitdiffstats
path: root/python/sip/siplib/objmap.c
blob: efc7bc2ae779e3d2878089c0f9b1a46df7a81a52 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
/*
 * 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;
}