EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.2 / Parser / node.c

/* Parse tree node implementation */\r
\r
#include "Python.h"\r
#include "node.h"\r
#include "errcode.h"\r
\r
node *\r
PyNode_New(int type)\r
{\r
    node *n = (node *) PyObject_MALLOC(1 * sizeof(node));\r
    if (n == NULL)\r
        return NULL;\r
    n->n_type = type;\r
    n->n_str = NULL;\r
    n->n_lineno = 0;\r
    n->n_nchildren = 0;\r
    n->n_child = NULL;\r
    return n;\r
}\r
\r
/* See comments at XXXROUNDUP below.  Returns -1 on overflow. */\r
static int\r
fancy_roundup(int n)\r
{\r
    /* Round up to the closest power of 2 >= n. */\r
    int result = 256;\r
    assert(n > 128);\r
    while (result < n) {\r
        result <<= 1;\r
        if (result <= 0)\r
            return -1;\r
    }\r
    return result;\r
}\r
\r
/* A gimmick to make massive numbers of reallocs quicker.  The result is\r
 * a number >= the input.  In PyNode_AddChild, it's used like so, when\r
 * we're about to add child number current_size + 1:\r
 *\r
 *     if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1):\r
 *         allocate space for XXXROUNDUP(current_size + 1) total children\r
 *     else:\r
 *         we already have enough space\r
 *\r
 * Since a node starts out empty, we must have\r
 *\r
 *     XXXROUNDUP(0) < XXXROUNDUP(1)\r
 *\r
 * so that we allocate space for the first child.  One-child nodes are very\r
 * common (presumably that would change if we used a more abstract form\r
 * of syntax tree), so to avoid wasting memory it's desirable that\r
 * XXXROUNDUP(1) == 1.  That in turn forces XXXROUNDUP(0) == 0.\r
 *\r
 * Else for 2 <= n <= 128, we round up to the closest multiple of 4.  Why 4?\r
 * Rounding up to a multiple of an exact power of 2 is very efficient, and\r
 * most nodes with more than one child have <= 4 kids.\r
 *\r
 * Else we call fancy_roundup() to grow proportionately to n.  We've got an\r
 * extreme case then (like test_longexp.py), and on many platforms doing\r
 * anything less than proportional growth leads to exorbitant runtime\r
 * (e.g., MacPython), or extreme fragmentation of user address space (e.g.,\r
 * Win98).\r
 *\r
 * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre\r
 * reported that, with this scheme, 89% of PyObject_REALLOC calls in\r
 * PyNode_AddChild passed 1 for the size, and 9% passed 4.  So this usually\r
 * wastes very little memory, but is very effective at sidestepping\r
 * platform-realloc disasters on vulnerable platforms.\r
 *\r
 * Note that this would be straightforward if a node stored its current\r
 * capacity.  The code is tricky to avoid that.\r
 */\r
#define XXXROUNDUP(n) ((n) <= 1 ? (n) :                 \\r
               (n) <= 128 ? (((n) + 3) & ~3) :          \\r
               fancy_roundup(n))\r
\r
\r
int\r
PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)\r
{\r
    const int nch = n1->n_nchildren;\r
    int current_capacity;\r
    int required_capacity;\r
    node *n;\r
\r
    if (nch == INT_MAX || nch < 0)\r
        return E_OVERFLOW;\r
\r
    current_capacity = XXXROUNDUP(nch);\r
    required_capacity = XXXROUNDUP(nch + 1);\r
    if (current_capacity < 0 || required_capacity < 0)\r
        return E_OVERFLOW;\r
    if (current_capacity < required_capacity) {\r
        if (required_capacity > PY_SIZE_MAX / sizeof(node)) {\r
            return E_NOMEM;\r
        }\r
        n = n1->n_child;\r
        n = (node *) PyObject_REALLOC(n,\r
                                      required_capacity * sizeof(node));\r
        if (n == NULL)\r
            return E_NOMEM;\r
        n1->n_child = n;\r
    }\r
\r
    n = &n1->n_child[n1->n_nchildren++];\r
    n->n_type = type;\r
    n->n_str = str;\r
    n->n_lineno = lineno;\r
    n->n_col_offset = col_offset;\r
    n->n_nchildren = 0;\r
    n->n_child = NULL;\r
    return 0;\r
}\r
\r
/* Forward */\r
static void freechildren(node *);\r
\r
\r
void\r
PyNode_Free(node *n)\r
{\r
    if (n != NULL) {\r
        freechildren(n);\r
        PyObject_FREE(n);\r
    }\r
}\r
\r
static void\r
freechildren(node *n)\r
{\r
    int i;\r
    for (i = NCH(n); --i >= 0; )\r
        freechildren(CHILD(n, i));\r
    if (n->n_child != NULL)\r
        PyObject_FREE(n->n_child);\r
    if (STR(n) != NULL)\r
        PyObject_FREE(STR(n));\r
}\r