AppPkg/Applications/Python/Python-2.7.10/Parser/node.c

   1 /* Parse tree node implementation */
   2
   3 #include "Python.h"
   4 #include "node.h"
   5 #include "errcode.h"
   6
   7 node *
   8 PyNode_New(int type)
   9 {
  10     node *n = (node *) PyObject_MALLOC(1 * sizeof(node));
  11     if (n == NULL)
  12         return NULL;
  13     n->n_type = type;
  14     n->n_str = NULL;
  15     n->n_lineno = 0;
  16     n->n_nchildren = 0;
  17     n->n_child = NULL;
  18     return n;
  19 }
  20
  21 /* See comments at XXXROUNDUP below.  Returns -1 on overflow. */
  22 static int
  23 fancy_roundup(int n)
  24 {
  25     /* Round up to the closest power of 2 >= n. */
  26     int result = 256;
  27     assert(n > 128);
  28     while (result < n) {
  29         result <<= 1;
  30         if (result <= 0)
  31             return -1;
  32     }
  33     return result;
  34 }
  35
  36 /* A gimmick to make massive numbers of reallocs quicker.  The result is
  37  * a number >= the input.  In PyNode_AddChild, it's used like so, when
  38  * we're about to add child number current_size + 1:
  39  *
  40  *     if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1):
  41  *         allocate space for XXXROUNDUP(current_size + 1) total children
  42  *     else:
  43  *         we already have enough space
  44  *
  45  * Since a node starts out empty, we must have
  46  *
  47  *     XXXROUNDUP(0) < XXXROUNDUP(1)
  48  *
  49  * so that we allocate space for the first child.  One-child nodes are very
  50  * common (presumably that would change if we used a more abstract form
  51  * of syntax tree), so to avoid wasting memory it's desirable that
  52  * XXXROUNDUP(1) == 1.  That in turn forces XXXROUNDUP(0) == 0.
  53  *
  54  * Else for 2 <= n <= 128, we round up to the closest multiple of 4.  Why 4?
  55  * Rounding up to a multiple of an exact power of 2 is very efficient, and
  56  * most nodes with more than one child have <= 4 kids.
  57  *
  58  * Else we call fancy_roundup() to grow proportionately to n.  We've got an
  59  * extreme case then (like test_longexp.py), and on many platforms doing
  60  * anything less than proportional growth leads to exorbitant runtime
  61  * (e.g., MacPython), or extreme fragmentation of user address space (e.g.,
  62  * Win98).
  63  *
  64  * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre
  65  * reported that, with this scheme, 89% of PyObject_REALLOC calls in
  66  * PyNode_AddChild passed 1 for the size, and 9% passed 4.  So this usually
  67  * wastes very little memory, but is very effective at sidestepping
  68  * platform-realloc disasters on vulnerable platforms.
  69  *
  70  * Note that this would be straightforward if a node stored its current
  71  * capacity.  The code is tricky to avoid that.
  72  */
  73 #define XXXROUNDUP(n) ((n) <= 1 ? (n) :                 \
  74                (n) <= 128 ? (((n) + 3) & ~3) :          \
  75                fancy_roundup(n))
  76
  77
  78 int
  79 PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)
  80 {
  81     const int nch = n1->n_nchildren;
  82     int current_capacity;
  83     int required_capacity;
  84     node *n;
  85
  86     if (nch == INT_MAX || nch < 0)
  87         return E_OVERFLOW;
  88
  89     current_capacity = XXXROUNDUP(nch);
  90     required_capacity = XXXROUNDUP(nch + 1);
  91     if (current_capacity < 0 || required_capacity < 0)
  92         return E_OVERFLOW;
  93     if (current_capacity < required_capacity) {
  94         if (required_capacity > PY_SIZE_MAX / sizeof(node)) {
  95             return E_NOMEM;
  96         }
  97         n = n1->n_child;
  98         n = (node *) PyObject_REALLOC(n,
  99                                       required_capacity * sizeof(node));
 100         if (n == NULL)
 101             return E_NOMEM;
 102         n1->n_child = n;
 103     }
 104
 105     n = &n1->n_child[n1->n_nchildren++];
 106     n->n_type = type;
 107     n->n_str = str;
 108     n->n_lineno = lineno;
 109     n->n_col_offset = col_offset;
 110     n->n_nchildren = 0;
 111     n->n_child = NULL;
 112     return 0;
 113 }
 114
 115 /* Forward */
 116 static void freechildren(node *);
 117 static Py_ssize_t sizeofchildren(node *n);
 118
 119
 120 void
 121 PyNode_Free(node *n)
 122 {
 123     if (n != NULL) {
 124         freechildren(n);
 125         PyObject_FREE(n);
 126     }
 127 }
 128
 129 Py_ssize_t
 130 _PyNode_SizeOf(node *n)
 131 {
 132     Py_ssize_t res = 0;
 133
 134     if (n != NULL)
 135         res = sizeof(node) + sizeofchildren(n);
 136     return res;
 137 }
 138
 139 static void
 140 freechildren(node *n)
 141 {
 142     int i;
 143     for (i = NCH(n); --i >= 0; )
 144         freechildren(CHILD(n, i));
 145     if (n->n_child != NULL)
 146         PyObject_FREE(n->n_child);
 147     if (STR(n) != NULL)
 148         PyObject_FREE(STR(n));
 149 }
 150
 151 static Py_ssize_t
 152 sizeofchildren(node *n)
 153 {
 154     Py_ssize_t res = 0;
 155     int i;
 156     for (i = NCH(n); --i >= 0; )
 157         res += sizeofchildren(CHILD(n, i));
 158     if (n->n_child != NULL)
 159         /* allocated size of n->n_child array */
 160         res += XXXROUNDUP(NCH(n)) * sizeof(node);
 161     if (STR(n) != NULL)
 162         res += strlen(STR(n)) + 1;
 163     return res;
 164 }