hb-decycler.hh (5451B)
1 /* 2 * Copyright © 2025 Behdad Esfahbod 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Author(s): Behdad Esfahbod 25 */ 26 27 #ifndef HB_DECYCLER_HH 28 #define HB_DECYCLER_HH 29 30 #include "hb.hh" 31 32 /* 33 * hb_decycler_t is an efficient cycle detector for graph traversal. 34 * It's a simple tortoise-and-hare algorithm with a twist: it's 35 * designed to detect cycles while traversing a graph in a DFS manner, 36 * instead of just a linked list. 37 * 38 * For Floyd's tortoise and hare algorithm, see: 39 * https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare 40 * 41 * hb_decycler_t is O(n) in the number of nodes in the DFS traversal 42 * if there are no cycles. Unlike Floyd's algorithm, hb_decycler_t 43 * can be used in a DFS traversal, where the graph is not a simple 44 * linked list, but a tree with possible cycles. Like Floyd's algorithm, 45 * it is constant-memory (~three pointers). 46 * 47 * The decycler works by creating an implicit linked-list on the stack, 48 * of the path from the root to the current node, and apply Floyd's 49 * algorithm on that list as it goes. 50 * 51 * The decycler is malloc-free, and as such, much faster to use than a 52 * hb_set_t or hb_map_t equivalent. 53 * 54 * The decycler detects cycles in the graph *eventually*, not *immediately*. 55 * That is, it may not detect a cycle until the cycle is fully traversed, 56 * even multiple times. See Floyd's algorithm analysis for details. 57 * 58 * The implementation saves a pointer storage on the stack by combining 59 * this->u.decycler and this->u.next into a union. This is possible because 60 * at any point we only need one of those values. The invariant is that 61 * after construction, and before destruction, of a node, the u.decycler 62 * field is always valid. The u.next field is only valid when the node is 63 * in the traversal path, parent to another node. 64 * 65 * There are three method's: 66 * 67 * - hb_decycler_node_t() constructor: Creates a new node in the traversal. 68 * The constructor takes a reference to the decycler object and inserts 69 * itself as the latest node in the traversal path, by advancing the hare 70 * pointer, and for every other descent, advancing the tortoise pointer. 71 * 72 * - ~hb_decycler_node_t() destructor: Restores the decycler object to its 73 * previous state by removing the node from the traversal path. 74 * 75 * - bool visit(uintptr_t value): Called on every node in the graph. Returns 76 * true if the node is not part of a cycle, and false if it is. The value 77 * parameter is used to detect cycles. It's the caller's responsibility 78 * to ensure that the value is unique for each node in the graph. 79 * The cycle detection is as simple as comparing the value to the value 80 * held by the tortoise pointer, which is the Floyd's algorithm. 81 * 82 * For usage examples see test-decycler.cc. 83 */ 84 85 struct hb_decycler_node_t; 86 87 struct hb_decycler_t 88 { 89 friend struct hb_decycler_node_t; 90 91 private: 92 bool tortoise_awake = false; 93 hb_decycler_node_t *tortoise = nullptr; 94 hb_decycler_node_t *hare = nullptr; 95 }; 96 97 struct hb_decycler_node_t 98 { 99 hb_decycler_node_t (hb_decycler_t &decycler) 100 { 101 u.decycler = &decycler; 102 103 decycler.tortoise_awake = !decycler.tortoise_awake; 104 105 if (!decycler.tortoise) 106 { 107 // First node. 108 assert (decycler.tortoise_awake); 109 assert (!decycler.hare); 110 decycler.tortoise = decycler.hare = this; 111 return; 112 } 113 114 if (decycler.tortoise_awake) 115 decycler.tortoise = decycler.tortoise->u.next; // Time to move. 116 117 this->prev = decycler.hare; 118 decycler.hare->u.next = this; 119 decycler.hare = this; 120 } 121 122 ~hb_decycler_node_t () 123 { 124 hb_decycler_t &decycler = *u.decycler; 125 126 // Inverse of the constructor. 127 128 assert (decycler.hare == this); 129 decycler.hare = prev; 130 if (prev) 131 prev->u.decycler = &decycler; 132 133 assert (decycler.tortoise); 134 if (decycler.tortoise_awake) 135 decycler.tortoise = decycler.tortoise->prev; 136 137 decycler.tortoise_awake = !decycler.tortoise_awake; 138 } 139 140 bool visit (uintptr_t value_) 141 { 142 value = value_; 143 144 hb_decycler_t &decycler = *u.decycler; 145 146 if (decycler.tortoise == this) 147 return true; // First node; not a cycle. 148 149 if (decycler.tortoise->value == value) 150 return false; // Cycle detected. 151 152 return true; 153 } 154 155 private: 156 union { 157 hb_decycler_t *decycler; 158 hb_decycler_node_t *next; 159 } u = {nullptr}; 160 hb_decycler_node_t *prev = nullptr; 161 uintptr_t value = 0; 162 }; 163 164 #endif /* HB_DECYCLER_HH */