AppPkg/Applications/Python/Python-2.7.10: Initial Checkin part 1/5.

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Python / pyarena.c

#include "Python.h"\r
#include "pyarena.h"\r
\r
/* A simple arena block structure.\r
\r
   Measurements with standard library modules suggest the average\r
   allocation is about 20 bytes and that most compiles use a single\r
   block.\r
\r
   TODO(jhylton): Think about a realloc API, maybe just for the last\r
   allocation?\r
*/\r
\r
#define DEFAULT_BLOCK_SIZE 8192\r
#define ALIGNMENT               8\r
#define ALIGNMENT_MASK          (ALIGNMENT - 1)\r
#define ROUNDUP(x)              (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)\r
\r
typedef struct _block {\r
    /* Total number of bytes owned by this block available to pass out.\r
     * Read-only after initialization.  The first such byte starts at\r
     * ab_mem.\r
     */\r
    size_t ab_size;\r
\r
    /* Total number of bytes already passed out.  The next byte available\r
     * to pass out starts at ab_mem + ab_offset.\r
     */\r
    size_t ab_offset;\r
\r
    /* An arena maintains a singly-linked, NULL-terminated list of\r
     * all blocks owned by the arena.  These are linked via the\r
     * ab_next member.\r
     */\r
    struct _block *ab_next;\r
\r
    /* Pointer to the first allocatable byte owned by this block.  Read-\r
     * only after initialization.\r
     */\r
    void *ab_mem;\r
} block;\r
\r
/* The arena manages two kinds of memory, blocks of raw memory\r
   and a list of PyObject* pointers.  PyObjects are decrefed\r
   when the arena is freed.\r
*/\r
\r
struct _arena {\r
    /* Pointer to the first block allocated for the arena, never NULL.\r
       It is used only to find the first block when the arena is\r
       being freed.\r
     */\r
    block *a_head;\r
\r
    /* Pointer to the block currently used for allocation.  It's\r
       ab_next field should be NULL.  If it is not-null after a\r
       call to block_alloc(), it means a new block has been allocated\r
       and a_cur should be reset to point it.\r
     */\r
    block *a_cur;\r
\r
    /* A Python list object containing references to all the PyObject\r
       pointers associated with this area.  They will be DECREFed\r
       when the arena is freed.\r
    */\r
    PyObject *a_objects;\r
\r
#if defined(Py_DEBUG)\r
    /* Debug output */\r
    size_t total_allocs;\r
    size_t total_size;\r
    size_t total_blocks;\r
    size_t total_block_size;\r
    size_t total_big_blocks;\r
#endif\r
};\r
\r
static block *\r
block_new(size_t size)\r
{\r
    /* Allocate header and block as one unit.\r
       ab_mem points just past header. */\r
    block *b = (block *)malloc(sizeof(block) + size);\r
    if (!b)\r
        return NULL;\r
    b->ab_size = size;\r
    b->ab_mem = (void *)(b + 1);\r
    b->ab_next = NULL;\r
    b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) -\r
      (Py_uintptr_t)(b->ab_mem);\r
    return b;\r
}\r
\r
static void\r
block_free(block *b) {\r
    while (b) {\r
        block *next = b->ab_next;\r
        free(b);\r
        b = next;\r
    }\r
}\r
\r
static void *\r
block_alloc(block *b, size_t size)\r
{\r
    void *p;\r
    assert(b);\r
    size = ROUNDUP(size);\r
    if (b->ab_offset + size > b->ab_size) {\r
        /* If we need to allocate more memory than will fit in\r
           the default block, allocate a one-off block that is\r
           exactly the right size. */\r
        /* TODO(jhylton): Think about space waste at end of block */\r
        block *newbl = block_new(\r
                        size < DEFAULT_BLOCK_SIZE ?\r
                        DEFAULT_BLOCK_SIZE : size);\r
        if (!newbl)\r
            return NULL;\r
        assert(!b->ab_next);\r
        b->ab_next = newbl;\r
        b = newbl;\r
    }\r
\r
    assert(b->ab_offset + size <= b->ab_size);\r
    p = (void *)(((char *)b->ab_mem) + b->ab_offset);\r
    b->ab_offset += size;\r
    return p;\r
}\r
\r
PyArena *\r
PyArena_New()\r
{\r
    PyArena* arena = (PyArena *)malloc(sizeof(PyArena));\r
    if (!arena)\r
        return (PyArena*)PyErr_NoMemory();\r
\r
    arena->a_head = block_new(DEFAULT_BLOCK_SIZE);\r
    arena->a_cur = arena->a_head;\r
    if (!arena->a_head) {\r
        free((void *)arena);\r
        return (PyArena*)PyErr_NoMemory();\r
    }\r
    arena->a_objects = PyList_New(0);\r
    if (!arena->a_objects) {\r
        block_free(arena->a_head);\r
        free((void *)arena);\r
        return (PyArena*)PyErr_NoMemory();\r
    }\r
#if defined(Py_DEBUG)\r
    arena->total_allocs = 0;\r
    arena->total_size = 0;\r
    arena->total_blocks = 1;\r
    arena->total_block_size = DEFAULT_BLOCK_SIZE;\r
    arena->total_big_blocks = 0;\r
#endif\r
    return arena;\r
}\r
\r
void\r
PyArena_Free(PyArena *arena)\r
{\r
    assert(arena);\r
#if defined(Py_DEBUG)\r
    /*\r
    fprintf(stderr,\r
        "alloc=%d size=%d blocks=%d block_size=%d big=%d objects=%d\n",\r
        arena->total_allocs, arena->total_size, arena->total_blocks,\r
        arena->total_block_size, arena->total_big_blocks,\r
        PyList_Size(arena->a_objects));\r
    */\r
#endif\r
    block_free(arena->a_head);\r
    /* This property normally holds, except when the code being compiled\r
       is sys.getobjects(0), in which case there will be two references.\r
    assert(arena->a_objects->ob_refcnt == 1);\r
    */\r
\r
    Py_DECREF(arena->a_objects);\r
    free(arena);\r
}\r
\r
void *\r
PyArena_Malloc(PyArena *arena, size_t size)\r
{\r
    void *p = block_alloc(arena->a_cur, size);\r
    if (!p)\r
        return PyErr_NoMemory();\r
#if defined(Py_DEBUG)\r
    arena->total_allocs++;\r
    arena->total_size += size;\r
#endif\r
    /* Reset cur if we allocated a new block. */\r
    if (arena->a_cur->ab_next) {\r
        arena->a_cur = arena->a_cur->ab_next;\r
#if defined(Py_DEBUG)\r
        arena->total_blocks++;\r
        arena->total_block_size += arena->a_cur->ab_size;\r
        if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE)\r
            ++arena->total_big_blocks;\r
#endif\r
    }\r
    return p;\r
}\r
\r
int\r
PyArena_AddPyObject(PyArena *arena, PyObject *obj)\r
{\r
    int r = PyList_Append(arena->a_objects, obj);\r
    if (r >= 0) {\r
        Py_DECREF(obj);\r
    }\r
    return r;\r
}\r