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.5.2" />
<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.0em;
margin-bottom: 1.5em;
}
div.admonitionblock {
margin-top: 2.0em;
margin-bottom: 2.0em;
margin-right: 10%;
color: #606060;
}
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, div.verseblock {
padding-left: 1.0em;
margin-left: 1.0em;
margin-right: 10%;
border-left: 5px solid #dddddd;
color: #777777;
}
div.quoteblock > div.attribution {
padding-top: 0.5em;
text-align: right;
}
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: 3px solid #dddddd;
}
div.exampleblock > div.content {
border-left: 3px solid #dddddd;
padding-left: 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, p.table.header {
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;
}
.footnote, .footnoteref {
font-size: 0.8em;
}
span.footnote, span.footnoteref {
vertical-align: super;
}
#footnotes {
margin: 20px 0 20px 0;
padding: 7px 0 0 0;
}
#footnotes div.footnote {
margin: 0 0 5px 0;
}
#footnotes hr {
border: none;
border-top: 1px solid silver;
height: 1px;
text-align: left;
margin-left: 0;
width: 20%;
min-width: 100px;
}
@media print {
div#footer-badges { display: none; }
}
div#toc {
margin-bottom: 2.5em;
}
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: 3px solid #dddddd;
padding-left: 0.5em;
}
/* IE6 sets dynamically generated links as visited. */
div#toc a:visited { color: blue; }
</style>
<script type="text/javascript">
window.onload = function(){asciidoc.footnotes();}
var asciidoc = {
toc: function (toclevels) {
function getText(el) {
var text = "";
for (var i = el.firstChild; i != null; i = i.nextSibling) {
if (i.nodeType == 3 ) text += i.data;
else if (i.firstChild != null)
text += getText(i);
}
return text;
}
function TocEntry(el, text, toclevel) {
this.element = el;
this.text = text;
this.toclevel = toclevel;
}
function tocEntries(el, toclevels) {
var result = new Array;
var re = new RegExp('[hH]([2-'+(toclevels+1)+'])');
var iterate = function (el) {
for (var i = el.firstChild; i != null; i = i.nextSibling) {
if (i.nodeType == 1 ) {
var mo = re.exec(i.tagName);
if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
}
iterate(i);
}
}
}
iterate(el);
return result;
}
var toc = document.getElementById("toc");
var entries = tocEntries(document.getElementById("content"), toclevels);
for (var i = 0; i < entries.length; ++i) {
var entry = entries[i];
if (entry.element.id == "")
entry.element.id = "_toc_" + i;
var a = document.createElement("a");
a.href = "#" + entry.element.id;
a.appendChild(document.createTextNode(entry.text));
var div = document.createElement("div");
div.appendChild(a);
div.className = "toclevel" + entry.toclevel;
toc.appendChild(div);
}
if (entries.length == 0)
toc.parentNode.removeChild(toc);
},
footnotes: function () {
var cont = document.getElementById("content");
var noteholder = document.getElementById("footnotes");
var spans = cont.getElementsByTagName("span");
var refs = {};
var n = 0;
for (i=0; i<spans.length; i++) {
if (spans[i].className == "footnote") {
n++;
note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
noteholder.innerHTML +=
"<div class='footnote' id='_footnote_" + n + "'>" +
"<a href='#_footnoteref_" + n + "' title='Return to text'>" +
n + "</a>. " + note + "</div>";
spans[i].innerHTML =
"[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
"' title='View footnote' class='footnote'>" + n + "</a>]";
var id =spans[i].getAttribute("id");
if (id != null) refs["#"+id] = n;
}
}
if (n == 0)
noteholder.parentNode.removeChild(noteholder);
else {
for (i=0; i<spans.length; i++) {
if (spans[i].className == "footnoteref") {
var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
href = href.match(/#.*/)[0]; n = refs[href];
spans[i].innerHTML =
"[<a href='#_footnote_" + n +
"' title='View footnote' class='footnote'>" + n + "</a>]";
}
}
}
}
}
</script>
</head>
<body>
<div id="header">
<h1>string-list API</h1>
</div>
<div id="content">
<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>
Can remove individual items of an unsorted list using
<tt>unsorted_string_list_delete_item</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. If the given
string already exists the insertion will be skipped and the
pointer to the existing item returned.
</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>
<dt class="hdlist1">
<tt>unsorted_string_list_delete_item</tt>
</dt>
<dd>
<p>
Remove an item from 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 third parameter controls if the <tt>util</tt> pointer of the
items should be freed or not.
</p>
</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>
<div id="footnotes"><hr /></div>
<div id="footer">
<div id="footer-text">
Last updated 2012-03-31 11:18:40 PDT
</div>
</div>
</body>
</html>