# cpython-withatomic / Parser / node.c

The branch '2.2' 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``` ```/* Parse tree node implementation */ #include "Python.h" #include "node.h" #include "errcode.h" node * PyNode_New(int type) { node *n = PyMem_NEW(node, 1); 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. For n=0 we must return 0. * For n=1, we return 1, to avoid wasting memory in common 1-child nodes * (XXX are those actually common?). * Else for n <= 128, round up to the closest multiple of 4. Why 4? * Rounding up to a multiple of an exact power of 2 is very efficient. * Else 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). * This would be straightforward if a node stored its current capacity. The * code is tricky to avoid that. */ #define XXXROUNDUP(n) ((n) == 1 ? 1 : \ (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; PyMem_RESIZE(n, node, required_capacity); 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); PyMem_DEL(n); } } static void freechildren(node *n) { int i; for (i = NCH(n); --i >= 0; ) freechildren(CHILD(n, i)); if (n->n_child != NULL) PyMem_DEL(n->n_child); if (STR(n) != NULL) PyMem_DEL(STR(n)); } ```