1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 /////////////////////////////////////////////////////////////////
26 // This file implements the memorization and token propagation
27 // routines used by the Rete matching algorithm.
28 /////////////////////////////////////////////////////////////////
29 #include <AD/rete/retenet.h>
30 #include <AD/memory/boundtag.h>
32 /////////////////////////////////////////////////////////////////
33 // A description of the data structures:
34 // There are 3 kinds of nodes within the network.
35 // (1) And nodes: these nodes have a left and a right input.
36 // A new token, computed as the concatention of the
37 // two inputs, is propagate to its output node if the new
38 // token satisfies the node test.
39 // (2) Not nodes: these nodes also have a left and a right input.
40 // The token from the left node is propagated only if
41 // there is no input from the right.
42 // (3) Terminal nodes: when a token arrives at these nodes it
43 // will be added to the conflict set.
44 /////////////////////////////////////////////////////////////////
46 /////////////////////////////////////////////////////////////////
47 // Make hidden types visible at top level
48 /////////////////////////////////////////////////////////////////
49 typedef ReteNet::NodeId NodeId
;
50 typedef ReteNet::RuleId RuleId
;
51 typedef ReteNet::Token Token
;
52 typedef ReteNet::Node Node
;
54 /////////////////////////////////////////////////////////////////
55 // Constructor for class
56 /////////////////////////////////////////////////////////////////
57 ReteNet::ReteNet(int N
, const Node net
[])
58 : mem (* new BoundaryTag(4096)), // create new memory manager
62 // set up alpha and beta memory.
63 alpha
= (AlphaMemo
*) mem
.c_alloc(sizeof(AlphaMemo
) * N
);
64 beta
= (BetaMemo
*) mem
.c_alloc(sizeof(BetaMemo
) * N
);
67 /////////////////////////////////////////////////////////////////
68 // Destructor for class
69 /////////////////////////////////////////////////////////////////
70 ReteNet::~ReteNet() { delete (&mem
); }
72 /////////////////////////////////////////////////////////////////
73 // Clears all alpha/beta memory
74 /////////////////////////////////////////////////////////////////
76 { mem
.clear(); // reset the memory manager
77 // reallocate all alpha/beta memory
78 alpha
= (AlphaMemo
*) mem
.c_alloc(sizeof(AlphaMemo
) * number_of_nodes
);
79 beta
= (BetaMemo
*) mem
.c_alloc(sizeof(BetaMemo
) * number_of_nodes
);
82 /////////////////////////////////////////////////////////////////
84 /////////////////////////////////////////////////////////////////
86 inline void copy (register T
* dest
, register T
* src
, register int n
)
87 { for ( ; n
> 0; n
--) *dest
++ = *src
++; }
89 /////////////////////////////////////////////////////////////////
90 // Routines for memorization management
91 /////////////////////////////////////////////////////////////////
93 /////////////////////////////////////////////////////////////////
94 // Method: memorize_beta(...)
95 // This method addes a new token ``facts'' to the beta memory
96 // of a node; the beta memory is resized if necessary.
97 /////////////////////////////////////////////////////////////////
98 inline void ReteNet::memorize_beta(NodeId n
, Fact
** facts
)
99 { register BetaMemo
& memo
= beta
[n
];
100 if (memo
.count
== memo
.capacity
) {
101 int new_capacity
= memo
.capacity
* 3 / 2 + 2;
102 Token
* new_facts
= (Token
*)mem
.m_alloc(new_capacity
* sizeof(Token
));
104 copy(new_facts
,memo
.tokens
,memo
.capacity
);
105 mem
.free(memo
.tokens
);
107 memo
.capacity
= new_capacity
;
108 memo
.tokens
= new_facts
;
110 Fact
** new_token
= (Fact
**)mem
.m_alloc(network
[n
].arity
* sizeof(Fact
*));
111 copy(new_token
,facts
,(int)network
[n
].arity
);
112 memo
.tokens
[memo
.count
++] = new_token
;
115 /////////////////////////////////////////////////////////////////
116 // Method: memorize_alpha(...)
117 // This method addes a new token ``facts'' to the alpha memory
118 // of a node; the alpha memory is resized if necessary.
119 /////////////////////////////////////////////////////////////////
120 inline void ReteNet::memorize_alpha(NodeId n
, Fact
* fact
)
121 { register AlphaMemo
& memo
= alpha
[n
];
122 if (memo
.count
== memo
.capacity
) {
123 int new_capacity
= memo
.capacity
* 3 / 2 + 2;
124 Fact
** new_facts
= (Fact
**)mem
.m_alloc(new_capacity
* sizeof(Fact
*));
126 copy(new_facts
,memo
.facts
,memo
.capacity
);
127 mem
.free(memo
.facts
);
129 memo
.capacity
= new_capacity
;
130 memo
.facts
= new_facts
;
132 memo
.facts
[memo
.count
++] = fact
;
135 /////////////////////////////////////////////////////////////////
136 // Method: memorize_not_on_beta(...)
137 // This method addes a new token ``facts'' to the beta memory
138 // of a negation node; the beta memory is resized if necessary.
139 /////////////////////////////////////////////////////////////////
140 inline void ReteNet::memorize_not_on_beta(NodeId n
, int matches
, Fact
** facts
)
141 { register BetaMemo
& memo
= beta
[n
];
142 if (memo
.count
== memo
.capacity
) {
143 int new_capacity
= memo
.capacity
* 3 / 2 + 2;
144 Token
* new_facts
= (Token
*)mem
.m_alloc(new_capacity
* sizeof(Token
));
145 int * new_matches
= (int *)mem
.c_alloc(new_capacity
* sizeof(int));
147 copy(new_facts
,memo
.tokens
,memo
.capacity
);
148 copy(new_matches
,memo
.matches
,memo
.capacity
);
149 mem
.free(memo
.tokens
);
150 mem
.free(memo
.matches
);
152 memo
.capacity
= new_capacity
;
153 memo
.tokens
= new_facts
;
154 memo
.matches
= new_matches
;
156 Fact
** new_token
= (Fact
**)mem
.m_alloc(network
[n
].arity
* sizeof(Fact
*));
157 copy(new_token
,facts
,(int)network
[n
].arity
);
158 memo
.matches
[memo
.count
] = matches
;
159 memo
.tokens
[memo
.count
++] = new_token
;
162 //////////////////////////////////////////////////////////////////////////
163 // Insert a partially constructed token into a node from the beta side
164 //////////////////////////////////////////////////////////////////////////
165 void ReteNet::insert_beta(NodeId n
, Fact
* facts
[])
166 { register const Node
& node
= network
[n
];
170 ////////////////////////////////////////////////////////////////////
171 // Testing node; just apply the test and propagate the token
172 // if the test is satisfied.
173 ////////////////////////////////////////////////////////////////////
175 insert_beta(node
.child
,facts
); insert_beta(n
+1,facts
); break;
177 if (node
.join
== 0 || beta_test(node
.join
,facts
))
178 insert_beta(node
.child
,facts
);
180 ////////////////////////////////////////////////////////////////////
182 // Concatenate the new fact with every alpha input memorized;
183 // apply the join on this new token, and propagate the token
184 // if it is satisfied. Also, memorize the new beta input.
185 ////////////////////////////////////////////////////////////////////
187 { register AlphaMemo
& memo
= alpha
[n
];
188 for (i
= memo
.count
- 1; i
>= 0; i
--) {
189 facts
[node
.beta_arity
] = memo
.facts
[i
];
190 if (node
.join
== 0 || beta_test(node
.join
,facts
))
191 insert_beta(node
.child
,facts
);
193 memorize_beta(n
,facts
);
195 ////////////////////////////////////////////////////////////////////
197 // Concatenate the new fact with every alpha input memorized;
198 // apply the join on this new token, and propagate the token
199 // if *none* of the join is satisfied.
200 // Also, memorize the new beta input.
201 ////////////////////////////////////////////////////////////////////
203 { register AlphaMemo
& memo
= alpha
[n
];
205 for (match_count
= 0, i
= memo
.count
- 1; i
>= 0; i
--) {
206 facts
[node
.beta_arity
] = memo
.facts
[i
];
207 if (node
.join
== 0 || beta_test(node
.join
,facts
)) match_count
++;
209 memorize_not_on_beta(n
,match_count
,facts
);
210 if (match_count
== 0) insert_beta(node
.child
,facts
);
212 ////////////////////////////////////////////////////////////////////
213 // Terminal node: when we get here we call activate(...)
214 // to add the token into the conflict set.
215 ////////////////////////////////////////////////////////////////////
216 case Node::Bot
: activate(node
.child
,node
.arity
,facts
); break;
221 //////////////////////////////////////////////////////////////////////////
222 // Insert a partially constructed token into a node from the alpha side
223 //////////////////////////////////////////////////////////////////////////
224 void ReteNet::insert_alpha(NodeId n
, Fact
* fact
)
225 { register const Node
& node
= network
[n
];
230 memorize_alpha(n
,fact
);
231 insert_alpha(node
.child
, fact
);
233 ////////////////////////////////////////////////////////////////////
235 // Concatenate the new fact with every beta input memorized;
236 // apply the join on this new token, and propagate the token
237 // if it is satisfied. Also, memorize the new alpha input.
238 ////////////////////////////////////////////////////////////////////
240 { register BetaMemo
& memo
= beta
[n
];
241 for (i
= memo
.count
- 1; i
>= 0; i
--) {
242 Fact
** facts
= memo
.tokens
[i
];
243 facts
[node
.beta_arity
] = fact
;
244 if (node
.join
== 0 || beta_test(node
.join
,facts
))
245 insert_beta(node
.child
,facts
);
247 memorize_alpha(n
,fact
);
249 ////////////////////////////////////////////////////////////////////
251 // Concatenate the new fact with every beta input memorized;
252 // apply the join on this new token, and propagate the token
253 // to be removed if the join is not satisfied when previously
255 // Also, memorize the new alpha input.
256 ////////////////////////////////////////////////////////////////////
258 { register BetaMemo
& memo
= beta
[n
];
259 for (i
= memo
.count
- 1; i
>= 0; i
--) {
260 Fact
** facts
= memo
.tokens
[i
];
261 facts
[node
.beta_arity
] = fact
;
262 if (node
.join
== 0 || beta_test(node
.join
,facts
))
263 if (memo
.matches
[i
]++ == 0) remove_beta(node
.child
,facts
);
265 memorize_alpha(n
,fact
);
267 ////////////////////////////////////////////////////////////////////
269 ////////////////////////////////////////////////////////////////////
273 activate(node
.child
,1,facts
);
279 //////////////////////////////////////////////////////////////////////////
280 // Remove a token from a node from the beta side
281 //////////////////////////////////////////////////////////////////////////
282 void ReteNet::remove_beta(NodeId n
, Fact
* facts
[])
283 { register const Node
& node
= network
[n
];
287 ////////////////////////////////////////////////////////////////////
288 // Testing node: apply the join and if it is satisfied
289 // propagate the token to be removed.
290 ////////////////////////////////////////////////////////////////////
292 remove_beta(node
.child
,facts
); remove_beta(n
+1,facts
); break;
294 if (node
.join
== 0 || beta_test(node
.join
,facts
))
295 remove_beta(node
.child
,facts
);
297 ////////////////////////////////////////////////////////////////////
298 // Conjunctive, Negation node:
299 // Concatenate the new fact with every beta input memorized;
300 // apply the join on this new token, and propagate the token
301 // to be removed if it is satisfied. Also, remove the token
302 // from the beta memory.
303 ////////////////////////////////////////////////////////////////////
306 { register BetaMemo
& l
= beta
[n
];
307 register AlphaMemo
& r
= alpha
[n
];
308 for (i
= l
.count
- 1; i
>= 0; i
--) {
310 for (j
= node
.beta_arity
- 1; j
>= 0; j
--)
311 if (l
.tokens
[i
][j
] != facts
[j
]) goto next
;
312 for (j
= r
.count
- 1; j
>= 0; j
--) {
313 facts
[node
.beta_arity
] = r
.facts
[j
];
314 if (node
.join
== 0 || beta_test(node
.join
,facts
))
315 remove_beta(node
.child
,facts
);
317 l
.tokens
[i
] = l
.tokens
[--l
.count
];
318 l
.matches
[i
] = l
.matches
[l
.count
];
319 mem
.free(l
.tokens
[i
]);
323 case Node::Bot
: deactivate(node
.child
,node
.arity
,facts
); break;
328 //////////////////////////////////////////////////////////////////////////
329 // Remove a token from a node from the alpha side
330 //////////////////////////////////////////////////////////////////////////
331 void ReteNet::remove_alpha(NodeId n
, Fact
* fact
)
332 { register const Node
& node
= network
[n
];
337 { register AlphaMemo
& r
= alpha
[n
];
338 for (i
= r
.count
- 1; i
>= 0; i
--) {
339 if (r
.facts
[i
] == fact
) {
340 remove_alpha(node
.child
, fact
);
341 mem
.free(r
.facts
[i
]);
342 r
.facts
[i
] = r
.facts
[--r
.count
];
347 ////////////////////////////////////////////////////////////////////
349 // Concatenate the new fact with every alpha input memorized;
350 // apply the join on this new token, and propagate the token
351 // to be removed if it is satisfied. Also, remove the token
352 // from the alpha memory.
353 ////////////////////////////////////////////////////////////////////
355 { register AlphaMemo
& r
= alpha
[n
];
356 register BetaMemo
& l
= beta
[n
];
357 for (i
= r
.count
- 1; i
>= 0; i
--) {
358 if (r
.facts
[i
] == fact
) {
359 for (int j
= l
.count
- 1; j
>= 0; j
--) {
360 Fact
** facts
= l
.tokens
[j
];
361 facts
[node
.beta_arity
] = fact
;
362 if (node
.join
== 0 || beta_test(node
.join
,facts
))
363 remove_beta(node
.child
,facts
);
365 mem
.free(r
.facts
[i
]);
366 r
.facts
[i
] = r
.facts
[--r
.count
];
370 ////////////////////////////////////////////////////////////////////
372 // Concatenate the new fact with every beta input memorized;
373 // apply the join on this new token, and propagate the token
374 // to be removed if it is satisfied. Also, remove the token
375 // from the alpha memory.
376 ////////////////////////////////////////////////////////////////////
378 { register AlphaMemo
& r
= alpha
[n
];
379 /////////////////////////////////////////////////////////////////
380 // Search for the given fact from the alpha side. If it is found,
381 // we'll run the join with the beta side.
382 /////////////////////////////////////////////////////////////////
383 for (i
= r
.count
- 1; i
>= 0; i
--) {
384 if (r
.facts
[i
] == fact
) {
385 register BetaMemo
& l
= beta
[n
];
386 for (int j
= l
.count
- 1; j
>= 0; j
--) {
387 Fact
** facts
= l
.tokens
[j
];
388 facts
[node
.beta_arity
] = fact
;
389 ///////////////////////////////////////////////////////////
390 // If the join is good, we'll decrement the matching count.
391 // When this count reaches 0, the beta token is propagated.
392 ///////////////////////////////////////////////////////////
393 if (node
.join
== 0 || beta_test(node
.join
,facts
)) {
394 if (--l
.matches
[j
] == 0) {
395 insert_beta(node
.child
,facts
);
397 l
.tokens
[j
] = l
.tokens
[--l
.count
];
398 l
.matches
[j
] = l
.matches
[l
.count
];
402 r
.facts
[i
] = r
.facts
[--r
.count
];