Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | /* |
2 | * Copyright (c) 1992 William F. Jolitz, TeleMuse | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms, with or without | |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * 2. Redistributions in binary form must reproduce the above copyright | |
11 | * notice, this list of conditions and the following disclaimer in the | |
12 | * documentation and/or other materials provided with the distribution. | |
13 | * 3. All advertising materials mentioning features or use of this software | |
14 | * must display the following acknowledgement: | |
15 | * This software is a component of "386BSD" developed by | |
16 | William F. Jolitz, TeleMuse. | |
17 | * 4. Neither the name of the developer nor the name "386BSD" | |
18 | * may be used to endorse or promote products derived from this software | |
19 | * without specific prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS A COMPONENT OF 386BSD DEVELOPED BY WILLIAM F. JOLITZ | |
22 | * AND IS INTENDED FOR RESEARCH AND EDUCATIONAL PURPOSES ONLY. THIS | |
23 | * SOFTWARE SHOULD NOT BE CONSIDERED TO BE A COMMERCIAL PRODUCT. | |
24 | * THE DEVELOPER URGES THAT USERS WHO REQUIRE A COMMERCIAL PRODUCT | |
25 | * NOT MAKE USE THIS WORK. | |
26 | * | |
27 | * FOR USERS WHO WISH TO UNDERSTAND THE 386BSD SYSTEM DEVELOPED | |
28 | * BY WILLIAM F. JOLITZ, WE RECOMMEND THE USER STUDY WRITTEN | |
29 | * REFERENCES SUCH AS THE "PORTING UNIX TO THE 386" SERIES | |
30 | * (BEGINNING JANUARY 1991 "DR. DOBBS JOURNAL", USA AND BEGINNING | |
31 | * JUNE 1991 "UNIX MAGAZIN", GERMANY) BY WILLIAM F. JOLITZ AND | |
32 | * LYNNE GREER JOLITZ, AS WELL AS OTHER BOOKS ON UNIX AND THE | |
33 | * ON-LINE 386BSD USER MANUAL BEFORE USE. A BOOK DISCUSSING THE INTERNALS | |
34 | * OF 386BSD ENTITLED "386BSD FROM THE INSIDE OUT" WILL BE AVAILABLE LATE 1992. | |
35 | * | |
36 | * THIS SOFTWARE IS PROVIDED BY THE DEVELOPER ``AS IS'' AND | |
37 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
38 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
39 | * ARE DISCLAIMED. IN NO EVENT SHALL THE DEVELOPER BE LIABLE | |
40 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
41 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
42 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
43 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
44 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
45 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
46 | * SUCH DAMAGE. | |
47 | * | |
600f7f07 | 48 | * $Id$ |
15637ed4 | 49 | */ |
15637ed4 RG |
50 | |
51 | #include "sys/param.h" | |
52 | #include "sys/cdefs.h" | |
53 | #include "sys/malloc.h" | |
54 | #include "rlist.h" | |
55 | ||
56 | /* | |
57 | * Resource lists. | |
58 | */ | |
59 | ||
60 | /* | |
61 | * Add space to a resource list. Used to either | |
62 | * initialize a list or return free space to it. | |
63 | */ | |
64 | rlist_free (rlp, start, end) | |
65 | register struct rlist **rlp; unsigned start, end; { | |
66 | struct rlist *head; | |
67 | ||
68 | head = *rlp; | |
69 | ||
70 | loop: | |
71 | /* if nothing here, insert (tail of list) */ | |
72 | if (*rlp == 0) { | |
73 | *rlp = (struct rlist *)malloc(sizeof(**rlp), M_TEMP, M_NOWAIT); | |
74 | (*rlp)->rl_start = start; | |
75 | (*rlp)->rl_end = end; | |
76 | (*rlp)->rl_next = 0; | |
77 | return; | |
78 | } | |
79 | ||
80 | /* if new region overlaps something currently present, panic */ | |
81 | if (start >= (*rlp)->rl_start && start <= (*rlp)->rl_end) { | |
82 | printf("Frag %d:%d, ent %d:%d ", start, end, | |
83 | (*rlp)->rl_start, (*rlp)->rl_end); | |
84 | panic("overlapping front rlist_free: freed twice?"); | |
85 | } | |
86 | if (end >= (*rlp)->rl_start && end <= (*rlp)->rl_end) { | |
87 | printf("Frag %d:%d, ent %d:%d ", start, end, | |
88 | (*rlp)->rl_start, (*rlp)->rl_end); | |
89 | panic("overlapping tail rlist_free: freed twice?"); | |
90 | } | |
91 | ||
92 | /* are we adjacent to this element? (in front) */ | |
93 | if (end+1 == (*rlp)->rl_start) { | |
94 | /* coalesce */ | |
95 | (*rlp)->rl_start = start; | |
96 | goto scan; | |
97 | } | |
98 | ||
99 | /* are we before this element? */ | |
100 | if (end < (*rlp)->rl_start) { | |
101 | register struct rlist *nlp; | |
102 | ||
103 | nlp = (struct rlist *)malloc(sizeof(*nlp), M_TEMP, M_NOWAIT); | |
104 | nlp->rl_start = start; | |
105 | nlp->rl_end = end; | |
106 | nlp->rl_next = *rlp; | |
107 | *rlp = nlp; | |
108 | return; | |
109 | } | |
110 | ||
111 | /* are we adjacent to this element? (at tail) */ | |
112 | if ((*rlp)->rl_end + 1 == start) { | |
113 | /* coalesce */ | |
114 | (*rlp)->rl_end = end; | |
115 | goto scan; | |
116 | } | |
117 | ||
118 | /* are we after this element */ | |
119 | if (start > (*rlp)->rl_end) { | |
120 | rlp = &((*rlp)->rl_next); | |
121 | goto loop; | |
122 | } else | |
123 | panic("rlist_free: can't happen"); | |
124 | ||
125 | scan: | |
126 | /* can we coalesce list now that we've filled a void? */ | |
127 | { | |
128 | register struct rlist *lp, *lpn; | |
129 | ||
130 | for (lp = head; lp->rl_next ;) { | |
131 | lpn = lp->rl_next; | |
132 | ||
133 | /* coalesce ? */ | |
134 | if (lp->rl_end + 1 == lpn->rl_start) { | |
135 | lp->rl_end = lpn->rl_end; | |
136 | lp->rl_next = lpn->rl_next; | |
137 | free(lpn, M_TEMP); | |
138 | } else | |
139 | lp = lp->rl_next; | |
140 | } | |
141 | } | |
142 | } | |
143 | ||
144 | /* | |
145 | * Obtain a region of desired size from a resource list. | |
146 | * If nothing available of that size, return 0. Otherwise, | |
147 | * return a value of 1 and set resource start location with | |
148 | * "*loc". (Note: loc can be zero if we don't wish the value) | |
149 | */ | |
150 | int rlist_alloc (rlp, size, loc) | |
151 | struct rlist **rlp; unsigned size, *loc; { | |
152 | register struct rlist *lp; | |
153 | ||
154 | ||
155 | /* walk list, allocating first thing that's big enough (first fit) */ | |
156 | for (; *rlp; rlp = &((*rlp)->rl_next)) | |
157 | if(size <= (*rlp)->rl_end - (*rlp)->rl_start + 1) { | |
158 | ||
159 | /* hand it to the caller */ | |
160 | if (loc) *loc = (*rlp)->rl_start; | |
161 | (*rlp)->rl_start += size; | |
162 | ||
163 | /* did we eat this element entirely? */ | |
164 | if ((*rlp)->rl_start > (*rlp)->rl_end) { | |
165 | lp = (*rlp)->rl_next; | |
166 | free (*rlp, M_TEMP); | |
167 | *rlp = lp; | |
168 | } | |
169 | ||
170 | return (1); | |
171 | } | |
172 | ||
173 | /* nothing in list that's big enough */ | |
174 | return (0); | |
175 | } | |
176 | ||
177 | /* | |
178 | * Finished with this resource list, reclaim all space and | |
179 | * mark it as being empty. | |
180 | */ | |
181 | rlist_destroy (rlp) | |
182 | struct rlist **rlp; { | |
183 | struct rlist *lp, *nlp; | |
184 | ||
185 | lp = *rlp; | |
186 | *rlp = 0; | |
187 | for (; lp; lp = nlp) { | |
188 | nlp = lp->rl_next; | |
189 | free (lp, M_TEMP); | |
190 | } | |
191 | } |