<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <meta name="generator" content="AsciiDoc 8.4.5" /> <title>string-list API</title> <style type="text/css"> /* Debug borders */ p, li, dt, dd, div, pre, h1, h2, h3, h4, h5, h6 { /* border: 1px solid red; */ } body { margin: 1em 5% 1em 5%; } a { color: blue; text-decoration: underline; } a:visited { color: fuchsia; } em { font-style: italic; color: navy; } strong { font-weight: bold; color: #083194; } tt { color: navy; } h1, h2, h3, h4, h5, h6 { color: #527bbd; font-family: sans-serif; margin-top: 1.2em; margin-bottom: 0.5em; line-height: 1.3; } h1, h2, h3 { border-bottom: 2px solid silver; } h2 { padding-top: 0.5em; } h3 { float: left; } h3 + * { clear: left; } div.sectionbody { font-family: serif; margin-left: 0; } hr { border: 1px solid silver; } p { margin-top: 0.5em; margin-bottom: 0.5em; } ul, ol, li > p { margin-top: 0; } pre { padding: 0; margin: 0; } span#author { color: #527bbd; font-family: sans-serif; font-weight: bold; font-size: 1.1em; } span#email { } span#revnumber, span#revdate, span#revremark { font-family: sans-serif; } div#footer { font-family: sans-serif; font-size: small; border-top: 2px solid silver; padding-top: 0.5em; margin-top: 4.0em; } div#footer-text { float: left; padding-bottom: 0.5em; } div#footer-badges { float: right; padding-bottom: 0.5em; } div#preamble { margin-top: 1.5em; margin-bottom: 1.5em; } div.tableblock, div.imageblock, div.exampleblock, div.verseblock, div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock, div.admonitionblock { margin-top: 1.5em; margin-bottom: 1.5em; } div.admonitionblock { margin-top: 2.5em; margin-bottom: 2.5em; } div.content { /* Block element content. */ padding: 0; } /* Block element titles. */ div.title, caption.title { color: #527bbd; font-family: sans-serif; font-weight: bold; text-align: left; margin-top: 1.0em; margin-bottom: 0.5em; } div.title + * { margin-top: 0; } td div.title:first-child { margin-top: 0.0em; } div.content div.title:first-child { margin-top: 0.0em; } div.content + div.title { margin-top: 0.0em; } div.sidebarblock > div.content { background: #ffffee; border: 1px solid silver; padding: 0.5em; } div.listingblock > div.content { border: 1px solid silver; background: #f4f4f4; padding: 0.5em; } div.quoteblock { padding-left: 2.0em; margin-right: 10%; } div.quoteblock > div.attribution { padding-top: 0.5em; text-align: right; } div.verseblock { padding-left: 2.0em; margin-right: 10%; } div.verseblock > div.content { white-space: pre; } div.verseblock > div.attribution { padding-top: 0.75em; text-align: left; } /* DEPRECATED: Pre version 8.2.7 verse style literal block. */ div.verseblock + div.attribution { text-align: left; } div.admonitionblock .icon { vertical-align: top; font-size: 1.1em; font-weight: bold; text-decoration: underline; color: #527bbd; padding-right: 0.5em; } div.admonitionblock td.content { padding-left: 0.5em; border-left: 2px solid silver; } div.exampleblock > div.content { border-left: 2px solid silver; padding: 0.5em; } div.imageblock div.content { padding-left: 0; } span.image img { border-style: none; } a.image:visited { color: white; } dl { margin-top: 0.8em; margin-bottom: 0.8em; } dt { margin-top: 0.5em; margin-bottom: 0; font-style: normal; color: navy; } dd > *:first-child { margin-top: 0.1em; } ul, ol { list-style-position: outside; } ol.arabic { list-style-type: decimal; } ol.loweralpha { list-style-type: lower-alpha; } ol.upperalpha { list-style-type: upper-alpha; } ol.lowerroman { list-style-type: lower-roman; } ol.upperroman { list-style-type: upper-roman; } div.compact ul, div.compact ol, div.compact p, div.compact p, div.compact div, div.compact div { margin-top: 0.1em; margin-bottom: 0.1em; } div.tableblock > table { border: 3px solid #527bbd; } thead { font-family: sans-serif; font-weight: bold; } tfoot { font-weight: bold; } td > div.verse { white-space: pre; } p.table { margin-top: 0; } /* Because the table frame attribute is overriden by CSS in most browsers. */ div.tableblock > table[frame="void"] { border-style: none; } div.tableblock > table[frame="hsides"] { border-left-style: none; border-right-style: none; } div.tableblock > table[frame="vsides"] { border-top-style: none; border-bottom-style: none; } div.hdlist { margin-top: 0.8em; margin-bottom: 0.8em; } div.hdlist tr { padding-bottom: 15px; } dt.hdlist1.strong, td.hdlist1.strong { font-weight: bold; } td.hdlist1 { vertical-align: top; font-style: normal; padding-right: 0.8em; color: navy; } td.hdlist2 { vertical-align: top; } div.hdlist.compact tr { margin: 0; padding-bottom: 0; } .comment { background: yellow; } @media print { div#footer-badges { display: none; } } div#toctitle { color: #527bbd; font-family: sans-serif; font-size: 1.1em; font-weight: bold; margin-top: 1.0em; margin-bottom: 0.1em; } div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 { margin-top: 0; margin-bottom: 0; } div.toclevel2 { margin-left: 2em; font-size: 0.9em; } div.toclevel3 { margin-left: 4em; font-size: 0.9em; } div.toclevel4 { margin-left: 6em; font-size: 0.9em; } /* Workarounds for IE6's broken and incomplete CSS2. */ div.sidebar-content { background: #ffffee; border: 1px solid silver; padding: 0.5em; } div.sidebar-title, div.image-title { color: #527bbd; font-family: sans-serif; font-weight: bold; margin-top: 0.0em; margin-bottom: 0.5em; } div.listingblock div.content { border: 1px solid silver; background: #f4f4f4; padding: 0.5em; } div.quoteblock-attribution { padding-top: 0.5em; text-align: right; } div.verseblock-content { white-space: pre; } div.verseblock-attribution { padding-top: 0.75em; text-align: left; } div.exampleblock-content { border-left: 2px solid silver; padding-left: 0.5em; } /* IE6 sets dynamically generated links as visited. */ div#toc a:visited { color: blue; } </style> </head> <body> <div id="header"> <h1>string-list API</h1> </div> <div id="preamble"> <div class="sectionbody"> <div class="paragraph"><p>The string_list API offers a data structure and functions to handle sorted and unsorted string lists.</p></div> <div class="paragraph"><p>The <em>string_list</em> struct used to be called <em>path_list</em>, but was renamed because it is not specific to paths.</p></div> <div class="paragraph"><p>The caller:</p></div> <div class="olist arabic"><ol class="arabic"> <li> <p> Allocates and clears a <tt>struct string_list</tt> variable. </p> </li> <li> <p> Initializes the members. You might want to set the flag <tt>strdup_strings</tt> if the strings should be strdup()ed. For example, this is necessary when you add something like git_path("…"), since that function returns a static buffer that will change with the next call to git_path(). </p> <div class="paragraph"><p>If you need something advanced, you can manually malloc() the <tt>items</tt> member (you need this if you add things later) and you should set the <tt>nr</tt> and <tt>alloc</tt> members in that case, too.</p></div> </li> <li> <p> Adds new items to the list, using <tt>string_list_append</tt> or <tt>string_list_insert</tt>. </p> </li> <li> <p> Can check if a string is in the list using <tt>string_list_has_string</tt> or <tt>unsorted_string_list_has_string</tt> and get it from the list using <tt>string_list_lookup</tt> for sorted lists. </p> </li> <li> <p> Can sort an unsorted list using <tt>sort_string_list</tt>. </p> </li> <li> <p> Finally it should free the list using <tt>string_list_clear</tt>. </p> </li> </ol></div> <div class="paragraph"><p>Example:</p></div> <div class="listingblock"> <div class="content"> <pre><tt>struct string_list list; int i; memset(&list, 0, sizeof(struct string_list)); string_list_append(&list, "foo"); string_list_append(&list, "bar"); for (i = 0; i < list.nr; i++) printf("%s\n", list.items[i].string)</tt></pre> </div></div> <div class="admonitionblock"> <table><tr> <td class="icon"> <div class="title">Note</div> </td> <td class="content">It is more efficient to build an unsorted list and sort it afterwards, instead of building a sorted list (<tt>O(n log n)</tt> instead of <tt>O(n^2)</tt>).</td> </tr></table> </div> <div class="paragraph"><p>+ However, if you use the list to check if a certain string was added already, you should not do that (using unsorted_string_list_has_string()), because the complexity would be quadratic again (but with a worse factor).</p></div> </div> </div> <h2 id="_functions">Functions</h2> <div class="sectionbody"> <div class="ulist"><ul> <li> <p> General ones (works with sorted and unsorted lists as well) </p> <div class="dlist"><dl> <dt class="hdlist1"> <tt>print_string_list</tt> </dt> <dd> <p> Dump a string_list to stdout, useful mainly for debugging purposes. It can take an optional header argument and it writes out the string-pointer pairs of the string_list, each one in its own line. </p> </dd> <dt class="hdlist1"> <tt>string_list_clear</tt> </dt> <dd> <p> Free a string_list. The <tt>string</tt> pointer of the items will be freed in case the <tt>strdup_strings</tt> member of the string_list is set. The second parameter controls if the <tt>util</tt> pointer of the items should be freed or not. </p> </dd> </dl></div> </li> <li> <p> Functions for sorted lists only </p> <div class="dlist"><dl> <dt class="hdlist1"> <tt>string_list_has_string</tt> </dt> <dd> <p> Determine if the string_list has a given string or not. </p> </dd> <dt class="hdlist1"> <tt>string_list_insert</tt> </dt> <dd> <p> Insert a new element to the string_list. The returned pointer can be handy if you want to write something to the <tt>util</tt> pointer of the string_list_item containing the just added string. </p> <div class="paragraph"><p>Since this function uses xrealloc() (which die()s if it fails) if the list needs to grow, it is safe not to check the pointer. I.e. you may write <tt>string_list_insert(…)→util = …;</tt>.</p></div> </dd> <dt class="hdlist1"> <tt>string_list_lookup</tt> </dt> <dd> <p> Look up a given string in the string_list, returning the containing string_list_item. If the string is not found, NULL is returned. </p> </dd> </dl></div> </li> <li> <p> Functions for unsorted lists only </p> <div class="dlist"><dl> <dt class="hdlist1"> <tt>string_list_append</tt> </dt> <dd> <p> Append a new string to the end of the string_list. </p> </dd> <dt class="hdlist1"> <tt>sort_string_list</tt> </dt> <dd> <p> Make an unsorted list sorted. </p> </dd> <dt class="hdlist1"> <tt>unsorted_string_list_has_string</tt> </dt> <dd> <p> It’s like <tt>string_list_has_string()</tt> but for unsorted lists. </p> </dd> <dt class="hdlist1"> <tt>unsorted_string_list_lookup</tt> </dt> <dd> <p> It’s like <tt>string_list_lookup()</tt> but for unsorted lists. </p> <div class="paragraph"><p>The above two functions need to look through all items, as opposed to their counterpart for sorted lists, which performs a binary search.</p></div> </dd> </dl></div> </li> </ul></div> </div> <h2 id="_data_structures">Data structures</h2> <div class="sectionbody"> <div class="ulist"><ul> <li> <p> <tt>struct string_list_item</tt> </p> </li> </ul></div> <div class="paragraph"><p>Represents an item of the list. The <tt>string</tt> member is a pointer to the string, and you may use the <tt>util</tt> member for any purpose, if you want.</p></div> <div class="ulist"><ul> <li> <p> <tt>struct string_list</tt> </p> </li> </ul></div> <div class="paragraph"><p>Represents the list itself.</p></div> <div class="olist arabic"><ol class="arabic"> <li> <p> The array of items are available via the <tt>items</tt> member. </p> </li> <li> <p> The <tt>nr</tt> member contains the number of items stored in the list. </p> </li> <li> <p> The <tt>alloc</tt> member is used to avoid reallocating at every insertion. You should not tamper with it. </p> </li> <li> <p> Setting the <tt>strdup_strings</tt> member to 1 will strdup() the strings before adding them, see above. </p> </li> </ol></div> </div> <div id="footer"> <div id="footer-text"> Last updated 2010-12-16 02:52:11 UTC </div> </div> </body> </html>