api-string-list.html [plain text]
<!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-17 03:09:32 UTC
</div>
</div>
</body>
</html>