1 | /**************************************************************************
|
---|
2 | *
|
---|
3 | * lstevent.c -- Routines to implement "events" using MTF lists.
|
---|
4 | * Copyright (C) 1987 Alistair Moffat
|
---|
5 | *
|
---|
6 | * This program is free software; you can redistribute it and/or modify
|
---|
7 | * it under the terms of the GNU General Public License as published by
|
---|
8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
9 | * (at your option) any later version.
|
---|
10 | *
|
---|
11 | * This program is distributed in the hope that it will be useful,
|
---|
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | * GNU General Public License for more details.
|
---|
15 | *
|
---|
16 | * You should have received a copy of the GNU General Public License
|
---|
17 | * along with this program; if not, write to the Free Software
|
---|
18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
19 | *
|
---|
20 | * $Id: lstevent.c 3745 2003-02-20 21:20:24Z mdewsnip $
|
---|
21 | *
|
---|
22 | **************************************************************************/
|
---|
23 |
|
---|
24 | #include "sysfuncs.h"
|
---|
25 |
|
---|
26 | #include "arithcode.h"
|
---|
27 | #include "model.h"
|
---|
28 |
|
---|
29 | /*
|
---|
30 | $Log$
|
---|
31 | Revision 1.1 2003/02/20 21:16:56 mdewsnip
|
---|
32 | Addition of MG package for search and retrieval
|
---|
33 |
|
---|
34 | Revision 1.1 1999/08/10 21:17:26 sjboddie
|
---|
35 | renamed mg-1.3d directory mg
|
---|
36 |
|
---|
37 | Revision 1.1 1998/11/17 09:33:37 rjmcnab
|
---|
38 | *** empty log message ***
|
---|
39 |
|
---|
40 | * Revision 1.2 1994/09/20 04:41:40 tes
|
---|
41 | * For version 1.1
|
---|
42 | *
|
---|
43 | */
|
---|
44 |
|
---|
45 | static char *RCSID = "$Id: lstevent.c 3745 2003-02-20 21:20:24Z mdewsnip $";
|
---|
46 |
|
---|
47 | void
|
---|
48 | write_method ()
|
---|
49 | {
|
---|
50 | fprintf (stderr, "C");
|
---|
51 | }
|
---|
52 |
|
---|
53 |
|
---|
54 | /*===========================================*/
|
---|
55 |
|
---|
56 | /*
|
---|
57 | * [Rodney Brown - Sep/95]
|
---|
58 | * On IBM RS/6000 AIX version 3.2 the compiler defines NULL as (void *)0
|
---|
59 | * when in ANSI mode. Hence the (event) and (point) casts
|
---|
60 | */
|
---|
61 |
|
---|
62 |
|
---|
63 | #define GETNEWNODE(e,node) \
|
---|
64 | do \
|
---|
65 | { node = p32(numnodes) ; \
|
---|
66 | node->eventnum = (event)e ; \
|
---|
67 | node->count = increment ; \
|
---|
68 | node->foll.totalcnt = 0 ; \
|
---|
69 | node->foll.notfound = 0 ; \
|
---|
70 | node->foll.list = (point)NULL ; \
|
---|
71 | numnodes += 1 ; \
|
---|
72 | nfreenodes -= 1 ; \
|
---|
73 | } \
|
---|
74 | while (false)
|
---|
75 |
|
---|
76 | /*===========================================*/
|
---|
77 |
|
---|
78 | #define INSERTNODE(U,node) \
|
---|
79 | do \
|
---|
80 | { node->next = U->list ; \
|
---|
81 | U->list = p16(node) ; \
|
---|
82 | U->totalcnt += increment; \
|
---|
83 | } \
|
---|
84 | while (false)
|
---|
85 |
|
---|
86 | /*===========================================*/
|
---|
87 |
|
---|
88 | int
|
---|
89 | halvelist (p)
|
---|
90 | register eventnode *p;
|
---|
91 | {
|
---|
92 | register int sum = 0;
|
---|
93 | while (p != ENULL)
|
---|
94 | {
|
---|
95 | sum += p->count = (p->count + 1) / 2;
|
---|
96 | p = p32 (p->next);
|
---|
97 | }
|
---|
98 | return (sum);
|
---|
99 | }
|
---|
100 |
|
---|
101 | /*===========================================*/
|
---|
102 |
|
---|
103 | void
|
---|
104 | halveallcounts (U)
|
---|
105 | register eventset *U;
|
---|
106 | {
|
---|
107 | U->notfound = (U->notfound + 1) / 2;
|
---|
108 | U->totalcnt = U->notfound;
|
---|
109 | U->totalcnt += halvelist (p32 (U->list));
|
---|
110 | }
|
---|
111 |
|
---|
112 | /*===========================================*/
|
---|
113 |
|
---|
114 | eventnode *
|
---|
115 | encode_event_noex (U, e, success)
|
---|
116 | register eventset *U;
|
---|
117 | event e;
|
---|
118 | boolean *success;
|
---|
119 | {
|
---|
120 | register eventnode *pnode, *node;
|
---|
121 | register int lbnd, totl;
|
---|
122 |
|
---|
123 | if (U->list == (point)NULL)
|
---|
124 | {
|
---|
125 | *success = false;
|
---|
126 | U->notfound += increment;
|
---|
127 | U->totalcnt += increment;
|
---|
128 | GETNEWNODE (e, node);
|
---|
129 | INSERTNODE (U, node);
|
---|
130 | return (node);
|
---|
131 | }
|
---|
132 |
|
---|
133 | lbnd = 0;
|
---|
134 | pnode = ENULL;
|
---|
135 | node = p32 (U->list);
|
---|
136 | while (node != ENULL)
|
---|
137 | {
|
---|
138 | if (e == node->eventnum)
|
---|
139 | break;
|
---|
140 | lbnd += node->count;
|
---|
141 | pnode = node;
|
---|
142 | node = p32 (node->next);
|
---|
143 | }
|
---|
144 |
|
---|
145 | totl = U->totalcnt;
|
---|
146 |
|
---|
147 | if (node == ENULL)
|
---|
148 | { /* event not found in list */
|
---|
149 | if ((totl > U->notfound))
|
---|
150 | arithmetic_encode (totl - U->notfound, totl, totl);
|
---|
151 | U->notfound += increment;
|
---|
152 | U->totalcnt += increment;
|
---|
153 | *success = false;
|
---|
154 | GETNEWNODE (e, node);
|
---|
155 | INSERTNODE (U, node);
|
---|
156 | }
|
---|
157 | else
|
---|
158 | { /* found in the list, so go ahead and code */
|
---|
159 | arithmetic_encode (lbnd, lbnd + node->count, totl);
|
---|
160 | node->count += increment;
|
---|
161 | U->totalcnt += increment;
|
---|
162 | *success = true;
|
---|
163 | /* and move to front */
|
---|
164 | if (pnode != ENULL)
|
---|
165 | {
|
---|
166 | pnode->next = node->next;
|
---|
167 | node->next = U->list;
|
---|
168 | U->list = p16 (node);
|
---|
169 | }
|
---|
170 | }
|
---|
171 | if (U->totalcnt > maxtotalcnt)
|
---|
172 | halveallcounts (U);
|
---|
173 | return (node);
|
---|
174 | }
|
---|
175 |
|
---|
176 | /*===========================================*/
|
---|
177 |
|
---|
178 | eventnode *
|
---|
179 | decode_event_noex (U, success, e)
|
---|
180 | register eventset *U;
|
---|
181 | boolean *success;
|
---|
182 | event *e;
|
---|
183 | {
|
---|
184 | register eventnode *node, *pnode;
|
---|
185 | register int tget, lbnd, totl;
|
---|
186 |
|
---|
187 | if (U->list == (point)NULL)
|
---|
188 | {
|
---|
189 | *success = false;
|
---|
190 | U->totalcnt += increment;
|
---|
191 | U->notfound += increment;
|
---|
192 | GETNEWNODE (NULL, node);
|
---|
193 | INSERTNODE (U, node);
|
---|
194 | return (node);
|
---|
195 | }
|
---|
196 | totl = U->totalcnt;
|
---|
197 | tget = arithmetic_decode_target (totl);
|
---|
198 |
|
---|
199 | if (tget >= totl - U->notfound)
|
---|
200 | {
|
---|
201 | if (totl > U->notfound)
|
---|
202 | arithmetic_decode (totl - U->notfound, totl, totl);
|
---|
203 | U->totalcnt += increment;
|
---|
204 | U->notfound += increment;
|
---|
205 | *success = false;
|
---|
206 | GETNEWNODE (NULL, node);
|
---|
207 | INSERTNODE (U, node);
|
---|
208 | }
|
---|
209 | else
|
---|
210 | {
|
---|
211 | pnode = ENULL;
|
---|
212 | node = p32 (U->list);
|
---|
213 | lbnd = 0;
|
---|
214 | for (;;)
|
---|
215 | {
|
---|
216 | if (tget < (lbnd += node->count))
|
---|
217 | break;
|
---|
218 | pnode = node;
|
---|
219 | node = p32 (node->next);
|
---|
220 | }
|
---|
221 |
|
---|
222 | arithmetic_decode (lbnd - node->count, lbnd, totl);
|
---|
223 | node->count += increment;
|
---|
224 | U->totalcnt += increment;
|
---|
225 | *e = node->eventnum;
|
---|
226 | *success = true;
|
---|
227 | /* and move to front */
|
---|
228 | if (pnode != ENULL)
|
---|
229 | {
|
---|
230 | pnode->next = node->next;
|
---|
231 | node->next = U->list;
|
---|
232 | U->list = p16 (node);
|
---|
233 | }
|
---|
234 | }
|
---|
235 | if (U->totalcnt > maxtotalcnt)
|
---|
236 | halveallcounts (U);
|
---|
237 | return (node);
|
---|
238 | }
|
---|
239 |
|
---|
240 | /*===========================================*/
|
---|
241 |
|
---|
242 | eventnode *
|
---|
243 | encode_event (U, e, success)
|
---|
244 | register eventset *U;
|
---|
245 | event e;
|
---|
246 | boolean *success;
|
---|
247 | {
|
---|
248 | register eventnode *pnode, *node, *p;
|
---|
249 | register int lbnd, totl;
|
---|
250 |
|
---|
251 | if (U->list == (point)NULL)
|
---|
252 | {
|
---|
253 | *success = false;
|
---|
254 | U->notfound += increment;
|
---|
255 | U->totalcnt += increment;
|
---|
256 | GETNEWNODE (e, node);
|
---|
257 | INSERTNODE (U, node);
|
---|
258 | return (node);
|
---|
259 | }
|
---|
260 |
|
---|
261 | lbnd = 0;
|
---|
262 | pnode = ENULL;
|
---|
263 | node = p32 (U->list);
|
---|
264 | while (node != ENULL)
|
---|
265 | {
|
---|
266 | if (!excluded[node->eventnum])
|
---|
267 | {
|
---|
268 | if (e == node->eventnum)
|
---|
269 | break;
|
---|
270 | lbnd += node->count;
|
---|
271 | }
|
---|
272 | pnode = node;
|
---|
273 | node = p32 (node->next);
|
---|
274 | }
|
---|
275 |
|
---|
276 | if (node == ENULL)
|
---|
277 | { /* event not found in list, and whole list has been scanned */
|
---|
278 | totl = lbnd + U->notfound;
|
---|
279 | if ((totl > U->notfound))
|
---|
280 | arithmetic_encode (totl - U->notfound, totl, totl);
|
---|
281 | U->notfound += increment;
|
---|
282 | U->totalcnt += increment;
|
---|
283 | *success = false;
|
---|
284 | GETNEWNODE (e, node);
|
---|
285 | INSERTNODE (U, node);
|
---|
286 | }
|
---|
287 | else
|
---|
288 | { /* found in the list, so go ahead and code */
|
---|
289 | /* first, total up rest of list */
|
---|
290 | totl = lbnd + node->count;
|
---|
291 | p = p32 (node->next);
|
---|
292 | while (p != ENULL)
|
---|
293 | {
|
---|
294 | if (!excluded[p->eventnum])
|
---|
295 | totl += p->count;
|
---|
296 | p = p32 (p->next);
|
---|
297 | }
|
---|
298 | totl += U->notfound;
|
---|
299 |
|
---|
300 | arithmetic_encode (lbnd, lbnd + node->count, totl);
|
---|
301 | node->count += increment;
|
---|
302 | U->totalcnt += increment;
|
---|
303 | *success = true;
|
---|
304 | /* and move to front */
|
---|
305 | if (pnode != ENULL)
|
---|
306 | {
|
---|
307 | pnode->next = node->next;
|
---|
308 | node->next = U->list;
|
---|
309 | U->list = p16 (node);
|
---|
310 | }
|
---|
311 | }
|
---|
312 | if (U->totalcnt > maxtotalcnt)
|
---|
313 | halveallcounts (U);
|
---|
314 | return (node);
|
---|
315 | }
|
---|
316 |
|
---|
317 | /*===========================================*/
|
---|
318 |
|
---|
319 | eventnode *
|
---|
320 | decode_event (U, success, e)
|
---|
321 | register eventset *U;
|
---|
322 | boolean *success;
|
---|
323 | event *e;
|
---|
324 | {
|
---|
325 | register eventnode *node, *pnode;
|
---|
326 | register int tget, lbnd, totl;
|
---|
327 |
|
---|
328 | if (U->list == (point)NULL)
|
---|
329 | {
|
---|
330 | *success = false;
|
---|
331 | U->totalcnt += increment;
|
---|
332 | U->notfound += increment;
|
---|
333 | GETNEWNODE (NULL, node);
|
---|
334 | INSERTNODE (U, node);
|
---|
335 | return (node);
|
---|
336 | }
|
---|
337 | totl = 0;
|
---|
338 | node = p32 (U->list);
|
---|
339 | while (node != ENULL)
|
---|
340 | {
|
---|
341 | if (!excluded[node->eventnum])
|
---|
342 | totl += node->count;
|
---|
343 | node = p32 (node->next);
|
---|
344 | }
|
---|
345 | totl += U->notfound;
|
---|
346 | tget = arithmetic_decode_target (totl);
|
---|
347 |
|
---|
348 | if (tget >= totl - U->notfound)
|
---|
349 | {
|
---|
350 | if (totl > U->notfound)
|
---|
351 | arithmetic_decode (totl - U->notfound, totl, totl);
|
---|
352 | U->totalcnt += increment;
|
---|
353 | U->notfound += increment;
|
---|
354 | *success = false;
|
---|
355 | GETNEWNODE (NULL, node);
|
---|
356 | INSERTNODE (U, node);
|
---|
357 | }
|
---|
358 | else
|
---|
359 | {
|
---|
360 | pnode = ENULL;
|
---|
361 | node = p32 (U->list);
|
---|
362 | lbnd = 0;
|
---|
363 | for (;;)
|
---|
364 | {
|
---|
365 | if (!excluded[node->eventnum])
|
---|
366 | {
|
---|
367 | lbnd += node->count;
|
---|
368 | if (tget < lbnd)
|
---|
369 | break;
|
---|
370 | }
|
---|
371 | pnode = node;
|
---|
372 | node = p32 (node->next);
|
---|
373 | }
|
---|
374 |
|
---|
375 | arithmetic_decode (lbnd - node->count, lbnd, totl);
|
---|
376 | node->count += increment;
|
---|
377 | U->totalcnt += increment;
|
---|
378 | *e = node->eventnum;
|
---|
379 | *success = true;
|
---|
380 | /* and move to front */
|
---|
381 | if (pnode != ENULL)
|
---|
382 | {
|
---|
383 | pnode->next = node->next;
|
---|
384 | node->next = U->list;
|
---|
385 | U->list = p16 (node);
|
---|
386 | }
|
---|
387 | }
|
---|
388 | if (U->totalcnt > maxtotalcnt)
|
---|
389 | halveallcounts (U);
|
---|
390 | return (node);
|
---|
391 | }
|
---|
392 |
|
---|
393 | /*===========================================*/
|
---|
394 |
|
---|
395 | eventnode *
|
---|
396 | newnode (e)
|
---|
397 | event e;
|
---|
398 | {
|
---|
399 | register eventnode *node;
|
---|
400 | GETNEWNODE (e, node);
|
---|
401 | node->next = (point)NULL;
|
---|
402 | node->prev = (point)NULL;
|
---|
403 | return (node);
|
---|
404 | }
|
---|
405 |
|
---|
406 | /*===========================================*/
|
---|
407 |
|
---|
408 | /* not required in this version */
|
---|
409 |
|
---|
410 | #if 0
|
---|
411 | eventnode *
|
---|
412 | addevent (U, e)
|
---|
413 | register eventset *U;
|
---|
414 | event e;
|
---|
415 | {
|
---|
416 | register eventnode *node;
|
---|
417 | /* get an event node */
|
---|
418 | GETNEWNODE (e, node);
|
---|
419 | INSERTNODE (U, node);
|
---|
420 | if (U->totalcnt > maxtotalcnt)
|
---|
421 | halveallcounts (U);
|
---|
422 | return (node);
|
---|
423 | }
|
---|
424 | #endif
|
---|