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
|
// Probabilistic reachability set storage -*- c++ -*-
#ifndef HASHGRAPH_H_
# define HASHGRAPH_H_
# ifdef __GNUC__
# pragma interface
# endif // __GNUC__
# include "StateSet.h"
/** @file HashGraph.h
* Transient, probabilistic reachability set storage
*/
/* Copyright 2001-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. */
/** Probabilistic reachability set storage */
class HashGraph : public StateSet
{
public:
/** Constructor */
HashGraph () : StateSet (),
myNumTables (0), myFuncSize (0), myHashSize (0),
myHashers (0), myHashes (0) {}
private:
/** Copy constructor */
HashGraph (const class HashGraph& old);
/** Assignment operator */
class HashGraph& operator= (const class HashGraph& old);
public:
/** Destructor */
~HashGraph ();
/** Initialize the hash tables
* @param numTables number of hash tables
* @param funcSize (in/out) number of elements in the hash functions
* @param hashSize (in/out) number of elements in the hash tables
* @return true if the initialization succeeded
*/
bool init (unsigned numTables,
unsigned& funcSize,
unsigned& hashSize);
private:
/** Add a state to the graph
* @param state the encoded state
* @param size length of the encoded state, in bytes
* @return true if the state was enqueued to mySearch
*/
bool do_add (const void* state,
size_t size);
protected:
/** Get a deflated state from myPathFile
* @param pos file offset to the state
* @param size (output) length of the encoded state
*/
word_t* getState (long pos, size_t* size) const;
public:
/** Fetch an encoded state
* @param tail flag: retrieve from tail of list instead of head
* @param size (output) length of the encoded stream
* @return the encoded state
*/
word_t* pop (bool tail, size_t& size);
private:
/** Fetch a state from a counterexample path
* @param u cursor to the counterexample path
* @return the encoded state, inflated
*/
word_t* getState (class ByteUnpacker& u) const;
/** Number of hash tables */
unsigned myNumTables;
/** Number of elements in the hash function tables (power of 2) */
unsigned myFuncSize;
/** Number of elements in the hash tables (power of 2) */
unsigned myHashSize;
/** The hash functions */
size_t** myHashers;
/** The hash tables */
size_t** myHashes;
};
#endif // HASHGRAPH_H_
|
