A question about fill_free_list(void) function

[Peter Otten]

Pedram wrote:

> On Jul 1, 10:01 pm, Christian Heimes <li... at cheimes.de> wrote:
>> Pedram schrieb:
>>
>> > Hello community,
>> > I'm reading the CPython interpreter source code,
>> > first, if you have something that I should know for better reading
>> > this source code, I would much appreciate that :)
>> > second, in intobject.c file, I read the following code in
>> > fill_free_list function that I couldn't understand:
>> > <code>while (--q > p)
>> > Py_TYPE(q) = (struct _typeobject *)(q-1);
>> > Py_TYPE(q) = NULL;
>> > </code>
>> > What does it mean?
>>
>> The code is abusing the ob_type member to store a single linked, NULL
>> terminated list of free integer objects. It's a tricky optimization you
>> don't have to understand in order to understand the rest of the code.
>>
>> And no, the code in ctypes.h is totally unrelated to the free list in
>> intobject.c.
>>
>> Christian
> 
> Thanks for reply.
> I totally understood the fill_free_list() function. Thanks.
> But I have problems in understanding the PyInt_FromLong(). Here's the
> code:
> 
> PyObject *
> PyInt_FromLong(long ival)
> {
> register PyIntObject *v;
> #if NSMALLNEGINTS + NSMALLPOSINTS > 0
> if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
> v = small_ints[ival + NSMALLNEGINTS];
> Py_INCREF(v);
> #ifdef COUNT_ALLOCS
> if (ival >= 0)
> quick_int_allocs++;
> else
> quick_neg_int_allocs++;
> #endif
> return (PyObject *) v;
> }
> #endif
> if (free_list == NULL) {
> if ((free_list = fill_free_list()) == NULL)
> return NULL;
> }
> 
> v = free_list; // <-- No problem till here :)
> free_list = (PyIntObject *)Py_TYPE(v);
> PyObject_INIT(v, &PyInt_Type);
> v->ob_ival = ival;
> return (PyObject *) v;
> }
> 
> I understood that small numbers (between -5 and 256) are referenced to
> small_ints list. Others have to store in PyIntBlock, am I right? OK,
> no problem till 'v = free_list;' but can't understand the line
> 'free_list = (PyIntObject *)Py_TYPE(v);' :(. Where free_list
> referenced to? Don't this correct that free_list have to be referenced
> to another free block so next time the function called v store in this
> location?
> Sorry for my bad English. I hope you could understand me :)

Well, if I understand fill_free_list() correctly, you haven't ;) It only 
makes sense together with the allocation code in PyInt_FromLong().

Py_TYPE(v) translates to v->ob_type, and in fill_free_list() that field was 
abused(*) to hold a pointer to the previous item in the array of free 
integers, thereby temporarily turning it into a linked list.

Assuming that free_list pointed to block->objects[10] in the current 
PyIntBlock it will now point to block->objects[9].

When block->objects[0] is reached free_list will be set to NULL as block-
>objects[0]->ob_type was initialized with NULL by the line

Py_TYPE(q) = NULL; /* in fill_free_list() */

The next call of PyInt_FromLong() will then trigger the allocation of a new 
block.

Peter

(*) It may help if you think of the objects array as a

union linked {
    linked *next;
    PyInt_Object obj;
};