technical/api-string-list.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>string-list 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>string-list API</h1>
 388 </div>
 389 <div id="preamble">
 390 <div class="sectionbody">
 391 <div class="paragraph"><p>The string_list API offers a data structure and functions to handle sorted
 392 and unsorted string lists.</p></div>
 393 <div class="paragraph"><p>The <em>string_list</em> struct used to be called <em>path_list</em>, but was renamed
 394 because it is not specific to paths.</p></div>
 395 <div class="paragraph"><p>The caller:</p></div>
 396 <div class="olist arabic"><ol class="arabic">
 397 <li>
 398 <p>
 399 Allocates and clears a <tt>struct string_list</tt> variable.
 400 </p>
 401 </li>
 402 <li>
 403 <p>
 404 Initializes the members. You might want to set the flag <tt>strdup_strings</tt>
 405   if the strings should be strdup()ed. For example, this is necessary
 406   when you add something like git_path("&#8230;"), since that function returns
 407   a static buffer that will change with the next call to git_path().
 408 </p>
 409 <div class="paragraph"><p>If you need something advanced, you can manually malloc() the <tt>items</tt>
 410 member (you need this if you add things later) and you should set the
 411 <tt>nr</tt> and <tt>alloc</tt> members in that case, too.</p></div>
 412 </li>
 413 <li>
 414 <p>
 415 Adds new items to the list, using <tt>string_list_append</tt> or
 416   <tt>string_list_insert</tt>.
 417 </p>
 418 </li>
 419 <li>
 420 <p>
 421 Can check if a string is in the list using <tt>string_list_has_string</tt> or
 422   <tt>unsorted_string_list_has_string</tt> and get it from the list using
 423   <tt>string_list_lookup</tt> for sorted lists.
 424 </p>
 425 </li>
 426 <li>
 427 <p>
 428 Can sort an unsorted list using <tt>sort_string_list</tt>.
 429 </p>
 430 </li>
 431 <li>
 432 <p>
 433 Finally it should free the list using <tt>string_list_clear</tt>.
 434 </p>
 435 </li>
 436 </ol></div>
 437 <div class="paragraph"><p>Example:</p></div>
 438 <div class="listingblock">
 439 <div class="content">
 440 <pre><tt>struct string_list list;
 441 int i;
 442
 443 memset(&amp;list, 0, sizeof(struct string_list));
 444 string_list_append(&amp;list, "foo");
 445 string_list_append(&amp;list, "bar");
 446 for (i = 0; i &lt; list.nr; i++)
 447         printf("%s\n", list.items[i].string)</tt></pre>
 448 </div></div>
 449 <div class="admonitionblock">
 450 <table><tr>
 451 <td class="icon">
 452 <div class="title">Note</div>
 453 </td>
 454 <td class="content">It is more efficient to build an unsorted list and sort it
 455 afterwards, instead of building a sorted list (<tt>O(n log n)</tt> instead of
 456 <tt>O(n^2)</tt>).</td>
 457 </tr></table>
 458 </div>
 459 <div class="paragraph"><p>+
 460 However, if you use the list to check if a certain string was added
 461 already, you should not do that (using unsorted_string_list_has_string()),
 462 because the complexity would be quadratic again (but with a worse factor).</p></div>
 463 </div>
 464 </div>
 465 <h2 id="_functions">Functions</h2>
 466 <div class="sectionbody">
 467 <div class="ulist"><ul>
 468 <li>
 469 <p>
 470 General ones (works with sorted and unsorted lists as well)
 471 </p>
 472 <div class="dlist"><dl>
 473 <dt class="hdlist1">
 474 <tt>print_string_list</tt>
 475 </dt>
 476 <dd>
 477 <p>
 478         Dump a string_list to stdout, useful mainly for debugging purposes. It
 479         can take an optional header argument and it writes out the
 480         string-pointer pairs of the string_list, each one in its own line.
 481 </p>
 482 </dd>
 483 <dt class="hdlist1">
 484 <tt>string_list_clear</tt>
 485 </dt>
 486 <dd>
 487 <p>
 488         Free a string_list. The <tt>string</tt> pointer of the items will be freed in
 489         case the <tt>strdup_strings</tt> member of the string_list is set. The second
 490         parameter controls if the <tt>util</tt> pointer of the items should be freed
 491         or not.
 492 </p>
 493 </dd>
 494 </dl></div>
 495 </li>
 496 <li>
 497 <p>
 498 Functions for sorted lists only
 499 </p>
 500 <div class="dlist"><dl>
 501 <dt class="hdlist1">
 502 <tt>string_list_has_string</tt>
 503 </dt>
 504 <dd>
 505 <p>
 506         Determine if the string_list has a given string or not.
 507 </p>
 508 </dd>
 509 <dt class="hdlist1">
 510 <tt>string_list_insert</tt>
 511 </dt>
 512 <dd>
 513 <p>
 514         Insert a new element to the string_list. The returned pointer can be
 515         handy if you want to write something to the <tt>util</tt> pointer of the
 516         string_list_item containing the just added string.
 517 </p>
 518 <div class="paragraph"><p>Since this function uses xrealloc() (which die()s if it fails) if the
 519 list needs to grow, it is safe not to check the pointer. I.e. you may
 520 write <tt>string_list_insert(&#8230;)&#8594;util = &#8230;;</tt>.</p></div>
 521 </dd>
 522 <dt class="hdlist1">
 523 <tt>string_list_lookup</tt>
 524 </dt>
 525 <dd>
 526 <p>
 527         Look up a given string in the string_list, returning the containing
 528         string_list_item. If the string is not found, NULL is returned.
 529 </p>
 530 </dd>
 531 </dl></div>
 532 </li>
 533 <li>
 534 <p>
 535 Functions for unsorted lists only
 536 </p>
 537 <div class="dlist"><dl>
 538 <dt class="hdlist1">
 539 <tt>string_list_append</tt>
 540 </dt>
 541 <dd>
 542 <p>
 543         Append a new string to the end of the string_list.
 544 </p>
 545 </dd>
 546 <dt class="hdlist1">
 547 <tt>sort_string_list</tt>
 548 </dt>
 549 <dd>
 550 <p>
 551         Make an unsorted list sorted.
 552 </p>
 553 </dd>
 554 <dt class="hdlist1">
 555 <tt>unsorted_string_list_has_string</tt>
 556 </dt>
 557 <dd>
 558 <p>
 559         It&#8217;s like <tt>string_list_has_string()</tt> but for unsorted lists.
 560 </p>
 561 </dd>
 562 <dt class="hdlist1">
 563 <tt>unsorted_string_list_lookup</tt>
 564 </dt>
 565 <dd>
 566 <p>
 567         It&#8217;s like <tt>string_list_lookup()</tt> but for unsorted lists.
 568 </p>
 569 <div class="paragraph"><p>The above two functions need to look through all items, as opposed to their
 570 counterpart for sorted lists, which performs a binary search.</p></div>
 571 </dd>
 572 </dl></div>
 573 </li>
 574 </ul></div>
 575 </div>
 576 <h2 id="_data_structures">Data structures</h2>
 577 <div class="sectionbody">
 578 <div class="ulist"><ul>
 579 <li>
 580 <p>
 581 <tt>struct string_list_item</tt>
 582 </p>
 583 </li>
 584 </ul></div>
 585 <div class="paragraph"><p>Represents an item of the list. The <tt>string</tt> member is a pointer to the
 586 string, and you may use the <tt>util</tt> member for any purpose, if you want.</p></div>
 587 <div class="ulist"><ul>
 588 <li>
 589 <p>
 590 <tt>struct string_list</tt>
 591 </p>
 592 </li>
 593 </ul></div>
 594 <div class="paragraph"><p>Represents the list itself.</p></div>
 595 <div class="olist arabic"><ol class="arabic">
 596 <li>
 597 <p>
 598 The array of items are available via the <tt>items</tt> member.
 599 </p>
 600 </li>
 601 <li>
 602 <p>
 603 The <tt>nr</tt> member contains the number of items stored in the list.
 604 </p>
 605 </li>
 606 <li>
 607 <p>
 608 The <tt>alloc</tt> member is used to avoid reallocating at every insertion.
 609   You should not tamper with it.
 610 </p>
 611 </li>
 612 <li>
 613 <p>
 614 Setting the <tt>strdup_strings</tt> member to 1 will strdup() the strings
 615   before adding them, see above.
 616 </p>
 617 </li>
 618 </ol></div>
 619 </div>
 620 <div id="footer">
 621 <div id="footer-text">
 622 Last updated 2010-07-01 00:08:13 UTC
 623 </div>
 624 </div>
 625 </body>
 626 </html>