hadrian: eliminate most of the remaining big rule enumerations
[ghc.git] / rts / RetainerSet.h
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 2001
4 * Author: Sungwoo Park
5 *
6 * Retainer set interface for retainer profiling.
7 *
8 * ---------------------------------------------------------------------------*/
9
10 #pragma once
11
12 #include <stdio.h>
13
14 #if defined(PROFILING)
15
16 #include "BeginPrivate.h"
17
18 /*
19 Type 'retainer' defines the retainer identity.
20
21 Invariant:
22 1. The retainer identity of a given retainer cannot change during
23 program execution, no matter where it is actually stored.
24 For instance, the memory address of a retainer cannot be used as
25 its retainer identity because its location may change during garbage
26 collections.
27 2. Type 'retainer' must come with comparison operations as well as
28 an equality operation. That is, <, >, and == must be supported -
29 this is necessary to store retainers in a sorted order in retainer sets.
30 Therefore, you cannot use a huge structure type as 'retainer', for instance.
31 */
32
33
34 typedef CostCentreStack *retainer;
35
36 /*
37 Type 'retainerSet' defines an abstract datatype for sets of retainers.
38
39 Invariants:
40 A retainer set stores its elements in increasing order (in element[] array).
41 */
42
43 typedef struct _RetainerSet {
44 uint32_t num; // number of elements
45 StgWord hashKey; // hash key for this retainer set
46 struct _RetainerSet *link; // link to the next retainer set in the bucket
47 int id; // unique id of this retainer set (used when printing)
48 // Its absolute value is interpreted as its true id; if id is
49 // negative, it indicates that this retainer set has had a positive
50 // cost after some retainer profiling.
51 retainer element[0]; // elements of this retainer set
52 // do not put anything below here!
53 } RetainerSet;
54
55 /*
56 Note:
57 There are two ways of maintaining all retainer sets. The first is simply by
58 freeing all the retainer sets and re-initialize the hash table at each
59 retainer profiling. The second is by setting the cost field of each
60 retainer set. The second is preferred to the first if most retainer sets
61 are likely to be observed again during the next retainer profiling. Note
62 that in the first approach, we do not free the memory allocated for
63 retainer sets; we just invalidate all retainer sets.
64 */
65 #if defined(DEBUG_RETAINER)
66 // In thise case, FIRST_APPROACH must be turned on because the memory pool
67 // for retainer sets is freed each time.
68 #define FIRST_APPROACH
69 #else
70 // #define FIRST_APPROACH
71 #define SECOND_APPROACH
72 #endif
73
74 // Creates the first pool and initializes a hash table. Frees all pools if any.
75 void initializeAllRetainerSet(void);
76
77 // Refreshes all pools for reuse and initializes a hash table.
78 void refreshAllRetainerSet(void);
79
80 // Frees all pools.
81 void closeAllRetainerSet(void);
82
83 // Finds or creates if needed a singleton retainer set.
84 RetainerSet *singleton(retainer r);
85
86 extern RetainerSet rs_MANY;
87
88 // Checks if a given retainer is a member of the retainer set.
89 //
90 // Note & (maybe) Todo:
91 // This function needs to be declared as an inline function, so it is declared
92 // as an inline static function here.
93 // This make the interface really bad, but isMember() returns a value, so
94 // it is not easy either to write it as a macro (due to my lack of C
95 // programming experience). Sungwoo
96 //
97 // bool isMember(retainer, retainerSet *);
98 /*
99 Returns true if r is a member of *rs.
100 Invariants:
101 rs is not NULL.
102 Note:
103 The efficiency of this function is subject to the typical size of
104 retainer sets. If it is small, linear scan is better. If it
105 is large in most cases, binary scan is better.
106 The current implementation mixes the two search strategies.
107 */
108
109 #define BINARY_SEARCH_THRESHOLD 8
110 INLINE_HEADER bool
111 isMember(retainer r, RetainerSet *rs)
112 {
113 int i, left, right; // must be int, not uint32_t (because -1 can appear)
114 retainer ri;
115
116 if (rs == &rs_MANY) { return true; }
117
118 if (rs->num < BINARY_SEARCH_THRESHOLD) {
119 for (i = 0; i < (int)rs->num; i++) {
120 ri = rs->element[i];
121 if (r == ri) return true;
122 else if (r < ri) return false;
123 }
124 } else {
125 left = 0;
126 right = rs->num - 1;
127 while (left <= right) {
128 i = (left + right) / 2;
129 ri = rs->element[i];
130 if (r == ri) return true;
131 else if (r < ri) right = i - 1;
132 else left = i + 1;
133 }
134 }
135 return false;
136 }
137
138 // Finds or creates a retainer set augmented with a new retainer.
139 RetainerSet *addElement(retainer, RetainerSet *);
140
141 #if defined(SECOND_APPROACH)
142 // Prints a single retainer set.
143 void printRetainerSetShort(FILE *, RetainerSet *, uint32_t);
144 #endif
145
146 // Print the statistics on all the retainer sets.
147 // store the sum of all costs and the number of all retainer sets.
148 void outputRetainerSet(FILE *, uint32_t *, uint32_t *);
149
150 #if defined(SECOND_APPROACH)
151 // Print all retainer sets at the exit of the program.
152 void outputAllRetainerSet(FILE *);
153 #endif
154
155 // Hashing functions
156 /*
157 Invariants:
158 Once either initializeAllRetainerSet() or refreshAllRetainerSet()
159 is called, there exists only one copy of any retainer set created
160 through singleton() and addElement(). The pool (the storage for
161 retainer sets) is consumed linearly. All the retainer sets of the
162 same hash function value are linked together from an element in
163 hashTable[]. See the invariants of allocateInPool() for the
164 maximum size of retainer sets. The hashing function is defined by
165 hashKeySingleton() and hashKeyAddElement(). The hash key for a set
166 must be unique regardless of the order its elements are inserted,
167 i.e., the hashing function must be additive(?).
168 */
169 #define hashKeySingleton(r) ((StgWord)(r))
170 #define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey)
171
172 #include "EndPrivate.h"
173
174 #endif /* PROFILING */