Debian Codegraph @

gcc/m2/gm2-libs-iso/RTentity.mod

raw
1 (* RTentity.mod implements a grouping of different opaque types.
2
3 Copyright (C) 2008-2025 Free Software Foundation, Inc.
4 Contributed by Gaius Mulley <[email protected]>.
5
6 This file is part of GNU Modula-2.
7
8 GNU Modula-2 is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GNU Modula-2 is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
17
18 Under Section 7 of GPL version 3, you are granted additional
19 permissions described in the GCC Runtime Library Exception, version
20 3.1, as published by the Free Software Foundation.
21
22 You should have received a copy of the GNU General Public License and
23 a copy of the GCC Runtime Library Exception along with this program;
24 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 <http://www.gnu.org/licenses/>. *)
26
27 IMPLEMENTATION MODULE RTentity ;
28
29 FROM libc IMPORT malloc, free ;
30 FROM M2RTS IMPORT Halt ;
31 FROM RTco IMPORT init, initSemaphore, wait, signal ;
32
33 TYPE
34 Group = POINTER TO RECORD
35 left, right: Group ;
36 entity : SYSTEM.ADDRESS ;
37 entityKey : CARDINAL ;
38 END ;
39
40
41 PROCEDURE InitGroup () : Group ;
42 VAR
43 g: Group ;
44 BEGIN
45 checkInitialized ;
46 wait (mutex) ;
47 g := malloc (SIZE (g^)) ;
48 WITH g^ DO
49 left := NIL ;
50 right := NIL ;
51 entity := NIL ;
52 entityKey := 0
53 END ;
54 signal (mutex) ;
55 RETURN g
56 END InitGroup ;
57
58
59 (*
60 killGroup -
61 *)
62
63 PROCEDURE killGroup (g: Group) : Group ;
64 BEGIN
65 IF g # NIL
66 THEN
67 WITH g^ DO
68 left := killGroup (left) ;
69 right := killGroup (right)
70 END ;
71 free (g)
72 END ;
73 RETURN NIL
74 END killGroup ;
75
76
77
78 PROCEDURE KillGroup (g: Group) : Group ;
79 BEGIN
80 wait (mutex) ;
81 g := killGroup (g) ;
82 signal (mutex) ;
83 RETURN g
84 END KillGroup ;
85
86
87 PROCEDURE GetKey (g: Group; a: SYSTEM.ADDRESS) : CARDINAL ;
88 VAR
89 parent,
90 child : Group ;
91 BEGIN
92 assert (initialized) ;
93 wait (mutex) ;
94 findChildAndParent (g, a, child, parent) ;
95 signal (mutex) ;
96 IF child = NIL
97 THEN
98 RETURN 0
99 ELSE
100 RETURN child^.entityKey
101 END
102 END GetKey ;
103
104
105 PROCEDURE PutKey (g: Group; a: SYSTEM.ADDRESS; key: CARDINAL) ;
106 VAR
107 parent,
108 child : Group ;
109 BEGIN
110 assert (initialized) ;
111 wait (mutex) ;
112 findChildAndParent (g, a, child, parent) ;
113 IF child = NIL
114 THEN
115 (* no child found, now is, a, less than parent or greater? *)
116 IF parent = g
117 THEN
118 (* empty tree, add it to the left branch of t *)
119 child := malloc (SIZE (child^)) ;
120 parent^.left := child
121 ELSE
122 (* parent is a leaf node *)
123 IF a < parent^.entity
124 THEN
125 child := malloc (SIZE (child^)) ;
126 parent^.left := child
127 ELSIF a > parent^.entity
128 THEN
129 child := malloc (SIZE (child^)) ;
130 parent^.right := child
131 END
132 END ;
133 WITH child^ DO
134 right := NIL ;
135 left := NIL ;
136 entity := a ;
137 entityKey := key
138 END
139 ELSE
140 Halt ('internal runtime error, entity already stored',
141 __FILE__, __FUNCTION__, __LINE__)
142 END ;
143 signal (mutex)
144 END PutKey ;
145
146
147 PROCEDURE IsIn (g: Group; a: SYSTEM.ADDRESS) : BOOLEAN ;
148 VAR
149 child, parent: Group ;
150 BEGIN
151 assert (initialized) ;
152 wait (mutex) ;
153 findChildAndParent (g, a, child, parent) ;
154 signal (mutex) ;
155 RETURN child # NIL
156 END IsIn ;
157
158
159 (*
160 DelKey - deletes an entry in the binary tree.
161
162 NB in order for this to work we must
163 ensure that the InitGroup sets
164 both left and right to NIL.
165 *)
166
167 PROCEDURE DelKey (g: Group; a: SYSTEM.ADDRESS) ;
168 VAR
169 i, child, parent: Group ;
170 BEGIN
171 assert (initialized) ;
172 wait (mutex) ;
173 (* find parent and child of the node *)
174 findChildAndParent (g, a, child, parent) ;
175 IF (child # NIL) AND (child^.entity = a)
176 THEN
177 (* Have found the node to be deleted *)
178 IF parent^.right = child
179 THEN
180 (* Node is child and this is greater than the parent. *)
181 (* Greater being on the right. *)
182 (* Connect child^.left onto the parent^.right. *)
183 (* Connect child^.right onto the end of the right *)
184 (* most branch of child^.left. *)
185 IF child^.left # NIL
186 THEN
187 (* Scan for right most node of child^.left *)
188 i := child^.left ;
189 WHILE i^.right # NIL DO
190 i := i^.right
191 END ;
192 i^.right := child^.right ;
193 parent^.right := child^.left
194 ELSE
195 (* No child^.left node therefore link over child *)
196 (* (as in a single linked list) to child^.right *)
197 parent^.right := child^.right
198 END ;
199 free (child)
200 ELSE
201 (* assert that parent^.left=child will always be true *)
202 (* Perform exactly the mirror image of the above code *)
203
204 (* Connect child^.right onto the parent^.left. *)
205 (* Connect child^.left onto the end of the left most *)
206 (* branch of child^.right *)
207 IF child^.right # NIL
208 THEN
209 (* Scan for left most node of child^.right *)
210 i := child^.right ;
211 WHILE i^.left # NIL DO
212 i := i^.left
213 END ;
214 i^.left := child^.left ;
215 parent^.left := child^.right
216 ELSE
217 (* No child^.right node therefore link over c *)
218 (* (as in a single linked list) to child^.left. *)
219 parent^.left := child^.left
220 END ;
221 free (child)
222 END
223 ELSE
224 Halt('internal runtime error, trying to delete an entity which is not in the tree',
225 __FILE__, __FUNCTION__, __LINE__)
226 END ;
227 signal (mutex)
228 END DelKey ;
229
230
231 (*
232 findChildAndParent - find a node, child, in a binary tree, t, with name
233 equal to n. If an entry is found, parent is set
234 to the node above child.
235 *)
236
237 PROCEDURE findChildAndParent (t: Group; a: SYSTEM.ADDRESS;
238 VAR child, parent: Group) ;
239 BEGIN
240 (* remember to skip the sentinal value and assign parent and child *)
241 parent := t ;
242 IF t = NIL
243 THEN
244 Halt ('internal runtime error, RTentity is either corrupt or the module storage has not been initialized yet',
245 __FILE__, __FUNCTION__, __LINE__)
246 END ;
247 child := t^.left ;
248 IF child # NIL
249 THEN
250 REPEAT
251 IF a < child^.entity
252 THEN
253 parent := child ;
254 child := child^.left
255 ELSIF a > child^.entity
256 THEN
257 parent := child ;
258 child := child^.right
259 END
260 UNTIL (child = NIL) OR (a = child^.entity)
261 END
262 END findChildAndParent ;
263
264
265 (*
266 assert - simple assertion procedure.
267 *)
268
269 PROCEDURE assert (condition: BOOLEAN) ;
270 BEGIN
271 IF NOT condition
272 THEN
273 Halt ('internal runtime error, RTentity is either corrupt or the module storage has not been initialized yet',
274 __FILE__, __FUNCTION__, __LINE__)
275 END
276 END assert ;
277
278
279 (*
280 checkInitialized -
281 *)
282
283 PROCEDURE checkInitialized ;
284 VAR
285 result: INTEGER ;
286 BEGIN
287 IF NOT initialized
288 THEN
289 initialized := TRUE ;
290 result := init () ;
291 mutex := initSemaphore (1)
292 END
293 END checkInitialized ;
294
295
296 VAR
297 initialized: BOOLEAN ; (* Set to FALSE when the bss is created. *)
298 mutex : INTEGER ;
299
300 END RTentity.