Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | \ ========== Copyright Header Begin ========================================== |
2 | \ | |
3 | \ Hypervisor Software File: queue.fth | |
4 | \ | |
5 | \ Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
6 | \ | |
7 | \ - Do no alter or remove copyright notices | |
8 | \ | |
9 | \ - Redistribution and use of this software in source and binary forms, with | |
10 | \ or without modification, are permitted provided that the following | |
11 | \ conditions are met: | |
12 | \ | |
13 | \ - Redistribution of source code must retain the above copyright notice, | |
14 | \ this list of conditions and the following disclaimer. | |
15 | \ | |
16 | \ - Redistribution in binary form must reproduce the above copyright notice, | |
17 | \ this list of conditions and the following disclaimer in the | |
18 | \ documentation and/or other materials provided with the distribution. | |
19 | \ | |
20 | \ Neither the name of Sun Microsystems, Inc. or the names of contributors | |
21 | \ may be used to endorse or promote products derived from this software | |
22 | \ without specific prior written permission. | |
23 | \ | |
24 | \ This software is provided "AS IS," without a warranty of any kind. | |
25 | \ ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, | |
26 | \ INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A | |
27 | \ PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN | |
28 | \ MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR | |
29 | \ ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR | |
30 | \ DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN | |
31 | \ OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR | |
32 | \ FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE | |
33 | \ DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, | |
34 | \ ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF | |
35 | \ SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. | |
36 | \ | |
37 | \ You acknowledge that this software is not designed, licensed or | |
38 | \ intended for use in the design, construction, operation or maintenance of | |
39 | \ any nuclear facility. | |
40 | \ | |
41 | \ ========== Copyright Header End ============================================ | |
42 | id: @(#)queue.fth 1.1 04/09/07 | |
43 | purpose: Generic queue utility functions | |
44 | copyright: Copyright 2004 Sun Microsystems, Inc. All Rights Reserved | |
45 | copyright: Use is subject to license terms. | |
46 | ||
47 | \ Generic doubly-linked list (queue) implementation. Supports a queue | |
48 | \ of abstract objects. The queue is maintained within that object. | |
49 | ||
50 | headerless | |
51 | ||
52 | struct | |
53 | /n field >q-next \ Next entry in queue | |
54 | /n field >q-prev \ Previous entry in queue | |
55 | constant /queue-entry | |
56 | ||
57 | /queue-entry constant /queue-head | |
58 | ||
59 | \ Initialize a queue | |
60 | : queue-init ( qhead -- ) dup 2dup >q-next ! >q-prev ! ; | |
61 | ||
62 | \ Get to next entry in queue | |
63 | : queue-next ( qentry -- next ) >q-next @ ; | |
64 | ||
65 | \ Get to previous entry in queue | |
66 | : queue-prev ( qentry -- prev ) >q-prev @ ; | |
67 | ||
68 | \ First entry in queue | |
69 | : queue-first ( qhead -- qentry ) queue-next ; | |
70 | ||
71 | \ Last entry in queue | |
72 | : queue-last ( qhead -- qentry ) queue-prev ; | |
73 | ||
74 | \ Check if we are at the end of the queue | |
75 | : queue-end? ( qhead qentry -- flag ) = ; | |
76 | ||
77 | \ Is the queue empty? | |
78 | : queue-empty? ( qhead -- flag ) dup queue-first queue-end? ; | |
79 | ||
80 | \ Get number of entries in the queue | |
81 | : queue-size ( qhead -- qsize ) | |
82 | 0 swap queue-first ( 0 qhead qentry ) | |
83 | begin 2dup queue-end? 0= while ( n qhead qentry ) | |
84 | rot 1+ -rot queue-next ( n' qhead qentry ) | |
85 | repeat 2drop ( qsize ) | |
86 | ; | |
87 | ||
88 | \ Insert entry after element "pred". | |
89 | : insqueue ( pred qentry -- ) | |
90 | over queue-next over >q-next ! \ qentry.next = pred.next | |
91 | 2dup >q-prev ! \ qentry.prev = pred | |
92 | 2dup swap queue-next >q-prev ! \ pred.next.prev = qentry | |
93 | swap >q-next ! \ pred.next = qentry | |
94 | ; | |
95 | ||
96 | \ Remove entry from queue | |
97 | : remqueue ( qentry -- ) | |
98 | dup queue-prev over queue-next >q-prev ! | |
99 | dup queue-next swap queue-prev >q-next ! | |
100 | ; | |
101 | ||
102 | \ Insert element at tail of queue | |
103 | : enqueue ( qhead qentry -- ) | |
104 | swap queue-last swap insqueue | |
105 | ; | |
106 | ||
107 | \ Dequeue element at head of queue | |
108 | : dequeue ( qhead -- qentry | 0 ) | |
109 | dup queue-empty? if drop 0 else queue-first dup remqueue then | |
110 | ; | |
111 | ||
112 | \ Iterate over each item in the queue, performing the desired operation. | |
113 | : queue-iterate ( qhead acf -- ) | |
114 | >r dup queue-first ( qhead qentry ) ( r: acf ) | |
115 | begin 2dup queue-end? 0= while ( qhead qentry ) | |
116 | dup r@ execute queue-next ( qhead qentry' ) | |
117 | repeat ( qhead qentry' ) | |
118 | r> 3drop ( ) ( r: ) | |
119 | ; | |
120 | ||
121 | \ Find a queue entry which matches the specified criteria. "acf" | |
122 | \ is executed on each queue entry to determine a match. The match | |
123 | \ routine must have a stack diagram of the form | |
124 | \ ( ... qentry -- ... match? ) | |
125 | \ Stack items under qentry are values used by the "acf" routine to | |
126 | \ determine a match. | |
127 | ||
128 | : find-queue-entry ( ... qhead acf -- ... qentry | ... 0 ) | |
129 | >r ( ... qhead ) ( r: acf ) | |
130 | dup queue-first ( ... qhead qentry ) | |
131 | begin 2dup queue-end? 0= while ( ... qhead qentry ) | |
132 | dup r@ 2swap >r >r execute if ( ... ) ( r: acf qentry qhead ) | |
133 | r> drop r> r> drop exit ( ... qentry ) ( r: ) | |
134 | then ( ... ) ( r: acf qentry qhead ) | |
135 | r> r> queue-next ( ... qhead qnext ) ( r: acf ) | |
136 | repeat ( ... qhead qnext ) | |
137 | 2drop r> drop 0 ( ... 0 ) ( r: ) | |
138 | ; | |
139 | ||
140 | headers |