technical/api-tree-walking.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
   2     "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
   6 <meta name="generator" content="AsciiDoc 8.4.5" />
   7 <title>tree walking API</title>
   8 <style type="text/css">
   9 /* Debug borders */
  10 p, li, dt, dd, div, pre, h1, h2, h3, h4, h5, h6 {
  11 /*
  12   border: 1px solid red;
  13 */
  14 }
  15
  16 body {
  17   margin: 1em 5% 1em 5%;
  18 }
  19
  20 a {
  21   color: blue;
  22   text-decoration: underline;
  23 }
  24 a:visited {
  25   color: fuchsia;
  26 }
  27
  28 em {
  29   font-style: italic;
  30   color: navy;
  31 }
  32
  33 strong {
  34   font-weight: bold;
  35   color: #083194;
  36 }
  37
  38 tt {
  39   color: navy;
  40 }
  41
  42 h1, h2, h3, h4, h5, h6 {
  43   color: #527bbd;
  44   font-family: sans-serif;
  45   margin-top: 1.2em;
  46   margin-bottom: 0.5em;
  47   line-height: 1.3;
  48 }
  49
  50 h1, h2, h3 {
  51   border-bottom: 2px solid silver;
  52 }
  53 h2 {
  54   padding-top: 0.5em;
  55 }
  56 h3 {
  57   float: left;
  58 }
  59 h3 + * {
  60   clear: left;
  61 }
  62
  63 div.sectionbody {
  64   font-family: serif;
  65   margin-left: 0;
  66 }
  67
  68 hr {
  69   border: 1px solid silver;
  70 }
  71
  72 p {
  73   margin-top: 0.5em;
  74   margin-bottom: 0.5em;
  75 }
  76
  77 ul, ol, li > p {
  78   margin-top: 0;
  79 }
  80
  81 pre {
  82   padding: 0;
  83   margin: 0;
  84 }
  85
  86 span#author {
  87   color: #527bbd;
  88   font-family: sans-serif;
  89   font-weight: bold;
  90   font-size: 1.1em;
  91 }
  92 span#email {
  93 }
  94 span#revnumber, span#revdate, span#revremark {
  95   font-family: sans-serif;
  96 }
  97
  98 div#footer {
  99   font-family: sans-serif;
 100   font-size: small;
 101   border-top: 2px solid silver;
 102   padding-top: 0.5em;
 103   margin-top: 4.0em;
 104 }
 105 div#footer-text {
 106   float: left;
 107   padding-bottom: 0.5em;
 108 }
 109 div#footer-badges {
 110   float: right;
 111   padding-bottom: 0.5em;
 112 }
 113
 114 div#preamble {
 115   margin-top: 1.5em;
 116   margin-bottom: 1.5em;
 117 }
 118 div.tableblock, div.imageblock, div.exampleblock, div.verseblock,
 119 div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
 120 div.admonitionblock {
 121   margin-top: 1.5em;
 122   margin-bottom: 1.5em;
 123 }
 124 div.admonitionblock {
 125   margin-top: 2.5em;
 126   margin-bottom: 2.5em;
 127 }
 128
 129 div.content { /* Block element content. */
 130   padding: 0;
 131 }
 132
 133 /* Block element titles. */
 134 div.title, caption.title {
 135   color: #527bbd;
 136   font-family: sans-serif;
 137   font-weight: bold;
 138   text-align: left;
 139   margin-top: 1.0em;
 140   margin-bottom: 0.5em;
 141 }
 142 div.title + * {
 143   margin-top: 0;
 144 }
 145
 146 td div.title:first-child {
 147   margin-top: 0.0em;
 148 }
 149 div.content div.title:first-child {
 150   margin-top: 0.0em;
 151 }
 152 div.content + div.title {
 153   margin-top: 0.0em;
 154 }
 155
 156 div.sidebarblock > div.content {
 157   background: #ffffee;
 158   border: 1px solid silver;
 159   padding: 0.5em;
 160 }
 161
 162 div.listingblock > div.content {
 163   border: 1px solid silver;
 164   background: #f4f4f4;
 165   padding: 0.5em;
 166 }
 167
 168 div.quoteblock {
 169   padding-left: 2.0em;
 170   margin-right: 10%;
 171 }
 172 div.quoteblock > div.attribution {
 173   padding-top: 0.5em;
 174   text-align: right;
 175 }
 176
 177 div.verseblock {
 178   padding-left: 2.0em;
 179   margin-right: 10%;
 180 }
 181 div.verseblock > div.content {
 182   white-space: pre;
 183 }
 184 div.verseblock > div.attribution {
 185   padding-top: 0.75em;
 186   text-align: left;
 187 }
 188 /* DEPRECATED: Pre version 8.2.7 verse style literal block. */
 189 div.verseblock + div.attribution {
 190   text-align: left;
 191 }
 192
 193 div.admonitionblock .icon {
 194   vertical-align: top;
 195   font-size: 1.1em;
 196   font-weight: bold;
 197   text-decoration: underline;
 198   color: #527bbd;
 199   padding-right: 0.5em;
 200 }
 201 div.admonitionblock td.content {
 202   padding-left: 0.5em;
 203   border-left: 2px solid silver;
 204 }
 205
 206 div.exampleblock > div.content {
 207   border-left: 2px solid silver;
 208   padding: 0.5em;
 209 }
 210
 211 div.imageblock div.content { padding-left: 0; }
 212 span.image img { border-style: none; }
 213 a.image:visited { color: white; }
 214
 215 dl {
 216   margin-top: 0.8em;
 217   margin-bottom: 0.8em;
 218 }
 219 dt {
 220   margin-top: 0.5em;
 221   margin-bottom: 0;
 222   font-style: normal;
 223   color: navy;
 224 }
 225 dd > *:first-child {
 226   margin-top: 0.1em;
 227 }
 228
 229 ul, ol {
 230     list-style-position: outside;
 231 }
 232 ol.arabic {
 233   list-style-type: decimal;
 234 }
 235 ol.loweralpha {
 236   list-style-type: lower-alpha;
 237 }
 238 ol.upperalpha {
 239   list-style-type: upper-alpha;
 240 }
 241 ol.lowerroman {
 242   list-style-type: lower-roman;
 243 }
 244 ol.upperroman {
 245   list-style-type: upper-roman;
 246 }
 247
 248 div.compact ul, div.compact ol,
 249 div.compact p, div.compact p,
 250 div.compact div, div.compact div {
 251   margin-top: 0.1em;
 252   margin-bottom: 0.1em;
 253 }
 254
 255 div.tableblock > table {
 256   border: 3px solid #527bbd;
 257 }
 258 thead {
 259   font-family: sans-serif;
 260   font-weight: bold;
 261 }
 262 tfoot {
 263   font-weight: bold;
 264 }
 265 td > div.verse {
 266   white-space: pre;
 267 }
 268 p.table {
 269   margin-top: 0;
 270 }
 271 /* Because the table frame attribute is overriden by CSS in most browsers. */
 272 div.tableblock > table[frame="void"] {
 273   border-style: none;
 274 }
 275 div.tableblock > table[frame="hsides"] {
 276   border-left-style: none;
 277   border-right-style: none;
 278 }
 279 div.tableblock > table[frame="vsides"] {
 280   border-top-style: none;
 281   border-bottom-style: none;
 282 }
 283
 284
 285 div.hdlist {
 286   margin-top: 0.8em;
 287   margin-bottom: 0.8em;
 288 }
 289 div.hdlist tr {
 290   padding-bottom: 15px;
 291 }
 292 dt.hdlist1.strong, td.hdlist1.strong {
 293   font-weight: bold;
 294 }
 295 td.hdlist1 {
 296   vertical-align: top;
 297   font-style: normal;
 298   padding-right: 0.8em;
 299   color: navy;
 300 }
 301 td.hdlist2 {
 302   vertical-align: top;
 303 }
 304 div.hdlist.compact tr {
 305   margin: 0;
 306   padding-bottom: 0;
 307 }
 308
 309 .comment {
 310   background: yellow;
 311 }
 312
 313 @media print {
 314   div#footer-badges { display: none; }
 315 }
 316
 317 div#toctitle {
 318   color: #527bbd;
 319   font-family: sans-serif;
 320   font-size: 1.1em;
 321   font-weight: bold;
 322   margin-top: 1.0em;
 323   margin-bottom: 0.1em;
 324 }
 325
 326 div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
 327   margin-top: 0;
 328   margin-bottom: 0;
 329 }
 330 div.toclevel2 {
 331   margin-left: 2em;
 332   font-size: 0.9em;
 333 }
 334 div.toclevel3 {
 335   margin-left: 4em;
 336   font-size: 0.9em;
 337 }
 338 div.toclevel4 {
 339   margin-left: 6em;
 340   font-size: 0.9em;
 341 }
 342 /* Workarounds for IE6's broken and incomplete CSS2. */
 343
 344 div.sidebar-content {
 345   background: #ffffee;
 346   border: 1px solid silver;
 347   padding: 0.5em;
 348 }
 349 div.sidebar-title, div.image-title {
 350   color: #527bbd;
 351   font-family: sans-serif;
 352   font-weight: bold;
 353   margin-top: 0.0em;
 354   margin-bottom: 0.5em;
 355 }
 356
 357 div.listingblock div.content {
 358   border: 1px solid silver;
 359   background: #f4f4f4;
 360   padding: 0.5em;
 361 }
 362
 363 div.quoteblock-attribution {
 364   padding-top: 0.5em;
 365   text-align: right;
 366 }
 367
 368 div.verseblock-content {
 369   white-space: pre;
 370 }
 371 div.verseblock-attribution {
 372   padding-top: 0.75em;
 373   text-align: left;
 374 }
 375
 376 div.exampleblock-content {
 377   border-left: 2px solid silver;
 378   padding-left: 0.5em;
 379 }
 380
 381 /* IE6 sets dynamically generated links as visited. */
 382 div#toc a:visited { color: blue; }
 383 </style>
 384 </head>
 385 <body>
 386 <div id="header">
 387 <h1>tree walking API</h1>
 388 </div>
 389 <div id="preamble">
 390 <div class="sectionbody">
 391 <div class="paragraph"><p>The tree walking API is used to traverse and inspect trees.</p></div>
 392 </div>
 393 </div>
 394 <h2 id="_data_structures">Data Structures</h2>
 395 <div class="sectionbody">
 396 <div class="dlist"><dl>
 397 <dt class="hdlist1">
 398 <tt>struct name_entry</tt>
 399 </dt>
 400 <dd>
 401 <p>
 402         An entry in a tree. Each entry has a sha1 identifier, pathname, and
 403         mode.
 404 </p>
 405 </dd>
 406 <dt class="hdlist1">
 407 <tt>struct tree_desc</tt>
 408 </dt>
 409 <dd>
 410 <p>
 411         A semi-opaque data structure used to maintain the current state of the
 412         walk.
 413 </p>
 414 <div class="ulist"><ul>
 415 <li>
 416 <p>
 417 <tt>buffer</tt> is a pointer into the memory representation of the tree. It always
 418 points at the current entry being visited.
 419 </p>
 420 </li>
 421 <li>
 422 <p>
 423 <tt>size</tt> counts the number of bytes left in the <tt>buffer</tt>.
 424 </p>
 425 </li>
 426 <li>
 427 <p>
 428 <tt>entry</tt> points to the current entry being visited.
 429 </p>
 430 </li>
 431 </ul></div>
 432 </dd>
 433 <dt class="hdlist1">
 434 <tt>struct traverse_info</tt>
 435 </dt>
 436 <dd>
 437 <p>
 438         A structure used to maintain the state of a traversal.
 439 </p>
 440 <div class="ulist"><ul>
 441 <li>
 442 <p>
 443 <tt>prev</tt> points to the traverse_info which was used to descend into the
 444 current tree. If this is the top-level tree <tt>prev</tt> will point to
 445 a dummy traverse_info.
 446 </p>
 447 </li>
 448 <li>
 449 <p>
 450 <tt>name</tt> is the entry for the current tree (if the tree is a subtree).
 451 </p>
 452 </li>
 453 <li>
 454 <p>
 455 <tt>pathlen</tt> is the length of the full path for the current tree.
 456 </p>
 457 </li>
 458 <li>
 459 <p>
 460 <tt>conflicts</tt> can be used by callbacks to maintain directory-file conflicts.
 461 </p>
 462 </li>
 463 <li>
 464 <p>
 465 <tt>fn</tt> is a callback called for each entry in the tree. See Traversing for more
 466 information.
 467 </p>
 468 </li>
 469 <li>
 470 <p>
 471 <tt>data</tt> can be anything the <tt>fn</tt> callback would want to use.
 472 </p>
 473 </li>
 474 <li>
 475 <p>
 476 <tt>show_all_errors</tt> tells whether to stop at the first error or not.
 477 </p>
 478 </li>
 479 </ul></div>
 480 </dd>
 481 </dl></div>
 482 </div>
 483 <h2 id="_initializing">Initializing</h2>
 484 <div class="sectionbody">
 485 <div class="dlist"><dl>
 486 <dt class="hdlist1">
 487 <tt>init_tree_desc</tt>
 488 </dt>
 489 <dd>
 490 <p>
 491         Initialize a <tt>tree_desc</tt> and decode its first entry. The buffer and
 492         size parameters are assumed to be the same as the buffer and size
 493         members of <tt>struct tree</tt>.
 494 </p>
 495 </dd>
 496 <dt class="hdlist1">
 497 <tt>fill_tree_descriptor</tt>
 498 </dt>
 499 <dd>
 500 <p>
 501         Initialize a <tt>tree_desc</tt> and decode its first entry given the sha1 of
 502         a tree. Returns the <tt>buffer</tt> member if the sha1 is a valid tree
 503         identifier and NULL otherwise.
 504 </p>
 505 </dd>
 506 <dt class="hdlist1">
 507 <tt>setup_traverse_info</tt>
 508 </dt>
 509 <dd>
 510 <p>
 511         Initialize a <tt>traverse_info</tt> given the pathname of the tree to start
 512         traversing from. The <tt>base</tt> argument is assumed to be the <tt>path</tt>
 513         member of the <tt>name_entry</tt> being recursed into unless the tree is a
 514         top-level tree in which case the empty string ("") is used.
 515 </p>
 516 </dd>
 517 </dl></div>
 518 </div>
 519 <h2 id="_walking">Walking</h2>
 520 <div class="sectionbody">
 521 <div class="dlist"><dl>
 522 <dt class="hdlist1">
 523 <tt>tree_entry</tt>
 524 </dt>
 525 <dd>
 526 <p>
 527         Visit the next entry in a tree. Returns 1 when there are more entries
 528         left to visit and 0 when all entries have been visited. This is
 529         commonly used in the test of a while loop.
 530 </p>
 531 </dd>
 532 <dt class="hdlist1">
 533 <tt>tree_entry_len</tt>
 534 </dt>
 535 <dd>
 536 <p>
 537         Calculate the length of a tree entry&#8217;s pathname. This utilizes the
 538         memory structure of a tree entry to avoid the overhead of using a
 539         generic strlen().
 540 </p>
 541 </dd>
 542 <dt class="hdlist1">
 543 <tt>update_tree_entry</tt>
 544 </dt>
 545 <dd>
 546 <p>
 547         Walk to the next entry in a tree. This is commonly used in conjunction
 548         with <tt>tree_entry_extract</tt> to inspect the current entry.
 549 </p>
 550 </dd>
 551 <dt class="hdlist1">
 552 <tt>tree_entry_extract</tt>
 553 </dt>
 554 <dd>
 555 <p>
 556         Decode the entry currently being visited (the one pointed to by
 557         <tt>tree_desc&#8217;s</tt> <tt>entry</tt> member) and return the sha1 of the entry. The
 558         <tt>pathp</tt> and <tt>modep</tt> arguments are set to the entry&#8217;s pathname and mode
 559         respectively.
 560 </p>
 561 </dd>
 562 <dt class="hdlist1">
 563 <tt>get_tree_entry</tt>
 564 </dt>
 565 <dd>
 566 <p>
 567         Find an entry in a tree given a pathname and the sha1 of a tree to
 568         search. Returns 0 if the entry is found and -1 otherwise. The third
 569         and fourth parameters are set to the entry&#8217;s sha1 and mode
 570         respectively.
 571 </p>
 572 </dd>
 573 </dl></div>
 574 </div>
 575 <h2 id="_traversing">Traversing</h2>
 576 <div class="sectionbody">
 577 <div class="dlist"><dl>
 578 <dt class="hdlist1">
 579 <tt>traverse_trees</tt>
 580 </dt>
 581 <dd>
 582 <p>
 583         Traverse <tt>n</tt> number of trees in parallel. The <tt>fn</tt> callback member of
 584         <tt>traverse_info</tt> is called once for each tree entry.
 585 </p>
 586 </dd>
 587 <dt class="hdlist1">
 588 <tt>traverse_callback_t</tt>
 589 </dt>
 590 <dd>
 591 <p>
 592         The arguments passed to the traverse callback are as follows:
 593 </p>
 594 <div class="ulist"><ul>
 595 <li>
 596 <p>
 597 <tt>n</tt> counts the number of trees being traversed.
 598 </p>
 599 </li>
 600 <li>
 601 <p>
 602 <tt>mask</tt> has its nth bit set if something exists in the nth entry.
 603 </p>
 604 </li>
 605 <li>
 606 <p>
 607 <tt>dirmask</tt> has its nth bit set if the nth tree&#8217;s entry is a directory.
 608 </p>
 609 </li>
 610 <li>
 611 <p>
 612 <tt>entry</tt> is an array of size <tt>n</tt> where the nth entry is from the nth tree.
 613 </p>
 614 </li>
 615 <li>
 616 <p>
 617 <tt>info</tt> maintains the state of the traversal.
 618 </p>
 619 </li>
 620 </ul></div>
 621 <div class="paragraph"><p>Returning a negative value will terminate the traversal. Otherwise the
 622 return value is treated as an update mask. If the nth bit is set the nth tree
 623 will be updated and if the bit is not set the nth tree entry will be the
 624 same in the next callback invocation.</p></div>
 625 </dd>
 626 <dt class="hdlist1">
 627 <tt>make_traverse_path</tt>
 628 </dt>
 629 <dd>
 630 <p>
 631         Generate the full pathname of a tree entry based from the root of the
 632         traversal. For example, if the traversal has recursed into another
 633         tree named "bar" the pathname of an entry "baz" in the "bar"
 634         tree would be "bar/baz".
 635 </p>
 636 </dd>
 637 <dt class="hdlist1">
 638 <tt>traverse_path_len</tt>
 639 </dt>
 640 <dd>
 641 <p>
 642         Calculate the length of a pathname returned by <tt>make_traverse_path</tt>.
 643         This utilizes the memory structure of a tree entry to avoid the
 644         overhead of using a generic strlen().
 645 </p>
 646 </dd>
 647 </dl></div>
 648 </div>
 649 <h2 id="_authors">Authors</h2>
 650 <div class="sectionbody">
 651 <div class="paragraph"><p>Written by Junio C Hamano &lt;<a href="mailto:gitster@pobox.com">gitster@pobox.com</a>&gt; and Linus Torvalds
 652 &lt;<a href="mailto:torvalds@linux-foundation.org">torvalds@linux-foundation.org</a>&gt;</p></div>
 653 </div>
 654 <div id="footer">
 655 <div id="footer-text">
 656 Last updated 2010-08-22 07:24:51 UTC
 657 </div>
 658 </div>
 659 </body>
 660 </html>