1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
<!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>Open SCAP Library: /home/pvrabec/project/openscap/openscap-0.5.12/src/OVAL/probes/SEAP/generic/rbt/rbt_common.h 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.6.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</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>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
<h1>/home/pvrabec/project/openscap/openscap-0.5.12/src/OVAL/probes/SEAP/generic/rbt/rbt_common.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> * Copyright 2010 Red Hat Inc., Durham, North Carolina.</span>
<a name="l00003"></a>00003 <span class="comment"> * All Rights Reserved.</span>
<a name="l00004"></a>00004 <span class="comment"> *</span>
<a name="l00005"></a>00005 <span class="comment"> * This library is free software; you can redistribute it and/or</span>
<a name="l00006"></a>00006 <span class="comment"> * modify it under the terms of the GNU Lesser General Public</span>
<a name="l00007"></a>00007 <span class="comment"> * License as published by the Free Software Foundation; either</span>
<a name="l00008"></a>00008 <span class="comment"> * version 2.1 of the License, or (at your option) any later version.</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * This library is distributed in the hope that it will be useful,</span>
<a name="l00011"></a>00011 <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00012"></a>00012 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span>
<a name="l00013"></a>00013 <span class="comment"> * Lesser General Public License for more details.</span>
<a name="l00014"></a>00014 <span class="comment"> *</span>
<a name="l00015"></a>00015 <span class="comment"> * You should have received a copy of the GNU Lesser General Public</span>
<a name="l00016"></a>00016 <span class="comment"> * License along with this library; if not, write to the Free Software</span>
<a name="l00017"></a>00017 <span class="comment"> * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA</span>
<a name="l00018"></a>00018 <span class="comment"> *</span>
<a name="l00019"></a>00019 <span class="comment"> * Authors:</span>
<a name="l00020"></a>00020 <span class="comment"> * "Daniel Kopecek" <dkopecek@redhat.com></span>
<a name="l00021"></a>00021 <span class="comment"> */</span>
<a name="l00022"></a>00022 <span class="preprocessor">#ifndef RBT_COMMON_H</span>
<a name="l00023"></a>00023 <span class="preprocessor"></span><span class="preprocessor">#define RBT_COMMON_H</span>
<a name="l00024"></a>00024 <span class="preprocessor"></span>
<a name="l00025"></a>00025 <span class="preprocessor">#include <stdint.h></span>
<a name="l00026"></a>00026 <span class="preprocessor">#include <stdbool.h></span>
<a name="l00027"></a>00027
<a name="l00028"></a>00028 <span class="preprocessor">#if defined(RBT_IMPLICIT_LOCKING)</span>
<a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor"># include <pthread.h></span>
<a name="l00030"></a>00030 <span class="preprocessor">#endif</span>
<a name="l00031"></a>00031 <span class="preprocessor"></span>
<a name="l00032"></a>00032 <span class="keyword">typedef</span> <span class="keyword">enum</span> {
<a name="l00033"></a>00033 RBT_GENKEY,
<a name="l00034"></a>00034 RBT_STRKEY,
<a name="l00035"></a>00035 RBT_I32KEY,
<a name="l00036"></a>00036 RBT_I64KEY
<a name="l00037"></a>00037 } rbt_type_t;
<a name="l00038"></a>00038
<a name="l00039"></a>00039 <span class="keyword">typedef</span> <span class="keyword">enum</span> {
<a name="l00040"></a>00040 RBT_WALK_PREORDER = 0x01,
<a name="l00041"></a>00041 RBT_WALK_INORDER = 0x02,
<a name="l00042"></a>00042 RBT_WALK_POSTORDER = 0x03,
<a name="l00043"></a>00043 RBT_WALK_LEVELORDER = 0x04,
<a name="l00044"></a>00044 RBT_WALK_RAWNODE = 0x10
<a name="l00045"></a>00045 } rbt_walk_t;
<a name="l00046"></a>00046
<a name="l00047"></a>00047 <span class="preprocessor">#define RBT_WALK_TYPEMASK 0x0f</span>
<a name="l00048"></a>00048 <span class="preprocessor"></span><span class="preprocessor">#define RBT_WALK_FLAGMASK 0xf0</span>
<a name="l00049"></a>00049 <span class="preprocessor"></span>
<a name="l00054"></a><a class="code" href="structrbt__node.html">00054</a> <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> {
<a name="l00055"></a>00055 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *_chld[2];
<a name="l00056"></a>00056 uint8_t _node[];
<a name="l00057"></a>00057 };
<a name="l00058"></a>00058
<a name="l00059"></a>00059 <span class="preprocessor">#define RBT_NODE_CB 0</span>
<a name="l00060"></a>00060 <span class="preprocessor"></span><span class="preprocessor">#define RBT_NODE_CR 1</span>
<a name="l00061"></a>00061 <span class="preprocessor"></span><span class="preprocessor">#define RBT_NODE_SL 0</span>
<a name="l00062"></a>00062 <span class="preprocessor"></span><span class="preprocessor">#define RBT_NODE_SR 1</span>
<a name="l00063"></a>00063 <span class="preprocessor"></span>
<a name="l00064"></a>00064 <span class="preprocessor">#define rbt_node_ptr(np) ((struct rbt_node *)((uintptr_t)(np)&(UINTPTR_MAX << 1)))</span>
<a name="l00065"></a>00065 <span class="preprocessor"></span><span class="preprocessor">#define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1))</span>
<a name="l00066"></a>00066 <span class="preprocessor"></span>
<a name="l00067"></a>00067 <span class="preprocessor">#define rbt_node_setcolor(np, cb) \</span>
<a name="l00068"></a>00068 <span class="preprocessor"> do { \</span>
<a name="l00069"></a>00069 <span class="preprocessor"> register struct rbt_node *__n = rbt_node_ptr(np); \</span>
<a name="l00070"></a>00070 <span class="preprocessor"> register uint8_t __c = (cb) & 1; \</span>
<a name="l00071"></a>00071 <span class="preprocessor"> \</span>
<a name="l00072"></a>00072 <span class="preprocessor"> if (__n != NULL) { \</span>
<a name="l00073"></a>00073 <span class="preprocessor"> if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \</span>
<a name="l00074"></a>00074 <span class="preprocessor"> else __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \</span>
<a name="l00075"></a>00075 <span class="preprocessor"> } \</span>
<a name="l00076"></a>00076 <span class="preprocessor"> } while(0)</span>
<a name="l00077"></a>00077 <span class="preprocessor"></span><span class="preprocessor">#define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1)</span>
<a name="l00078"></a>00078 <span class="preprocessor"></span><span class="preprocessor">#define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0]))</span>
<a name="l00079"></a>00079 <span class="preprocessor"></span><span class="preprocessor">#define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn))</span>
<a name="l00080"></a>00080 <span class="preprocessor"></span>
<a name="l00081"></a>00081 <span class="preprocessor">#define rbt_hpush4(__a, __p) \</span>
<a name="l00082"></a>00082 <span class="preprocessor"> do { \</span>
<a name="l00083"></a>00083 <span class="preprocessor"> __a[3] = __a[2]; \</span>
<a name="l00084"></a>00084 <span class="preprocessor"> __a[2] = __a[1]; \</span>
<a name="l00085"></a>00085 <span class="preprocessor"> __a[1] = __a[0]; \</span>
<a name="l00086"></a>00086 <span class="preprocessor"> __a[0] = __p; \</span>
<a name="l00087"></a>00087 <span class="preprocessor"> } while(0)</span>
<a name="l00088"></a>00088 <span class="preprocessor"></span>
<a name="l00089"></a>00089 <span class="preprocessor">#define rbt_hpush3(__a, __p) \</span>
<a name="l00090"></a>00090 <span class="preprocessor"> do { \</span>
<a name="l00091"></a>00091 <span class="preprocessor"> __a[2] = __a[1]; \</span>
<a name="l00092"></a>00092 <span class="preprocessor"> __a[1] = __a[0]; \</span>
<a name="l00093"></a>00093 <span class="preprocessor"> __a[0] = __p; \</span>
<a name="l00094"></a>00094 <span class="preprocessor"> } while(0)</span>
<a name="l00095"></a>00095 <span class="preprocessor"></span>
<a name="l00096"></a>00096 <span class="preprocessor">#define rbt_redfix(__h, __d, v) \</span>
<a name="l00097"></a>00097 <span class="preprocessor"> do { \</span>
<a name="l00098"></a>00098 <span class="preprocessor"> if (((__d) & 3) < 2) { \</span>
<a name="l00099"></a>00099 <span class="preprocessor"> if (((__d) & 3) == 0) { \</span>
<a name="l00100"></a>00100 <span class="preprocessor"> rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \</span>
<a name="l00101"></a>00101 <span class="preprocessor"> } else { \</span>
<a name="l00102"></a>00102 <span class="preprocessor"> rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \</span>
<a name="l00103"></a>00103 <span class="preprocessor"> } \</span>
<a name="l00104"></a>00104 <span class="preprocessor"> } else { \</span>
<a name="l00105"></a>00105 <span class="preprocessor"> if (((__d) & 3) == 2) { \</span>
<a name="l00106"></a>00106 <span class="preprocessor"> rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \</span>
<a name="l00107"></a>00107 <span class="preprocessor"> } else { \</span>
<a name="l00108"></a>00108 <span class="preprocessor"> rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \</span>
<a name="l00109"></a>00109 <span class="preprocessor"> } \</span>
<a name="l00110"></a>00110 <span class="preprocessor"> } \</span>
<a name="l00111"></a>00111 <span class="preprocessor"> } while(0)</span>
<a name="l00112"></a>00112 <span class="preprocessor"></span>
<a name="l00113"></a><a class="code" href="structrbt.html">00113</a> <span class="keyword">struct </span><a class="code" href="structrbt.html">rbt</a> {
<a name="l00114"></a>00114 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *root;
<a name="l00115"></a>00115 <span class="keywordtype">size_t</span> size;
<a name="l00116"></a>00116 rbt_type_t type;
<a name="l00117"></a>00117 <span class="preprocessor">#if defined(RBT_IMPLICIT_LOCKING)</span>
<a name="l00118"></a>00118 <span class="preprocessor"></span> pthread_rwlock_t lock;
<a name="l00119"></a>00119 <span class="preprocessor">#endif</span>
<a name="l00120"></a>00120 <span class="preprocessor"></span>};
<a name="l00121"></a>00121
<a name="l00122"></a>00122 <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structrbt.html">rbt</a> <a class="code" href="structrbt.html">rbt_t</a>;
<a name="l00123"></a>00123
<a name="l00128"></a>00128 <a class="code" href="structrbt.html">rbt_t</a> *rbt_new(rbt_type_t type);
<a name="l00129"></a>00129
<a name="l00136"></a>00136 <span class="keywordtype">void</span> rbt_free(<a class="code" href="structrbt.html">rbt_t</a> *<a class="code" href="structrbt.html">rbt</a>, <span class="keywordtype">void</span> (*<a class="code" href="structcallback__t.html" title="Typedef of callback structure with system identificator, callback function and usr...">callback</a>)(<span class="keywordtype">void</span> *));
<a name="l00137"></a>00137
<a name="l00142"></a>00142 <span class="keywordtype">int</span> rbt_rlock(<a class="code" href="structrbt.html">rbt_t</a> *rbt);
<a name="l00143"></a>00143
<a name="l00148"></a>00148 <span class="keywordtype">void</span> rbt_runlock(<a class="code" href="structrbt.html">rbt_t</a> *rbt);
<a name="l00149"></a>00149
<a name="l00154"></a>00154 <span class="keywordtype">int</span> rbt_wlock(<a class="code" href="structrbt.html">rbt_t</a> *rbt);
<a name="l00155"></a>00155
<a name="l00160"></a>00160 <span class="keywordtype">void</span> rbt_wunlock(<a class="code" href="structrbt.html">rbt_t</a> *rbt);
<a name="l00161"></a>00161
<a name="l00162"></a>00162 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *rbt_node_rotate_L(<span class="keyword">struct</span> <a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *);
<a name="l00163"></a>00163 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *rbt_node_rotate_R(<span class="keyword">struct</span> <a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *);
<a name="l00164"></a>00164 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *rbt_node_rotate_LR(<span class="keyword">struct</span> <a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *);
<a name="l00165"></a>00165 <span class="keyword">struct </span><a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *rbt_node_rotate_RL(<span class="keyword">struct</span> <a class="code" href="structrbt__node.html" title="Generic node structure Lowest bit of _chld[0] holds the color bit.">rbt_node</a> *);
<a name="l00166"></a>00166
<a name="l00167"></a>00167 <span class="keywordtype">size_t</span> rbt_size(<a class="code" href="structrbt.html">rbt_t</a> *rbt);
<a name="l00168"></a>00168
<a name="l00169"></a>00169 <span class="preprocessor">#define rbt_walk_push(n) stack[depth++] = (n)</span>
<a name="l00170"></a>00170 <span class="preprocessor"></span><span class="preprocessor">#define rbt_walk_pop() stack[--depth]</span>
<a name="l00171"></a>00171 <span class="preprocessor"></span><span class="preprocessor">#define rbt_walk_top() stack[depth-1]</span>
<a name="l00172"></a>00172 <span class="preprocessor"></span>
<a name="l00173"></a>00173 <span class="keywordtype">int</span> rbt_walk_preorder(<a class="code" href="structrbt.html">rbt_t</a> *rbt, <span class="keywordtype">int</span> (*<a class="code" href="structcallback__t.html" title="Typedef of callback structure with system identificator, callback function and usr...">callback</a>)(<span class="keywordtype">void</span> *), rbt_walk_t flags);
<a name="l00174"></a>00174 <span class="keywordtype">int</span> rbt_walk_inorder(<a class="code" href="structrbt.html">rbt_t</a> *rbt, <span class="keywordtype">int</span> (*<a class="code" href="structcallback__t.html" title="Typedef of callback structure with system identificator, callback function and usr...">callback</a>)(<span class="keywordtype">void</span> *), rbt_walk_t flags);
<a name="l00175"></a>00175 <span class="keywordtype">int</span> rbt_walk_postorder(<a class="code" href="structrbt.html">rbt_t</a> *rbt, <span class="keywordtype">int</span> (*<a class="code" href="structcallback__t.html" title="Typedef of callback structure with system identificator, callback function and usr...">callback</a>)(<span class="keywordtype">void</span> *), rbt_walk_t flags);
<a name="l00176"></a>00176
<a name="l00177"></a>00177 <span class="preprocessor">#endif </span><span class="comment">/* RBT_COMMON_H */</span>
</pre></div></div>
<hr size="1"/><address style="text-align: right;"><small>Generated on 30 Jun 2010 for Open SCAP Library by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
|
