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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Hash Management</TITLE>
<META NAME="description" CONTENT="Hash Management">
<META NAME="keywords" CONTENT="tpman">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="tpman.css">
<LINK REL="previous" HREF="node55.html">
<LINK REL="up" HREF="node49.html">
<LINK REL="next" HREF="node57.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html818"
HREF="node57.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html814"
HREF="node49.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html810"
HREF="node55.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html816"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html817"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html819"
HREF="node57.html">Bibliography</A>
<B> Up:</B> <A NAME="tex2html815"
HREF="node49.html">Future</A>
<B> Previous:</B> <A NAME="tex2html811"
HREF="node55.html">Polymorfism</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION000157000000000000000">
Hash Management</A>
</H2>
In addition to the routines described in <A HREF="node17.html#gen-func">2.2</A> the routines
<I>kc_ht_static</I>, <I>kc_ht_dynamic</I>,
<I>kc_ht_inc_level</I>, <I>kc_ht_dec_level</I>, and
<I>kc_ht_free_level</I> have been added as an experiment.
Right now it is unclear whether they are useful or not, or
whether this sort of features should be offered in Kimwitu, or
are better left to the individual programmer.
A compromise might be to supply such routines as a kind of
library in the form of a Kimwitu input (.k) file.
<P>
Controlling the lifetime of unique memory cells by the creation, freeing and
(re-) assignment of hashtables has one disadvantage: the uniqueness of storage
property is no longer guaranteed.
The following alternative does not have this flaw, but may be slower in execution time.
The idea is to treat the hashtable as a stack of life-times, called segments, or memory-levels.
New memory cells will always be created in the memory segment at the top of the stack.
A new segment can be pushed onto the stack, eg. to store intermediate results of a computation.
When the computation is finished, the segment can be popped from the stack;
its memory cells remain alive.
When now the final result of the computation is copied, its memory cells in the popped segment are re-created in the now topmost segment.
Finally, the popped segment can be deleted.
For each hashtable such a stack of segments can be used, and pushing and popping the segments of one hashtable does not
influence the segments of another one.
<P>
In addition to the segments on the stack, there is one `heap' segment, that is meant for memory cells that never will be reclaimed.
In Kimwitu, we call the heap segment `static', and the stack segments `dynamic'.
Kimwitu offers two routines to switch between the use of the `static' segment and the `dynamic' segments.
By default, all unique memory cells are created in the `heap' segments of the hashtables,
ie. by default the `static' segments are used.
<P>
The routines that `manage' the segments (pushing, popping, freeing, switching between `static' (heap) and `dynamic' (stack)), and
the routines that manage the hashtables (creation, assignment, freeing, deletion, reuse) can be freely intermixed, to
use the best of both approaches.
<P>
Below follows a description of the memory level routines.
<P>
<!-- MATH: $\fbox{\sf void kc\_ht\_static( kc\_storageclass\_t sc ); }$ -->
<IMG
WIDTH="281" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img44.gif"
ALT="\fbox{\sf void kc\_ht\_static( kc\_storageclass\_t sc ); }"><A NAME="1452"> </A>
<P>
Allocate everything using the `static' scheme,
until <I>kc_ht_dynamic</I> is called for this storage class. This is the default.
<P>
<!-- MATH: $\fbox{\sf void kc\_ht\_dynamic( kc\_storageclass\_t sc );}$ -->
<IMG
WIDTH="294" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img45.gif"
ALT="\fbox{\sf void kc\_ht\_dynamic( kc\_storageclass\_t sc );}"><A NAME="1453"> </A>
<P>
Allocate everything using the `dynamic' scheme,
until <I>kc_ht_dynamic</I> is called for this storage class, or until the
hashtable is changed (by assignment, deletion, clearing or reuse).
<P>
<!-- MATH: $\fbox{\sf void kc\_ht\_inc\_level( kc\_storageclass\_t sc );}$ -->
<IMG
WIDTH="293" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img46.gif"
ALT="\fbox{\sf void kc\_ht\_inc\_level( kc\_storageclass\_t sc );}"><A NAME="1454"> </A>
<P>
Increment the memory level: everything allocated in
hashtable <I>ht</I> using the `dynamic' scheme will be freed during subsequent
<I>kc_ht_dec_level</I>, <I>kc_ht_free_level</I> calls.
<P>
<!-- MATH: $\fbox{\sf void kc\_ht\_dec\_level( kc\_storageclass\_t sc ); }$ -->
<IMG
WIDTH="302" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img47.gif"
ALT="\fbox{\sf void kc\_ht\_dec\_level( kc\_storageclass\_t sc ); }"><A NAME="1455"> </A>
<P>
Decrements the memory level: everything allocated
using the `dynamic' scheme in the previous, higher, memory level is still
available, but can no longer be found using the hashtable,
ie. copying a node that was created in the previous, higher,
memory level will yield a new copy of that node
(and the initialization code of its phylum will be executed).
<P>
<!-- MATH: $\fbox{\sf void kc\_ht\_free\_level( kc\_storageclass\_t sc ); }$ -->
<IMG
WIDTH="304" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img48.gif"
ALT="\fbox{\sf void kc\_ht\_free\_level( kc\_storageclass\_t sc ); }"><A NAME="1456"> </A>
<P>
Free all nodes/elements allocated during previous, higher, memory levels.
<P>
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html818"
HREF="node57.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html814"
HREF="node49.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html810"
HREF="node55.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html816"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html817"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html819"
HREF="node57.html">Bibliography</A>
<B> Up:</B> <A NAME="tex2html815"
HREF="node49.html">Future</A>
<B> Previous:</B> <A NAME="tex2html811"
HREF="node55.html">Polymorfism</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>
|
