src/TortoiseProc/RevisionGraph/SearchPathTree.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2007-2008 - TortoiseSVN\r
   4 \r
   5 // This program is free software; you can redistribute it and/or\r
   6 // modify it under the terms of the GNU General Public License\r
   7 // as published by the Free Software Foundation; either version 2\r
   8 // of the License, or (at your option) any later version.\r
   9 \r
  10 // This program is distributed in the hope that it will be useful,\r
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13 // GNU General Public License for more details.\r
  14 \r
  15 // You should have received a copy of the GNU General Public License\r
  16 // along with this program; if not, write to the Free Software Foundation,\r
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
  18 //\r
  19 \r
  20 #include "StdAfx.h"\r
  21 #include "SearchPathTree.h"\r
  22 #include "FullGraphNode.h"\r
  23 \r
  24 #ifdef _DEBUG\r
  25 #define new DEBUG_NEW\r
  26 #undef THIS_FILE\r
  27 static char THIS_FILE[] = __FILE__;\r
  28 #endif\r
  29 \r
  30 void CSearchPathTree::DeLink()\r
  31 {\r
  32         assert (parent);\r
  33 \r
  34         if (previous)\r
  35                 previous->next = next;\r
  36         if (next)\r
  37                 next->previous = previous;\r
  38 \r
  39         if (parent->firstChild == this)\r
  40                 parent->firstChild = next;\r
  41         if (parent->lastChild == this)\r
  42                 parent->lastChild = previous;\r
  43 \r
  44         parent = NULL;\r
  45 }\r
  46 \r
  47 void CSearchPathTree::Link (CSearchPathTree* newParent)\r
  48 {\r
  49         assert (parent == NULL);\r
  50         assert (newParent != NULL);\r
  51 \r
  52         // ensure that for every cached path element hierarchy level\r
  53         // there is a node in the tree hierarchy\r
  54 \r
  55         index_t pathID = path.GetBasePath().GetIndex();\r
  56         index_t parentPathID = path.IsFullyCachedPath()\r
  57                                                  ? path.GetDictionary()->GetParent (pathID)\r
  58                                                  : pathID;\r
  59 \r
  60         if (newParent->path.GetBasePath().GetIndex() < parentPathID)\r
  61         {\r
  62                 CDictionaryBasedPath parentPath ( path.GetDictionary()\r
  63                                                                                 , parentPathID);\r
  64                 newParent = new CSearchPathTree ( CDictionaryBasedTempPath (parentPath)\r
  65                                                                                 , (revision_t)NO_REVISION\r
  66                                                                                 , newParent);\r
  67         }\r
  68 \r
  69         parent = newParent;\r
  70 \r
  71         // insert into parent's child list ordered by pathID\r
  72 \r
  73         // O(1) insertion in most cases\r
  74 \r
  75         if (parent->firstChild == NULL)\r
  76         {\r
  77                 // no child yet\r
  78 \r
  79                 parent->firstChild = this;\r
  80                 parent->lastChild = this;\r
  81         }\r
  82         else if (parent->lastChild->path.GetBasePath().GetIndex() <= pathID)\r
  83         {\r
  84                 // insert at the end\r
  85 \r
  86                 previous = parent->lastChild;\r
  87 \r
  88                 parent->lastChild = this;\r
  89                 previous->next = this;\r
  90         }\r
  91         else if (parent->firstChild->path.GetBasePath().GetIndex() >= pathID)\r
  92         {\r
  93                 // insert at the beginning\r
  94 \r
  95                 next = parent->firstChild;\r
  96 \r
  97                 parent->firstChild = this;\r
  98                 next->previous = this;\r
  99         }\r
 100         else\r
 101         {\r
 102                 assert (parent->firstChild != parent->lastChild);\r
 103 \r
 104                 // scan for insertion position\r
 105 \r
 106                 CSearchPathTree* node = parent->firstChild;\r
 107                 while (node->path.GetBasePath().GetIndex() < pathID)\r
 108                         node = node->next;\r
 109 \r
 110                 // insert us there\r
 111 \r
 112                 previous = node->previous;\r
 113                 next = node;\r
 114 \r
 115                 previous->next = this;\r
 116                 node->previous = this;\r
 117         }\r
 118 }\r
 119 \r
 120 // construction / destruction\r
 121 \r
 122 CSearchPathTree::CSearchPathTree (const CPathDictionary* dictionary)\r
 123         : path (dictionary, std::string())\r
 124         , startRevision ((revision_t)NO_REVISION)\r
 125         , lastEntry (NULL)\r
 126         , parent (NULL)\r
 127         , firstChild (NULL)\r
 128         , lastChild (NULL)\r
 129         , previous (NULL)\r
 130         , next (NULL)\r
 131 {\r
 132 }\r
 133 \r
 134 CSearchPathTree::CSearchPathTree ( const CDictionaryBasedTempPath& path\r
 135                                                                  , revision_t startrev\r
 136                                                                  , CSearchPathTree* parent)\r
 137         : path (path)\r
 138         , startRevision (startrev)\r
 139         , lastEntry (NULL)\r
 140         , parent (NULL)\r
 141         , firstChild (NULL)\r
 142         , lastChild (NULL)\r
 143         , previous (NULL)\r
 144         , next (NULL)\r
 145 {\r
 146         Link (parent);\r
 147 }\r
 148 \r
 149 CSearchPathTree::~CSearchPathTree()\r
 150 {\r
 151         while (firstChild != NULL)\r
 152                 delete firstChild;\r
 153 \r
 154         if (parent)\r
 155                 DeLink();\r
 156 }\r
 157 \r
 158 // add a node for the given path and rev. to the tree\r
 159 \r
 160 CSearchPathTree* CSearchPathTree::Insert ( const CDictionaryBasedTempPath& path\r
 161                                                                                  , revision_t startrev)\r
 162 {\r
 163         assert (startrev != NO_REVISION);\r
 164 \r
 165         // exact match (will happen on root node only)?\r
 166 \r
 167         if (this->path == path)\r
 168         {\r
 169                 startRevision = startrev;\r
 170                 return this;\r
 171         }\r
 172 \r
 173         // (partly or fully) overlap with an existing child?\r
 174 \r
 175         CDictionaryBasedPath cachedPath = path.GetBasePath();\r
 176         for (CSearchPathTree* child = firstChild; child != NULL; child = child->next)\r
 177         {\r
 178                 CDictionaryBasedTempPath commonPath\r
 179                         = child->path.GetCommonRoot (path);\r
 180 \r
 181                 if (commonPath != this->path)\r
 182                 {\r
 183                         if (child->path == path)\r
 184                         {\r
 185                                 // there is already a node for the exact same path\r
 186                                 // -> use it, if unused so far; append a new node otherwise\r
 187 \r
 188                                 if (child->startRevision == NO_REVISION)\r
 189                                         child->startRevision = startrev;\r
 190                                 else\r
 191                                         return new CSearchPathTree (path, startrev, this);\r
 192                         }\r
 193                         else\r
 194                         {\r
 195                                 // the path is a (true) sub-node of the child\r
 196 \r
 197                                 return child->Insert (path, startrev);\r
 198                         }\r
 199                 }\r
 200         }\r
 201 \r
 202         // no overlap with any existing node\r
 203         // -> create a new child\r
 204 \r
 205         return new CSearchPathTree (path, startrev, this);\r
 206 }\r
 207 \r
 208 void CSearchPathTree::Remove()\r
 209 {\r
 210         startRevision = revision_t (NO_REVISION);\r
 211         lastEntry = NULL;\r
 212 \r
 213         CSearchPathTree* node = this;\r
 214         while (node->IsEmpty() && (node->parent != NULL))\r
 215         {\r
 216                 CSearchPathTree* temp = node;\r
 217                 node = node->parent;\r
 218 \r
 219                 delete temp;\r
 220         }\r
 221 }\r
 222 \r
 223 // there is a new revision entry for this path\r
 224 \r
 225 void CSearchPathTree::ChainEntries (CFullGraphNode* entry)\r
 226 {\r
 227         assert (entry != NULL);\r
 228 \r
 229         lastEntry = entry;\r
 230         startRevision = max (startRevision, entry->GetRevision());\r
 231 }\r
 232 \r
 233 // return true for active paths that don't have a revEntry for this revision\r
 234 \r
 235 bool CSearchPathTree::YetToCover (revision_t revision) const\r
 236 {\r
 237     return    IsActive() \r
 238            && ((lastEntry == NULL) || (lastEntry->GetRevision() < revision));\r
 239 }\r
 240 \r
 241 // return next node in pre-order\r
 242 \r
 243 CSearchPathTree* CSearchPathTree::GetPreOrderNext (CSearchPathTree* lastNode)\r
 244 {\r
 245         if (firstChild != NULL)\r
 246         return firstChild;\r
 247 \r
 248     // there is no sub-tree\r
 249 \r
 250     return GetSkipSubTreeNext (lastNode);\r
 251 }\r
 252 \r
 253 // return next node in pre-order but skip this sub-tree\r
 254 \r
 255 CSearchPathTree* CSearchPathTree::GetSkipSubTreeNext (CSearchPathTree* lastNode)\r
 256 {\r
 257     CSearchPathTree* result = this;\r
 258     while ((result != lastNode) && (result->next == NULL))\r
 259                 result = result->parent;\r
 260 \r
 261     return result == lastNode \r
 262         ? result\r
 263         : result->next;\r
 264 }\r
 265 \r
 266 // find sub-tree of pathID  \r
 267 // (return NULL if there is no such node)\r
 268 \r
 269 CSearchPathTree* CSearchPathTree::FindCommonParent (index_t pathID)\r
 270 {\r
 271         index_t nodePathID = path.GetBasePath().GetIndex();\r
 272 \r
 273         // collect all path elements to find *below* this one\r
 274 \r
 275         index_t pathToFind[MAX_PATH];\r
 276         size_t index = 0;\r
 277 \r
 278         while ((pathID != NO_INDEX) && (pathID > nodePathID))\r
 279         {\r
 280                 pathToFind[index] = pathID;\r
 281                 ++index;\r
 282                 assert (index < MAX_PATH);\r
 283 \r
 284                 pathID = path.GetDictionary()->GetParent (pathID);\r
 285         }\r
 286 \r
 287         // start search at *this node\r
 288 \r
 289         CSearchPathTree* node = this;\r
 290         CSearchPathTree* oldNode = node;\r
 291 \r
 292         while (node != NULL)\r
 293         {\r
 294                 // follow the desired path until it hits or passes the node\r
 295 \r
 296                 while ((index != 0) && (nodePathID > pathID))\r
 297                         pathID = pathToFind[--index];\r
 298 \r
 299                 // scan sibling branches for a match, if this node wasn't one.\r
 300                 // Since all are on the *same* level, either\r
 301                 // * one must match\r
 302                 // * nodePathID < pathID (i.e. node is a true child)\r
 303                 // * path not found\r
 304 \r
 305                 while ((nodePathID < pathID) && (node->next != NULL))\r
 306                 {\r
 307                         node = node->next;\r
 308                         nodePathID = node->path.GetBasePath().GetIndex();\r
 309                 }\r
 310 \r
 311                 // end of search or not in this sub-tree?\r
 312 \r
 313                 if ((index == 0) || (nodePathID != pathID))\r
 314                         return node;\r
 315 \r
 316                 // descend one level\r
 317 \r
 318                 pathID = pathToFind[--index];\r
 319                 \r
 320                 oldNode = node;\r
 321                 node = node->firstChild;\r
 322                 if (node != NULL)\r
 323                         nodePathID = node->path.GetBasePath().GetIndex();\r
 324         }\r
 325 \r
 326         // not found\r
 327 \r
 328         return oldNode;\r
 329 }\r