1 /* -----------------------------------------------------------------------------
2 * $Id: RetainerSet.h,v 1.1 2001/11/22 14:25:12 simonmar Exp $
4 * (c) The GHC Team, 2001
7 * Retainer set interface for retainer profiling.
9 * ---------------------------------------------------------------------------*/
15 There are two ways of maintaining all retainer sets. The first is simply by
16 freeing all the retainer sets and re-initialize the hash table at each
17 retainer profiling. The second is by setting the cost field of each
18 retainer set. The second is preferred to the first if most retainer sets
19 are likely to be observed again during the next retainer profiling. Note
20 that in the first approach, we do not free the memory allocated for
21 retainer sets; we just invalidate all retainer sets.
24 // In thise case, FIRST_APPROACH must be turned on because the memory pool
25 // for retainer sets is freed each time.
26 #define FIRST_APPROACH
28 // #define FIRST_APPROACH
29 #define SECOND_APPROACH
32 // Creates the first pool and initializes a hash table. Frees all pools if any.
33 void initializeAllRetainerSet(void);
35 // Refreshes all pools for reuse and initializes a hash table.
36 void refreshAllRetainerSet(void);
39 void closeAllRetainerSet(void);
41 // Finds or creates if needed a singleton retainer set.
42 RetainerSet *singleton(retainer r);
44 extern RetainerSet rs_MANY;
46 // Checks if a given retainer is a memeber of the retainer set.
48 // Note & (maybe) Todo:
49 // This function needs to be declared as an inline function, so it is declared
50 // as an inline static function here.
51 // This make the interface really bad, but isMember() returns a value, so
52 // it is not easy either to write it as a macro (due to my lack of C
53 // programming experience). Sungwoo
55 // rtsBool isMember(retainer, retainerSet *);
57 Returns rtsTrue if r is a member of *rs.
61 The efficiency of this function is subject to the typical size of
62 retainer sets. If it is small, linear scan is better. If it
63 is large in most cases, binary scan is better.
64 The current implementation mixes the two search strategies.
67 #define BINARY_SEARCH_THRESHOLD 8
69 isMember(retainer r, RetainerSet *rs)
71 int i, left, right; // must be int, not nat (because -1 can appear)
74 if (rs == &rs_MANY) { return rtsTrue; }
76 if (rs->num < BINARY_SEARCH_THRESHOLD) {
77 for (i = 0; i < (int)rs->num; i++) {
79 if (r == ri) return rtsTrue;
80 else if (r < ri) return rtsFalse;
85 while (left <= right) {
86 i = (left + right) / 2;
88 if (r == ri) return rtsTrue;
89 else if (r < ri) right = i - 1;
96 // Finds or creates a retainer set augmented with a new retainer.
97 RetainerSet *addElement(retainer, RetainerSet *);
99 // Call f() for each retainer set.
100 void traverseAllRetainerSet(void (*f)(RetainerSet *));
102 #ifdef SECOND_APPROACH
103 // Prints a single retainer set.
104 void printRetainerSetShort(FILE *, RetainerSet *);
107 // Print the statistics on all the retainer sets.
108 // store the sum of all costs and the number of all retainer sets.
109 void outputRetainerSet(FILE *, nat *, nat *);
111 #ifdef SECOND_APPROACH
112 // Print all retainer sets at the exit of the program.
113 void outputAllRetainerSet(FILE *);
119 Once either initializeAllRetainerSet() or refreshAllRetainerSet()
120 is called, there exists only one copy of any retainer set created
121 through singleton() and addElement(). The pool (the storage for
122 retainer sets) is consumed linearly. All the retainer sets of the
123 same hash function value are linked together from an element in
124 hashTable[]. See the invariants of allocateInPool() for the
125 maximum size of retainer sets. The hashing function is defined by
126 hashKeySingleton() and hashKeyAddElement(). The hash key for a set
127 must be unique regardless of the order its elements are inserted,
128 i.e., the hashing function must be additive(?).
130 #define hashKeySingleton(r) ((StgWord)(r))
131 #define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey)
133 // Prints the full information on a given retainer.
134 // Note: This function is not part of retainerSet interface, but this is
135 // the best place to define it.
136 void printRetainer(FILE *, retainer);
138 #endif /* PROFILING */