Debian Codegraph @

include/libcork/ipset/nodes.h

raw
1 /* -*- coding: utf-8 -*-
2 * ----------------------------------------------------------------------
3 * Copyright © 2010, libcorkipset authors
4 * All rights reserved.
5 *
6 * Please see the COPYING file in this distribution for license details.
7 * ----------------------------------------------------------------------
8 */
9
10 #ifndef LIBCORK_IPSET_NODES_H
11 #define LIBCORK_IPSET_NODES_H
12
13
14 #include <stdio.h>
15
16 #include <libcork/core.h>
17 #include <libcork/ds.h>
18
19
20 /*-----------------------------------------------------------------------
21 * Preliminaries
22 */
23
24 /**
25 * Each variable in a BDD is referred to by number.
26 */
27 typedef unsigned int ipset_variable;
28
29
30 /**
31 * Each BDD terminal represents an integer value. The integer must be
32 * non-negative, but must be within the range of the <i>signed</i>
33 * integer type.
34 */
35 typedef unsigned int ipset_value;
36
37
38 /**
39 * An identifier for each distinct node in a BDD.
40 *
41 * Internal implementation note. Since pointers are aligned to at
42 * least two bytes, the ID of a terminal node has its LSB set to 1,
43 * and has the terminal value stored in the remaining bits. The ID of
44 * a nonterminal node is simply a pointer to the node struct.
45 */
46 typedef unsigned int ipset_node_id;
47
48
49 /**
50 * Nodes can either be terminal or nonterminal.
51 */
52 enum ipset_node_type {
53 IPSET_NONTERMINAL_NODE = 0,
54 IPSET_TERMINAL_NODE = 1
55 };
56
57
58 /**
59 * Return the type of node represented by a particular node ID.
60 */
61 #define ipset_node_get_type(node_id) ((node_id) & 0x01)
62
63 #define IPSET_NODE_ID_FORMAT "%s%u"
64 #define IPSET_NODE_ID_VALUES(node_id) \
65 (ipset_node_get_type((node_id)) == IPSET_NONTERMINAL_NODE? "s": ""), \
66 ((node_id) >> 1)
67
68
69 /*-----------------------------------------------------------------------
70 * Terminal nodes
71 */
72
73 /**
74 * Return the value of a terminal node. The result is undefined if
75 * the node ID represents a nonterminal.
76 */
77 #define ipset_terminal_value(node_id) ((node_id) >> 1)
78
79 /**
80 * Creates a terminal node ID from a terminal value.
81 */
82 #define ipset_terminal_node_id(value) \
83 (((value) << 1) | IPSET_TERMINAL_NODE)
84
85
86 /*-----------------------------------------------------------------------
87 * Nonterminal nodes
88 */
89
90 /**
91 * A nonterminal BDD node. This is an inner node of the BDD tree.
92 * The node represents one variable in an overall variable assignment.
93 * The node has two children: a “low” child and a “high” child. The
94 * low child is the subtree that applies when the node's variable is
95 * false or 0; the high child is the subtree that applies when it's
96 * true or 1.
97 *
98 * This type does not take care of ensuring that all BDD nodes are
99 * reduced; that is handled by the node_cache class.
100 */
101 struct ipset_node {
102 /** The reference count for this node. */
103 unsigned int refcount;
104 /** The variable that this node represents. */
105 ipset_variable variable;
106 /** The subtree node for when the variable is false. */
107 ipset_node_id low;
108 /** The subtree node for when the variable is true. */
109 ipset_node_id high;
110 };
111
112 /**
113 * Return the "value" of a nonterminal node. The value of a nonterminal
114 * is the index into the node array of the cache that the node belongs
115 * to.
116 */
117 #define ipset_nonterminal_value(node_id) ((node_id) >> 1)
118
119 /**
120 * Creates a nonterminal node ID from a nonterminal value.
121 */
122 #define ipset_nonterminal_node_id(value) \
123 (((value) << 1) | IPSET_NONTERMINAL_NODE)
124
125 /**
126 * Print out a node object.
127 */
128 void
129 ipset_node_fprint(FILE *stream, struct ipset_node *node);
130
131
132 /*-----------------------------------------------------------------------
133 * Node caches
134 */
135
136 /**
137 * The log2 of the size of each chunk of BDD nodes.
138 */
139 /* 16K elements per cache */
140 #define IPSET_BDD_NODE_CACHE_BIT_SIZE 6
141 #define IPSET_BDD_NODE_CACHE_SIZE (1 << IPSET_BDD_NODE_CACHE_BIT_SIZE)
142 #define IPSET_BDD_NODE_CACHE_MASK (IPSET_BDD_NODE_CACHE_SIZE - 1)
143
144 /**
145 * A cache for BDD nodes. By creating and retrieving nodes through
146 * the cache, we ensure that a BDD is reduced.
147 */
148 struct ipset_node_cache {
149 /** The storage for the nodes managed by this cache. */
150 cork_array(struct ipset_node *) chunks;
151 /** The largest nonterminal index that has been handed out. */
152 ipset_value largest_index;
153 /** The index of the first node in the free list. */
154 ipset_value free_list;
155 /** A cache of the nonterminal nodes, keyed by their contents. */
156 struct cork_hash_table *node_cache;
157 };
158
159 /**
160 * Returns the index of the chunk that the given nonterminal lives in.
161 */
162 #define ipset_nonterminal_chunk_index(index) \
163 ((index) >> IPSET_BDD_NODE_CACHE_BIT_SIZE)
164
165 /**
166 * Returns the offset of the given nonterminal within its chunk.
167 */
168 #define ipset_nonterminal_chunk_offset(index) \
169 ((index) & IPSET_BDD_NODE_CACHE_MASK)
170
171 /**
172 * Returns a pointer to the ipset_node for a given nonterminal index.
173 */
174 #define ipset_node_cache_get_nonterminal_by_index(cache, index) \
175 (&cork_array_at(&(cache)->chunks, ipset_nonterminal_chunk_index((index))) \
176 [ipset_nonterminal_chunk_offset((index))])
177
178 /**
179 * Returns the ipset_node for a given nonterminal node ID.
180 */
181 #define ipset_node_cache_get_nonterminal(cache, node_id) \
182 (ipset_node_cache_get_nonterminal_by_index \
183 ((cache), ipset_nonterminal_value((node_id))))
184
185 /**
186 * Create a new node cache.
187 */
188 struct ipset_node_cache *
189 ipset_node_cache_new(void);
190
191 /**
192 * Free a node cache.
193 */
194 void
195 ipset_node_cache_free(struct ipset_node_cache *cache);
196
197 /**
198 * Create a new nonterminal node with the given contents, returning
199 * its ID. This function ensures that there is only one node with the
200 * given contents in this cache.
201 *
202 * Steals references to low and high.
203 */
204 ipset_node_id
205 ipset_node_cache_nonterminal(struct ipset_node_cache *cache,
206 ipset_variable variable,
207 ipset_node_id low, ipset_node_id high);
208
209
210 /**
211 * Increment the reference count of a nonterminal node. (This is a
212 * no-op for terminal nodes.)
213 */
214 ipset_node_id
215 ipset_node_incref(struct ipset_node_cache *cache, ipset_node_id node);
216
217 /**
218 * Decrement the reference count of a nonterminal node. If the
219 * reference count reaches 0, the storage for the node will be
220 * reclaimed. (This is a no-op for terminal nodes.)
221 */
222 void
223 ipset_node_decref(struct ipset_node_cache *cache, ipset_node_id node);
224
225
226 /**
227 * Return the number of nodes that are reachable from the given node.
228 * This does not include duplicates if a node is reachable via more
229 * than one path.
230 */
231 size_t
232 ipset_node_reachable_count(const struct ipset_node_cache *cache,
233 ipset_node_id node);
234
235
236 /**
237 * Return the amount of memory used by the nodes in the given BDD.
238 */
239 size_t
240 ipset_node_memory_size(const struct ipset_node_cache *cache,
241 ipset_node_id node);
242
243
244 /**
245 * Load a BDD from an input stream. The error field is filled in with
246 * an error condition is the BDD can't be read for any reason.
247 */
248 ipset_node_id
249 ipset_node_cache_load(FILE *stream, struct ipset_node_cache *cache);
250
251
252 /**
253 * Save a BDD to an output stream. This encodes the set using only
254 * those nodes that are reachable from the BDD's root node.
255 */
256 int
257 ipset_node_cache_save(struct cork_stream_consumer *stream,
258 struct ipset_node_cache *cache, ipset_node_id node);
259
260
261 /**
262 * Compare two BDD nodes, possibly from different caches, for equality.
263 */
264 bool
265 ipset_node_cache_nodes_equal(const struct ipset_node_cache *cache1,
266 ipset_node_id node1,
267 const struct ipset_node_cache *cache2,
268 ipset_node_id node2);
269
270
271 /**
272 * Save a GraphViz dot graph for a BDD. The graph script is written
273 * to the given output stream. This graph only includes those nodes
274 * that are reachable from the BDD's root node.
275 */
276 int
277 ipset_node_cache_save_dot(struct cork_stream_consumer *stream,
278 struct ipset_node_cache *cache, ipset_node_id node);
279
280
281 /*-----------------------------------------------------------------------
282 * BDD operators
283 */
284
285 /**
286 * A function that provides the value for each variable in a BDD.
287 */
288 typedef bool
289 (*ipset_assignment_func)(const void *user_data,
290 ipset_variable variable);
291
292 /**
293 * An assignment function that gets the variable values from an array
294 * of gbooleans.
295 */
296 bool
297 ipset_bool_array_assignment(const void *user_data,
298 ipset_variable variable);
299
300 /**
301 * An assignment function that gets the variable values from an array
302 * of bits.
303 */
304 bool
305 ipset_bit_array_assignment(const void *user_data,
306 ipset_variable variable);
307
308 /**
309 * Evaluate a BDD given a particular assignment of variables.
310 */
311 ipset_value
312 ipset_node_evaluate(const struct ipset_node_cache *cache, ipset_node_id node,
313 ipset_assignment_func assignment,
314 const void *user_data);
315
316 /**
317 * Add an assignment to the BDD.
318 */
319 ipset_node_id
320 ipset_node_insert(struct ipset_node_cache *cache, ipset_node_id node,
321 ipset_assignment_func assignment,
322 const void *user_data, ipset_variable variable_count,
323 ipset_value value);
324
325
326 /*-----------------------------------------------------------------------
327 * Variable assignments
328 */
329
330 /**
331 * Each variable in the input to a Boolean function can be true or
332 * false; it can also be EITHER, which means that the variable can be
333 * either true or false in a particular assignment without affecting
334 * the result of the function.
335 */
336 enum ipset_tribool {
337 IPSET_FALSE = 0,
338 IPSET_TRUE = 1,
339 IPSET_EITHER = 2
340 };
341
342
343 /**
344 * An assignment is a mapping of variable numbers to Boolean values.
345 * It represents an input to a Boolean function that maps to a
346 * particular output value. Each variable in the input to a Boolean
347 * function can be true or false; it can also be EITHER, which means
348 * that the variable can be either true or false in a particular
349 * assignment without affecting the result of the function.
350 */
351
352 struct ipset_assignment {
353 /**
354 * The underlying variable assignments are stored in a vector of
355 * tribools. Every variable that has a true or false value must
356 * appear in the vector. Variables that are EITHER only have to
357 * appear to prevent gaps in the vector. Any variables outside
358 * the range of the vector are assumed to be EITHER.
359 */
360 cork_array(enum ipset_tribool) values;
361 };
362
363
364 /**
365 * Create a new assignment where all variables are indeterminite.
366 */
367 struct ipset_assignment *
368 ipset_assignment_new();
369
370
371 /**
372 * Free an assignment.
373 */
374 void
375 ipset_assignment_free(struct ipset_assignment *assignment);
376
377
378 /**
379 * Compare two assignments for equality.
380 */
381 bool
382 ipset_assignment_equal(const struct ipset_assignment *assignment1,
383 const struct ipset_assignment *assignment2);
384
385
386 /**
387 * Set the given variable, and all higher variables, to the EITHER
388 * value.
389 */
390 void
391 ipset_assignment_cut(struct ipset_assignment *assignment, ipset_variable var);
392
393
394 /**
395 * Clear the assignment, setting all variables to the EITHER value.
396 */
397 void
398 ipset_assignment_clear(struct ipset_assignment *assignment);
399
400
401 /**
402 * Return the value assigned to a particular variable.
403 */
404 enum ipset_tribool
405 ipset_assignment_get(struct ipset_assignment *assignment, ipset_variable var);
406
407
408 /**
409 * Set the value assigned to a particular variable.
410 */
411 void
412 ipset_assignment_set(struct ipset_assignment *assignment,
413 ipset_variable var, enum ipset_tribool value);
414
415
416 /*-----------------------------------------------------------------------
417 * Expanded assignments
418 */
419
420 /**
421 * An iterator for expanding a variable assignment. For each EITHER
422 * variable in the assignment, the iterator yields a result with both
423 * values.
424 */
425 struct ipset_expanded_assignment {
426 /** Whether there are any more assignments in this iterator. */
427 bool finished;
428
429 /**
430 * The variable values in the current expanded assignment. Since
431 * there won't be any EITHERs in the expanded assignment, we can
432 * use a byte array, and represent each variable by a single bit.
433 */
434 struct cork_buffer values;
435
436 /**
437 * An array containing all of the variables that are EITHER in the
438 * original assignment.
439 */
440 cork_array(ipset_variable) eithers;
441 };
442
443
444 /**
445 * Return an iterator that expands a variable assignment. For each
446 * variable that's EITHER in the assignment, the iterator yields a
447 * result with both values. The iterator will ensure that the
448 * specified number of variables are given concrete values.
449 */
450 struct ipset_expanded_assignment *
451 ipset_assignment_expand(const struct ipset_assignment *assignment,
452 ipset_variable var_count);
453
454
455 /**
456 * Free an expanded assignment iterator.
457 */
458 void
459 ipset_expanded_assignment_free(struct ipset_expanded_assignment *exp);
460
461
462 /**
463 * Advance the iterator to the next assignment.
464 */
465 void
466 ipset_expanded_assignment_advance(struct ipset_expanded_assignment *exp);
467
468
469 /*-----------------------------------------------------------------------
470 * BDD iterators
471 */
472
473 /**
474 * An iterator for walking through the assignments for a given BDD
475 * node.
476 *
477 * The iterator walks through each path in the BDD tree, stopping at
478 * each terminal node. Each time we reach a terminal node, we yield a
479 * new ipset_assignment object representing the assignment of variables
480 * along the current path.
481 *
482 * We maintain a stack of nodes leading to the current terminal, which
483 * allows us to backtrack up the path to find the next terminal when
484 * we increment the iterator.
485 */
486 struct ipset_bdd_iterator {
487 /** Whether there are any more assignments in this iterator. */
488 bool finished;
489
490 /** The node cache that we're iterating through. */
491 struct ipset_node_cache *cache;
492
493 /**
494 * The sequence of nonterminal nodes leading to the current
495 * terminal.
496 */
497 cork_array(ipset_node_id) stack;
498
499 /** The current assignment. */
500 struct ipset_assignment *assignment;
501
502 /**
503 * The value of the BDD's function when applied to the current
504 * assignment.
505 */
506 ipset_value value;
507 };
508
509
510 /**
511 * Return an iterator that yields all of the assignments in the given
512 * BDD. The iterator contains two items of interest. The first is an
513 * ipset_assignment providing the value that each variable takes, while
514 * the second is the terminal value that is the result of the BDD's
515 * function when applied to that variable assignment.
516 */
517 struct ipset_bdd_iterator *
518 ipset_node_iterate(struct ipset_node_cache *cache, ipset_node_id root);
519
520
521 /**
522 * Free a BDD iterator.
523 */
524 void
525 ipset_bdd_iterator_free(struct ipset_bdd_iterator *iterator);
526
527
528 /**
529 * Advance the iterator to the next assignment.
530 */
531 void
532 ipset_bdd_iterator_advance(struct ipset_bdd_iterator *iterator);
533
534
535 #endif /* LIBCORK_IPSET_NODES_H */