cpython-withatomic / Parser / node.c

The branch '2.4' does not exist.
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134``` ```/* 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 PyMem_RESIZE 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 vulnernable 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) { 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) { 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_nchildren = 0; n->n_child = NULL; return 0; } /* Forward */ static void freechildren(node *); void PyNode_Free(node *n) { if (n != NULL) { freechildren(n); PyObject_FREE(n); } } 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)); } ```