<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>pcsc-lite: simclist.c Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.3 -->
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">pcsc-lite <span id="projectnumber">1.7.2</span></div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li><a href="dirs.html"><span>Directories</span></a></li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="dir_7a4553ee0c3b13d0e595a5d1659110a6.html">src</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="headertitle">
<h1>simclist.c</h1> </div>
</div>
<div class="contents">
<div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> * Copyright (c) 2007,2008,2009,2010 Mij <mij@bitchx.it></span>
<a name="l00003"></a>00003 <span class="comment"> *</span>
<a name="l00004"></a>00004 <span class="comment"> * Permission to use, copy, modify, and distribute this software for any</span>
<a name="l00005"></a>00005 <span class="comment"> * purpose with or without fee is hereby granted, provided that the above</span>
<a name="l00006"></a>00006 <span class="comment"> * copyright notice and this permission notice appear in all copies.</span>
<a name="l00007"></a>00007 <span class="comment"> *</span>
<a name="l00008"></a>00008 <span class="comment"> * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES</span>
<a name="l00009"></a>00009 <span class="comment"> * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF</span>
<a name="l00010"></a>00010 <span class="comment"> * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR</span>
<a name="l00011"></a>00011 <span class="comment"> * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES</span>
<a name="l00012"></a>00012 <span class="comment"> * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN</span>
<a name="l00013"></a>00013 <span class="comment"> * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF</span>
<a name="l00014"></a>00014 <span class="comment"> * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.</span>
<a name="l00015"></a>00015 <span class="comment"> */</span>
<a name="l00016"></a>00016
<a name="l00017"></a>00017
<a name="l00018"></a>00018 <span class="comment">/*</span>
<a name="l00019"></a>00019 <span class="comment"> * SimCList library. See http://mij.oltrelinux.com/devel/simclist</span>
<a name="l00020"></a>00020 <span class="comment"> */</span>
<a name="l00021"></a>00021
<a name="l00022"></a>00022 <span class="comment">/* SimCList implementation, version 1.5 */</span>
<a name="l00023"></a>00023
<a name="l00024"></a>00024 <span class="preprocessor">#include <stdlib.h></span>
<a name="l00025"></a>00025 <span class="preprocessor">#include <string.h></span>
<a name="l00026"></a>00026 <span class="preprocessor">#include <errno.h></span> <span class="comment">/* for setting errno */</span>
<a name="l00027"></a>00027 <span class="preprocessor">#include <sys/types.h></span>
<a name="l00028"></a>00028 <span class="preprocessor">#include <sys/uio.h></span> <span class="comment">/* for READ_ERRCHECK() and write() */</span>
<a name="l00029"></a>00029 <span class="preprocessor">#include <fcntl.h></span> <span class="comment">/* for open() etc */</span>
<a name="l00030"></a>00030 <span class="preprocessor">#include <arpa/inet.h></span> <span class="comment">/* for htons() */</span>
<a name="l00031"></a>00031 <span class="preprocessor">#include <unistd.h></span>
<a name="l00032"></a>00032 <span class="preprocessor">#include <time.h></span> <span class="comment">/* for time() for random seed */</span>
<a name="l00033"></a>00033 <span class="preprocessor">#include <sys/time.h></span> <span class="comment">/* for gettimeofday() */</span>
<a name="l00034"></a>00034 <span class="preprocessor">#include <sys/stat.h></span> <span class="comment">/* for open()'s access modes S_IRUSR etc */</span>
<a name="l00035"></a>00035 <span class="preprocessor">#include <limits.h></span>
<a name="l00036"></a>00036 <span class="preprocessor">#include <stdint.h></span>
<a name="l00037"></a>00037
<a name="l00038"></a>00038
<a name="l00039"></a>00039 <span class="comment">/* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */</span>
<a name="l00040"></a>00040 <span class="preprocessor">#if !defined(WIN32) || !defined(_MSC_VER)</span>
<a name="l00041"></a>00041 <span class="preprocessor"></span><span class="preprocessor"># include <inttypes.h></span> <span class="comment">/* (u)int*_t */</span>
<a name="l00042"></a>00042 <span class="preprocessor">#else</span>
<a name="l00043"></a>00043 <span class="preprocessor"></span><span class="preprocessor"># include <basetsd.h></span>
<a name="l00044"></a>00044 <span class="keyword">typedef</span> UINT8 uint8_t;
<a name="l00045"></a>00045 <span class="keyword">typedef</span> UINT16 uint16_t;
<a name="l00046"></a>00046 <span class="keyword">typedef</span> ULONG32 uint32_t;
<a name="l00047"></a>00047 <span class="keyword">typedef</span> UINT64 uint64_t;
<a name="l00048"></a>00048 <span class="keyword">typedef</span> INT8 int8_t;
<a name="l00049"></a>00049 <span class="keyword">typedef</span> INT16 int16_t;
<a name="l00050"></a>00050 <span class="keyword">typedef</span> LONG32 int32_t;
<a name="l00051"></a>00051 <span class="keyword">typedef</span> INT64 int64_t;
<a name="l00052"></a>00052 <span class="preprocessor">#endif</span>
<a name="l00053"></a>00053 <span class="preprocessor"></span>
<a name="l00054"></a>00054
<a name="l00055"></a>00055
<a name="l00056"></a>00056 <span class="preprocessor">#ifndef SIMCLIST_NO_DUMPRESTORE</span>
<a name="l00057"></a>00057 <span class="preprocessor"></span><span class="comment">/* convert 64bit integers from host to network format */</span>
<a name="l00058"></a>00058 <span class="preprocessor">#define hton64(x) (\</span>
<a name="l00059"></a>00059 <span class="preprocessor"> htons(1) == 1 ? \</span>
<a name="l00060"></a>00060 <span class="preprocessor"> (uint64_t)x </span><span class="comment">/* big endian */</span> \
<a name="l00061"></a>00061 : <span class="comment">/* little endian */</span> \
<a name="l00062"></a>00062 ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
<a name="l00063"></a>00063 (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
<a name="l00064"></a>00064 (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
<a name="l00065"></a>00065 (((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \
<a name="l00066"></a>00066 (((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \
<a name="l00067"></a>00067 (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
<a name="l00068"></a>00068 (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
<a name="l00069"></a>00069 (((uint64_t)(x) & 0x00000000000000ffULL) << 56))) \
<a name="l00070"></a>00070 )
<a name="l00071"></a>00071
<a name="l00072"></a>00072 <span class="comment">/* convert 64bit integers from network to host format */</span>
<a name="l00073"></a>00073 <span class="preprocessor">#define ntoh64(x) (hton64(x))</span>
<a name="l00074"></a>00074 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00075"></a>00075 <span class="preprocessor"></span>
<a name="l00076"></a>00076 <span class="comment">/* some OSes don't have EPROTO (eg OpenBSD) */</span>
<a name="l00077"></a>00077 <span class="preprocessor">#ifndef EPROTO</span>
<a name="l00078"></a>00078 <span class="preprocessor"></span><span class="preprocessor">#define EPROTO EIO</span>
<a name="l00079"></a>00079 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00080"></a>00080 <span class="preprocessor"></span>
<a name="l00081"></a>00081 <span class="comment">/* disable asserts */</span>
<a name="l00082"></a>00082 <span class="preprocessor">#ifndef SIMCLIST_DEBUG</span>
<a name="l00083"></a>00083 <span class="preprocessor"></span><span class="preprocessor">#define NDEBUG</span>
<a name="l00084"></a>00084 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00085"></a>00085 <span class="preprocessor"></span>
<a name="l00086"></a>00086 <span class="preprocessor">#include <assert.h></span>
<a name="l00087"></a>00087
<a name="l00088"></a>00088 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00089"></a>00089 <span class="preprocessor"></span><span class="comment">/* limit (approx) to the number of threads running</span>
<a name="l00090"></a>00090 <span class="comment"> * for threaded operations. Only meant when</span>
<a name="l00091"></a>00091 <span class="comment"> * SIMCLIST_WITH_THREADS is defined */</span>
<a name="l00092"></a>00092 <span class="preprocessor">#define SIMCLIST_MAXTHREADS 2</span>
<a name="l00093"></a>00093 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00094"></a>00094 <span class="preprocessor"></span>
<a name="l00095"></a>00095 <span class="comment">/*</span>
<a name="l00096"></a>00096 <span class="comment"> * how many elems to keep as spare. During a deletion, an element</span>
<a name="l00097"></a>00097 <span class="comment"> * can be saved in a "free-list", not free()d immediately. When</span>
<a name="l00098"></a>00098 <span class="comment"> * latter insertions are performed, spare elems can be used instead</span>
<a name="l00099"></a>00099 <span class="comment"> * of malloc()ing new elems.</span>
<a name="l00100"></a>00100 <span class="comment"> *</span>
<a name="l00101"></a>00101 <span class="comment"> * about this param, some values for appending</span>
<a name="l00102"></a>00102 <span class="comment"> * 10 million elems into an empty list:</span>
<a name="l00103"></a>00103 <span class="comment"> * (#, time[sec], gain[%], gain/no[%])</span>
<a name="l00104"></a>00104 <span class="comment"> * 0 2,164 0,00 0,00 <-- feature disabled</span>
<a name="l00105"></a>00105 <span class="comment"> * 1 1,815 34,9 34,9</span>
<a name="l00106"></a>00106 <span class="comment"> * 2 1,446 71,8 35,9 <-- MAX gain/no</span>
<a name="l00107"></a>00107 <span class="comment"> * 3 1,347 81,7 27,23</span>
<a name="l00108"></a>00108 <span class="comment"> * 5 1,213 95,1 19,02</span>
<a name="l00109"></a>00109 <span class="comment"> * 8 1,064 110,0 13,75</span>
<a name="l00110"></a>00110 <span class="comment"> * 10 1,015 114,9 11,49 <-- MAX gain w/ likely sol</span>
<a name="l00111"></a>00111 <span class="comment"> * 15 1,019 114,5 7,63</span>
<a name="l00112"></a>00112 <span class="comment"> * 25 0,985 117,9 4,72</span>
<a name="l00113"></a>00113 <span class="comment"> * 50 1,088 107,6 2,15</span>
<a name="l00114"></a>00114 <span class="comment"> * 75 1,016 114,8 1,53</span>
<a name="l00115"></a>00115 <span class="comment"> * 100 0,988 117,6 1,18</span>
<a name="l00116"></a>00116 <span class="comment"> * 150 1,022 114,2 0,76</span>
<a name="l00117"></a>00117 <span class="comment"> * 200 0,939 122,5 0,61 <-- MIN time</span>
<a name="l00118"></a>00118 <span class="comment"> */</span>
<a name="l00119"></a>00119 <span class="preprocessor">#ifndef SIMCLIST_MAX_SPARE_ELEMS</span>
<a name="l00120"></a>00120 <span class="preprocessor"></span><span class="preprocessor">#define SIMCLIST_MAX_SPARE_ELEMS 5</span>
<a name="l00121"></a>00121 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00122"></a>00122 <span class="preprocessor"></span>
<a name="l00123"></a>00123
<a name="l00124"></a>00124 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00125"></a>00125 <span class="preprocessor"></span><span class="preprocessor">#include <pthread.h></span>
<a name="l00126"></a>00126 <span class="preprocessor">#endif</span>
<a name="l00127"></a>00127 <span class="preprocessor"></span>
<a name="l00128"></a>00128 <span class="preprocessor">#include "simclist.h"</span>
<a name="l00129"></a>00129
<a name="l00130"></a>00130
<a name="l00131"></a>00131 <span class="comment">/* minumum number of elements for sorting with quicksort instead of insertion */</span>
<a name="l00132"></a>00132 <span class="preprocessor">#define SIMCLIST_MINQUICKSORTELS 24</span>
<a name="l00133"></a>00133 <span class="preprocessor"></span>
<a name="l00134"></a>00134
<a name="l00135"></a>00135 <span class="comment">/* list dump declarations */</span>
<a name="l00136"></a>00136 <span class="preprocessor">#define SIMCLIST_DUMPFORMAT_VERSION 1 </span><span class="comment">/* (short integer) version of fileformat managed by _dump* and _restore* functions */</span>
<a name="l00137"></a>00137
<a name="l00138"></a>00138 <span class="preprocessor">#define SIMCLIST_DUMPFORMAT_HEADERLEN 30 </span><span class="comment">/* length of the header */</span>
<a name="l00139"></a>00139
<a name="l00140"></a>00140 <span class="comment">/* header for a list dump */</span>
<a name="l00141"></a><a class="code" href="structlist__dump__header__s.html">00141</a> <span class="keyword">struct </span><a class="code" href="structlist__dump__header__s.html">list_dump_header_s</a> {
<a name="l00142"></a>00142 uint16_t ver; <span class="comment">/* version */</span>
<a name="l00143"></a>00143 int64_t timestamp; <span class="comment">/* dump timestamp */</span>
<a name="l00144"></a>00144 int32_t rndterm; <span class="comment">/* random value terminator -- terminates the data sequence */</span>
<a name="l00145"></a>00145
<a name="l00146"></a>00146 uint32_t totlistlen; <span class="comment">/* sum of every element' size, bytes */</span>
<a name="l00147"></a>00147 uint32_t numels; <span class="comment">/* number of elements */</span>
<a name="l00148"></a>00148 uint32_t elemlen; <span class="comment">/* bytes length of an element, for constant-size lists, <= 0 otherwise */</span>
<a name="l00149"></a>00149 int32_t listhash; <span class="comment">/* hash of the list at the time of dumping, or 0 if to be ignored */</span>
<a name="l00150"></a>00150 };
<a name="l00151"></a>00151
<a name="l00152"></a>00152
<a name="l00153"></a>00153
<a name="l00154"></a>00154 <span class="comment">/* deletes tmp from list, with care wrt its position (head, tail, middle) */</span>
<a name="l00155"></a>00155 <span class="keyword">static</span> <span class="keywordtype">int</span> list_drop_elem(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *tmp, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos);
<a name="l00156"></a>00156
<a name="l00157"></a>00157 <span class="comment">/* set default values for initialized lists */</span>
<a name="l00158"></a>00158 <span class="keyword">static</span> <span class="keywordtype">int</span> list_attributes_setdefaults(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l);
<a name="l00159"></a>00159
<a name="l00160"></a>00160 <span class="preprocessor">#ifndef NDEBUG</span>
<a name="l00161"></a>00161 <span class="preprocessor"></span><span class="comment">/* check whether the list internal REPresentation is valid -- Costs O(n) */</span>
<a name="l00162"></a>00162 <span class="keyword">static</span> <span class="keywordtype">int</span> list_repOk(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l);
<a name="l00163"></a>00163
<a name="l00164"></a>00164 <span class="comment">/* check whether the list attribute set is valid -- Costs O(1) */</span>
<a name="l00165"></a>00165 <span class="keyword">static</span> <span class="keywordtype">int</span> list_attrOk(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l);
<a name="l00166"></a>00166 <span class="preprocessor">#endif</span>
<a name="l00167"></a>00167 <span class="preprocessor"></span>
<a name="l00168"></a>00168 <span class="comment">/* do not inline, this is recursive */</span>
<a name="l00169"></a>00169 <span class="keyword">static</span> <span class="keywordtype">void</span> list_sort_quicksort(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus,
<a name="l00170"></a>00170 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> first, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *fel,
<a name="l00171"></a>00171 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> last, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *lel);
<a name="l00172"></a>00172
<a name="l00173"></a>00173 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> list_sort_selectionsort(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus,
<a name="l00174"></a>00174 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> first, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *fel,
<a name="l00175"></a>00175 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> last, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *lel);
<a name="l00176"></a>00176
<a name="l00177"></a>00177 <span class="keyword">static</span> <span class="keywordtype">void</span> *list_get_minmax(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus);
<a name="l00178"></a>00178
<a name="l00179"></a>00179 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *list_findpos(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> posstart);
<a name="l00180"></a>00180
<a name="l00181"></a>00181 <span class="comment">/* write() decorated with error checking logic */</span>
<a name="l00182"></a>00182 <span class="preprocessor">#define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \</span>
<a name="l00183"></a>00183 <span class="preprocessor"> if (write(fd, msgbuf, msglen) < 0) return -1; \</span>
<a name="l00184"></a>00184 <span class="preprocessor"> } while (0);</span>
<a name="l00185"></a>00185 <span class="preprocessor"></span><span class="comment">/* READ_ERRCHECK() decorated with error checking logic */</span>
<a name="l00186"></a>00186 <span class="preprocessor">#define READ_ERRCHECK(fd, msgbuf, msglen) do { \</span>
<a name="l00187"></a>00187 <span class="preprocessor"> if (read(fd, msgbuf, msglen) != msglen) { \</span>
<a name="l00188"></a>00188 <span class="preprocessor"> </span><span class="comment">/*errno = EPROTO;*/</span> \
<a name="l00189"></a>00189 return -1; \
<a name="l00190"></a>00190 } \
<a name="l00191"></a>00191 } while (0);
<a name="l00192"></a>00192
<a name="l00193"></a>00193 <span class="comment">/*</span>
<a name="l00194"></a>00194 <span class="comment"> * Random Number Generator</span>
<a name="l00195"></a>00195 <span class="comment"> * </span>
<a name="l00196"></a>00196 <span class="comment"> * The user is expected to seed the RNG (ie call srand()) if </span>
<a name="l00197"></a>00197 <span class="comment"> * SIMCLIST_SYSTEM_RNG is defined.</span>
<a name="l00198"></a>00198 <span class="comment"> *</span>
<a name="l00199"></a>00199 <span class="comment"> * Otherwise, a self-contained RNG based on LCG is used; see</span>
<a name="l00200"></a>00200 <span class="comment"> * http://en.wikipedia.org/wiki/Linear_congruential_generator .</span>
<a name="l00201"></a>00201 <span class="comment"> *</span>
<a name="l00202"></a>00202 <span class="comment"> * Facts pro local RNG:</span>
<a name="l00203"></a>00203 <span class="comment"> * 1. no need for the user to call srand() on his own</span>
<a name="l00204"></a>00204 <span class="comment"> * 2. very fast, possibly faster than OS</span>
<a name="l00205"></a>00205 <span class="comment"> * 3. avoid interference with user's RNG</span>
<a name="l00206"></a>00206 <span class="comment"> *</span>
<a name="l00207"></a>00207 <span class="comment"> * Facts pro system RNG:</span>
<a name="l00208"></a>00208 <span class="comment"> * 1. may be more accurate (irrelevant for SimCList randno purposes)</span>
<a name="l00209"></a>00209 <span class="comment"> * 2. why reinvent the wheel</span>
<a name="l00210"></a>00210 <span class="comment"> *</span>
<a name="l00211"></a>00211 <span class="comment"> * Default to local RNG for user's ease of use.</span>
<a name="l00212"></a>00212 <span class="comment"> */</span>
<a name="l00213"></a>00213
<a name="l00214"></a>00214 <span class="preprocessor">#ifdef SIMCLIST_SYSTEM_RNG</span>
<a name="l00215"></a>00215 <span class="preprocessor"></span><span class="comment">/* keep track whether we initialized already (non-0) or not (0) */</span>
<a name="l00216"></a>00216 <span class="keyword">static</span> <span class="keywordtype">unsigned</span> random_seed = 0;
<a name="l00217"></a>00217
<a name="l00218"></a>00218 <span class="comment">/* use local RNG */</span>
<a name="l00219"></a>00219 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> seed_random() {
<a name="l00220"></a>00220 <span class="keywordflow">if</span> (random_seed == 0)
<a name="l00221"></a>00221 random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
<a name="l00222"></a>00222 }
<a name="l00223"></a>00223
<a name="l00224"></a>00224 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">long</span> get_random() {
<a name="l00225"></a>00225 random_seed = (1664525 * random_seed + 1013904223);
<a name="l00226"></a>00226 <span class="keywordflow">return</span> random_seed;
<a name="l00227"></a>00227 }
<a name="l00228"></a>00228
<a name="l00229"></a>00229 <span class="preprocessor">#else</span>
<a name="l00230"></a>00230 <span class="preprocessor"></span><span class="comment">/* use OS's random generator */</span>
<a name="l00231"></a>00231 <span class="preprocessor"># define seed_random()</span>
<a name="l00232"></a>00232 <span class="preprocessor"></span><span class="preprocessor"># define get_random() (rand())</span>
<a name="l00233"></a>00233 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00234"></a>00234 <span class="preprocessor"></span>
<a name="l00235"></a>00235
<a name="l00236"></a>00236 <span class="comment">/* list initialization */</span>
<a name="l00237"></a>00237 <span class="keywordtype">int</span> list_init(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00238"></a>00238 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00239"></a>00239
<a name="l00240"></a>00240 seed_random();
<a name="l00241"></a>00241
<a name="l00242"></a>00242 l->numels = 0;
<a name="l00243"></a>00243
<a name="l00244"></a>00244 <span class="comment">/* head/tail sentinels and mid pointer */</span>
<a name="l00245"></a>00245 l->head_sentinel = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a>));
<a name="l00246"></a>00246 l->tail_sentinel = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a>));
<a name="l00247"></a>00247 l->head_sentinel->next = l->tail_sentinel;
<a name="l00248"></a>00248 l->tail_sentinel->prev = l->head_sentinel;
<a name="l00249"></a>00249 l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
<a name="l00250"></a>00250 l->head_sentinel->data = l->tail_sentinel->data = NULL;
<a name="l00251"></a>00251
<a name="l00252"></a>00252 <span class="comment">/* iteration attributes */</span>
<a name="l00253"></a>00253 l->iter_active = 0;
<a name="l00254"></a>00254 l->iter_pos = 0;
<a name="l00255"></a>00255 l->iter_curentry = NULL;
<a name="l00256"></a>00256
<a name="l00257"></a>00257 <span class="comment">/* free-list attributes */</span>
<a name="l00258"></a>00258 l->spareels = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> **)malloc(SIMCLIST_MAX_SPARE_ELEMS * <span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *));
<a name="l00259"></a>00259 l->spareelsnum = 0;
<a name="l00260"></a>00260
<a name="l00261"></a>00261 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00262"></a>00262 <span class="preprocessor"></span> l->threadcount = 0;
<a name="l00263"></a>00263 <span class="preprocessor">#endif</span>
<a name="l00264"></a>00264 <span class="preprocessor"></span>
<a name="l00265"></a>00265 list_attributes_setdefaults(l);
<a name="l00266"></a>00266
<a name="l00267"></a>00267 assert(list_repOk(l));
<a name="l00268"></a>00268 assert(list_attrOk(l));
<a name="l00269"></a>00269
<a name="l00270"></a>00270 <span class="keywordflow">return</span> 0;
<a name="l00271"></a>00271 }
<a name="l00272"></a>00272
<a name="l00273"></a>00273 <span class="keywordtype">void</span> list_destroy(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00274"></a>00274 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00275"></a>00275
<a name="l00276"></a>00276 list_clear(l);
<a name="l00277"></a>00277 <span class="keywordflow">for</span> (i = 0; i < l->spareelsnum; i++) {
<a name="l00278"></a>00278 free(l->spareels[i]);
<a name="l00279"></a>00279 }
<a name="l00280"></a>00280 free(l->spareels);
<a name="l00281"></a>00281 free(l->head_sentinel);
<a name="l00282"></a>00282 free(l->tail_sentinel);
<a name="l00283"></a>00283 }
<a name="l00284"></a>00284
<a name="l00285"></a>00285 <span class="keywordtype">int</span> list_attributes_setdefaults(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00286"></a>00286 l->attrs.comparator = NULL;
<a name="l00287"></a>00287 l->attrs.seeker = NULL;
<a name="l00288"></a>00288
<a name="l00289"></a>00289 <span class="comment">/* also free() element data when removing and element from the list */</span>
<a name="l00290"></a>00290 l->attrs.meter = NULL;
<a name="l00291"></a>00291 l->attrs.copy_data = 0;
<a name="l00292"></a>00292
<a name="l00293"></a>00293 l->attrs.hasher = NULL;
<a name="l00294"></a>00294
<a name="l00295"></a>00295 <span class="comment">/* serializer/unserializer */</span>
<a name="l00296"></a>00296 l->attrs.serializer = NULL;
<a name="l00297"></a>00297 l->attrs.unserializer = NULL;
<a name="l00298"></a>00298
<a name="l00299"></a>00299 assert(list_attrOk(l));
<a name="l00300"></a>00300
<a name="l00301"></a>00301 <span class="keywordflow">return</span> 0;
<a name="l00302"></a>00302 }
<a name="l00303"></a>00303
<a name="l00304"></a>00304 <span class="comment">/* setting list properties */</span>
<a name="l00305"></a>00305 <span class="keywordtype">int</span> list_attributes_comparator(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_comparator comparator_fun) {
<a name="l00306"></a>00306 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00307"></a>00307
<a name="l00308"></a>00308 l->attrs.comparator = comparator_fun;
<a name="l00309"></a>00309
<a name="l00310"></a>00310 assert(list_attrOk(l));
<a name="l00311"></a>00311
<a name="l00312"></a>00312 <span class="keywordflow">return</span> 0;
<a name="l00313"></a>00313 }
<a name="l00314"></a>00314
<a name="l00315"></a>00315 <span class="keywordtype">int</span> list_attributes_seeker(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_seeker seeker_fun) {
<a name="l00316"></a>00316 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00317"></a>00317
<a name="l00318"></a>00318 l->attrs.seeker = seeker_fun;
<a name="l00319"></a>00319 assert(list_attrOk(l));
<a name="l00320"></a>00320
<a name="l00321"></a>00321 <span class="keywordflow">return</span> 0;
<a name="l00322"></a>00322 }
<a name="l00323"></a>00323
<a name="l00324"></a>00324 <span class="keywordtype">int</span> list_attributes_copy(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_meter metric_fun, <span class="keywordtype">int</span> copy_data) {
<a name="l00325"></a>00325 <span class="keywordflow">if</span> (l == NULL || (metric_fun == NULL && copy_data != 0)) <span class="keywordflow">return</span> -1;
<a name="l00326"></a>00326
<a name="l00327"></a>00327 l->attrs.meter = metric_fun;
<a name="l00328"></a>00328 l->attrs.copy_data = copy_data;
<a name="l00329"></a>00329
<a name="l00330"></a>00330 assert(list_attrOk(l));
<a name="l00331"></a>00331
<a name="l00332"></a>00332 <span class="keywordflow">return</span> 0;
<a name="l00333"></a>00333 }
<a name="l00334"></a>00334
<a name="l00335"></a>00335 <span class="keywordtype">int</span> list_attributes_hash_computer(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_hash_computer hash_computer_fun) {
<a name="l00336"></a>00336 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00337"></a>00337
<a name="l00338"></a>00338 l->attrs.hasher = hash_computer_fun;
<a name="l00339"></a>00339 assert(list_attrOk(l));
<a name="l00340"></a>00340 <span class="keywordflow">return</span> 0;
<a name="l00341"></a>00341 }
<a name="l00342"></a>00342
<a name="l00343"></a>00343 <span class="keywordtype">int</span> list_attributes_serializer(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_serializer serializer_fun) {
<a name="l00344"></a>00344 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00345"></a>00345
<a name="l00346"></a>00346 l->attrs.serializer = serializer_fun;
<a name="l00347"></a>00347 assert(list_attrOk(l));
<a name="l00348"></a>00348 <span class="keywordflow">return</span> 0;
<a name="l00349"></a>00349 }
<a name="l00350"></a>00350
<a name="l00351"></a>00351 <span class="keywordtype">int</span> list_attributes_unserializer(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, element_unserializer unserializer_fun) {
<a name="l00352"></a>00352 <span class="keywordflow">if</span> (l == NULL) <span class="keywordflow">return</span> -1;
<a name="l00353"></a>00353
<a name="l00354"></a>00354 l->attrs.unserializer = unserializer_fun;
<a name="l00355"></a>00355 assert(list_attrOk(l));
<a name="l00356"></a>00356 <span class="keywordflow">return</span> 0;
<a name="l00357"></a>00357 }
<a name="l00358"></a>00358
<a name="l00359"></a>00359 <span class="keywordtype">int</span> list_append(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data) {
<a name="l00360"></a>00360 <span class="keywordflow">return</span> list_insert_at(l, data, l->numels);
<a name="l00361"></a>00361 }
<a name="l00362"></a>00362
<a name="l00363"></a>00363 <span class="keywordtype">int</span> list_prepend(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data) {
<a name="l00364"></a>00364 <span class="keywordflow">return</span> list_insert_at(l, data, 0);
<a name="l00365"></a>00365 }
<a name="l00366"></a>00366
<a name="l00367"></a>00367 <span class="keywordtype">void</span> *list_fetch(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00368"></a>00368 <span class="keywordflow">return</span> list_extract_at(l, 0);
<a name="l00369"></a>00369 }
<a name="l00370"></a>00370
<a name="l00371"></a>00371 <span class="keywordtype">void</span> *list_get_at(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos) {
<a name="l00372"></a>00372 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *tmp;
<a name="l00373"></a>00373
<a name="l00374"></a>00374 tmp = list_findpos(l, pos);
<a name="l00375"></a>00375
<a name="l00376"></a>00376 <span class="keywordflow">return</span> (tmp != NULL ? tmp->data : NULL);
<a name="l00377"></a>00377 }
<a name="l00378"></a>00378
<a name="l00379"></a>00379 <span class="keywordtype">void</span> *list_get_max(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00380"></a>00380 <span class="keywordflow">return</span> list_get_minmax(l, +1);
<a name="l00381"></a>00381 }
<a name="l00382"></a>00382
<a name="l00383"></a>00383 <span class="keywordtype">void</span> *list_get_min(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00384"></a>00384 <span class="keywordflow">return</span> list_get_minmax(l, -1);
<a name="l00385"></a>00385 }
<a name="l00386"></a>00386
<a name="l00387"></a>00387 <span class="comment">/* REQUIRES {list->numels >= 1}</span>
<a name="l00388"></a>00388 <span class="comment"> * return the min (versus < 0) or max value (v > 0) in l */</span>
<a name="l00389"></a>00389 <span class="keyword">static</span> <span class="keywordtype">void</span> *list_get_minmax(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus) {
<a name="l00390"></a>00390 <span class="keywordtype">void</span> *curminmax;
<a name="l00391"></a>00391 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *s;
<a name="l00392"></a>00392
<a name="l00393"></a>00393 <span class="keywordflow">if</span> (l->attrs.comparator == NULL || l->numels == 0)
<a name="l00394"></a>00394 <span class="keywordflow">return</span> NULL;
<a name="l00395"></a>00395
<a name="l00396"></a>00396 curminmax = l->head_sentinel->next->data;
<a name="l00397"></a>00397 <span class="keywordflow">for</span> (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
<a name="l00398"></a>00398 <span class="keywordflow">if</span> (l->attrs.comparator(curminmax, s->data) * versus > 0)
<a name="l00399"></a>00399 curminmax = s->data;
<a name="l00400"></a>00400 }
<a name="l00401"></a>00401
<a name="l00402"></a>00402 <span class="keywordflow">return</span> curminmax;
<a name="l00403"></a>00403 }
<a name="l00404"></a>00404
<a name="l00405"></a>00405 <span class="comment">/* set tmp to point to element at index posstart in l */</span>
<a name="l00406"></a>00406 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *list_findpos(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> posstart) {
<a name="l00407"></a>00407 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *ptr;
<a name="l00408"></a>00408 <span class="keywordtype">float</span> x;
<a name="l00409"></a>00409 <span class="keywordtype">int</span> i;
<a name="l00410"></a>00410
<a name="l00411"></a>00411 <span class="comment">/* accept 1 slot overflow for fetching head and tail sentinels */</span>
<a name="l00412"></a>00412 <span class="keywordflow">if</span> (posstart < -1 || posstart > (<span class="keywordtype">int</span>)l->numels) <span class="keywordflow">return</span> NULL;
<a name="l00413"></a>00413
<a name="l00414"></a>00414
<a name="l00415"></a>00415 <span class="keywordflow">if</span> (0 == l->numels)
<a name="l00416"></a>00416 x = 0;
<a name="l00417"></a>00417 <span class="keywordflow">else</span>
<a name="l00418"></a>00418 x = (float)(posstart+1) / l->numels;
<a name="l00419"></a>00419 <span class="keywordflow">if</span> (x <= 0.25) {
<a name="l00420"></a>00420 <span class="comment">/* first quarter: get to posstart from head */</span>
<a name="l00421"></a>00421 <span class="keywordflow">for</span> (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
<a name="l00422"></a>00422 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (x < 0.5) {
<a name="l00423"></a>00423 <span class="comment">/* second quarter: get to posstart from mid */</span>
<a name="l00424"></a>00424 <span class="keywordflow">for</span> (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
<a name="l00425"></a>00425 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (x <= 0.75) {
<a name="l00426"></a>00426 <span class="comment">/* third quarter: get to posstart from mid */</span>
<a name="l00427"></a>00427 <span class="keywordflow">for</span> (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
<a name="l00428"></a>00428 } <span class="keywordflow">else</span> {
<a name="l00429"></a>00429 <span class="comment">/* fourth quarter: get to posstart from tail */</span>
<a name="l00430"></a>00430 <span class="keywordflow">for</span> (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
<a name="l00431"></a>00431 }
<a name="l00432"></a>00432
<a name="l00433"></a>00433 <span class="keywordflow">return</span> ptr;
<a name="l00434"></a>00434 }
<a name="l00435"></a>00435
<a name="l00436"></a>00436 <span class="keywordtype">void</span> *list_extract_at(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos) {
<a name="l00437"></a>00437 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *tmp;
<a name="l00438"></a>00438 <span class="keywordtype">void</span> *data;
<a name="l00439"></a>00439
<a name="l00440"></a>00440 <span class="keywordflow">if</span> (l->iter_active || pos >= l->numels) <span class="keywordflow">return</span> NULL;
<a name="l00441"></a>00441
<a name="l00442"></a>00442 tmp = list_findpos(l, pos);
<a name="l00443"></a>00443 data = tmp->data;
<a name="l00444"></a>00444
<a name="l00445"></a>00445 tmp->data = NULL; <span class="comment">/* save data from list_drop_elem() free() */</span>
<a name="l00446"></a>00446 list_drop_elem(l, tmp, pos);
<a name="l00447"></a>00447 l->numels--;
<a name="l00448"></a>00448
<a name="l00449"></a>00449 assert(list_repOk(l));
<a name="l00450"></a>00450
<a name="l00451"></a>00451 <span class="keywordflow">return</span> data;
<a name="l00452"></a>00452 }
<a name="l00453"></a>00453
<a name="l00454"></a>00454 <span class="keywordtype">int</span> list_insert_at(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos) {
<a name="l00455"></a>00455 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *lent, *succ, *prec;
<a name="l00456"></a>00456
<a name="l00457"></a>00457 <span class="keywordflow">if</span> (l->iter_active || pos > l->numels) <span class="keywordflow">return</span> -1;
<a name="l00458"></a>00458
<a name="l00459"></a>00459 <span class="comment">/* this code optimizes malloc() with a free-list */</span>
<a name="l00460"></a>00460 <span class="keywordflow">if</span> (l->spareelsnum > 0) {
<a name="l00461"></a>00461 lent = l->spareels[l->spareelsnum-1];
<a name="l00462"></a>00462 l->spareelsnum--;
<a name="l00463"></a>00463 } <span class="keywordflow">else</span> {
<a name="l00464"></a>00464 lent = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a>));
<a name="l00465"></a>00465 <span class="keywordflow">if</span> (lent == NULL)
<a name="l00466"></a>00466 <span class="keywordflow">return</span> -1;
<a name="l00467"></a>00467 }
<a name="l00468"></a>00468
<a name="l00469"></a>00469 <span class="keywordflow">if</span> (l->attrs.copy_data) {
<a name="l00470"></a>00470 <span class="comment">/* make room for user' data (has to be copied) */</span>
<a name="l00471"></a>00471 <span class="keywordtype">size_t</span> datalen = l->attrs.meter(data);
<a name="l00472"></a>00472 lent->data = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(datalen);
<a name="l00473"></a>00473 memcpy(lent->data, data, datalen);
<a name="l00474"></a>00474 } <span class="keywordflow">else</span> {
<a name="l00475"></a>00475 lent->data = (<span class="keywordtype">void</span>*)data;
<a name="l00476"></a>00476 }
<a name="l00477"></a>00477
<a name="l00478"></a>00478 <span class="comment">/* actually append element */</span>
<a name="l00479"></a>00479 prec = list_findpos(l, pos-1);
<a name="l00480"></a>00480 succ = prec->next;
<a name="l00481"></a>00481
<a name="l00482"></a>00482 prec->next = lent;
<a name="l00483"></a>00483 lent->prev = prec;
<a name="l00484"></a>00484 lent->next = succ;
<a name="l00485"></a>00485 succ->prev = lent;
<a name="l00486"></a>00486
<a name="l00487"></a>00487 l->numels++;
<a name="l00488"></a>00488
<a name="l00489"></a>00489 <span class="comment">/* fix mid pointer */</span>
<a name="l00490"></a>00490 <span class="keywordflow">if</span> (l->numels == 1) { <span class="comment">/* first element, set pointer */</span>
<a name="l00491"></a>00491 l->mid = lent;
<a name="l00492"></a>00492 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (l->numels % 2) { <span class="comment">/* now odd */</span>
<a name="l00493"></a>00493 <span class="keywordflow">if</span> (pos >= (l->numels-1)/2) l->mid = l->mid->next;
<a name="l00494"></a>00494 } <span class="keywordflow">else</span> { <span class="comment">/* now even */</span>
<a name="l00495"></a>00495 <span class="keywordflow">if</span> (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
<a name="l00496"></a>00496 }
<a name="l00497"></a>00497
<a name="l00498"></a>00498 assert(list_repOk(l));
<a name="l00499"></a>00499
<a name="l00500"></a>00500 <span class="keywordflow">return</span> 1;
<a name="l00501"></a>00501 }
<a name="l00502"></a>00502
<a name="l00503"></a>00503 <span class="keywordtype">int</span> list_delete(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data) {
<a name="l00504"></a>00504 <span class="keywordtype">int</span> pos, r;
<a name="l00505"></a>00505
<a name="l00506"></a>00506 pos = list_locate(l, data);
<a name="l00507"></a>00507 <span class="keywordflow">if</span> (pos < 0)
<a name="l00508"></a>00508 <span class="keywordflow">return</span> -1;
<a name="l00509"></a>00509
<a name="l00510"></a>00510 r = list_delete_at(l, pos);
<a name="l00511"></a>00511 <span class="keywordflow">if</span> (r < 0)
<a name="l00512"></a>00512 <span class="keywordflow">return</span> -1;
<a name="l00513"></a>00513
<a name="l00514"></a>00514 assert(list_repOk(l));
<a name="l00515"></a>00515
<a name="l00516"></a>00516 <span class="keywordflow">return</span> 0;
<a name="l00517"></a>00517 }
<a name="l00518"></a>00518
<a name="l00519"></a>00519 <span class="keywordtype">int</span> list_delete_at(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos) {
<a name="l00520"></a>00520 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *delendo;
<a name="l00521"></a>00521
<a name="l00522"></a>00522
<a name="l00523"></a>00523 <span class="keywordflow">if</span> (l->iter_active || pos >= l->numels) <span class="keywordflow">return</span> -1;
<a name="l00524"></a>00524
<a name="l00525"></a>00525 delendo = list_findpos(l, pos);
<a name="l00526"></a>00526
<a name="l00527"></a>00527 list_drop_elem(l, delendo, pos);
<a name="l00528"></a>00528
<a name="l00529"></a>00529 l->numels--;
<a name="l00530"></a>00530
<a name="l00531"></a>00531
<a name="l00532"></a>00532 assert(list_repOk(l));
<a name="l00533"></a>00533
<a name="l00534"></a>00534 <span class="keywordflow">return</span> 0;
<a name="l00535"></a>00535 }
<a name="l00536"></a>00536
<a name="l00537"></a>00537 <span class="keywordtype">int</span> list_delete_range(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> posstart, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> posend) {
<a name="l00538"></a>00538 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *lastvalid, *tmp, *tmp2;
<a name="l00539"></a>00539 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00540"></a>00540 <span class="keywordtype">int</span> movedx;
<a name="l00541"></a>00541 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> numdel, midposafter;
<a name="l00542"></a>00542
<a name="l00543"></a>00543 <span class="keywordflow">if</span> (l->iter_active || posend < posstart || posend >= l->numels) <span class="keywordflow">return</span> -1;
<a name="l00544"></a>00544
<a name="l00545"></a>00545 tmp = list_findpos(l, posstart); <span class="comment">/* first el to be deleted */</span>
<a name="l00546"></a>00546 lastvalid = tmp->prev; <span class="comment">/* last valid element */</span>
<a name="l00547"></a>00547
<a name="l00548"></a>00548 numdel = posend - posstart + 1;
<a name="l00549"></a>00549 midposafter = (l->numels-1-numdel)/2;
<a name="l00550"></a>00550
<a name="l00551"></a>00551 midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
<a name="l00552"></a>00552 movedx = midposafter - (l->numels-1)/2;
<a name="l00553"></a>00553
<a name="l00554"></a>00554 <span class="keywordflow">if</span> (movedx > 0) { <span class="comment">/* move right */</span>
<a name="l00555"></a>00555 <span class="keywordflow">for</span> (i = 0; i < (<span class="keywordtype">unsigned</span> int)movedx; l->mid = l->mid->next, i++);
<a name="l00556"></a>00556 } <span class="keywordflow">else</span> { <span class="comment">/* move left */</span>
<a name="l00557"></a>00557 movedx = -movedx;
<a name="l00558"></a>00558 <span class="keywordflow">for</span> (i = 0; i < (<span class="keywordtype">unsigned</span> int)movedx; l->mid = l->mid->prev, i++);
<a name="l00559"></a>00559 }
<a name="l00560"></a>00560
<a name="l00561"></a>00561 assert(posstart == 0 || lastvalid != l->head_sentinel);
<a name="l00562"></a>00562 i = posstart;
<a name="l00563"></a>00563 <span class="keywordflow">if</span> (l->attrs.copy_data) {
<a name="l00564"></a>00564 <span class="comment">/* also free element data */</span>
<a name="l00565"></a>00565 <span class="keywordflow">for</span> (; i <= posend; i++) {
<a name="l00566"></a>00566 tmp2 = tmp;
<a name="l00567"></a>00567 tmp = tmp->next;
<a name="l00568"></a>00568 <span class="keywordflow">if</span> (tmp2->data != NULL) free(tmp2->data);
<a name="l00569"></a>00569 <span class="keywordflow">if</span> (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
<a name="l00570"></a>00570 l->spareels[l->spareelsnum++] = tmp2;
<a name="l00571"></a>00571 } <span class="keywordflow">else</span> {
<a name="l00572"></a>00572 free(tmp2);
<a name="l00573"></a>00573 }
<a name="l00574"></a>00574 }
<a name="l00575"></a>00575 } <span class="keywordflow">else</span> {
<a name="l00576"></a>00576 <span class="comment">/* only free containers */</span>
<a name="l00577"></a>00577 <span class="keywordflow">for</span> (; i <= posend; i++) {
<a name="l00578"></a>00578 tmp2 = tmp;
<a name="l00579"></a>00579 tmp = tmp->next;
<a name="l00580"></a>00580 <span class="keywordflow">if</span> (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
<a name="l00581"></a>00581 l->spareels[l->spareelsnum++] = tmp2;
<a name="l00582"></a>00582 } <span class="keywordflow">else</span> {
<a name="l00583"></a>00583 free(tmp2);
<a name="l00584"></a>00584 }
<a name="l00585"></a>00585 }
<a name="l00586"></a>00586 }
<a name="l00587"></a>00587 assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));
<a name="l00588"></a>00588
<a name="l00589"></a>00589 lastvalid->next = tmp;
<a name="l00590"></a>00590 tmp->prev = lastvalid;
<a name="l00591"></a>00591
<a name="l00592"></a>00592 l->numels -= posend - posstart + 1;
<a name="l00593"></a>00593
<a name="l00594"></a>00594 assert(list_repOk(l));
<a name="l00595"></a>00595
<a name="l00596"></a>00596 <span class="keywordflow">return</span> 0;
<a name="l00597"></a>00597 }
<a name="l00598"></a>00598
<a name="l00599"></a>00599 <span class="keywordtype">int</span> list_clear(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00600"></a>00600 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *s;
<a name="l00601"></a>00601
<a name="l00602"></a>00602 <span class="keywordflow">if</span> (l->iter_active) <span class="keywordflow">return</span> -1;
<a name="l00603"></a>00603
<a name="l00604"></a>00604 <span class="keywordflow">if</span> (l->attrs.copy_data) { <span class="comment">/* also free user data */</span>
<a name="l00605"></a>00605 <span class="comment">/* spare a loop conditional with two loops: spareing elems and freeing elems */</span>
<a name="l00606"></a>00606 <span class="keywordflow">for</span> (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
<a name="l00607"></a>00607 <span class="comment">/* move elements as spares as long as there is room */</span>
<a name="l00608"></a>00608 <span class="keywordflow">if</span> (s->data != NULL) free(s->data);
<a name="l00609"></a>00609 l->spareels[l->spareelsnum++] = s;
<a name="l00610"></a>00610 }
<a name="l00611"></a>00611 <span class="keywordflow">while</span> (s != l->tail_sentinel) {
<a name="l00612"></a>00612 <span class="comment">/* free the remaining elems */</span>
<a name="l00613"></a>00613 <span class="keywordflow">if</span> (s->data != NULL) free(s->data);
<a name="l00614"></a>00614 s = s->next;
<a name="l00615"></a>00615 free(s->prev);
<a name="l00616"></a>00616 }
<a name="l00617"></a>00617 l->head_sentinel->next = l->tail_sentinel;
<a name="l00618"></a>00618 l->tail_sentinel->prev = l->head_sentinel;
<a name="l00619"></a>00619 } <span class="keywordflow">else</span> { <span class="comment">/* only free element containers */</span>
<a name="l00620"></a>00620 <span class="comment">/* spare a loop conditional with two loops: spareing elems and freeing elems */</span>
<a name="l00621"></a>00621 <span class="keywordflow">for</span> (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
<a name="l00622"></a>00622 <span class="comment">/* move elements as spares as long as there is room */</span>
<a name="l00623"></a>00623 l->spareels[l->spareelsnum++] = s;
<a name="l00624"></a>00624 }
<a name="l00625"></a>00625 <span class="keywordflow">while</span> (s != l->tail_sentinel) {
<a name="l00626"></a>00626 <span class="comment">/* free the remaining elems */</span>
<a name="l00627"></a>00627 s = s->next;
<a name="l00628"></a>00628 free(s->prev);
<a name="l00629"></a>00629 }
<a name="l00630"></a>00630 l->head_sentinel->next = l->tail_sentinel;
<a name="l00631"></a>00631 l->tail_sentinel->prev = l->head_sentinel;
<a name="l00632"></a>00632 }
<a name="l00633"></a>00633 l->numels = 0;
<a name="l00634"></a>00634 l->mid = NULL;
<a name="l00635"></a>00635
<a name="l00636"></a>00636 assert(list_repOk(l));
<a name="l00637"></a>00637
<a name="l00638"></a>00638 <span class="keywordflow">return</span> 0;
<a name="l00639"></a>00639 }
<a name="l00640"></a>00640
<a name="l00641"></a>00641 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> list_size(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00642"></a>00642 <span class="keywordflow">return</span> l->numels;
<a name="l00643"></a>00643 }
<a name="l00644"></a>00644
<a name="l00645"></a>00645 <span class="keywordtype">int</span> list_empty(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00646"></a>00646 <span class="keywordflow">return</span> (l->numels == 0);
<a name="l00647"></a>00647 }
<a name="l00648"></a>00648
<a name="l00649"></a>00649 <span class="keywordtype">int</span> list_locate(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data) {
<a name="l00650"></a>00650 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *el;
<a name="l00651"></a>00651 <span class="keywordtype">int</span> pos = 0;
<a name="l00652"></a>00652
<a name="l00653"></a>00653 <span class="keywordflow">if</span> (l->attrs.comparator != NULL) {
<a name="l00654"></a>00654 <span class="comment">/* use comparator */</span>
<a name="l00655"></a>00655 <span class="keywordflow">for</span> (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
<a name="l00656"></a>00656 <span class="keywordflow">if</span> (l->attrs.comparator(data, el->data) == 0) <span class="keywordflow">break</span>;
<a name="l00657"></a>00657 }
<a name="l00658"></a>00658 } <span class="keywordflow">else</span> {
<a name="l00659"></a>00659 <span class="comment">/* compare references */</span>
<a name="l00660"></a>00660 <span class="keywordflow">for</span> (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
<a name="l00661"></a>00661 <span class="keywordflow">if</span> (el->data == data) <span class="keywordflow">break</span>;
<a name="l00662"></a>00662 }
<a name="l00663"></a>00663 }
<a name="l00664"></a>00664 <span class="keywordflow">if</span> (el == l->tail_sentinel) <span class="keywordflow">return</span> -1;
<a name="l00665"></a>00665
<a name="l00666"></a>00666 <span class="keywordflow">return</span> pos;
<a name="l00667"></a>00667 }
<a name="l00668"></a>00668
<a name="l00669"></a>00669 <span class="keywordtype">void</span> *list_seek(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *indicator) {
<a name="l00670"></a>00670 <span class="keyword">const</span> <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *iter;
<a name="l00671"></a>00671
<a name="l00672"></a>00672 <span class="keywordflow">if</span> (l->attrs.seeker == NULL) <span class="keywordflow">return</span> NULL;
<a name="l00673"></a>00673
<a name="l00674"></a>00674 <span class="keywordflow">for</span> (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
<a name="l00675"></a>00675 <span class="keywordflow">if</span> (l->attrs.seeker(iter->data, indicator) != 0) <span class="keywordflow">return</span> iter->data;
<a name="l00676"></a>00676 }
<a name="l00677"></a>00677
<a name="l00678"></a>00678 <span class="keywordflow">return</span> NULL;
<a name="l00679"></a>00679 }
<a name="l00680"></a>00680
<a name="l00681"></a>00681 <span class="keywordtype">int</span> list_contains(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">void</span> *data) {
<a name="l00682"></a>00682 <span class="keywordflow">return</span> (list_locate(l, data) >= 0);
<a name="l00683"></a>00683 }
<a name="l00684"></a>00684
<a name="l00685"></a>00685 <span class="keywordtype">int</span> list_concat(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *l1, <span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *l2, <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict dest) {
<a name="l00686"></a>00686 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *el, *srcel;
<a name="l00687"></a>00687 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> cnt;
<a name="l00688"></a>00688 <span class="keywordtype">int</span> err;
<a name="l00689"></a>00689
<a name="l00690"></a>00690
<a name="l00691"></a>00691 <span class="keywordflow">if</span> (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
<a name="l00692"></a>00692 <span class="keywordflow">return</span> -1;
<a name="l00693"></a>00693
<a name="l00694"></a>00694 list_init(dest);
<a name="l00695"></a>00695
<a name="l00696"></a>00696 dest->numels = l1->numels + l2->numels;
<a name="l00697"></a>00697 <span class="keywordflow">if</span> (dest->numels == 0)
<a name="l00698"></a>00698 <span class="keywordflow">return</span> 0;
<a name="l00699"></a>00699
<a name="l00700"></a>00700 <span class="comment">/* copy list1 */</span>
<a name="l00701"></a>00701 srcel = l1->head_sentinel->next;
<a name="l00702"></a>00702 el = dest->head_sentinel;
<a name="l00703"></a>00703 <span class="keywordflow">while</span> (srcel != l1->tail_sentinel) {
<a name="l00704"></a>00704 el->next = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a>));
<a name="l00705"></a>00705 el->next->prev = el;
<a name="l00706"></a>00706 el = el->next;
<a name="l00707"></a>00707 el->data = srcel->data;
<a name="l00708"></a>00708 srcel = srcel->next;
<a name="l00709"></a>00709 }
<a name="l00710"></a>00710 dest->mid = el; <span class="comment">/* approximate position (adjust later) */</span>
<a name="l00711"></a>00711 <span class="comment">/* copy list 2 */</span>
<a name="l00712"></a>00712 srcel = l2->head_sentinel->next;
<a name="l00713"></a>00713 <span class="keywordflow">while</span> (srcel != l2->tail_sentinel) {
<a name="l00714"></a>00714 el->next = (<span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a>));
<a name="l00715"></a>00715 el->next->prev = el;
<a name="l00716"></a>00716 el = el->next;
<a name="l00717"></a>00717 el->data = srcel->data;
<a name="l00718"></a>00718 srcel = srcel->next;
<a name="l00719"></a>00719 }
<a name="l00720"></a>00720 el->next = dest->tail_sentinel;
<a name="l00721"></a>00721 dest->tail_sentinel->prev = el;
<a name="l00722"></a>00722
<a name="l00723"></a>00723 <span class="comment">/* fix mid pointer */</span>
<a name="l00724"></a>00724 err = l2->numels - l1->numels;
<a name="l00725"></a>00725 <span class="keywordflow">if</span> ((err+1)/2 > 0) { <span class="comment">/* correct pos RIGHT (err-1)/2 moves */</span>
<a name="l00726"></a>00726 err = (err+1)/2;
<a name="l00727"></a>00727 <span class="keywordflow">for</span> (cnt = 0; cnt < (<span class="keywordtype">unsigned</span> int)err; cnt++) dest->mid = dest->mid->next;
<a name="l00728"></a>00728 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (err/2 < 0) { <span class="comment">/* correct pos LEFT (err/2)-1 moves */</span>
<a name="l00729"></a>00729 err = -err/2;
<a name="l00730"></a>00730 <span class="keywordflow">for</span> (cnt = 0; cnt < (<span class="keywordtype">unsigned</span> int)err; cnt++) dest->mid = dest->mid->prev;
<a name="l00731"></a>00731 }
<a name="l00732"></a>00732
<a name="l00733"></a>00733 assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));
<a name="l00734"></a>00734
<a name="l00735"></a>00735 <span class="keywordflow">return</span> 0;
<a name="l00736"></a>00736 }
<a name="l00737"></a>00737
<a name="l00738"></a>00738 <span class="keywordtype">int</span> list_sort(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus) {
<a name="l00739"></a>00739 <span class="keywordflow">if</span> (l->iter_active || l->attrs.comparator == NULL) <span class="comment">/* cannot modify list in the middle of an iteration */</span>
<a name="l00740"></a>00740 <span class="keywordflow">return</span> -1;
<a name="l00741"></a>00741
<a name="l00742"></a>00742 <span class="keywordflow">if</span> (l->numels <= 1)
<a name="l00743"></a>00743 <span class="keywordflow">return</span> 0;
<a name="l00744"></a>00744 list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
<a name="l00745"></a>00745 assert(list_repOk(l));
<a name="l00746"></a>00746 <span class="keywordflow">return</span> 0;
<a name="l00747"></a>00747 }
<a name="l00748"></a>00748
<a name="l00749"></a>00749 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00750"></a>00750 <span class="preprocessor"></span><span class="keyword">struct </span>list_sort_wrappedparams {
<a name="l00751"></a>00751 <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l;
<a name="l00752"></a>00752 <span class="keywordtype">int</span> versus;
<a name="l00753"></a>00753 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> first, last;
<a name="l00754"></a>00754 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *fel, *lel;
<a name="l00755"></a>00755 };
<a name="l00756"></a>00756
<a name="l00757"></a>00757 <span class="keyword">static</span> <span class="keywordtype">void</span> *list_sort_quicksort_threadwrapper(<span class="keywordtype">void</span> *wrapped_params) {
<a name="l00758"></a>00758 <span class="keyword">struct </span>list_sort_wrappedparams *wp = (<span class="keyword">struct </span>list_sort_wrappedparams *)wrapped_params;
<a name="l00759"></a>00759 list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
<a name="l00760"></a>00760 free(wp);
<a name="l00761"></a>00761 pthread_exit(NULL);
<a name="l00762"></a>00762 <span class="keywordflow">return</span> NULL;
<a name="l00763"></a>00763 }
<a name="l00764"></a>00764 <span class="preprocessor">#endif</span>
<a name="l00765"></a>00765 <span class="preprocessor"></span>
<a name="l00766"></a>00766 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> list_sort_selectionsort(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus,
<a name="l00767"></a>00767 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> first, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *fel,
<a name="l00768"></a>00768 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> last, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *lel) {
<a name="l00769"></a>00769 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *cursor, *toswap, *firstunsorted;
<a name="l00770"></a>00770 <span class="keywordtype">void</span> *tmpdata;
<a name="l00771"></a>00771
<a name="l00772"></a>00772 <span class="keywordflow">if</span> (last <= first) <span class="comment">/* <= 1-element lists are always sorted */</span>
<a name="l00773"></a>00773 <span class="keywordflow">return</span>;
<a name="l00774"></a>00774
<a name="l00775"></a>00775 <span class="keywordflow">for</span> (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
<a name="l00776"></a>00776 <span class="comment">/* find min or max in the remainder of the list */</span>
<a name="l00777"></a>00777 <span class="keywordflow">for</span> (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
<a name="l00778"></a>00778 <span class="keywordflow">if</span> (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
<a name="l00779"></a>00779 <span class="keywordflow">if</span> (toswap != firstunsorted) { <span class="comment">/* swap firstunsorted with toswap */</span>
<a name="l00780"></a>00780 tmpdata = firstunsorted->data;
<a name="l00781"></a>00781 firstunsorted->data = toswap->data;
<a name="l00782"></a>00782 toswap->data = tmpdata;
<a name="l00783"></a>00783 }
<a name="l00784"></a>00784 }
<a name="l00785"></a>00785 }
<a name="l00786"></a>00786
<a name="l00787"></a>00787 <span class="keyword">static</span> <span class="keywordtype">void</span> list_sort_quicksort(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> versus,
<a name="l00788"></a>00788 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> first, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *fel,
<a name="l00789"></a>00789 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> last, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *lel) {
<a name="l00790"></a>00790 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pivotid;
<a name="l00791"></a>00791 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00792"></a>00792 <span class="keyword">register</span> <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *pivot;
<a name="l00793"></a>00793 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *left, *right;
<a name="l00794"></a>00794 <span class="keywordtype">void</span> *tmpdata;
<a name="l00795"></a>00795 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00796"></a>00796 <span class="preprocessor"></span> pthread_t tid;
<a name="l00797"></a>00797 <span class="keywordtype">int</span> traised;
<a name="l00798"></a>00798 <span class="preprocessor">#endif</span>
<a name="l00799"></a>00799 <span class="preprocessor"></span>
<a name="l00800"></a>00800
<a name="l00801"></a>00801 <span class="keywordflow">if</span> (last <= first) <span class="comment">/* <= 1-element lists are always sorted */</span>
<a name="l00802"></a>00802 <span class="keywordflow">return</span>;
<a name="l00803"></a>00803
<a name="l00804"></a>00804 <span class="keywordflow">if</span> (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
<a name="l00805"></a>00805 list_sort_selectionsort(l, versus, first, fel, last, lel);
<a name="l00806"></a>00806 <span class="keywordflow">return</span>;
<a name="l00807"></a>00807 }
<a name="l00808"></a>00808
<a name="l00809"></a>00809 <span class="comment">/* base of iteration: one element list */</span>
<a name="l00810"></a>00810 <span class="keywordflow">if</span> (! (last > first)) <span class="keywordflow">return</span>;
<a name="l00811"></a>00811
<a name="l00812"></a>00812 pivotid = (get_random() % (last - first + 1));
<a name="l00813"></a>00813 <span class="comment">/* pivotid = (last - first + 1) / 2; */</span>
<a name="l00814"></a>00814
<a name="l00815"></a>00815 <span class="comment">/* find pivot */</span>
<a name="l00816"></a>00816 <span class="keywordflow">if</span> (pivotid < (last - first + 1)/2) {
<a name="l00817"></a>00817 <span class="keywordflow">for</span> (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
<a name="l00818"></a>00818 } <span class="keywordflow">else</span> {
<a name="l00819"></a>00819 <span class="keywordflow">for</span> (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
<a name="l00820"></a>00820 }
<a name="l00821"></a>00821
<a name="l00822"></a>00822 <span class="comment">/* smaller PIVOT bigger */</span>
<a name="l00823"></a>00823 left = fel;
<a name="l00824"></a>00824 right = lel;
<a name="l00825"></a>00825 <span class="comment">/* iterate --- left ---> PIV <--- right --- */</span>
<a name="l00826"></a>00826 <span class="keywordflow">while</span> (left != pivot && right != pivot) {
<a name="l00827"></a>00827 <span class="keywordflow">for</span> (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
<a name="l00828"></a>00828 <span class="comment">/* left points to a smaller element, or to pivot */</span>
<a name="l00829"></a>00829 <span class="keywordflow">for</span> (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
<a name="l00830"></a>00830 <span class="comment">/* right points to a bigger element, or to pivot */</span>
<a name="l00831"></a>00831 <span class="keywordflow">if</span> (left != pivot && right != pivot) {
<a name="l00832"></a>00832 <span class="comment">/* swap, then move iterators */</span>
<a name="l00833"></a>00833 tmpdata = left->data;
<a name="l00834"></a>00834 left->data = right->data;
<a name="l00835"></a>00835 right->data = tmpdata;
<a name="l00836"></a>00836
<a name="l00837"></a>00837 left = left->next;
<a name="l00838"></a>00838 right = right->prev;
<a name="l00839"></a>00839 }
<a name="l00840"></a>00840 }
<a name="l00841"></a>00841
<a name="l00842"></a>00842 <span class="comment">/* now either left points to pivot (end run), or right */</span>
<a name="l00843"></a>00843 <span class="keywordflow">if</span> (right == pivot) { <span class="comment">/* left part longer */</span>
<a name="l00844"></a>00844 <span class="keywordflow">while</span> (left != pivot) {
<a name="l00845"></a>00845 <span class="keywordflow">if</span> (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
<a name="l00846"></a>00846 tmpdata = left->data;
<a name="l00847"></a>00847 left->data = pivot->prev->data;
<a name="l00848"></a>00848 pivot->prev->data = pivot->data;
<a name="l00849"></a>00849 pivot->data = tmpdata;
<a name="l00850"></a>00850 pivot = pivot->prev;
<a name="l00851"></a>00851 pivotid--;
<a name="l00852"></a>00852 <span class="keywordflow">if</span> (pivot == left) <span class="keywordflow">break</span>;
<a name="l00853"></a>00853 } <span class="keywordflow">else</span> {
<a name="l00854"></a>00854 left = left->next;
<a name="l00855"></a>00855 }
<a name="l00856"></a>00856 }
<a name="l00857"></a>00857 } <span class="keywordflow">else</span> { <span class="comment">/* right part longer */</span>
<a name="l00858"></a>00858 <span class="keywordflow">while</span> (right != pivot) {
<a name="l00859"></a>00859 <span class="keywordflow">if</span> (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
<a name="l00860"></a>00860 <span class="comment">/* move current right before pivot */</span>
<a name="l00861"></a>00861 tmpdata = right->data;
<a name="l00862"></a>00862 right->data = pivot->next->data;
<a name="l00863"></a>00863 pivot->next->data = pivot->data;
<a name="l00864"></a>00864 pivot->data = tmpdata;
<a name="l00865"></a>00865 pivot = pivot->next;
<a name="l00866"></a>00866 pivotid++;
<a name="l00867"></a>00867 <span class="keywordflow">if</span> (pivot == right) <span class="keywordflow">break</span>;
<a name="l00868"></a>00868 } <span class="keywordflow">else</span> {
<a name="l00869"></a>00869 right = right->prev;
<a name="l00870"></a>00870 }
<a name="l00871"></a>00871 }
<a name="l00872"></a>00872 }
<a name="l00873"></a>00873
<a name="l00874"></a>00874 <span class="comment">/* sort sublists A and B : |---A---| pivot |---B---| */</span>
<a name="l00875"></a>00875
<a name="l00876"></a>00876 <span class="preprocessor">#ifdef SIMCLIST_WITH_THREADS</span>
<a name="l00877"></a>00877 <span class="preprocessor"></span> traised = 0;
<a name="l00878"></a>00878 <span class="keywordflow">if</span> (pivotid > 0) {
<a name="l00879"></a>00879 <span class="comment">/* prepare wrapped args, then start thread */</span>
<a name="l00880"></a>00880 <span class="keywordflow">if</span> (l->threadcount < SIMCLIST_MAXTHREADS-1) {
<a name="l00881"></a>00881 <span class="keyword">struct </span>list_sort_wrappedparams *wp = (<span class="keyword">struct </span>list_sort_wrappedparams *)malloc(<span class="keyword">sizeof</span>(<span class="keyword">struct</span> list_sort_wrappedparams));
<a name="l00882"></a>00882 l->threadcount++;
<a name="l00883"></a>00883 traised = 1;
<a name="l00884"></a>00884 wp->l = l;
<a name="l00885"></a>00885 wp->versus = versus;
<a name="l00886"></a>00886 wp->first = first;
<a name="l00887"></a>00887 wp->fel = fel;
<a name="l00888"></a>00888 wp->last = first+pivotid-1;
<a name="l00889"></a>00889 wp->lel = pivot->prev;
<a name="l00890"></a>00890 <span class="keywordflow">if</span> (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
<a name="l00891"></a>00891 free(wp);
<a name="l00892"></a>00892 traised = 0;
<a name="l00893"></a>00893 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
<a name="l00894"></a>00894 }
<a name="l00895"></a>00895 } <span class="keywordflow">else</span> {
<a name="l00896"></a>00896 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
<a name="l00897"></a>00897 }
<a name="l00898"></a>00898 }
<a name="l00899"></a>00899 <span class="keywordflow">if</span> (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
<a name="l00900"></a>00900 <span class="keywordflow">if</span> (traised) {
<a name="l00901"></a>00901 pthread_join(tid, (<span class="keywordtype">void</span> **)NULL);
<a name="l00902"></a>00902 l->threadcount--;
<a name="l00903"></a>00903 }
<a name="l00904"></a>00904 <span class="preprocessor">#else</span>
<a name="l00905"></a>00905 <span class="preprocessor"></span> <span class="keywordflow">if</span> (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
<a name="l00906"></a>00906 <span class="keywordflow">if</span> (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
<a name="l00907"></a>00907 <span class="preprocessor">#endif</span>
<a name="l00908"></a>00908 <span class="preprocessor"></span>}
<a name="l00909"></a>00909
<a name="l00910"></a>00910 <span class="keywordtype">int</span> list_iterator_start(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00911"></a>00911 <span class="keywordflow">if</span> (l->iter_active) <span class="keywordflow">return</span> 0;
<a name="l00912"></a>00912 l->iter_pos = 0;
<a name="l00913"></a>00913 l->iter_active = 1;
<a name="l00914"></a>00914 l->iter_curentry = l->head_sentinel->next;
<a name="l00915"></a>00915 <span class="keywordflow">return</span> 1;
<a name="l00916"></a>00916 }
<a name="l00917"></a>00917
<a name="l00918"></a>00918 <span class="keywordtype">void</span> *list_iterator_next(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00919"></a>00919 <span class="keywordtype">void</span> *toret;
<a name="l00920"></a>00920
<a name="l00921"></a>00921 <span class="keywordflow">if</span> (! l->iter_active) <span class="keywordflow">return</span> NULL;
<a name="l00922"></a>00922
<a name="l00923"></a>00923 toret = l->iter_curentry->data;
<a name="l00924"></a>00924 l->iter_curentry = l->iter_curentry->next;
<a name="l00925"></a>00925 l->iter_pos++;
<a name="l00926"></a>00926
<a name="l00927"></a>00927 <span class="keywordflow">return</span> toret;
<a name="l00928"></a>00928 }
<a name="l00929"></a>00929
<a name="l00930"></a>00930 <span class="keywordtype">int</span> list_iterator_hasnext(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00931"></a>00931 <span class="keywordflow">if</span> (! l->iter_active) <span class="keywordflow">return</span> 0;
<a name="l00932"></a>00932 <span class="keywordflow">return</span> (l->iter_pos < l->numels);
<a name="l00933"></a>00933 }
<a name="l00934"></a>00934
<a name="l00935"></a>00935 <span class="keywordtype">int</span> list_iterator_stop(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l00936"></a>00936 <span class="keywordflow">if</span> (! l->iter_active) <span class="keywordflow">return</span> 0;
<a name="l00937"></a>00937 l->iter_pos = 0;
<a name="l00938"></a>00938 l->iter_active = 0;
<a name="l00939"></a>00939 <span class="keywordflow">return</span> 1;
<a name="l00940"></a>00940 }
<a name="l00941"></a>00941
<a name="l00942"></a>00942 <span class="keywordtype">int</span> list_hash(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, list_hash_t *restrict hash) {
<a name="l00943"></a>00943 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *x;
<a name="l00944"></a>00944 list_hash_t tmphash;
<a name="l00945"></a>00945
<a name="l00946"></a>00946 assert(hash != NULL);
<a name="l00947"></a>00947
<a name="l00948"></a>00948 tmphash = l->numels * 2 + 100;
<a name="l00949"></a>00949 <span class="keywordflow">if</span> (l->attrs.hasher == NULL) {
<a name="l00950"></a>00950 <span class="preprocessor">#ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES</span>
<a name="l00951"></a>00951 <span class="preprocessor"></span> <span class="comment">/* ENABLE WITH CARE !! */</span>
<a name="l00952"></a>00952 <span class="preprocessor">#warning "Memlocation-based hash is consistent only for testing modification in the same program run."</span>
<a name="l00953"></a>00953 <span class="preprocessor"></span> <span class="keywordtype">int</span> i;
<a name="l00954"></a>00954
<a name="l00955"></a>00955 <span class="comment">/* only use element references */</span>
<a name="l00956"></a>00956 <span class="keywordflow">for</span> (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
<a name="l00957"></a>00957 <span class="keywordflow">for</span> (i = 0; i < <span class="keyword">sizeof</span>(x->data); i++) {
<a name="l00958"></a>00958 tmphash += (tmphash ^ (uintptr_t)x->data);
<a name="l00959"></a>00959 }
<a name="l00960"></a>00960 tmphash += tmphash % l->numels;
<a name="l00961"></a>00961 }
<a name="l00962"></a>00962 <span class="preprocessor">#else</span>
<a name="l00963"></a>00963 <span class="preprocessor"></span> <span class="keywordflow">return</span> -1;
<a name="l00964"></a>00964 <span class="preprocessor">#endif</span>
<a name="l00965"></a>00965 <span class="preprocessor"></span> } <span class="keywordflow">else</span> {
<a name="l00966"></a>00966 <span class="comment">/* hash each element with the user-given function */</span>
<a name="l00967"></a>00967 <span class="keywordflow">for</span> (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
<a name="l00968"></a>00968 tmphash += tmphash ^ l->attrs.hasher(x->data);
<a name="l00969"></a>00969 tmphash +=* hash % l->numels;
<a name="l00970"></a>00970 }
<a name="l00971"></a>00971 }
<a name="l00972"></a>00972
<a name="l00973"></a>00973 *hash = tmphash;
<a name="l00974"></a>00974
<a name="l00975"></a>00975 <span class="keywordflow">return</span> 0;
<a name="l00976"></a>00976 }
<a name="l00977"></a>00977
<a name="l00978"></a>00978 <span class="preprocessor">#ifndef SIMCLIST_NO_DUMPRESTORE</span>
<a name="l00979"></a>00979 <span class="preprocessor"></span><span class="keywordtype">int</span> list_dump_getinfo_filedescriptor(<span class="keywordtype">int</span> fd, <a class="code" href="structlist__dump__info__t.html">list_dump_info_t</a> *restrict info) {
<a name="l00980"></a>00980 int32_t terminator_head, terminator_tail;
<a name="l00981"></a>00981 uint32_t elemlen;
<a name="l00982"></a>00982 off_t hop;
<a name="l00983"></a>00983
<a name="l00984"></a>00984
<a name="l00985"></a>00985 <span class="comment">/* version */</span>
<a name="l00986"></a>00986 READ_ERRCHECK(fd, & info->version, <span class="keyword">sizeof</span>(info->version));
<a name="l00987"></a>00987 info->version = ntohs(info->version);
<a name="l00988"></a>00988 <span class="keywordflow">if</span> (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
<a name="l00989"></a>00989 errno = EILSEQ;
<a name="l00990"></a>00990 <span class="keywordflow">return</span> -1;
<a name="l00991"></a>00991 }
<a name="l00992"></a>00992
<a name="l00993"></a>00993 <span class="comment">/* timestamp */</span>
<a name="l00994"></a>00994 READ_ERRCHECK(fd, & info->timestamp, <span class="keyword">sizeof</span>(info->timestamp));
<a name="l00995"></a>00995 info->timestamp = hton64(info->timestamp);
<a name="l00996"></a>00996
<a name="l00997"></a>00997 <span class="comment">/* list terminator (to check thereafter) */</span>
<a name="l00998"></a>00998 READ_ERRCHECK(fd, & terminator_head, <span class="keyword">sizeof</span>(terminator_head));
<a name="l00999"></a>00999 terminator_head = ntohl(terminator_head);
<a name="l01000"></a>01000
<a name="l01001"></a>01001 <span class="comment">/* list size */</span>
<a name="l01002"></a>01002 READ_ERRCHECK(fd, & info->list_size, <span class="keyword">sizeof</span>(info->list_size));
<a name="l01003"></a>01003 info->list_size = ntohl(info->list_size);
<a name="l01004"></a>01004
<a name="l01005"></a>01005 <span class="comment">/* number of elements */</span>
<a name="l01006"></a>01006 READ_ERRCHECK(fd, & info->list_numels, <span class="keyword">sizeof</span>(info->list_numels));
<a name="l01007"></a>01007 info->list_numels = ntohl(info->list_numels);
<a name="l01008"></a>01008
<a name="l01009"></a>01009 <span class="comment">/* length of each element (for checking for consistency) */</span>
<a name="l01010"></a>01010 READ_ERRCHECK(fd, & elemlen, <span class="keyword">sizeof</span>(elemlen));
<a name="l01011"></a>01011 elemlen = ntohl(elemlen);
<a name="l01012"></a>01012
<a name="l01013"></a>01013 <span class="comment">/* list hash */</span>
<a name="l01014"></a>01014 READ_ERRCHECK(fd, & info->list_hash, <span class="keyword">sizeof</span>(info->list_hash));
<a name="l01015"></a>01015 info->list_hash = ntohl(info->list_hash);
<a name="l01016"></a>01016
<a name="l01017"></a>01017 <span class="comment">/* check consistency */</span>
<a name="l01018"></a>01018 <span class="keywordflow">if</span> (elemlen > 0) {
<a name="l01019"></a>01019 <span class="comment">/* constant length, hop by size only */</span>
<a name="l01020"></a>01020 hop = info->list_size;
<a name="l01021"></a>01021 } <span class="keywordflow">else</span> {
<a name="l01022"></a>01022 <span class="comment">/* non-constant length, hop by size + all element length blocks */</span>
<a name="l01023"></a>01023 hop = info->list_size + elemlen*info->list_numels;
<a name="l01024"></a>01024 }
<a name="l01025"></a>01025 <span class="keywordflow">if</span> (lseek(fd, hop, SEEK_CUR) == -1) {
<a name="l01026"></a>01026 <span class="keywordflow">return</span> -1;
<a name="l01027"></a>01027 }
<a name="l01028"></a>01028
<a name="l01029"></a>01029 <span class="comment">/* read the trailing value and compare with terminator_head */</span>
<a name="l01030"></a>01030 READ_ERRCHECK(fd, & terminator_tail, <span class="keyword">sizeof</span>(terminator_tail));
<a name="l01031"></a>01031 terminator_tail = ntohl(terminator_tail);
<a name="l01032"></a>01032
<a name="l01033"></a>01033 <span class="keywordflow">if</span> (terminator_head == terminator_tail)
<a name="l01034"></a>01034 info->consistent = 1;
<a name="l01035"></a>01035 <span class="keywordflow">else</span>
<a name="l01036"></a>01036 info->consistent = 0;
<a name="l01037"></a>01037
<a name="l01038"></a>01038 <span class="keywordflow">return</span> 0;
<a name="l01039"></a>01039 }
<a name="l01040"></a>01040
<a name="l01041"></a>01041 <span class="keywordtype">int</span> list_dump_getinfo_file(<span class="keyword">const</span> <span class="keywordtype">char</span> *restrict filename, <a class="code" href="structlist__dump__info__t.html">list_dump_info_t</a> *restrict info) {
<a name="l01042"></a>01042 <span class="keywordtype">int</span> fd, ret;
<a name="l01043"></a>01043
<a name="l01044"></a>01044 fd = open(filename, O_RDONLY, 0);
<a name="l01045"></a>01045 <span class="keywordflow">if</span> (fd < 0) <span class="keywordflow">return</span> -1;
<a name="l01046"></a>01046
<a name="l01047"></a>01047 ret = list_dump_getinfo_filedescriptor(fd, info);
<a name="l01048"></a>01048 close(fd);
<a name="l01049"></a>01049
<a name="l01050"></a>01050 <span class="keywordflow">return</span> ret;
<a name="l01051"></a>01051 }
<a name="l01052"></a>01052
<a name="l01053"></a>01053 <span class="keywordtype">int</span> list_dump_filedescriptor(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> fd, <span class="keywordtype">size_t</span> *restrict len) {
<a name="l01054"></a>01054 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *x;
<a name="l01055"></a>01055 <span class="keywordtype">void</span> *ser_buf;
<a name="l01056"></a>01056 uint32_t bufsize;
<a name="l01057"></a>01057 <span class="keyword">struct </span>timeval timeofday;
<a name="l01058"></a>01058 <span class="keyword">struct </span><a class="code" href="structlist__dump__header__s.html">list_dump_header_s</a> header;
<a name="l01059"></a>01059
<a name="l01060"></a>01060 <span class="keywordflow">if</span> (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
<a name="l01061"></a>01061 errno = ENOTTY;
<a name="l01062"></a>01062 <span class="keywordflow">return</span> -1;
<a name="l01063"></a>01063 }
<a name="l01064"></a>01064
<a name="l01065"></a>01065 <span class="comment">/**** DUMP FORMAT ****</span>
<a name="l01066"></a>01066 <span class="comment"></span>
<a name="l01067"></a>01067 <span class="comment"> [ ver timestamp | totlen numels elemlen hash | DATA ]</span>
<a name="l01068"></a>01068 <span class="comment"> </span>
<a name="l01069"></a>01069 <span class="comment"> where DATA can be:</span>
<a name="l01070"></a>01070 <span class="comment"> @ for constant-size list (element size is constant; elemlen > 0)</span>
<a name="l01071"></a>01071 <span class="comment"> [ elem elem ... elem ]</span>
<a name="l01072"></a>01072 <span class="comment"> @ for other lists (element size dictated by element_meter each time; elemlen <= 0)</span>
<a name="l01073"></a>01073 <span class="comment"> [ size elem size elem ... size elem ]</span>
<a name="l01074"></a>01074 <span class="comment"> </span>
<a name="l01075"></a>01075 <span class="comment"> all integers are encoded in NETWORK BYTE FORMAT</span>
<a name="l01076"></a>01076 <span class="comment"> *****/</span>
<a name="l01077"></a>01077
<a name="l01078"></a>01078
<a name="l01079"></a>01079 <span class="comment">/* prepare HEADER */</span>
<a name="l01080"></a>01080 <span class="comment">/* version */</span>
<a name="l01081"></a>01081 header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );
<a name="l01082"></a>01082
<a name="l01083"></a>01083 <span class="comment">/* timestamp */</span>
<a name="l01084"></a>01084 gettimeofday(&timeofday, NULL);
<a name="l01085"></a>01085 header.timestamp = (int64_t)timeofday.tv_sec * 1000000 + (int64_t)timeofday.tv_usec;
<a name="l01086"></a>01086 header.timestamp = hton64(header.timestamp);
<a name="l01087"></a>01087
<a name="l01088"></a>01088 header.rndterm = htonl((int32_t)get_random());
<a name="l01089"></a>01089
<a name="l01090"></a>01090 <span class="comment">/* total list size is postprocessed afterwards */</span>
<a name="l01091"></a>01091
<a name="l01092"></a>01092 <span class="comment">/* number of elements */</span>
<a name="l01093"></a>01093 header.numels = htonl(l->numels);
<a name="l01094"></a>01094
<a name="l01095"></a>01095 <span class="comment">/* include an hash, if possible */</span>
<a name="l01096"></a>01096 <span class="keywordflow">if</span> (l->attrs.hasher != NULL) {
<a name="l01097"></a>01097 <span class="keywordflow">if</span> (htonl(list_hash(l, & header.listhash)) != 0) {
<a name="l01098"></a>01098 <span class="comment">/* could not compute list hash! */</span>
<a name="l01099"></a>01099 <span class="keywordflow">return</span> -1;
<a name="l01100"></a>01100 }
<a name="l01101"></a>01101 } <span class="keywordflow">else</span> {
<a name="l01102"></a>01102 header.listhash = htonl(0);
<a name="l01103"></a>01103 }
<a name="l01104"></a>01104
<a name="l01105"></a>01105 header.totlistlen = header.elemlen = 0;
<a name="l01106"></a>01106
<a name="l01107"></a>01107 <span class="comment">/* leave room for the header at the beginning of the file */</span>
<a name="l01108"></a>01108 <span class="keywordflow">if</span> (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
<a name="l01109"></a>01109 <span class="comment">/* errno set by lseek() */</span>
<a name="l01110"></a>01110 <span class="keywordflow">return</span> -1;
<a name="l01111"></a>01111 }
<a name="l01112"></a>01112
<a name="l01113"></a>01113 <span class="comment">/* write CONTENT */</span>
<a name="l01114"></a>01114 <span class="keywordflow">if</span> (l->numels > 0) {
<a name="l01115"></a>01115 <span class="comment">/* SPECULATE that the list has constant element size */</span>
<a name="l01116"></a>01116
<a name="l01117"></a>01117 <span class="keywordflow">if</span> (l->attrs.serializer != NULL) { <span class="comment">/* user user-specified serializer */</span>
<a name="l01118"></a>01118 <span class="comment">/* get preliminary length of serialized element in header.elemlen */</span>
<a name="l01119"></a>01119 ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
<a name="l01120"></a>01120 free(ser_buf);
<a name="l01121"></a>01121 <span class="comment">/* request custom serialization of each element */</span>
<a name="l01122"></a>01122 <span class="keywordflow">for</span> (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
<a name="l01123"></a>01123 ser_buf = l->attrs.serializer(x->data, &bufsize);
<a name="l01124"></a>01124 header.totlistlen += bufsize;
<a name="l01125"></a>01125 <span class="keywordflow">if</span> (header.elemlen != 0) { <span class="comment">/* continue on speculation */</span>
<a name="l01126"></a>01126 <span class="keywordflow">if</span> (header.elemlen != bufsize) {
<a name="l01127"></a>01127 free(ser_buf);
<a name="l01128"></a>01128 <span class="comment">/* constant element length speculation broken! */</span>
<a name="l01129"></a>01129 header.elemlen = 0;
<a name="l01130"></a>01130 header.totlistlen = 0;
<a name="l01131"></a>01131 x = l->head_sentinel;
<a name="l01132"></a>01132 <span class="keywordflow">if</span> (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
<a name="l01133"></a>01133 <span class="comment">/* errno set by lseek() */</span>
<a name="l01134"></a>01134 <span class="keywordflow">return</span> -1;
<a name="l01135"></a>01135 }
<a name="l01136"></a>01136 <span class="comment">/* restart from the beginning */</span>
<a name="l01137"></a>01137 <span class="keywordflow">continue</span>;
<a name="l01138"></a>01138 }
<a name="l01139"></a>01139 <span class="comment">/* speculation confirmed */</span>
<a name="l01140"></a>01140 WRITE_ERRCHECK(fd, ser_buf, bufsize);
<a name="l01141"></a>01141 } <span class="keywordflow">else</span> { <span class="comment">/* speculation found broken */</span>
<a name="l01142"></a>01142 WRITE_ERRCHECK(fd, & bufsize, <span class="keyword">sizeof</span>(<span class="keywordtype">size_t</span>));
<a name="l01143"></a>01143 WRITE_ERRCHECK(fd, ser_buf, bufsize);
<a name="l01144"></a>01144 }
<a name="l01145"></a>01145 free(ser_buf);
<a name="l01146"></a>01146 }
<a name="l01147"></a>01147 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (l->attrs.meter != NULL) {
<a name="l01148"></a>01148 header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);
<a name="l01149"></a>01149
<a name="l01150"></a>01150 <span class="comment">/* serialize the element straight from its data */</span>
<a name="l01151"></a>01151 <span class="keywordflow">for</span> (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
<a name="l01152"></a>01152 bufsize = l->attrs.meter(x->data);
<a name="l01153"></a>01153 header.totlistlen += bufsize;
<a name="l01154"></a>01154 <span class="keywordflow">if</span> (header.elemlen != 0) {
<a name="l01155"></a>01155 <span class="keywordflow">if</span> (header.elemlen != bufsize) {
<a name="l01156"></a>01156 <span class="comment">/* constant element length speculation broken! */</span>
<a name="l01157"></a>01157 header.elemlen = 0;
<a name="l01158"></a>01158 header.totlistlen = 0;
<a name="l01159"></a>01159 x = l->head_sentinel;
<a name="l01160"></a>01160 <span class="comment">/* restart from the beginning */</span>
<a name="l01161"></a>01161 <span class="keywordflow">continue</span>;
<a name="l01162"></a>01162 }
<a name="l01163"></a>01163 WRITE_ERRCHECK(fd, x->data, bufsize);
<a name="l01164"></a>01164 } <span class="keywordflow">else</span> {
<a name="l01165"></a>01165 WRITE_ERRCHECK(fd, &bufsize, <span class="keyword">sizeof</span>(<span class="keywordtype">size_t</span>));
<a name="l01166"></a>01166 WRITE_ERRCHECK(fd, x->data, bufsize);
<a name="l01167"></a>01167 }
<a name="l01168"></a>01168 }
<a name="l01169"></a>01169 }
<a name="l01170"></a>01170 <span class="comment">/* adjust endianness */</span>
<a name="l01171"></a>01171 header.elemlen = htonl(header.elemlen);
<a name="l01172"></a>01172 header.totlistlen = htonl(header.totlistlen);
<a name="l01173"></a>01173 }
<a name="l01174"></a>01174
<a name="l01175"></a>01175 <span class="comment">/* write random terminator */</span>
<a name="l01176"></a>01176 WRITE_ERRCHECK(fd, & header.rndterm, <span class="keyword">sizeof</span>(header.rndterm)); <span class="comment">/* list terminator */</span>
<a name="l01177"></a>01177
<a name="l01178"></a>01178
<a name="l01179"></a>01179 <span class="comment">/* write header */</span>
<a name="l01180"></a>01180 lseek(fd, 0, SEEK_SET);
<a name="l01181"></a>01181
<a name="l01182"></a>01182 WRITE_ERRCHECK(fd, & header.ver, <span class="keyword">sizeof</span>(header.ver)); <span class="comment">/* version */</span>
<a name="l01183"></a>01183 WRITE_ERRCHECK(fd, & header.timestamp, <span class="keyword">sizeof</span>(header.timestamp)); <span class="comment">/* timestamp */</span>
<a name="l01184"></a>01184 WRITE_ERRCHECK(fd, & header.rndterm, <span class="keyword">sizeof</span>(header.rndterm)); <span class="comment">/* random terminator */</span>
<a name="l01185"></a>01185
<a name="l01186"></a>01186 WRITE_ERRCHECK(fd, & header.totlistlen, <span class="keyword">sizeof</span>(header.totlistlen)); <span class="comment">/* total length of elements */</span>
<a name="l01187"></a>01187 WRITE_ERRCHECK(fd, & header.numels, <span class="keyword">sizeof</span>(header.numels)); <span class="comment">/* number of elements */</span>
<a name="l01188"></a>01188 WRITE_ERRCHECK(fd, & header.elemlen, <span class="keyword">sizeof</span>(header.elemlen)); <span class="comment">/* size of each element, or 0 for independent */</span>
<a name="l01189"></a>01189 WRITE_ERRCHECK(fd, & header.listhash, <span class="keyword">sizeof</span>(header.listhash)); <span class="comment">/* list hash, or 0 for "ignore" */</span>
<a name="l01190"></a>01190
<a name="l01191"></a>01191
<a name="l01192"></a>01192 <span class="comment">/* possibly store total written length in "len" */</span>
<a name="l01193"></a>01193 <span class="keywordflow">if</span> (len != NULL) {
<a name="l01194"></a>01194 *len = <span class="keyword">sizeof</span>(header) + ntohl(header.totlistlen);
<a name="l01195"></a>01195 }
<a name="l01196"></a>01196
<a name="l01197"></a>01197 <span class="keywordflow">return</span> 0;
<a name="l01198"></a>01198 }
<a name="l01199"></a>01199
<a name="l01200"></a>01200 <span class="keywordtype">int</span> list_restore_filedescriptor(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keywordtype">int</span> fd, <span class="keywordtype">size_t</span> *restrict len) {
<a name="l01201"></a>01201 <span class="keyword">struct </span><a class="code" href="structlist__dump__header__s.html">list_dump_header_s</a> header;
<a name="l01202"></a>01202 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> cnt;
<a name="l01203"></a>01203 <span class="keywordtype">void</span> *buf;
<a name="l01204"></a>01204 uint32_t elsize, totreadlen, totmemorylen;
<a name="l01205"></a>01205
<a name="l01206"></a>01206 memset(& header, 0, <span class="keyword">sizeof</span>(header));
<a name="l01207"></a>01207
<a name="l01208"></a>01208 <span class="comment">/* read header */</span>
<a name="l01209"></a>01209
<a name="l01210"></a>01210 <span class="comment">/* version */</span>
<a name="l01211"></a>01211 READ_ERRCHECK(fd, &header.ver, <span class="keyword">sizeof</span>(header.ver));
<a name="l01212"></a>01212 header.ver = ntohs(header.ver);
<a name="l01213"></a>01213 <span class="keywordflow">if</span> (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
<a name="l01214"></a>01214 errno = EILSEQ;
<a name="l01215"></a>01215 <span class="keywordflow">return</span> -1;
<a name="l01216"></a>01216 }
<a name="l01217"></a>01217
<a name="l01218"></a>01218 <span class="comment">/* timestamp */</span>
<a name="l01219"></a>01219 READ_ERRCHECK(fd, & header.timestamp, <span class="keyword">sizeof</span>(header.timestamp));
<a name="l01220"></a>01220
<a name="l01221"></a>01221 <span class="comment">/* list terminator */</span>
<a name="l01222"></a>01222 READ_ERRCHECK(fd, & header.rndterm, <span class="keyword">sizeof</span>(header.rndterm));
<a name="l01223"></a>01223
<a name="l01224"></a>01224 header.rndterm = ntohl(header.rndterm);
<a name="l01225"></a>01225
<a name="l01226"></a>01226 <span class="comment">/* total list size */</span>
<a name="l01227"></a>01227 READ_ERRCHECK(fd, & header.totlistlen, <span class="keyword">sizeof</span>(header.totlistlen));
<a name="l01228"></a>01228 header.totlistlen = ntohl(header.totlistlen);
<a name="l01229"></a>01229
<a name="l01230"></a>01230 <span class="comment">/* number of elements */</span>
<a name="l01231"></a>01231 READ_ERRCHECK(fd, & header.numels, <span class="keyword">sizeof</span>(header.numels));
<a name="l01232"></a>01232 header.numels = ntohl(header.numels);
<a name="l01233"></a>01233
<a name="l01234"></a>01234 <span class="comment">/* length of every element, or '0' = variable */</span>
<a name="l01235"></a>01235 READ_ERRCHECK(fd, & header.elemlen, <span class="keyword">sizeof</span>(header.elemlen));
<a name="l01236"></a>01236 header.elemlen = ntohl(header.elemlen);
<a name="l01237"></a>01237
<a name="l01238"></a>01238 <span class="comment">/* list hash, or 0 = 'ignore' */</span>
<a name="l01239"></a>01239 READ_ERRCHECK(fd, & header.listhash, <span class="keyword">sizeof</span>(header.listhash));
<a name="l01240"></a>01240 header.listhash = ntohl(header.listhash);
<a name="l01241"></a>01241
<a name="l01242"></a>01242
<a name="l01243"></a>01243 <span class="comment">/* read content */</span>
<a name="l01244"></a>01244 totreadlen = totmemorylen = 0;
<a name="l01245"></a>01245 <span class="keywordflow">if</span> (header.elemlen > 0) {
<a name="l01246"></a>01246 <span class="comment">/* elements have constant size = header.elemlen */</span>
<a name="l01247"></a>01247 <span class="keywordflow">if</span> (l->attrs.unserializer != NULL) {
<a name="l01248"></a>01248 <span class="comment">/* use unserializer */</span>
<a name="l01249"></a>01249 buf = malloc(header.elemlen);
<a name="l01250"></a>01250 <span class="keywordflow">for</span> (cnt = 0; cnt < header.numels; cnt++) {
<a name="l01251"></a>01251 READ_ERRCHECK(fd, buf, header.elemlen);
<a name="l01252"></a>01252 list_append(l, l->attrs.unserializer(buf, & elsize));
<a name="l01253"></a>01253 totmemorylen += elsize;
<a name="l01254"></a>01254 }
<a name="l01255"></a>01255 } <span class="keywordflow">else</span> {
<a name="l01256"></a>01256 <span class="comment">/* copy verbatim into memory */</span>
<a name="l01257"></a>01257 <span class="keywordflow">for</span> (cnt = 0; cnt < header.numels; cnt++) {
<a name="l01258"></a>01258 buf = malloc(header.elemlen);
<a name="l01259"></a>01259 READ_ERRCHECK(fd, buf, header.elemlen);
<a name="l01260"></a>01260 list_append(l, buf);
<a name="l01261"></a>01261 }
<a name="l01262"></a>01262 totmemorylen = header.numels * header.elemlen;
<a name="l01263"></a>01263 }
<a name="l01264"></a>01264 totreadlen = header.numels * header.elemlen;
<a name="l01265"></a>01265 } <span class="keywordflow">else</span> {
<a name="l01266"></a>01266 <span class="comment">/* elements have variable size. Each element is preceded by its size */</span>
<a name="l01267"></a>01267 <span class="keywordflow">if</span> (l->attrs.unserializer != NULL) {
<a name="l01268"></a>01268 <span class="comment">/* use unserializer */</span>
<a name="l01269"></a>01269 <span class="keywordflow">for</span> (cnt = 0; cnt < header.numels; cnt++) {
<a name="l01270"></a>01270 READ_ERRCHECK(fd, & elsize, <span class="keyword">sizeof</span>(elsize));
<a name="l01271"></a>01271 buf = malloc((<span class="keywordtype">size_t</span>)elsize);
<a name="l01272"></a>01272 READ_ERRCHECK(fd, buf, elsize);
<a name="l01273"></a>01273 totreadlen += elsize;
<a name="l01274"></a>01274 list_append(l, l->attrs.unserializer(buf, & elsize));
<a name="l01275"></a>01275 totmemorylen += elsize;
<a name="l01276"></a>01276 }
<a name="l01277"></a>01277 } <span class="keywordflow">else</span> {
<a name="l01278"></a>01278 <span class="comment">/* copy verbatim into memory */</span>
<a name="l01279"></a>01279 <span class="keywordflow">for</span> (cnt = 0; cnt < header.numels; cnt++) {
<a name="l01280"></a>01280 READ_ERRCHECK(fd, & elsize, <span class="keyword">sizeof</span>(elsize));
<a name="l01281"></a>01281 buf = malloc(elsize);
<a name="l01282"></a>01282 READ_ERRCHECK(fd, buf, elsize);
<a name="l01283"></a>01283 totreadlen += elsize;
<a name="l01284"></a>01284 list_append(l, buf);
<a name="l01285"></a>01285 }
<a name="l01286"></a>01286 totmemorylen = totreadlen;
<a name="l01287"></a>01287 }
<a name="l01288"></a>01288 }
<a name="l01289"></a>01289
<a name="l01290"></a>01290 READ_ERRCHECK(fd, &elsize, <span class="keyword">sizeof</span>(elsize)); <span class="comment">/* read list terminator */</span>
<a name="l01291"></a>01291 elsize = ntohl(elsize);
<a name="l01292"></a>01292
<a name="l01293"></a>01293 <span class="comment">/* possibly verify the list consistency */</span>
<a name="l01294"></a>01294 <span class="comment">/* wrt hash */</span>
<a name="l01295"></a>01295 <span class="comment">/* don't do that</span>
<a name="l01296"></a>01296 <span class="comment"> if (header.listhash != 0 && header.listhash != list_hash(l)) {</span>
<a name="l01297"></a>01297 <span class="comment"> errno = ECANCELED;</span>
<a name="l01298"></a>01298 <span class="comment"> return -1;</span>
<a name="l01299"></a>01299 <span class="comment"> }</span>
<a name="l01300"></a>01300 <span class="comment"> */</span>
<a name="l01301"></a>01301
<a name="l01302"></a>01302 <span class="comment">/* wrt header */</span>
<a name="l01303"></a>01303 <span class="keywordflow">if</span> (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
<a name="l01304"></a>01304 errno = EPROTO;
<a name="l01305"></a>01305 <span class="keywordflow">return</span> -1;
<a name="l01306"></a>01306 }
<a name="l01307"></a>01307
<a name="l01308"></a>01308 <span class="comment">/* wrt file */</span>
<a name="l01309"></a>01309 <span class="keywordflow">if</span> (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
<a name="l01310"></a>01310 errno = EPROTO;
<a name="l01311"></a>01311 <span class="keywordflow">return</span> -1;
<a name="l01312"></a>01312 }
<a name="l01313"></a>01313
<a name="l01314"></a>01314 <span class="keywordflow">if</span> (len != NULL) {
<a name="l01315"></a>01315 *len = totmemorylen;
<a name="l01316"></a>01316 }
<a name="l01317"></a>01317
<a name="l01318"></a>01318 <span class="keywordflow">return</span> 0;
<a name="l01319"></a>01319 }
<a name="l01320"></a>01320
<a name="l01321"></a>01321 <span class="keywordtype">int</span> list_dump_file(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">char</span> *restrict filename, <span class="keywordtype">size_t</span> *restrict len) {
<a name="l01322"></a>01322 <span class="keywordtype">int</span> fd;
<a name="l01323"></a>01323 <span class="keywordtype">size_t</span> sizetoret;
<a name="l01324"></a>01324
<a name="l01325"></a>01325 fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
<a name="l01326"></a>01326 <span class="keywordflow">if</span> (fd < 0) <span class="keywordflow">return</span> -1;
<a name="l01327"></a>01327
<a name="l01328"></a>01328 sizetoret = list_dump_filedescriptor(l, fd, len);
<a name="l01329"></a>01329 close(fd);
<a name="l01330"></a>01330
<a name="l01331"></a>01331 <span class="keywordflow">return</span> sizetoret;
<a name="l01332"></a>01332 }
<a name="l01333"></a>01333
<a name="l01334"></a>01334 <span class="keywordtype">int</span> list_restore_file(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">const</span> <span class="keywordtype">char</span> *restrict filename, <span class="keywordtype">size_t</span> *restrict len) {
<a name="l01335"></a>01335 <span class="keywordtype">int</span> fd;
<a name="l01336"></a>01336 <span class="keywordtype">size_t</span> totdata;
<a name="l01337"></a>01337
<a name="l01338"></a>01338 fd = open(filename, O_RDONLY, 0);
<a name="l01339"></a>01339 <span class="keywordflow">if</span> (fd < 0) <span class="keywordflow">return</span> -1;
<a name="l01340"></a>01340
<a name="l01341"></a>01341 totdata = list_restore_filedescriptor(l, fd, len);
<a name="l01342"></a>01342 close(fd);
<a name="l01343"></a>01343
<a name="l01344"></a>01344 <span class="keywordflow">return</span> totdata;
<a name="l01345"></a>01345 }
<a name="l01346"></a>01346 <span class="preprocessor">#endif </span><span class="comment">/* ifndef SIMCLIST_NO_DUMPRESTORE */</span>
<a name="l01347"></a>01347
<a name="l01348"></a>01348
<a name="l01349"></a>01349 <span class="keyword">static</span> <span class="keywordtype">int</span> list_drop_elem(<a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l, <span class="keyword">struct</span> <a class="code" href="structlist__entry__s.html">list_entry_s</a> *tmp, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pos) {
<a name="l01350"></a>01350 <span class="keywordflow">if</span> (tmp == NULL) <span class="keywordflow">return</span> -1;
<a name="l01351"></a>01351
<a name="l01352"></a>01352 <span class="comment">/* fix mid pointer. This is wrt the PRE situation */</span>
<a name="l01353"></a>01353 <span class="keywordflow">if</span> (l->numels % 2) { <span class="comment">/* now odd */</span>
<a name="l01354"></a>01354 <span class="comment">/* sort out the base case by hand */</span>
<a name="l01355"></a>01355 <span class="keywordflow">if</span> (l->numels == 1) l->mid = NULL;
<a name="l01356"></a>01356 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (pos >= l->numels/2) l->mid = l->mid->prev;
<a name="l01357"></a>01357 } <span class="keywordflow">else</span> { <span class="comment">/* now even */</span>
<a name="l01358"></a>01358 <span class="keywordflow">if</span> (pos < l->numels/2) l->mid = l->mid->next;
<a name="l01359"></a>01359 }
<a name="l01360"></a>01360
<a name="l01361"></a>01361 tmp->prev->next = tmp->next;
<a name="l01362"></a>01362 tmp->next->prev = tmp->prev;
<a name="l01363"></a>01363
<a name="l01364"></a>01364 <span class="comment">/* free what's to be freed */</span>
<a name="l01365"></a>01365 <span class="keywordflow">if</span> (l->attrs.copy_data && tmp->data != NULL)
<a name="l01366"></a>01366 free(tmp->data);
<a name="l01367"></a>01367
<a name="l01368"></a>01368 <span class="keywordflow">if</span> (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
<a name="l01369"></a>01369 l->spareels[l->spareelsnum++] = tmp;
<a name="l01370"></a>01370 } <span class="keywordflow">else</span> {
<a name="l01371"></a>01371 free(tmp);
<a name="l01372"></a>01372 }
<a name="l01373"></a>01373
<a name="l01374"></a>01374 <span class="keywordflow">return</span> 0;
<a name="l01375"></a>01375 }
<a name="l01376"></a>01376
<a name="l01377"></a>01377 <span class="comment">/* ready-made comparators and meters */</span>
<a name="l01378"></a>01378 <span class="preprocessor">#define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); } </span>
<a name="l01379"></a>01379 <span class="preprocessor"></span>
<a name="l01380"></a>01380 SIMCLIST_NUMBER_COMPARATOR(int8_t)
<a name="l01381"></a>01381 SIMCLIST_NUMBER_COMPARATOR(int16_t)
<a name="l01382"></a>01382 SIMCLIST_NUMBER_COMPARATOR(int32_t)
<a name="l01383"></a>01383 SIMCLIST_NUMBER_COMPARATOR(int64_t)
<a name="l01384"></a>01384
<a name="l01385"></a>01385 SIMCLIST_NUMBER_COMPARATOR(uint8_t)
<a name="l01386"></a>01386 SIMCLIST_NUMBER_COMPARATOR(uint16_t)
<a name="l01387"></a>01387 SIMCLIST_NUMBER_COMPARATOR(uint32_t)
<a name="l01388"></a>01388 SIMCLIST_NUMBER_COMPARATOR(uint64_t)
<a name="l01389"></a>01389
<a name="l01390"></a>01390 SIMCLIST_NUMBER_COMPARATOR(<span class="keywordtype">float</span>)
<a name="l01391"></a>01391 SIMCLIST_NUMBER_COMPARATOR(<span class="keywordtype">double</span>)
<a name="l01392"></a>01392
<a name="l01393"></a>01393 <span class="keywordtype">int</span> list_comparator_string(const <span class="keywordtype">void</span> *a, const <span class="keywordtype">void</span> *b) { <span class="keywordflow">return</span> strcmp((<span class="keyword">const</span> <span class="keywordtype">char</span> *)b, (<span class="keyword">const</span> <span class="keywordtype">char</span> *)a); }
<a name="l01394"></a>01394
<a name="l01395"></a>01395 <span class="comment">/* ready-made metric functions */</span>
<a name="l01396"></a>01396 <span class="preprocessor">#define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { </span><span class="comment">/* kill compiler whinge */</span> } return sizeof(type); }
<a name="l01397"></a>01397
<a name="l01398"></a>01398 SIMCLIST_METER(int8_t)
<a name="l01399"></a>01399 SIMCLIST_METER(int16_t)
<a name="l01400"></a>01400 SIMCLIST_METER(int32_t)
<a name="l01401"></a>01401 SIMCLIST_METER(int64_t)
<a name="l01402"></a>01402
<a name="l01403"></a>01403 SIMCLIST_METER(uint8_t)
<a name="l01404"></a>01404 SIMCLIST_METER(uint16_t)
<a name="l01405"></a>01405 SIMCLIST_METER(uint32_t)
<a name="l01406"></a>01406 SIMCLIST_METER(uint64_t)
<a name="l01407"></a>01407
<a name="l01408"></a>01408 SIMCLIST_METER(<span class="keywordtype">float</span>)
<a name="l01409"></a>01409 SIMCLIST_METER(<span class="keywordtype">double</span>)
<a name="l01410"></a>01410
<a name="l01411"></a>01411 <span class="keywordtype">size_t</span> list_meter_string(const <span class="keywordtype">void</span> *el) { <span class="keywordflow">return</span> strlen((<span class="keyword">const</span> <span class="keywordtype">char</span> *)el) + 1; }
<a name="l01412"></a>01412
<a name="l01413"></a>01413 <span class="comment">/* ready-made hashing functions */</span>
<a name="l01414"></a>01414 <span class="preprocessor">#define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); }</span>
<a name="l01415"></a>01415 <span class="preprocessor"></span>
<a name="l01416"></a>01416 SIMCLIST_HASHCOMPUTER(int8_t)
<a name="l01417"></a>01417 SIMCLIST_HASHCOMPUTER(int16_t)
<a name="l01418"></a>01418 SIMCLIST_HASHCOMPUTER(int32_t)
<a name="l01419"></a>01419 SIMCLIST_HASHCOMPUTER(int64_t)
<a name="l01420"></a>01420
<a name="l01421"></a>01421 SIMCLIST_HASHCOMPUTER(uint8_t)
<a name="l01422"></a>01422 SIMCLIST_HASHCOMPUTER(uint16_t)
<a name="l01423"></a>01423 SIMCLIST_HASHCOMPUTER(uint32_t)
<a name="l01424"></a>01424 SIMCLIST_HASHCOMPUTER(uint64_t)
<a name="l01425"></a>01425
<a name="l01426"></a>01426 SIMCLIST_HASHCOMPUTER(<span class="keywordtype">float</span>)
<a name="l01427"></a>01427 SIMCLIST_HASHCOMPUTER(<span class="keywordtype">double</span>)
<a name="l01428"></a>01428
<a name="l01429"></a>01429 list_hash_t list_hashcomputer_string(const <span class="keywordtype">void</span> *el) {
<a name="l01430"></a>01430 <span class="keywordtype">size_t</span> l;
<a name="l01431"></a>01431 list_hash_t hash = 123;
<a name="l01432"></a>01432 <span class="keyword">const</span> <span class="keywordtype">char</span> *str = (<span class="keyword">const</span> <span class="keywordtype">char</span> *)el;
<a name="l01433"></a>01433 <span class="keywordtype">char</span> plus;
<a name="l01434"></a>01434
<a name="l01435"></a>01435 <span class="keywordflow">for</span> (l = 0; str[l] != <span class="charliteral">'\0'</span>; l++) {
<a name="l01436"></a>01436 <span class="keywordflow">if</span> (l) plus = hash ^ str[l];
<a name="l01437"></a>01437 <span class="keywordflow">else</span> plus = hash ^ (str[l] - str[0]);
<a name="l01438"></a>01438 hash += (plus << (CHAR_BIT * (l % <span class="keyword">sizeof</span>(list_hash_t))));
<a name="l01439"></a>01439 }
<a name="l01440"></a>01440
<a name="l01441"></a>01441 <span class="keywordflow">return</span> hash;
<a name="l01442"></a>01442 }
<a name="l01443"></a>01443
<a name="l01444"></a>01444
<a name="l01445"></a>01445 <span class="preprocessor">#ifndef NDEBUG</span>
<a name="l01446"></a>01446 <span class="preprocessor"></span><span class="keyword">static</span> <span class="keywordtype">int</span> list_repOk(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l01447"></a>01447 <span class="keywordtype">int</span> ok, i;
<a name="l01448"></a>01448 <span class="keyword">struct </span><a class="code" href="structlist__entry__s.html">list_entry_s</a> *s;
<a name="l01449"></a>01449
<a name="l01450"></a>01450 ok = (l != NULL) && (
<a name="l01451"></a>01451 <span class="comment">/* head/tail checks */</span>
<a name="l01452"></a>01452 (l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
<a name="l01453"></a>01453 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
<a name="l01454"></a>01454 <span class="comment">/* empty list */</span>
<a name="l01455"></a>01455 (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
<a name="l01456"></a>01456 <span class="comment">/* spare elements checks */</span>
<a name="l01457"></a>01457 l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
<a name="l01458"></a>01458 );
<a name="l01459"></a>01459
<a name="l01460"></a>01460 <span class="keywordflow">if</span> (!ok) <span class="keywordflow">return</span> 0;
<a name="l01461"></a>01461
<a name="l01462"></a>01462 <span class="keywordflow">if</span> (l->numels >= 1) {
<a name="l01463"></a>01463 <span class="comment">/* correct referencing */</span>
<a name="l01464"></a>01464 <span class="keywordflow">for</span> (i = -1, s = l->head_sentinel; i < (<span class="keywordtype">int</span>)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
<a name="l01465"></a>01465 <span class="keywordflow">if</span> (s->next->prev != s) <span class="keywordflow">break</span>;
<a name="l01466"></a>01466 }
<a name="l01467"></a>01467 ok = (i == (int)(l->numels-1)/2 && l->mid == s);
<a name="l01468"></a>01468 <span class="keywordflow">if</span> (!ok) <span class="keywordflow">return</span> 0;
<a name="l01469"></a>01469 <span class="keywordflow">for</span> (; s->next != NULL; i++, s = s->next) {
<a name="l01470"></a>01470 <span class="keywordflow">if</span> (s->next->prev != s) <span class="keywordflow">break</span>;
<a name="l01471"></a>01471 }
<a name="l01472"></a>01472 ok = (i == (int)l->numels && s == l->tail_sentinel);
<a name="l01473"></a>01473 }
<a name="l01474"></a>01474
<a name="l01475"></a>01475 <span class="keywordflow">return</span> ok;
<a name="l01476"></a>01476 }
<a name="l01477"></a>01477
<a name="l01478"></a>01478 <span class="keyword">static</span> <span class="keywordtype">int</span> list_attrOk(<span class="keyword">const</span> <a class="code" href="structlist__t.html" title="list object">list_t</a> *restrict l) {
<a name="l01479"></a>01479 <span class="keywordtype">int</span> ok;
<a name="l01480"></a>01480
<a name="l01481"></a>01481 ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);
<a name="l01482"></a>01482 <span class="keywordflow">return</span> ok;
<a name="l01483"></a>01483 }
<a name="l01484"></a>01484
<a name="l01485"></a>01485 <span class="preprocessor">#endif</span>
<a name="l01486"></a>01486 <span class="preprocessor"></span>
</pre></div></div>
</div>
<hr class="footer"/><address class="footer"><small>Generated on Thu Mar 31 2011 for pcsc-lite by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.3 </small></address>
</body>
</html>
