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