Rivoreo Source Code Repositories
src.rivoreo.one / net / facil.io / 0.7.0.beta6 / . / docs / 0.6.x / fio_llist.html
blob: c97ee8c28a664e7988a73ea5add729a790fb7ca7 [file] [log] [blame] [raw]
<!DOCTYPE html><html><head><meta charset="utf-8" /><meta content="IE=edge" http-equiv="X-UA-Compatible" /><meta content="width=device-width, initial-scale=1, maximum-scale=2.0, user-scalable=yes, minimal-ui=yes" name="viewport" /><title>facil.io - Linked Lists</title><meta content="facil.io - Linked Lists" name="description" /><link href="https://fonts.googleapis.com/css?family=Montserrat|Quicksand|Karla" rel="stylesheet" type="text/css" /><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.4/jquery.min.js"></script><link href="/assets/styles/main.css" rel="stylesheet" type="text/css" /><script type="application/ld+json">{"@context":"http://schema.org","@type":"WebSite","url":"http://facil.io","name":"facil.io","description":"facil.io - a light web application framework in C, with support for HTTP, WebSockets and Pub/Sub out of the box.","keywords":"C, web, framework, websockets, websocket, realtime, real-time, easy","image":"http://facil.io/website/logo/facil-io.svg","author":[{"@type":"Person","name":"Bo (Myst)","url":"http://stackoverflow.com/users/4025095/myst","email":"bo(at)facil.io"}],"sourceOrganization":{"@context":"http://schema.org","@type":"Organization","name":"Plezi","url":"http://facil.io","description":"facil.io - a light web application framework in C, with support for HTTP, WebSockets and Pub/Sub out of the box.","logo":"http://facil.io/website/logo/facil-io.svg","image":"http://facil.io/website/logo/facil-io.svg","email":"bo(at)facil.io","member":[{"@type":"Person","name":"Bo (Myst)","url":"http://stackoverflow.com/users/4025095/myst","email":"bo(at)facil.io"}]}}</script><meta content="facil.io" name="apple-mobile-web-app-title" /><meta content="facil.io - the C Web Application Framework" name="application-name" /><meta content="#b91d47" name="msapplication-TileColor" /><meta content="/mstile-144x144.png" name="msapplication-TileImage" /><meta content="#ffffff" name="theme-color" /></head><body><a href="/" id="logo"></a><input id="show_nav" type="checkbox" /><nav id="top_nav"><ul><li><a href="/0.7.x/index">Latest Docs</a></li><li><a href="https://github.com/boazsegev/facil.io" target="_blank">Source Code</a></li><li><a href="javascript: change_themes();" id="theme">Night Theme</a></li></ul></nav><input id="show_sidebar" type="checkbox" /><nav id="side_bar"><h2 id="version-0-6-x"><a href="/0.6.x/index">Version 0.6.x</a></h2>
<ul>
<li><a href="/0.6.x/api">API Overview</a></li>
<li><a href="/0.6.x/modules">The Modules</a></li>
</ul>
<h3 id="core-api"><a href="/0.6.x/facil">Core API</a></h3>
<ul>
<li><a href="/0.6.x/defer">Event scheduling</a></li>
<li><a href="/0.6.x/evio">Low Level Polling</a></li>
<li><a href="/0.6.x/sock">Low Level Sockets</a></li>
<li><a href="/0.6.x/fio_mem">Memory Allocation</a></li>
</ul>
<h3 id="extensions">Extensions</h3>
<ul>
<li><a href="/0.6.x/http">HTTP</a></li>
<li><a href="/0.6.x/websockets">WebSockets</a></li>
<li><a href="/0.6.x/pubsub">Pub/Sub</a></li>
<li><a href="/0.6.x/fio_cli">CLI (command line)</a></li>
</ul>
<h3 id="the-fiobj-types"><a href="/0.6.x/fiobj">The FIOBJ types</a></h3>
<ul>
<li><a href="/0.6.x/fiobj_primitives">Primitives</a></li>
<li><a href="/0.6.x/fiobj_numbers">Numbers</a></li>
<li><a href="/0.6.x/fiobj_str">Strings</a></li>
<li><a href="/0.6.x/fiobj_ary">Array</a></li>
<li><a href="/0.6.x/fiobj_hash">HashMap</a></li>
<li><a href="/0.6.x/fiobj_json">JSON</a></li>
</ul>
<h3 id="core-types"><a href="/0.6.x/types">Core Types</a></h3>
<ul>
<li><a href="/0.6.x/fio_ary">C Arrays</a></li>
<li><a href="/0.6.x/fio_hashmap">C HashMap</a></li>
<li><a href="/0.6.x/fio_llist">Linked Lists</a></li>
</ul>
</nav><div id="md_container"><div class='toc'><ul>
<li>
<a href="#a-simple-linked-list">A Simple Linked List</a>
<ul>
<li>
<a href="#data-structure-and-initialization">Data Structure and Initialization.</a>
</li>
<li>
<a href="#generic-linked-list-api">Generic Linked List API</a>
<ul>
<li>
<a href="#fio_ls_push"><code>fio_ls_push</code></a>
</li>
<li>
<a href="#fio_ls_unshift"><code>fio_ls_unshift</code></a>
</li>
<li>
<a href="#fio_ls_pop"><code>fio_ls_pop</code></a>
</li>
<li>
<a href="#fio_ls_shift"><code>fio_ls_shift</code></a>
</li>
<li>
<a href="#fio_ls_remove"><code>fio_ls_remove</code></a>
</li>
<li>
<a href="#fio_ls_is_empty"><code>fio_ls_is_empty</code></a>
</li>
<li>
<a href="#fio_ls_any"><code>fio_ls_any</code></a>
</li>
<li>
<a href="#fio_ls_for"><code>FIO_LS_FOR</code></a>
</li>
</ul>
</li>
<li>
<a href="#embedded-list-api">Embedded List API</a>
<ul>
<li>
<a href="#fio_ls_embd_push"><code>fio_ls_embd_push</code></a>
</li>
<li>
<a href="#fio_ls_embd_unshift"><code>fio_ls_embd_unshift</code></a>
</li>
<li>
<a href="#fio_ls_embd_pop"><code>fio_ls_embd_pop</code></a>
</li>
<li>
<a href="#fio_ls_embd_shift"><code>fio_ls_embd_shift</code></a>
</li>
<li>
<a href="#fio_ls_embd_remove"><code>fio_ls_embd_remove</code></a>
</li>
<li>
<a href="#fio_ls_embd_is_empty"><code>fio_ls_embd_is_empty</code></a>
</li>
<li>
<a href="#fio_ls_embd_any"><code>fio_ls_embd_any</code></a>
</li>
<li>
<a href="#fio_ls_embd_for"><code>FIO_LS_EMBD_FOR</code></a>
</li>
<li>
<a href="#fio_ls_embd_obj"><code>FIO_LS_EMBD_OBJ</code></a>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div><h1 id="a-simple-linked-list">A Simple Linked List</h1>
<p>Linked lists come in two main flavors:</p>
<ol>
<li><p>Generic (or independent) Linked Lists:</p>
<p>Where the list&#39;s node structure has a pointer that points to the object being added to the list. This requires objects to be allocated separately from list node, but allows a single object to belong to many lists (one-to-many).</p></li>
<li><p>Embedded Linked Lists:</p>
<p>Where the list&#39;s node structure needs to be embedded within the object, thereby minimizing memory allocation and improving memory locality, while creating a one-to-one restriction (one object can belong to one list).</p></li>
</ol>
<p>The single file library <code>fio_llist.h</code> offers both flavors in a simple to use package.</p>
<p>The API is practically the same for both, the only difference is in the prefix (<code>fio_ls_X</code> vs. <code>fio_ls_embd_X</code>).</p>
<h2 id="data-structure-and-initialization">Data Structure and Initialization.</h2>
<p>The container for a list is the same as a node, however, it must be initialized so that it links to itself (see <code>FIO_LS_INIT</code>). i.e.:</p>
<pre><code class='highlight'><span class="n">fio_ls_s</span> <span class="n">my_list</span> <span class="o">=</span> <span class="n">FIO_LS_INIT</span><span class="p">(</span><span class="n">my_list</span><span class="p">);</span>
</code></pre>
<p>The linked list container is a simple data structure shown here... however, it is best to <strong>access the data using the API and avoid accessing the data directly</strong>. This will both protect the program from future changes to the data structures and minimize possible errors. </p>
<pre><code class='highlight'><span class="cm">/** an embeded linked list. */</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="n">fio_ls_embd_s</span> <span class="p">{</span>
<span class="k">struct</span> <span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">prev</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="p">}</span> <span class="n">fio_ls_embd_s</span><span class="p">;</span>
<span class="cm">/** an independent linked list. */</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="n">fio_ls_s</span> <span class="p">{</span>
<span class="k">struct</span> <span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">prev</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">obj</span><span class="p">;</span>
<span class="p">}</span> <span class="n">fio_ls_s</span><span class="p">;</span>
<span class="cp">#define FIO_LS_INIT(name) { .next = &amp;(name), .prev = &amp;(name) }
</span></code></pre>
<p>The container can be dynamically allocated, placed of the stack or embedded in a dynamic object.</p>
<h2 id="generic-linked-list-api">Generic Linked List API</h2>
<p>Note that the API is comprised of <strong>inline static functions that act like macros</strong>, so there is no performance to be gained by accessing the data structure directly (only integrity to be lost).</p>
<h3 id="fio_ls_push"><code>fio_ls_push</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="n">fio_ls_push</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">pos</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">obj</span><span class="p">)</span>
</code></pre>
<p>Adds an object to the list&#39;s head.</p>
<h3 id="fio_ls_unshift"><code>fio_ls_unshift</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="n">fio_ls_unshift</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">pos</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">obj</span><span class="p">)</span>
</code></pre>
<p>Adds an object to the list&#39;s tail. </p>
<h3 id="fio_ls_pop"><code>fio_ls_pop</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="o">*</span><span class="n">fio_ls_pop</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Removes an object from the list&#39;s head.</p>
<h3 id="fio_ls_shift"><code>fio_ls_shift</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="o">*</span><span class="n">fio_ls_shift</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Removes an object from the list&#39;s tail.</p>
<h3 id="fio_ls_remove"><code>fio_ls_remove</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="o">*</span><span class="n">fio_ls_remove</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">node</span><span class="p">)</span>
</code></pre>
<p>Removes a node from the list, returning the contained object.</p>
<h3 id="fio_ls_is_empty"><code>fio_ls_is_empty</code></h3>
<pre><code class='highlight'><span class="kt">int</span> <span class="n">fio_ls_is_empty</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Tests if the list is empty.</p>
<h3 id="fio_ls_any"><code>fio_ls_any</code></h3>
<pre><code class='highlight'><span class="kt">int</span> <span class="n">fio_ls_any</span><span class="p">(</span><span class="n">fio_ls_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Tests if the list is NOT empty (contains any nodes).</p>
<h3 id="fio_ls_for"><code>FIO_LS_FOR</code></h3>
<pre><code class='highlight'><span class="n">FIO_LS_FOR</span><span class="p">(</span><span class="n">list</span><span class="p">,</span> <span class="n">pos</span><span class="p">)</span>
</code></pre>
<p>Iterates through the list using a <code>for</code> loop.</p>
<p>Access the data with <code>pos-&gt;obj</code> (<code>pos</code> can be named however you please).</p>
<h2 id="embedded-list-api">Embedded List API</h2>
<h3 id="fio_ls_embd_push"><code>fio_ls_embd_push</code></h3>
<pre><code class='highlight'><span class="kt">void</span> <span class="n">fio_ls_embd_push</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">dest</span><span class="p">,</span> <span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">node</span><span class="p">)</span>
</code></pre>
<p>Adds a node to the list&#39;s head.</p>
<h3 id="fio_ls_embd_unshift"><code>fio_ls_embd_unshift</code></h3>
<pre><code class='highlight'><span class="n">fio_ls_embd_unshift</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">dest</span><span class="p">,</span> <span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">node</span><span class="p">)</span>
</code></pre>
<p>Adds a node to the list&#39;s tail.</p>
<h3 id="fio_ls_embd_pop"><code>fio_ls_embd_pop</code></h3>
<pre><code class='highlight'><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">fio_ls_embd_pop</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Removes a node from the list&#39;s head.</p>
<h3 id="fio_ls_embd_shift"><code>fio_ls_embd_shift</code></h3>
<pre><code class='highlight'><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">fio_ls_embd_shift</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Removes a node from the list&#39;s tail.</p>
<h3 id="fio_ls_embd_remove"><code>fio_ls_embd_remove</code></h3>
<pre><code class='highlight'><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">fio_ls_embd_remove</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">node</span><span class="p">)</span>
</code></pre>
<p>Removes a node from it&#39;s container list.</p>
<h3 id="fio_ls_embd_is_empty"><code>fio_ls_embd_is_empty</code></h3>
<pre><code class='highlight'><span class="n">fio_ls_embd_is_empty</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Tests if the list is empty.</p>
<h3 id="fio_ls_embd_any"><code>fio_ls_embd_any</code></h3>
<pre><code class='highlight'><span class="kt">int</span> <span class="n">fio_ls_embd_any</span><span class="p">(</span><span class="n">fio_ls_embd_s</span> <span class="o">*</span><span class="n">list</span><span class="p">)</span>
</code></pre>
<p>Tests if the list is NOT empty (contains any nodes).</p>
<h3 id="fio_ls_embd_for"><code>FIO_LS_EMBD_FOR</code></h3>
<pre><code class='highlight'><span class="n">FIO_LS_EMBD_FOR</span><span class="p">(</span><span class="n">list</span><span class="p">,</span> <span class="n">node</span><span class="p">)</span>
</code></pre>
<p>Iterates through the list using a <code>for</code> loop.</p>
<p>Access the data with <code>pos-&gt;obj</code> (<code>pos</code> can be named however you pleas..</p>
<h3 id="fio_ls_embd_obj"><code>FIO_LS_EMBD_OBJ</code></h3>
<pre><code class='highlight'><span class="n">FIO_LS_EMBD_OBJ</span><span class="p">(</span><span class="n">type</span><span class="p">,</span> <span class="n">member</span><span class="p">,</span> <span class="n">plist</span><span class="p">)</span> \
<span class="p">((</span><span class="n">type</span> <span class="o">*</span><span class="p">)((</span><span class="kt">uintptr_t</span><span class="p">)(</span><span class="n">plist</span><span class="p">)</span> <span class="o">-</span> <span class="p">(</span><span class="kt">uintptr_t</span><span class="p">)(</span><span class="o">&amp;</span><span class="p">(((</span><span class="n">type</span> <span class="o">*</span><span class="p">)</span><span class="mi">0</span><span class="p">)</span><span class="o">-&gt;</span><span class="n">member</span><span class="p">))))</span>
</code></pre>
<p>Takes a list pointer <code>plist</code> and returns a pointer to it&#39;s container.</p>
<p>This uses pointer offset calculations and can be used to calculate any struct&#39;s pointer (not just list containers) as an offset from a pointer of one of it&#39;s members.</p>
<p>This is a very useful macro to have around.</p>
</div><a href="/" id="sign"></a><div class="hidden" id="notice"><a class="notice_close" onclick="hide_notice()">X</a><div id="notice_text"></div></div><script>function change_themes() {
if(localStorage.getItem("theme") == 'dark') {
localStorage.setItem("theme", "light");
} else {
localStorage.setItem("theme", "dark");
}
$('body')[0].className = localStorage.getItem("theme");
set_theme_link();
$('#show_nav').attr('checked', false);
return false;
};
function sidebar_name() { return window.location.pathname.slice(0, window.location.pathname.lastIndexOf("/")); }
function on_sidebar_link(e) {
sessionStorage.setItem("sidebar.expect", sidebar_name());
sessionStorage.setItem("sidebar.pos", document.getElementById("side_bar").scrollTop);
}
function load_sidebar_pos() {
var e = document.getElementById("side_bar");
if(!e) {
console.warn("No sidebar detected");
return;
}
var expect = sidebar_name();
if(sessionStorage.getItem("sidebar.expect") == expect) {
e.scrollTo(0, parseInt(sessionStorage.getItem("sidebar.pos")));
} else {
sessionStorage.setItem("sidebar.expect", false);
sessionStorage.setItem("sidebar.pos", 0);
}
if(e) {
// add link callbacks
var links = document.links;
var count = links.length;
for (var i = 0; i < count; i++) {
var href = links[i].href;
if(href.startsWith(document.location.origin)) {
href = href.slice(document.location.origin.length);
}
if(href.startsWith(expect)) {
/* add link event */
links[i].addEventListener("click", on_sidebar_link);
}
}
}
};
load_sidebar_pos();
function set_theme_link() {
$("#theme").html( ( (localStorage.getItem("theme") == 'dark') ? "Day" : "Night") + " Theme" );
}
$('body')[0].className = (localStorage.getItem("theme") == 'dark') ? "dark" : "light";
set_theme_link();
function show_notice() { document.getElementById("notice").classList.remove('hidden'); };
function hide_notice() { document.getElementById("notice").classList.add('hidden'); };
$('#toc').on("touchstart", function (e) { return true; } );
$('#toc').on("hover", function (e) { return true; } );
// hljs.initHighlighting();
// Google Analytics
// if(location.hostname != "localhost") {
// (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
// (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
// m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
// })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
// ga('create', 'UA-69931401-1', 'auto');
// ga('send', 'pageview');
// }</script></body></html>