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
|
/** @file runtime/bush.h
* Declarations of low-level tree operations for handling multi-sets
*/
/* Copyright 2000-2002 Marko Mkel (msmakela@tcs.hut.fi).
This file is part of MARIA, a reachability analyzer and model checker
for high-level Petri nets.
MARIA is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
MARIA is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
The GNU General Public License is often shipped with GNU software, and
is generally kept in a file called COPYING or LICENSE. If you do not
have a copy of the license, write to the Free Software Foundation,
59 Temple Place, Suite 330, Boston, MA 02111 USA. */
#include<string.h>
#include<stdlib.h>
#include"Error.h"
#include"types.h"
#ifndef CONST
# ifdef __GNUC__
# define CONST __attribute__ ((const))
# else
# define CONST
# endif
#endif
/* multi-set and type declaration stuff */
/** three-way conditional comparison for data items
* @param f flag: perform the comparison?
* @param l left-hand-side argument
* @param r right-hand-side argument
* @param c component to compare
* @param s action to perform if l is smaller than right
* @param g action to perform if l is greater than right
*/
#define CC3(f,l,r,c,s,g) if (f) {if (l c<r c) {s;} else if (l c>r c) {g;}}
/** three-way comparison for data items
* @param l left-hand-side argument
* @param r right-hand-side argument
* @param c component to compare
* @param s action to perform if l is smaller than right
* @param g action to perform if l is greater than right
*/
#define C3(l,r,c,s,g) if (l c < r c) { s; } else if (l c > r c) { g; }
/** name of the current tree type */
#define TREE ID(tree)
/** name of the current type */
#define TYPE ID(t)
/** generic tree structure */
struct tree
{
struct tree *up, *left, *right;
#ifdef RED_BLACK
bool_t red;
#endif /* RED_BLACK */
card_t count;
};
/** declare a multi-set data structure */
#ifdef RED_BLACK
# define DECLARE_MULTISET \
struct TREE \
{ \
struct TREE *up, *left, *right; \
bool_t red; \
card_t count; \
TYPE item; \
}
#else /* RED_BLACK */
# define DECLARE_MULTISET \
struct TREE \
{ \
struct TREE *up, *left, *right; \
card_t count; \
TYPE item; \
}
#endif /* RED_BLACK */
/** declare multi-set operations */
#define DECLARE_MULTISET_OPS \
DECLARE_MULTISET; \
struct TREE* ID(insert) (struct TREE*,const TYPE*,card_t); \
struct TREE* ID(find) (struct TREE*,const TYPE*) CONST; \
bool_t ID(equal) (const struct TREE*,const struct TREE*) CONST; \
bool_t ID(subset) (const struct TREE*,const struct TREE*) CONST;\
void ID(intersect) (struct TREE*,const struct TREE*); \
void ID(subtract) (struct TREE*,const struct TREE*); \
struct TREE* ID(copy) (struct TREE*,const struct TREE*); \
struct TREE* ID(copyc) (struct TREE*,const struct TREE*,card_t)
/** climb to the root of a tree
* @param t in: a tree node; out: the root of the tree
*/
#define ROOT(t) if (t) while (t->up) t = t->up
/** get the minimum item in a tree
* @param t in: root of the tree; out: minimum item in tree
*/
#define FIRST(t) if (t) while ((t)->left) (t) = (t)->left
/** get the successor of a tree node
* @param t in: the tree node; out: successor of the node
*/
#define NEXT(t) do { \
if ((t)->right) for ((t) = (t)->right; (t)->left; (t) = (t)->left); \
else { \
while ((t)->up && (t) == (t)->up->right) (t) = (t)->up; \
(t) = (t)->up; \
} \
} while (0)
/** free a tree
* @param t in: tree to be freed; out: NULL
*/
#define FREE(t) (t ? (freetree (t), t = 0) : 0)
void freetree (void* node);
/** determine whether the multi-set a tree represents is singleton
* @param node the root of the tree
* @return pointer to the item, or 0 if the tree is not singleton
*/
void* singleton (void* node) CONST;
/** determine whether the multi-set a tree represents is empty
* @param node the root of the tree
* @return pointer to the first non-empty item, or 0 if the tree is empty
*/
const void* nonempty (const void* node) CONST;
|
