Lines Matching defs:node
25 the middle of the linked-list implicitly require finding the node first.
30 In order to preserve O(1) performance for node removal (finding nodes), we
36 to the corresponding node in the linked-list.
38 4. have the value stored for each key be a (value, node) pair, and adjust
42 mirroring the key order of dict's dk_entries with an array of node pointers.
52 matters during node lookup. We can simply defer any potential resizing
75 * _odictnode_KEY(node)
76 * _odictnode_VALUE(od, node)
77 * _odictnode_PREV(node)
78 * _odictnode_NEXT(node)
85 * _odict_FOREACH(od, node) - used in place of `for (node=...)`
89 * _odict_add_head(od, node)
90 * _odict_add_tail(od, node)
95 * _odict_clear_node(od, node, key, hash)
110 __delitem__ free ~ node
125 popitem X X free X X node
131 node in the linked-list. Everything else is iteration or relates to the
137 cause problems. If a node is stored in a variable, there is a chance that
138 the node may have been deallocated before the variable gets used, thus
145 * defer looking up the node until as late as possible and certainly after
147 * if the node is needed both before and after a point where the node might
148 be removed, do a check before using the node at the "after" location to
149 see if the node is still valid;
150 * like the last one, but simply pull the node again to ensure it's right;
151 * keep the key in the variable instead of the node and then look up the
152 node using the key at the point where the node is needed (this is what
439 - Set node->key to NULL to indicate the node is not-in-use.
441 - How to maintain consistency across resizes? Existing node pointers
486 _ODictNode *od_first; /* first node in the linked list, if any */
487 _ODictNode *od_last; /* last node in the linked list, if any */
512 #define _odictnode_KEY(node) \
513 (node->key)
514 #define _odictnode_HASH(node) \
515 (node->hash)
517 #define _odictnode_VALUE(node, od) \
518 PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))
519 #define _odictnode_PREV(node) (node->prev)
520 #define _odictnode_NEXT(node) (node->next)
525 #define _odict_FOREACH(od, node) \
526 for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))
528 /* Return the index into the hash table, regardless of a valid node. */
553 _ODictNode **fast_nodes, *node;
566 _odict_FOREACH(od, node) {
567 i = _odict_get_index_raw(od, _odictnode_KEY(node),
568 _odictnode_HASH(node));
573 fast_nodes[i] = node;
584 /* Return the index into the hash table, regardless of a valid node. */
638 _odict_add_head(PyODictObject *od, _ODictNode *node)
640 _odictnode_PREV(node) = NULL;
641 _odictnode_NEXT(node) = _odict_FIRST(od);
643 _odict_LAST(od) = node;
645 _odictnode_PREV(_odict_FIRST(od)) = node;
646 _odict_FIRST(od) = node;
651 _odict_add_tail(PyODictObject *od, _ODictNode *node)
653 _odictnode_PREV(node) = _odict_LAST(od);
654 _odictnode_NEXT(node) = NULL;
656 _odict_FIRST(od) = node;
658 _odictnode_NEXT(_odict_LAST(od)) = node;
659 _odict_LAST(od) = node;
663 /* adds the node to the end of the list */
668 _ODictNode *node;
680 /* We already have a node for the key so there's no need to add one. */
686 node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode));
687 if (node == NULL) {
693 _odictnode_KEY(node) = key;
694 _odictnode_HASH(node) = hash;
695 _odict_add_tail(od, node);
696 od->od_fast_nodes[i] = node;
701 #define _odictnode_DEALLOC(node) \
703 Py_DECREF(_odictnode_KEY(node)); \
704 PyMem_Free((void *)node); \
707 /* Repeated calls on the same node are no-ops. */
709 _odict_remove_node(PyODictObject *od, _ODictNode *node)
711 if (_odict_FIRST(od) == node)
712 _odict_FIRST(od) = _odictnode_NEXT(node);
713 else if (_odictnode_PREV(node) != NULL)
714 _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);
716 if (_odict_LAST(od) == node)
717 _odict_LAST(od) = _odictnode_PREV(node);
718 else if (_odictnode_NEXT(node) != NULL)
719 _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node);
721 _odictnode_PREV(node) = NULL;
722 _odictnode_NEXT(node) = NULL;
734 the index we got before deleting B. However, the node for C in
736 things don't get out of sync, we clear the node in od_fast_nodes
743 _odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,
759 if (node == NULL)
760 node = od->od_fast_nodes[i];
761 assert(node == od->od_fast_nodes[i]);
762 if (node == NULL) {
767 // Now clear the node.
769 _odict_remove_node(od, node);
770 _odictnode_DEALLOC(node);
777 _ODictNode *node, *next;
784 node = _odict_FIRST(od);
787 while (node != NULL) {
788 next = _odictnode_NEXT(node);
789 _odictnode_DEALLOC(node);
790 node = next;
1043 _ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash);
1044 if (node != NULL) {
1045 /* Pop the node first to avoid a possible dict resize (due to
1048 int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
1111 _ODictNode *node;
1120 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1121 key = _odictnode_KEY(node);
1123 value = _odict_popkey_hash((PyObject *)self, key, NULL, _odictnode_HASH(node));
1187 _ODictNode *node;
1198 _odict_FOREACH(od, node) {
1199 PyObject *key = _odictnode_KEY(node);
1200 PyObject *value = _odictnode_VALUE(node, od);
1207 _odictnode_HASH(node)) != 0)
1212 _odict_FOREACH(od, node) {
1215 _odictnode_KEY(node));
1219 _odictnode_KEY(node), value);
1268 _ODictNode *node;
1274 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1275 if (key != _odictnode_KEY(node)) {
1276 node = _odict_find_node(self, key);
1277 if (node == NULL) {
1284 if (node != _odict_LAST(self)) {
1285 _odict_remove_node(self, node);
1286 _odict_add_tail(self, node);
1291 if (node != _odict_FIRST(self)) {
1292 _odict_remove_node(self, node);
1293 _odict_add_head(self, node);
1387 _ODictNode *node;
1392 _odict_FOREACH(self, node) {
1394 PyObject *key = _odictnode_KEY(node);
1395 PyObject *value = _odictnode_VALUE(node, self);
1450 _ODictNode *node;
1453 _odict_FOREACH(od, node) {
1454 Py_VISIT(_odictnode_KEY(node));
1673 * the current key instead of the current node. */
1678 _ODictNode *node;
1700 node = _odict_find_node(di->di_odict, di->di_current);
1701 if (node == NULL) {
1711 node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
1712 if (node == NULL) {
1717 di->di_current = _odictnode_KEY(node);
1855 _ODictNode *node;
1874 node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
1875 di->di_current = node ? _odictnode_KEY(node) : NULL;