Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Commit Details
Date: | 2010-11-19 23:17:47 (13 years 4 months ago) |
---|---|
Author: | Werner Almesberger |
Commit: | 2787a45c436c35fc6fd0ed452903ad045fe9571d |
Message: | qpkg: added James S. Plank's red-black trees |
Files: |
qpkg/LICENSE.jrb (1 diff) qpkg/Makefile (1 diff) qpkg/README.jrb (1 diff) qpkg/jrb.c (1 diff) qpkg/jrb.h (1 diff) qpkg/jval.c (1 diff) qpkg/jval.h (1 diff) |
Change Details
qpkg/LICENSE.jrb | ||
---|---|---|
1 | Copyright (C) 1991, 1999 Free Software Foundation, Inc. | |
2 | 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
3 | Everyone is permitted to copy and distribute verbatim copies | |
4 | of this license document, but changing it is not allowed. | |
5 | ||
6 | [This is the first released version of the Lesser GPL. It also counts | |
7 | as the successor of the GNU Library Public License, version 2, hence | |
8 | the version number 2.1.] | |
9 | ||
10 | [9]Preamble | |
11 | ||
12 | The licenses for most software are designed to take away your freedom | |
13 | to share and change it. By contrast, the GNU General Public Licenses | |
14 | are intended to guarantee your freedom to share and change free | |
15 | software--to make sure the software is free for all its users. | |
16 | ||
17 | This license, the Lesser General Public License, applies to some | |
18 | specially designated software packages--typically libraries--of the | |
19 | Free Software Foundation and other authors who decide to use it. You | |
20 | can use it too, but we suggest you first think carefully about whether | |
21 | this license or the ordinary General Public License is the better | |
22 | strategy to use in any particular case, based on the explanations | |
23 | below. | |
24 | ||
25 | When we speak of free software, we are referring to freedom of use, | |
26 | not price. Our General Public Licenses are designed to make sure that | |
27 | you have the freedom to distribute copies of free software (and charge | |
28 | for this service if you wish); that you receive source code or can get | |
29 | it if you want it; that you can change the software and use pieces of | |
30 | it in new free programs; and that you are informed that you can do | |
31 | these things. | |
32 | ||
33 | To protect your rights, we need to make restrictions that forbid | |
34 | distributors to deny you these rights or to ask you to surrender these | |
35 | rights. These restrictions translate to certain responsibilities for | |
36 | you if you distribute copies of the library or if you modify it. | |
37 | ||
38 | For example, if you distribute copies of the library, whether gratis | |
39 | or for a fee, you must give the recipients all the rights that we gave | |
40 | you. You must make sure that they, too, receive or can get the source | |
41 | code. If you link other code with the library, you must provide | |
42 | complete object files to the recipients, so that they can relink them | |
43 | with the library after making changes to the library and recompiling | |
44 | it. And you must show them these terms so they know their rights. | |
45 | ||
46 | We protect your rights with a two-step method: (1) we copyright the | |
47 | library, and (2) we offer you this license, which gives you legal | |
48 | permission to copy, distribute and/or modify the library. | |
49 | ||
50 | To protect each distributor, we want to make it very clear that there | |
51 | is no warranty for the free library. Also, if the library is modified | |
52 | by someone else and passed on, the recipients should know that what | |
53 | they have is not the original version, so that the original author's | |
54 | reputation will not be affected by problems that might be introduced | |
55 | by others. | |
56 | ||
57 | Finally, software patents pose a constant threat to the existence of | |
58 | any free program. We wish to make sure that a company cannot | |
59 | effectively restrict the users of a free program by obtaining a | |
60 | restrictive license from a patent holder. Therefore, we insist that | |
61 | any patent license obtained for a version of the library must be | |
62 | consistent with the full freedom of use specified in this license. | |
63 | ||
64 | Most GNU software, including some libraries, is covered by the | |
65 | ordinary GNU General Public License. This license, the GNU Lesser | |
66 | General Public License, applies to certain designated libraries, and | |
67 | is quite different from the ordinary General Public License. We use | |
68 | this license for certain libraries in order to permit linking those | |
69 | libraries into non-free programs. | |
70 | ||
71 | When a program is linked with a library, whether statically or using a | |
72 | shared library, the combination of the two is legally speaking a | |
73 | combined work, a derivative of the original library. The ordinary | |
74 | General Public License therefore permits such linking only if the | |
75 | entire combination fits its criteria of freedom. The Lesser General | |
76 | Public License permits more lax criteria for linking other code with | |
77 | the library. | |
78 | ||
79 | We call this license the "Lesser" General Public License because it | |
80 | does Less to protect the user's freedom than the ordinary General | |
81 | Public License. It also provides other free software developers Less | |
82 | of an advantage over competing non-free programs. These disadvantages | |
83 | are the reason we use the ordinary General Public License for many | |
84 | libraries. However, the Lesser license provides advantages in certain | |
85 | special circumstances. | |
86 | ||
87 | For example, on rare occasions, there may be a special need to | |
88 | encourage the widest possible use of a certain library, so that it | |
89 | becomes a de-facto standard. To achieve this, non-free programs must | |
90 | be allowed to use the library. A more frequent case is that a free | |
91 | library does the same job as widely used non-free libraries. In this | |
92 | case, there is little to gain by limiting the free library to free | |
93 | software only, so we use the Lesser General Public License. | |
94 | ||
95 | In other cases, permission to use a particular library in non-free | |
96 | programs enables a greater number of people to use a large body of | |
97 | free software. For example, permission to use the GNU C Library in | |
98 | non-free programs enables many more people to use the whole GNU | |
99 | operating system, as well as its variant, the GNU/Linux operating | |
100 | system. | |
101 | ||
102 | Although the Lesser General Public License is Less protective of the | |
103 | users' freedom, it does ensure that the user of a program that is | |
104 | linked with the Library has the freedom and the wherewithal to run | |
105 | that program using a modified version of the Library. | |
106 | ||
107 | The precise terms and conditions for copying, distribution and | |
108 | modification follow. Pay close attention to the difference between a | |
109 | "work based on the library" and a "work that uses the library". The | |
110 | former contains code derived from the library, whereas the latter must | |
111 | be combined with the library in order to run. | |
112 | ||
113 | [10]TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
114 | ||
115 | 0. This License Agreement applies to any software library or other | |
116 | program which contains a notice placed by the copyright holder or | |
117 | other authorized party saying it may be distributed under the terms of | |
118 | this Lesser General Public License (also called "this License"). Each | |
119 | licensee is addressed as "you". | |
120 | ||
121 | A "library" means a collection of software functions and/or data | |
122 | prepared so as to be conveniently linked with application programs | |
123 | (which use some of those functions and data) to form executables. | |
124 | ||
125 | The "Library", below, refers to any such software library or work | |
126 | which has been distributed under these terms. A "work based on the | |
127 | Library" means either the Library or any derivative work under | |
128 | copyright law: that is to say, a work containing the Library or a | |
129 | portion of it, either verbatim or with modifications and/or translated | |
130 | straightforwardly into another language. (Hereinafter, translation is | |
131 | included without limitation in the term "modification".) | |
132 | ||
133 | "Source code" for a work means the preferred form of the work for | |
134 | making modifications to it. For a library, complete source code means | |
135 | all the source code for all modules it contains, plus any associated | |
136 | interface definition files, plus the scripts used to control | |
137 | compilation and installation of the library. | |
138 | ||
139 | Activities other than copying, distribution and modification are not | |
140 | covered by this License; they are outside its scope. The act of | |
141 | running a program using the Library is not restricted, and output from | |
142 | such a program is covered only if its contents constitute a work based | |
143 | on the Library (independent of the use of the Library in a tool for | |
144 | writing it). Whether that is true depends on what the Library does and | |
145 | what the program that uses the Library does. | |
146 | ||
147 | 1. You may copy and distribute verbatim copies of the Library's | |
148 | complete source code as you receive it, in any medium, provided that | |
149 | you conspicuously and appropriately publish on each copy an | |
150 | appropriate copyright notice and disclaimer of warranty; keep intact | |
151 | all the notices that refer to this License and to the absence of any | |
152 | warranty; and distribute a copy of this License along with the | |
153 | Library. | |
154 | ||
155 | You may charge a fee for the physical act of transferring a copy, and | |
156 | you may at your option offer warranty protection in exchange for a | |
157 | fee. | |
158 | ||
159 | 2. You may modify your copy or copies of the Library or any portion of | |
160 | it, thus forming a work based on the Library, and copy and distribute | |
161 | such modifications or work under the terms of Section 1 above, | |
162 | provided that you also meet all of these conditions: | |
163 | ||
164 | * a) The modified work must itself be a software library. | |
165 | * b) You must cause the files modified to carry prominent notices | |
166 | stating that you changed the files and the date of any change. | |
167 | * c) You must cause the whole of the work to be licensed at no | |
168 | charge to all third parties under the terms of this License. | |
169 | * d) If a facility in the modified Library refers to a function or a | |
170 | table of data to be supplied by an application program that uses | |
171 | the facility, other than as an argument passed when the facility | |
172 | is invoked, then you must make a good faith effort to ensure that, | |
173 | in the event an application does not supply such function or | |
174 | table, the facility still operates, and performs whatever part of | |
175 | its purpose remains meaningful. | |
176 | (For example, a function in a library to compute square roots has | |
177 | a purpose that is entirely well-defined independent of the | |
178 | application. Therefore, Subsection 2d requires that any | |
179 | application-supplied function or table used by this function must | |
180 | be optional: if the application does not supply it, the square | |
181 | root function must still compute square roots.) | |
182 | These requirements apply to the modified work as a whole. If | |
183 | identifiable sections of that work are not derived from the | |
184 | Library, and can be reasonably considered independent and separate | |
185 | works in themselves, then this License, and its terms, do not | |
186 | apply to those sections when you distribute them as separate | |
187 | works. But when you distribute the same sections as part of a | |
188 | whole which is a work based on the Library, the distribution of | |
189 | the whole must be on the terms of this License, whose permissions | |
190 | for other licensees extend to the entire whole, and thus to each | |
191 | and every part regardless of who wrote it. | |
192 | Thus, it is not the intent of this section to claim rights or | |
193 | contest your rights to work written entirely by you; rather, the | |
194 | intent is to exercise the right to control the distribution of | |
195 | derivative or collective works based on the Library. | |
196 | In addition, mere aggregation of another work not based on the | |
197 | Library with the Library (or with a work based on the Library) on | |
198 | a volume of a storage or distribution medium does not bring the | |
199 | other work under the scope of this License. | |
200 | ||
201 | 3. You may opt to apply the terms of the ordinary GNU General Public | |
202 | License instead of this License to a given copy of the Library. To do | |
203 | this, you must alter all the notices that refer to this License, so | |
204 | that they refer to the ordinary GNU General Public License, version 2, | |
205 | instead of to this License. (If a newer version than version 2 of the | |
206 | ordinary GNU General Public License has appeared, then you can specify | |
207 | that version instead if you wish.) Do not make any other change in | |
208 | these notices. | |
209 | ||
210 | Once this change is made in a given copy, it is irreversible for that | |
211 | copy, so the ordinary GNU General Public License applies to all | |
212 | subsequent copies and derivative works made from that copy. | |
213 | ||
214 | This option is useful when you wish to copy part of the code of the | |
215 | Library into a program that is not a library. | |
216 | ||
217 | 4. You may copy and distribute the Library (or a portion or derivative | |
218 | of it, under Section 2) in object code or executable form under the | |
219 | terms of Sections 1 and 2 above provided that you accompany it with | |
220 | the complete corresponding machine-readable source code, which must be | |
221 | distributed under the terms of Sections 1 and 2 above on a medium | |
222 | customarily used for software interchange. | |
223 | ||
224 | If distribution of object code is made by offering access to copy from | |
225 | a designated place, then offering equivalent access to copy the source | |
226 | code from the same place satisfies the requirement to distribute the | |
227 | source code, even though third parties are not compelled to copy the | |
228 | source along with the object code. | |
229 | ||
230 | 5. A program that contains no derivative of any portion of the | |
231 | Library, but is designed to work with the Library by being compiled or | |
232 | linked with it, is called a "work that uses the Library". Such a work, | |
233 | in isolation, is not a derivative work of the Library, and therefore | |
234 | falls outside the scope of this License. | |
235 | ||
236 | However, linking a "work that uses the Library" with the Library | |
237 | creates an executable that is a derivative of the Library (because it | |
238 | contains portions of the Library), rather than a "work that uses the | |
239 | library". The executable is therefore covered by this License. Section | |
240 | 6 states terms for distribution of such executables. | |
241 | ||
242 | When a "work that uses the Library" uses material from a header file | |
243 | that is part of the Library, the object code for the work may be a | |
244 | derivative work of the Library even though the source code is not. | |
245 | Whether this is true is especially significant if the work can be | |
246 | linked without the Library, or if the work is itself a library. The | |
247 | threshold for this to be true is not precisely defined by law. | |
248 | ||
249 | If such an object file uses only numerical parameters, data structure | |
250 | layouts and accessors, and small macros and small inline functions | |
251 | (ten lines or less in length), then the use of the object file is | |
252 | unrestricted, regardless of whether it is legally a derivative work. | |
253 | (Executables containing this object code plus portions of the Library | |
254 | will still fall under Section 6.) | |
255 | ||
256 | Otherwise, if the work is a derivative of the Library, you may | |
257 | distribute the object code for the work under the terms of Section 6. | |
258 | Any executables containing that work also fall under Section 6, | |
259 | whether or not they are linked directly with the Library itself. | |
260 | ||
261 | 6. As an exception to the Sections above, you may also combine or link | |
262 | a "work that uses the Library" with the Library to produce a work | |
263 | containing portions of the Library, and distribute that work under | |
264 | terms of your choice, provided that the terms permit modification of | |
265 | the work for the customer's own use and reverse engineering for | |
266 | debugging such modifications. | |
267 | ||
268 | You must give prominent notice with each copy of the work that the | |
269 | Library is used in it and that the Library and its use are covered by | |
270 | this License. You must supply a copy of this License. If the work | |
271 | during execution displays copyright notices, you must include the | |
272 | copyright notice for the Library among them, as well as a reference | |
273 | directing the user to the copy of this License. Also, you must do one | |
274 | of these things: | |
275 | ||
276 | * a) Accompany the work with the complete corresponding | |
277 | machine-readable source code for the Library including whatever | |
278 | changes were used in the work (which must be distributed under | |
279 | Sections 1 and 2 above); and, if the work is an executable linked | |
280 | with the Library, with the complete machine-readable "work that | |
281 | uses the Library", as object code and/or source code, so that the | |
282 | user can modify the Library and then relink to produce a modified | |
283 | executable containing the modified Library. (It is understood that | |
284 | the user who changes the contents of definitions files in the | |
285 | Library will not necessarily be able to recompile the application | |
286 | to use the modified definitions.) | |
287 | * b) Use a suitable shared library mechanism for linking with the | |
288 | Library. A suitable mechanism is one that (1) uses at run time a | |
289 | copy of the library already present on the user's computer system, | |
290 | rather than copying library functions into the executable, and (2) | |
291 | will operate properly with a modified version of the library, if | |
292 | the user installs one, as long as the modified version is | |
293 | interface-compatible with the version that the work was made with. | |
294 | * c) Accompany the work with a written offer, valid for at least | |
295 | three years, to give the same user the materials specified in | |
296 | Subsection 6a, above, for a charge no more than the cost of | |
297 | performing this distribution. | |
298 | * d) If distribution of the work is made by offering access to copy | |
299 | from a designated place, offer equivalent access to copy the above | |
300 | specified materials from the same place. | |
301 | * e) Verify that the user has already received a copy of these | |
302 | materials or that you have already sent this user a copy. | |
303 | ||
304 | For an executable, the required form of the "work that uses the | |
305 | Library" must include any data and utility programs needed for | |
306 | reproducing the executable from it. However, as a special exception, | |
307 | the materials to be distributed need not include anything that is | |
308 | normally distributed (in either source or binary form) with the major | |
309 | components (compiler, kernel, and so on) of the operating system on | |
310 | which the executable runs, unless that component itself accompanies | |
311 | the executable. | |
312 | ||
313 | It may happen that this requirement contradicts the license | |
314 | restrictions of other proprietary libraries that do not normally | |
315 | accompany the operating system. Such a contradiction means you cannot | |
316 | use both them and the Library together in an executable that you | |
317 | distribute. | |
318 | ||
319 | 7. You may place library facilities that are a work based on the | |
320 | Library side-by-side in a single library together with other library | |
321 | facilities not covered by this License, and distribute such a combined | |
322 | library, provided that the separate distribution of the work based on | |
323 | the Library and of the other library facilities is otherwise | |
324 | permitted, and provided that you do these two things: | |
325 | ||
326 | * a) Accompany the combined library with a copy of the same work | |
327 | based on the Library, uncombined with any other library | |
328 | facilities. This must be distributed under the terms of the | |
329 | Sections above. | |
330 | * b) Give prominent notice with the combined library of the fact | |
331 | that part of it is a work based on the Library, and explaining | |
332 | where to find the accompanying uncombined form of the same work. | |
333 | ||
334 | 8. You may not copy, modify, sublicense, link with, or distribute the | |
335 | Library except as expressly provided under this License. Any attempt | |
336 | otherwise to copy, modify, sublicense, link with, or distribute the | |
337 | Library is void, and will automatically terminate your rights under | |
338 | this License. However, parties who have received copies, or rights, | |
339 | from you under this License will not have their licenses terminated so | |
340 | long as such parties remain in full compliance. | |
341 | ||
342 | 9. You are not required to accept this License, since you have not | |
343 | signed it. However, nothing else grants you permission to modify or | |
344 | distribute the Library or its derivative works. These actions are | |
345 | prohibited by law if you do not accept this License. Therefore, by | |
346 | modifying or distributing the Library (or any work based on the | |
347 | Library), you indicate your acceptance of this License to do so, and | |
348 | all its terms and conditions for copying, distributing or modifying | |
349 | the Library or works based on it. | |
350 | ||
351 | 10. Each time you redistribute the Library (or any work based on the | |
352 | Library), the recipient automatically receives a license from the | |
353 | original licensor to copy, distribute, link with or modify the Library | |
354 | subject to these terms and conditions. You may not impose any further | |
355 | restrictions on the recipients' exercise of the rights granted herein. | |
356 | You are not responsible for enforcing compliance by third parties with | |
357 | this License. | |
358 | ||
359 | 11. If, as a consequence of a court judgment or allegation of patent | |
360 | infringement or for any other reason (not limited to patent issues), | |
361 | conditions are imposed on you (whether by court order, agreement or | |
362 | otherwise) that contradict the conditions of this License, they do not | |
363 | excuse you from the conditions of this License. If you cannot | |
364 | distribute so as to satisfy simultaneously your obligations under this | |
365 | License and any other pertinent obligations, then as a consequence you | |
366 | may not distribute the Library at all. For example, if a patent | |
367 | license would not permit royalty-free redistribution of the Library by | |
368 | all those who receive copies directly or indirectly through you, then | |
369 | the only way you could satisfy both it and this License would be to | |
370 | refrain entirely from distribution of the Library. | |
371 | ||
372 | If any portion of this section is held invalid or unenforceable under | |
373 | any particular circumstance, the balance of the section is intended to | |
374 | apply, and the section as a whole is intended to apply in other | |
375 | circumstances. | |
376 | ||
377 | It is not the purpose of this section to induce you to infringe any | |
378 | patents or other property right claims or to contest validity of any | |
379 | such claims; this section has the sole purpose of protecting the | |
380 | integrity of the free software distribution system which is | |
381 | implemented by public license practices. Many people have made | |
382 | generous contributions to the wide range of software distributed | |
383 | through that system in reliance on consistent application of that | |
384 | system; it is up to the author/donor to decide if he or she is willing | |
385 | to distribute software through any other system and a licensee cannot | |
386 | impose that choice. | |
387 | ||
388 | This section is intended to make thoroughly clear what is believed to | |
389 | be a consequence of the rest of this License. | |
390 | ||
391 | 12. If the distribution and/or use of the Library is restricted in | |
392 | certain countries either by patents or by copyrighted interfaces, the | |
393 | original copyright holder who places the Library under this License | |
394 | may add an explicit geographical distribution limitation excluding | |
395 | those countries, so that distribution is permitted only in or among | |
396 | countries not thus excluded. In such case, this License incorporates | |
397 | the limitation as if written in the body of this License. | |
398 | ||
399 | 13. The Free Software Foundation may publish revised and/or new | |
400 | versions of the Lesser General Public License from time to time. Such | |
401 | new versions will be similar in spirit to the present version, but may | |
402 | differ in detail to address new problems or concerns. | |
403 | ||
404 | Each version is given a distinguishing version number. If the Library | |
405 | specifies a version number of this License which applies to it and | |
406 | "any later version", you have the option of following the terms and | |
407 | conditions either of that version or of any later version published by | |
408 | the Free Software Foundation. If the Library does not specify a | |
409 | license version number, you may choose any version ever published by | |
410 | the Free Software Foundation. | |
411 | ||
412 | 14. If you wish to incorporate parts of the Library into other free | |
413 | programs whose distribution conditions are incompatible with these, | |
414 | write to the author to ask for permission. For software which is | |
415 | copyrighted by the Free Software Foundation, write to the Free | |
416 | Software Foundation; we sometimes make exceptions for this. Our | |
417 | decision will be guided by the two goals of preserving the free status | |
418 | of all derivatives of our free software and of promoting the sharing | |
419 | and reuse of software generally. | |
420 | ||
421 | NO WARRANTY | |
422 | ||
423 | 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO | |
424 | WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. | |
425 | EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR | |
426 | OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY | |
427 | KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE | |
428 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
429 | PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE | |
430 | LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME | |
431 | THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. | |
432 | ||
433 | 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN | |
434 | WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY | |
435 | AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU | |
436 | FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR | |
437 | CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE | |
438 | LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING | |
439 | RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A | |
440 | FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF | |
441 | SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH | |
442 | DAMAGES. | |
443 | ||
444 | END OF TERMS AND CONDITIONS | |
445 | ||
446 | [11]How to Apply These Terms to Your New Libraries | |
447 | ||
448 | If you develop a new library, and you want it to be of the greatest | |
449 | possible use to the public, we recommend making it free software that | |
450 | everyone can redistribute and change. You can do so by permitting | |
451 | redistribution under these terms (or, alternatively, under the terms | |
452 | of the ordinary General Public License). | |
453 | ||
454 | To apply these terms, attach the following notices to the library. It | |
455 | is safest to attach them to the start of each source file to most | |
456 | effectively convey the exclusion of warranty; and each file should | |
457 | have at least the "copyright" line and a pointer to where the full | |
458 | notice is found. | |
459 | ||
460 | one line to give the library's name and an idea of what it does. | |
461 | Copyright (C) year name of author | |
462 | ||
463 | This library is free software; you can redistribute it and/or | |
464 | modify it under the terms of the GNU Lesser General Public | |
465 | License as published by the Free Software Foundation; either | |
466 | version 2.1 of the License, or (at your option) any later version. | |
467 | ||
468 | This library is distributed in the hope that it will be useful, | |
469 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
470 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
471 | Lesser General Public License for more details. | |
472 | ||
473 | You should have received a copy of the GNU Lesser General Public | |
474 | License along with this library; if not, write to the Free Software | |
475 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
476 | ||
477 | Also add information on how to contact you by electronic and paper | |
478 | mail. | |
479 | ||
480 | You should also get your employer (if you work as a programmer) or | |
481 | your school, if any, to sign a "copyright disclaimer" for the library, | |
482 | if necessary. Here is a sample; alter the names: | |
483 | ||
484 | Yoyodyne, Inc., hereby disclaims all copyright interest in | |
485 | the library `Frob' (a library for tweaking knobs) written | |
486 | by James Random Hacker. | |
487 | ||
488 | signature of Ty Coon, 1 April 1990 | |
489 | Ty Coon, President of Vice | |
490 | ||
491 | That's all there is to it! | |
492 | _________________________________________________________________ | |
493 | ||
494 | Return to [12]GNU's home page. | |
495 | ||
496 | FSF & GNU inquiries & questions to [13]gnu@gnu.org. Other [14]ways to | |
497 | contact the FSF. | |
498 | ||
499 | Comments on these web pages to [15]webmasters@www.gnu.org, send other | |
500 | questions to [16]gnu@gnu.org. | |
501 | ||
502 | Copyright notice above. | |
503 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
504 | MA 02111, USA | |
505 | ||
506 | Updated: 7 Jan 2000 rms | |
507 | _________________________________________________________________ | |
508 | ||
509 | References | |
510 | ||
511 | 1. http://www.gnu.org/graphics/philosophicalgnu.html | |
512 | 2. http://www.gnu.org/copyleft/copyleft.html#translationsLGPL | |
513 | 3. http://www.gnu.org/philosophy/why-not-lgpl.html | |
514 | 4. http://www.gnu.org/copyleft/lesser.html#SEC1 | |
515 | 5. http://www.gnu.org/copyleft/lesser.html#SEC2 | |
516 | 6. http://www.gnu.org/copyleft/lesser.html#SEC3 | |
517 | 7. http://www.gnu.org/copyleft/lesser.html#SEC4 | |
518 | 8. http://www.gnu.org/copyleft/lesser.html#TOC1 | |
519 | 9. http://www.gnu.org/copyleft/lesser.html#TOC2 | |
520 | 10. http://www.gnu.org/copyleft/lesser.html#TOC3 | |
521 | 11. http://www.gnu.org/copyleft/lesser.html#TOC4 | |
522 | 12. http://www.gnu.org/home.html | |
523 | 13. mailto:gnu@gnu.org | |
524 | 14. http://www.gnu.org/home.html#ContactInfo | |
525 | 15. mailto:webmasters@www.gnu.org | |
526 | 16. mailto:gnu@gnu.org |
qpkg/Makefile | ||
---|---|---|
1 | CFLAGS = -Wall -Wshadow -g | |
1 | CFLAGS = -Wall -Wshadow -g -O | |
2 | 2 | # -O, so that we get data flow analysis, which helps to find more bugs |
3 | #LDFLAGS=-pg | |
3 | 4 | |
4 | OBJS = gobble.o id.o prereq.o qpkg.o | |
5 | OBJS = gobble.o id.o prereq.o qpkg.o jrb.o jval.o | |
5 | 6 | |
6 | 7 | all: qpkg |
7 | 8 |
qpkg/README.jrb | ||
---|---|---|
1 | Libraries for fields, doubly-linked lists and red-black trees. | |
2 | Copyright (C) 2001 James S. Plank | |
3 | ||
4 | This library is free software; you can redistribute it and/or | |
5 | modify it under the terms of the GNU Lesser General Public | |
6 | License as published by the Free Software Foundation; either | |
7 | version 2.1 of the License, or (at your option) any later version. | |
8 | ||
9 | This library is distributed in the hope that it will be useful, | |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
12 | Lesser General Public License for more details. | |
13 | ||
14 | You should have received a copy of the GNU Lesser General Public | |
15 | License along with this library; if not, write to the Free Software | |
16 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
17 | ||
18 | --------------------------------------------------------------------------- | |
19 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ | |
20 | for instruction on how to use this library. | |
21 | ||
22 | Jim Plank | |
23 | plank@cs.utk.edu | |
24 | http://www.cs.utk.edu/~plank | |
25 | ||
26 | Associate Professor | |
27 | Department of Computer Science | |
28 | University of Tennessee | |
29 | 203 Claxton Complex | |
30 | 1122 Volunteer Blvd. | |
31 | Knoxville, TN 37996-3450 | |
32 | ||
33 | 865-974-4397 | |
34 | Fax: 865-974-4404 |
qpkg/jrb.c | ||
---|---|---|
1 | /* | |
2 | Libraries for fields, doubly-linked lists and red-black trees. | |
3 | Copyright (C) 2001 James S. Plank | |
4 | ||
5 | This library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
9 | ||
10 | This library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Lesser General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Lesser General Public | |
16 | License along with this library; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
18 | ||
19 | --------------------------------------------------------------------------- | |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ | |
21 | for instruction on how to use this library. | |
22 | ||
23 | Jim Plank | |
24 | plank@cs.utk.edu | |
25 | http://www.cs.utk.edu/~plank | |
26 | ||
27 | Associate Professor | |
28 | Department of Computer Science | |
29 | University of Tennessee | |
30 | 203 Claxton Complex | |
31 | 1122 Volunteer Blvd. | |
32 | Knoxville, TN 37996-3450 | |
33 | ||
34 | 865-974-4397 | |
35 | Fax: 865-974-4404 | |
36 | */ | |
37 | /* Revision 1.2. Jim Plank */ | |
38 | ||
39 | /* Original code by Jim Plank (plank@cs.utk.edu) */ | |
40 | /* modified for THINK C 6.0 for Macintosh by Chris Bartley */ | |
41 | ||
42 | #include <string.h> | |
43 | #include <stdio.h> | |
44 | #include <stdlib.h> | |
45 | #include <ctype.h> | |
46 | #include "jrb.h" | |
47 | ||
48 | static void mk_new_int(JRB l, JRB r, JRB p, int il); | |
49 | static JRB lprev(JRB n); | |
50 | static JRB rprev(JRB n); | |
51 | static void recolor(JRB n); | |
52 | static void single_rotate(JRB y, int l); | |
53 | static void jrb_print_tree(JRB t, int level); | |
54 | static void jrb_iprint_tree(JRB t, int level); | |
55 | ||
56 | #define isred(n) (n->red) | |
57 | #define isblack(n) (!isred(n)) | |
58 | #define isleft(n) (n->left) | |
59 | #define isright(n) (!isleft(n)) | |
60 | #define isint(n) (n->internal) | |
61 | #define isext(n) (!isint(n)) | |
62 | #define ishead(n) (n->roothead & 2) | |
63 | #define isroot(n) (n->roothead & 1) | |
64 | #define getlext(n) ((struct jrb_node *)(n->key.v)) | |
65 | #define setlext(node, val) node->key.v = (void *) (val) | |
66 | #define getrext(n) ((struct jrb_node *)(n->val.v)) | |
67 | #define setrext(node, value) node->val.v = (void *) (value) | |
68 | #define setred(n) n->red = 1 | |
69 | #define setblack(n) n->red = 0 | |
70 | #define setleft(n) n->left = 1 | |
71 | #define setright(n) n->left = 0 | |
72 | #define sethead(n) (n->roothead |= 2) | |
73 | #define setroot(n) (n->roothead |= 1) | |
74 | #define setint(n) n->internal = 1 | |
75 | #define setext(n) n->internal = 0 | |
76 | #define setnormal(n) n->roothead = 0 | |
77 | #define sibling(n) ((isleft(n)) ? n->parent->blink : n->parent->flink) | |
78 | ||
79 | static void insert(JRB item, JRB list) /* Inserts to the end of a list */ | |
80 | { | |
81 | JRB last_node; | |
82 | ||
83 | last_node = list->blink; | |
84 | ||
85 | list->blink = item; | |
86 | last_node->flink = item; | |
87 | item->blink = last_node; | |
88 | item->flink = list; | |
89 | } | |
90 | ||
91 | static void delete_item(JRB item) /* Deletes an arbitrary iterm */ | |
92 | { | |
93 | item->flink->blink = item->blink; | |
94 | item->blink->flink = item->flink; | |
95 | } | |
96 | ||
97 | #define mk_new_ext(new, kkkey, vvval) {\ | |
98 | new = (JRB) malloc(sizeof(struct jrb_node));\ | |
99 | new->val = vvval;\ | |
100 | new->key = kkkey;\ | |
101 | setext(new);\ | |
102 | setblack(new);\ | |
103 | setnormal(new);\ | |
104 | } | |
105 | ||
106 | static void mk_new_int(JRB l, JRB r, JRB p, int il) | |
107 | { | |
108 | JRB newnode; | |
109 | ||
110 | newnode = (JRB) malloc(sizeof(struct jrb_node)); | |
111 | setint(newnode); | |
112 | setred(newnode); | |
113 | setnormal(newnode); | |
114 | newnode->flink = l; | |
115 | newnode->blink = r; | |
116 | newnode->parent = p; | |
117 | setlext(newnode, l); | |
118 | setrext(newnode, r); | |
119 | l->parent = newnode; | |
120 | r->parent = newnode; | |
121 | setleft(l); | |
122 | setright(r); | |
123 | if (ishead(p)) { | |
124 | p->parent = newnode; | |
125 | setroot(newnode); | |
126 | } else if (il) { | |
127 | setleft(newnode); | |
128 | p->flink = newnode; | |
129 | } else { | |
130 | setright(newnode); | |
131 | p->blink = newnode; | |
132 | } | |
133 | recolor(newnode); | |
134 | } | |
135 | ||
136 | ||
137 | JRB lprev(JRB n) | |
138 | { | |
139 | if (ishead(n)) return n; | |
140 | while (!isroot(n)) { | |
141 | if (isright(n)) return n->parent; | |
142 | n = n->parent; | |
143 | } | |
144 | return n->parent; | |
145 | } | |
146 | ||
147 | JRB rprev(JRB n) | |
148 | { | |
149 | if (ishead(n)) return n; | |
150 | while (!isroot(n)) { | |
151 | if (isleft(n)) return n->parent; | |
152 | n = n->parent; | |
153 | } | |
154 | return n->parent; | |
155 | } | |
156 | ||
157 | JRB make_jrb(void) | |
158 | { | |
159 | JRB head; | |
160 | ||
161 | head = (JRB) malloc (sizeof(struct jrb_node)); | |
162 | head->flink = head; | |
163 | head->blink = head; | |
164 | head->parent = head; | |
165 | head->key.s = ""; | |
166 | sethead(head); | |
167 | return head; | |
168 | } | |
169 | ||
170 | JRB jrb_find_gte_str(JRB n, char *key, int *fnd) | |
171 | { | |
172 | int cmp; | |
173 | ||
174 | *fnd = 0; | |
175 | if (!ishead(n)) { | |
176 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); | |
177 | exit(1); | |
178 | } | |
179 | if (n->parent == n) return n; | |
180 | cmp = strcmp(key, n->blink->key.s); | |
181 | if (cmp == 0) { | |
182 | *fnd = 1; | |
183 | return n->blink; | |
184 | } | |
185 | if (cmp > 0) return n; | |
186 | else n = n->parent; | |
187 | while (1) { | |
188 | if (isext(n)) return n; | |
189 | cmp = strcmp(key, getlext(n)->key.s); | |
190 | if (cmp == 0) { | |
191 | *fnd = 1; | |
192 | return getlext(n); | |
193 | } | |
194 | if (cmp < 0) n = n->flink ; else n = n->blink; | |
195 | } | |
196 | } | |
197 | ||
198 | JRB jrb_find_str(JRB n, char *key) | |
199 | { | |
200 | int fnd; | |
201 | JRB j; | |
202 | j = jrb_find_gte_str(n, key, &fnd); | |
203 | if (fnd) return j; else return NULL; | |
204 | } | |
205 | ||
206 | JRB jrb_find_gte_int(JRB n, int ikey, int *fnd) | |
207 | { | |
208 | *fnd = 0; | |
209 | if (!ishead(n)) { | |
210 | fprintf(stderr, "jrb_find_gte_int called on non-head %p\n", n); | |
211 | exit(1); | |
212 | } | |
213 | if (n->parent == n) return n; | |
214 | if (ikey == n->blink->key.i) { | |
215 | *fnd = 1; | |
216 | return n->blink; | |
217 | } | |
218 | if (ikey > n->blink->key.i) return n; | |
219 | else n = n->parent; | |
220 | while (1) { | |
221 | if (isext(n)) return n; | |
222 | if (ikey == getlext(n)->key.i) { | |
223 | *fnd = 1; | |
224 | return getlext(n); | |
225 | } | |
226 | n = (ikey < getlext(n)->key.i) ? n->flink : n->blink; | |
227 | } | |
228 | } | |
229 | ||
230 | JRB jrb_find_int(JRB n, int ikey) | |
231 | { | |
232 | int fnd; | |
233 | JRB j; | |
234 | ||
235 | j = jrb_find_gte_int(n, ikey, &fnd); | |
236 | if (fnd) return j; else return NULL; | |
237 | } | |
238 | ||
239 | JRB jrb_find_gte_dbl(JRB n, double dkey, int *fnd) | |
240 | { | |
241 | *fnd = 0; | |
242 | if (!ishead(n)) { | |
243 | fprintf(stderr, "jrb_find_gte_dbl called on non-head %p\n", n); | |
244 | exit(1); | |
245 | } | |
246 | if (n->parent == n) return n; | |
247 | if (dkey == n->blink->key.d) { | |
248 | *fnd = 1; | |
249 | return n->blink; | |
250 | } | |
251 | if (dkey > n->blink->key.d) return n; | |
252 | else n = n->parent; | |
253 | while (1) { | |
254 | if (isext(n)) return n; | |
255 | if (dkey == getlext(n)->key.d) { | |
256 | *fnd = 1; | |
257 | return getlext(n); | |
258 | } | |
259 | n = (dkey < getlext(n)->key.d) ? n->flink : n->blink; | |
260 | } | |
261 | } | |
262 | ||
263 | JRB jrb_find_dbl(JRB n, double dkey) | |
264 | { | |
265 | int fnd; | |
266 | JRB j; | |
267 | ||
268 | j = jrb_find_gte_dbl(n, dkey, &fnd); | |
269 | if (fnd) return j; else return NULL; | |
270 | } | |
271 | ||
272 | JRB jrb_find_gte_gen(JRB n, Jval key,int (*fxn)(Jval, Jval), int *fnd) | |
273 | { | |
274 | int cmp; | |
275 | ||
276 | *fnd = 0; | |
277 | if (!ishead(n)) { | |
278 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); | |
279 | exit(1); | |
280 | } | |
281 | if (n->parent == n) return n; | |
282 | cmp = (*fxn)(key, n->blink->key); | |
283 | if (cmp == 0) { | |
284 | *fnd = 1; | |
285 | return n->blink; | |
286 | } | |
287 | if (cmp > 0) return n; | |
288 | else n = n->parent; | |
289 | while (1) { | |
290 | if (isext(n)) return n; | |
291 | cmp = (*fxn)(key, getlext(n)->key); | |
292 | if (cmp == 0) { | |
293 | *fnd = 1; | |
294 | return getlext(n); | |
295 | } | |
296 | if (cmp < 0) n = n->flink ; else n = n->blink; | |
297 | } | |
298 | } | |
299 | ||
300 | JRB jrb_find_gen(JRB n, Jval key, int (*fxn)(Jval, Jval)) | |
301 | { | |
302 | int fnd; | |
303 | JRB j; | |
304 | ||
305 | j = jrb_find_gte_gen(n, key, fxn, &fnd); | |
306 | if (fnd) return j; else return NULL; | |
307 | } | |
308 | ||
309 | static JRB jrb_insert_b(JRB n, Jval key, Jval val) | |
310 | { | |
311 | JRB newleft, newright, newnode, p; | |
312 | ||
313 | if (ishead(n)) { | |
314 | if (n->parent == n) { /* Tree is empty */ | |
315 | mk_new_ext(newnode, key, val); | |
316 | insert(newnode, n); | |
317 | n->parent = newnode; | |
318 | newnode->parent = n; | |
319 | setroot(newnode); | |
320 | return newnode; | |
321 | } else { | |
322 | mk_new_ext(newright, key, val); | |
323 | insert(newright, n); | |
324 | newleft = newright->blink; | |
325 | setnormal(newleft); | |
326 | mk_new_int(newleft, newright, newleft->parent, isleft(newleft)); | |
327 | p = rprev(newright); | |
328 | if (!ishead(p)) setlext(p, newright); | |
329 | return newright; | |
330 | } | |
331 | } else { | |
332 | mk_new_ext(newleft, key, val); | |
333 | insert(newleft, n); | |
334 | setnormal(n); | |
335 | mk_new_int(newleft, n, n->parent, isleft(n)); | |
336 | p = lprev(newleft); | |
337 | if (!ishead(p)) setrext(p, newleft); | |
338 | return newleft; | |
339 | } | |
340 | } | |
341 | ||
342 | static void recolor(JRB n) | |
343 | { | |
344 | JRB p, gp, s; | |
345 | int done = 0; | |
346 | ||
347 | while(!done) { | |
348 | if (isroot(n)) { | |
349 | setblack(n); | |
350 | return; | |
351 | } | |
352 | ||
353 | p = n->parent; | |
354 | ||
355 | if (isblack(p)) return; | |
356 | ||
357 | if (isroot(p)) { | |
358 | setblack(p); | |
359 | return; | |
360 | } | |
361 | ||
362 | gp = p->parent; | |
363 | s = sibling(p); | |
364 | if (isred(s)) { | |
365 | setblack(p); | |
366 | setred(gp); | |
367 | setblack(s); | |
368 | n = gp; | |
369 | } else { | |
370 | done = 1; | |
371 | } | |
372 | } | |
373 | /* p's sibling is black, p is red, gp is black */ | |
374 | ||
375 | if ((isleft(n) == 0) == (isleft(p) == 0)) { | |
376 | single_rotate(gp, isleft(n)); | |
377 | setblack(p); | |
378 | setred(gp); | |
379 | } else { | |
380 | single_rotate(p, isleft(n)); | |
381 | single_rotate(gp, isleft(n)); | |
382 | setblack(n); | |
383 | setred(gp); | |
384 | } | |
385 | } | |
386 | ||
387 | static void single_rotate(JRB y, int l) | |
388 | { | |
389 | int rl = 0 /* for gcc */, ir; | |
390 | JRB x, yp; | |
391 | ||
392 | ir = isroot(y); | |
393 | yp = y->parent; | |
394 | if (!ir) { | |
395 | rl = isleft(y); | |
396 | } | |
397 | ||
398 | if (l) { | |
399 | x = y->flink; | |
400 | y->flink = x->blink; | |
401 | setleft(y->flink); | |
402 | y->flink->parent = y; | |
403 | x->blink = y; | |
404 | setright(y); | |
405 | } else { | |
406 | x = y->blink; | |
407 | y->blink = x->flink; | |
408 | setright(y->blink); | |
409 | y->blink->parent = y; | |
410 | x->flink = y; | |
411 | setleft(y); | |
412 | } | |
413 | ||
414 | x->parent = yp; | |
415 | y->parent = x; | |
416 | if (ir) { | |
417 | yp->parent = x; | |
418 | setnormal(y); | |
419 | setroot(x); | |
420 | } else { | |
421 | if (rl) { | |
422 | yp->flink = x; | |
423 | setleft(x); | |
424 | } else { | |
425 | yp->blink = x; | |
426 | setright(x); | |
427 | } | |
428 | } | |
429 | } | |
430 | ||
431 | void jrb_delete_node(JRB n) | |
432 | { | |
433 | JRB s, p, gp; | |
434 | char ir; | |
435 | ||
436 | if (isint(n)) { | |
437 | fprintf(stderr, "Cannot delete an internal node: %p\n", n); | |
438 | exit(1); | |
439 | } | |
440 | if (ishead(n)) { | |
441 | fprintf(stderr, "Cannot delete the head of an jrb_tree: %p\n", n); | |
442 | exit(1); | |
443 | } | |
444 | delete_item(n); /* Delete it from the list */ | |
445 | p = n->parent; /* The only node */ | |
446 | if (isroot(n)) { | |
447 | p->parent = p; | |
448 | free(n); | |
449 | return; | |
450 | } | |
451 | s = sibling(n); /* The only node after deletion */ | |
452 | if (isroot(p)) { | |
453 | s->parent = p->parent; | |
454 | s->parent->parent = s; | |
455 | setroot(s); | |
456 | free(p); | |
457 | free(n); | |
458 | return; | |
459 | } | |
460 | gp = p->parent; /* Set parent to sibling */ | |
461 | s->parent = gp; | |
462 | if (isleft(p)) { | |
463 | gp->flink = s; | |
464 | setleft(s); | |
465 | } else { | |
466 | gp->blink = s; | |
467 | setright(s); | |
468 | } | |
469 | ir = isred(p); | |
470 | free(p); | |
471 | free(n); | |
472 | ||
473 | if (isext(s)) { /* Update proper rext and lext values */ | |
474 | p = lprev(s); | |
475 | if (!ishead(p)) setrext(p, s); | |
476 | p = rprev(s); | |
477 | if (!ishead(p)) setlext(p, s); | |
478 | } else if (isblack(s)) { | |
479 | fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); | |
480 | exit(1); | |
481 | } else { | |
482 | p = lprev(s); | |
483 | if (!ishead(p)) setrext(p, s->flink); | |
484 | p = rprev(s); | |
485 | if (!ishead(p)) setlext(p, s->blink); | |
486 | setblack(s); | |
487 | return; | |
488 | } | |
489 | ||
490 | if (ir) return; | |
491 | ||
492 | /* Recolor */ | |
493 | ||
494 | n = s; | |
495 | p = n->parent; | |
496 | s = sibling(n); | |
497 | while(isblack(p) && isblack(s) && isint(s) && | |
498 | isblack(s->flink) && isblack(s->blink)) { | |
499 | setred(s); | |
500 | n = p; | |
501 | if (isroot(n)) return; | |
502 | p = n->parent; | |
503 | s = sibling(n); | |
504 | } | |
505 | ||
506 | if (isblack(p) && isred(s)) { /* Rotation 2.3b */ | |
507 | single_rotate(p, isright(n)); | |
508 | setred(p); | |
509 | setblack(s); | |
510 | s = sibling(n); | |
511 | } | |
512 | ||
513 | { JRB x, z; char il; | |
514 | ||
515 | if (isext(s)) { | |
516 | fprintf(stderr, "DELETION ERROR: sibling not internal\n"); | |
517 | exit(1); | |
518 | } | |
519 | ||
520 | il = isleft(n); | |
521 | x = il ? s->flink : s->blink ; | |
522 | z = sibling(x); | |
523 | ||
524 | if (isred(z)) { /* Rotation 2.3f */ | |
525 | single_rotate(p, !il); | |
526 | setblack(z); | |
527 | if (isred(p)) setred(s); else setblack(s); | |
528 | setblack(p); | |
529 | } else if (isblack(x)) { /* Recoloring only (2.3c) */ | |
530 | if (isred(s) || isblack(p)) { | |
531 | fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n"); | |
532 | exit(1); | |
533 | } | |
534 | setblack(p); | |
535 | setred(s); | |
536 | return; | |
537 | } else if (isred(p)) { /* 2.3d */ | |
538 | single_rotate(s, il); | |
539 | single_rotate(p, !il); | |
540 | setblack(x); | |
541 | setred(s); | |
542 | return; | |
543 | } else { /* 2.3e */ | |
544 | single_rotate(s, il); | |
545 | single_rotate(p, !il); | |
546 | setblack(x); | |
547 | return; | |
548 | } | |
549 | } | |
550 | } | |
551 | ||
552 | ||
553 | void jrb_print_tree(JRB t, int level) | |
554 | { | |
555 | int i; | |
556 | if (ishead(t) && t->parent == t) { | |
557 | printf("tree %p is empty\n", t); | |
558 | } else if (ishead(t)) { | |
559 | printf("Head: %p. Root = %p\n", t, t->parent); | |
560 | jrb_print_tree(t->parent, 0); | |
561 | } else { | |
562 | if (isext(t)) { | |
563 | for (i = 0; i < level; i++) putchar(' '); | |
564 | printf("Ext node %p: %c,%c: p=%p, k=%s\n", | |
565 | t, isred(t)?'R':'B', isleft(t)?'l':'r', t->parent, t->key.s); | |
566 | } else { | |
567 | jrb_print_tree(t->flink, level+2); | |
568 | jrb_print_tree(t->blink, level+2); | |
569 | for (i = 0; i < level; i++) putchar(' '); | |
570 | printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%s,%s)\n", | |
571 | t, isred(t)?'R':'B', isleft(t)?'l':'r', t->flink, | |
572 | t->blink, | |
573 | t->parent, getlext(t)->key.s, getrext(t)->key.s); | |
574 | } | |
575 | } | |
576 | } | |
577 | ||
578 | void jrb_iprint_tree(JRB t, int level) | |
579 | { | |
580 | int i; | |
581 | if (ishead(t) && t->parent == t) { | |
582 | printf("tree %p is empty\n", t); | |
583 | } else if (ishead(t)) { | |
584 | printf("Head: %p. Root = %p, < = %p, > = %p\n", | |
585 | t, t->parent, t->blink, t->flink); | |
586 | jrb_iprint_tree(t->parent, 0); | |
587 | } else { | |
588 | if (isext(t)) { | |
589 | for (i = 0; i < level; i++) putchar(' '); | |
590 | printf("Ext node %p: %c,%c: p=%p, <=%p, >=%p k=%d\n", | |
591 | t, isred(t)?'R':'B', isleft(t)?'l':'r', t->parent, | |
592 | t->blink, t->flink, t->key.i); | |
593 | } else { | |
594 | jrb_iprint_tree(t->flink, level+2); | |
595 | jrb_iprint_tree(t->blink, level+2); | |
596 | for (i = 0; i < level; i++) putchar(' '); | |
597 | printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%d,%d)\n", | |
598 | t, isred(t)?'R':'B', isleft(t)?'l':'r', t->flink, | |
599 | t->blink, | |
600 | t->parent, getlext(t)->key.i, getrext(t)->key.i); | |
601 | } | |
602 | } | |
603 | } | |
604 | ||
605 | int jrb_nblack(JRB n) | |
606 | { | |
607 | int nb; | |
608 | if (ishead(n) || isint(n)) { | |
609 | fprintf(stderr, "ERROR: jrb_nblack called on a non-external node %p\n", n); | |
610 | exit(1); | |
611 | } | |
612 | nb = 0; | |
613 | while(!ishead(n)) { | |
614 | if (isblack(n)) nb++; | |
615 | n = n->parent; | |
616 | } | |
617 | return nb; | |
618 | } | |
619 | ||
620 | int jrb_plength(JRB n) | |
621 | { | |
622 | int pl; | |
623 | if (ishead(n) || isint(n)) { | |
624 | fprintf(stderr, "ERROR: jrb_plength called on a non-external node %p\n", n); | |
625 | exit(1); | |
626 | } | |
627 | pl = 0; | |
628 | while(!ishead(n)) { | |
629 | pl++; | |
630 | n = n->parent; | |
631 | } | |
632 | return pl; | |
633 | } | |
634 | ||
635 | void jrb_free_tree(JRB n) | |
636 | { | |
637 | if (!ishead(n)) { | |
638 | fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n"); | |
639 | exit(1); | |
640 | } | |
641 | ||
642 | while(jrb_first(n) != jrb_nil(n)) { | |
643 | jrb_delete_node(jrb_first(n)); | |
644 | } | |
645 | free(n); | |
646 | } | |
647 | ||
648 | Jval jrb_val(JRB n) | |
649 | { | |
650 | return n->val; | |
651 | } | |
652 | ||
653 | #if 0 | |
654 | static JRB jrb_insert_a(JRB nd, Jval key, Jval val) | |
655 | { | |
656 | return jrb_insert_b(nd->flink, key, val); | |
657 | } | |
658 | #endif | |
659 | ||
660 | JRB jrb_insert_str(JRB tree, char *key, Jval val) | |
661 | { | |
662 | Jval k; | |
663 | int fnd; | |
664 | ||
665 | k.s = key; | |
666 | return jrb_insert_b(jrb_find_gte_str(tree, key, &fnd), k, val); | |
667 | } | |
668 | ||
669 | JRB jrb_insert_int(JRB tree, int ikey, Jval val) | |
670 | { | |
671 | Jval k; | |
672 | int fnd; | |
673 | ||
674 | k.i = ikey; | |
675 | return jrb_insert_b(jrb_find_gte_int(tree, ikey, &fnd), k, val); | |
676 | } | |
677 | ||
678 | JRB jrb_insert_dbl(JRB tree, double dkey, Jval val) | |
679 | { | |
680 | Jval k; | |
681 | int fnd; | |
682 | ||
683 | k.d = dkey; | |
684 | return jrb_insert_b(jrb_find_gte_dbl(tree, dkey, &fnd), k, val); | |
685 | } | |
686 | ||
687 | JRB jrb_insert_gen(JRB tree, Jval key, Jval val, | |
688 | int (*func)(Jval, Jval)) | |
689 | { | |
690 | int fnd; | |
691 | ||
692 | return jrb_insert_b(jrb_find_gte_gen(tree, key, func, &fnd), key, val); | |
693 | } | |
694 | ||
695 |
qpkg/jrb.h | ||
---|---|---|
1 | /* | |
2 | Libraries for fields, doubly-linked lists and red-black trees. | |
3 | Copyright (C) 2001 James S. Plank | |
4 | ||
5 | This library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
9 | ||
10 | This library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Lesser General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Lesser General Public | |
16 | License along with this library; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
18 | ||
19 | --------------------------------------------------------------------------- | |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ | |
21 | for instruction on how to use this library. | |
22 | ||
23 | Jim Plank | |
24 | plank@cs.utk.edu | |
25 | http://www.cs.utk.edu/~plank | |
26 | ||
27 | Associate Professor | |
28 | Department of Computer Science | |
29 | University of Tennessee | |
30 | 203 Claxton Complex | |
31 | 1122 Volunteer Blvd. | |
32 | Knoxville, TN 37996-3450 | |
33 | ||
34 | 865-974-4397 | |
35 | Fax: 865-974-4404 | |
36 | */ | |
37 | #ifndef _JRB_H_ | |
38 | #define _JRB_H_ | |
39 | ||
40 | #include "jval.h" | |
41 | ||
42 | /* Main jrb_node. You only ever use the fields | |
43 | flink | |
44 | blink | |
45 | k.key or k.ikey | |
46 | v.val | |
47 | */ | |
48 | ||
49 | ||
50 | typedef struct jrb_node { | |
51 | unsigned char red; | |
52 | unsigned char internal; | |
53 | unsigned char left; | |
54 | unsigned char roothead; /* (bit 1 is root, bit 2 is head) */ | |
55 | struct jrb_node *flink; | |
56 | struct jrb_node *blink; | |
57 | struct jrb_node *parent; | |
58 | Jval key; | |
59 | Jval val; | |
60 | } *JRB; | |
61 | ||
62 | ||
63 | extern JRB make_jrb(void); /* Creates a new rb-tree */ | |
64 | ||
65 | ||
66 | /* Creates a node with key key and val val and inserts it into the tree. | |
67 | jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=, | |
68 | jrb_insertg uses func() */ | |
69 | ||
70 | extern JRB jrb_insert_str(JRB tree, char *key, Jval val); | |
71 | extern JRB jrb_insert_int(JRB tree, int ikey, Jval val); | |
72 | extern JRB jrb_insert_dbl(JRB tree, double dkey, Jval val); | |
73 | extern JRB jrb_insert_gen(JRB tree, Jval key, Jval val, int (*func)(Jval,Jval)); | |
74 | ||
75 | /* returns an external node in t whose value is equal k. Returns NULL if | |
76 | there is no such node in the tree */ | |
77 | ||
78 | extern JRB jrb_find_str(JRB root, char *key); | |
79 | extern JRB jrb_find_int(JRB root, int ikey); | |
80 | extern JRB jrb_find_dbl(JRB root, double dkey); | |
81 | extern JRB jrb_find_gen(JRB root, Jval, int (*func)(Jval, Jval)); | |
82 | ||
83 | ||
84 | /* returns an external node in t whose value is equal | |
85 | k or whose value is the smallest value greater than k. Sets found to | |
86 | 1 if the key was found, and 0 otherwise. */ | |
87 | ||
88 | extern JRB jrb_find_gte_str(JRB root, char *key, int *found); | |
89 | extern JRB jrb_find_gte_int(JRB root, int ikey, int *found); | |
90 | extern JRB jrb_find_gte_dbl(JRB root, double dkey, int *found); | |
91 | extern JRB jrb_find_gte_gen(JRB root, Jval key, | |
92 | int (*func)(Jval, Jval), int *found); | |
93 | ||
94 | ||
95 | /* Creates a node with key key and val val and inserts it into the | |
96 | tree before/after node nd. Does not check to ensure that you are | |
97 | keeping the correct order */ | |
98 | ||
99 | extern void jrb_delete_node(JRB node); /* Deletes and frees a node (but | |
100 | not the key or val) */ | |
101 | extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */ | |
102 | ||
103 | extern Jval jrb_val(JRB node); /* Returns node->v.val -- this is to shut | |
104 | lint up */ | |
105 | ||
106 | extern int jrb_nblack(JRB n); /* returns # of black nodes in path from | |
107 | n to the root */ | |
108 | int jrb_plength(JRB n); /* returns the # of nodes in path from | |
109 | n to the root */ | |
110 | ||
111 | #define jrb_first(n) ((n)->flink) | |
112 | #define jrb_last(n) ((n)->blink) | |
113 | #define jrb_next(n) ((n)->flink) | |
114 | #define jrb_prev(n) ((n)->blink) | |
115 | #define jrb_empty(t) ((t)->flink == (t)) | |
116 | #ifndef jrb_nil | |
117 | #define jrb_nil(t) (t) | |
118 | #endif | |
119 | ||
120 | #define jrb_traverse(ptr, lst) \ | |
121 | for(ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr)) | |
122 | ||
123 | #define jrb_rtraverse(ptr, lst) \ | |
124 | for(ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr)) | |
125 | ||
126 | #endif |
qpkg/jval.c | ||
---|---|---|
1 | /* | |
2 | Libraries for fields, doubly-linked lists and red-black trees. | |
3 | Copyright (C) 2001 James S. Plank | |
4 | ||
5 | This library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
9 | ||
10 | This library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Lesser General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Lesser General Public | |
16 | License along with this library; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
18 | ||
19 | --------------------------------------------------------------------------- | |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ | |
21 | for instruction on how to use this library. | |
22 | ||
23 | Jim Plank | |
24 | plank@cs.utk.edu | |
25 | http://www.cs.utk.edu/~plank | |
26 | ||
27 | Associate Professor | |
28 | Department of Computer Science | |
29 | University of Tennessee | |
30 | 203 Claxton Complex | |
31 | 1122 Volunteer Blvd. | |
32 | Knoxville, TN 37996-3450 | |
33 | ||
34 | 865-974-4397 | |
35 | Fax: 865-974-4404 | |
36 | */ | |
37 | #include <stdio.h> | |
38 | #include <string.h> | |
39 | #include "jval.h" | |
40 | ||
41 | Jval JNULL; | |
42 | ||
43 | Jval new_jval_i(int i) { | |
44 | Jval j; | |
45 | j.i = i; | |
46 | return j; | |
47 | } | |
48 | ||
49 | Jval new_jval_l(long l) { | |
50 | Jval j; | |
51 | j.l = l; | |
52 | return j; | |
53 | } | |
54 | ||
55 | Jval new_jval_f(float f) { | |
56 | Jval j; | |
57 | j.f = f; | |
58 | return j; | |
59 | } | |
60 | ||
61 | Jval new_jval_d(double d) { | |
62 | Jval j; | |
63 | j.d = d; | |
64 | return j; | |
65 | } | |
66 | ||
67 | Jval new_jval_v(void *v) { | |
68 | Jval j; | |
69 | j.v = v; | |
70 | return j; | |
71 | } | |
72 | ||
73 | Jval new_jval_s(char *s) { | |
74 | Jval j; | |
75 | j.s = s; | |
76 | return j; | |
77 | } | |
78 | ||
79 | Jval new_jval_c(char c) { | |
80 | Jval j; | |
81 | j.c = c; | |
82 | return j; | |
83 | } | |
84 | ||
85 | Jval new_jval_uc(unsigned char uc) { | |
86 | Jval j; | |
87 | j.uc = uc; | |
88 | return j; | |
89 | } | |
90 | ||
91 | Jval new_jval_sh(short sh) { | |
92 | Jval j; | |
93 | j.sh = sh; | |
94 | return j; | |
95 | } | |
96 | ||
97 | Jval new_jval_ush(unsigned short ush) { | |
98 | Jval j; | |
99 | j.ush = ush; | |
100 | return j; | |
101 | } | |
102 | ||
103 | Jval new_jval_ui(unsigned int i) { | |
104 | Jval j; | |
105 | j.i = i; | |
106 | return j; | |
107 | } | |
108 | ||
109 | Jval new_jval_iarray(int i0, int i1) { | |
110 | Jval j; | |
111 | j.iarray[0] = i0; | |
112 | j.iarray[1] = i1; | |
113 | return j; | |
114 | } | |
115 | ||
116 | Jval new_jval_farray(float f0, float f1) { | |
117 | Jval j; | |
118 | j.farray[0] = f0; | |
119 | j.farray[1] = f1; | |
120 | return j; | |
121 | } | |
122 | ||
123 | Jval new_jval_carray_nt(char *carray) { | |
124 | Jval j; | |
125 | int i; | |
126 | ||
127 | for (i = 0; i < 8 && carray[i] != '\0'; i++) { | |
128 | j.carray[i] = carray[i]; | |
129 | } | |
130 | if (i < 8) j.carray[i] = carray[i]; | |
131 | return j; | |
132 | } | |
133 | ||
134 | Jval new_jval_carray_nnt(char *carray) { | |
135 | Jval j; | |
136 | ||
137 | memcpy(j.carray, carray, 8); | |
138 | return j; | |
139 | } | |
140 | ||
141 | int jval_i(Jval j) { | |
142 | return j.i; | |
143 | } | |
144 | ||
145 | long jval_l(Jval j) { | |
146 | return j.l; | |
147 | } | |
148 | ||
149 | float jval_f(Jval j) { | |
150 | return j.f; | |
151 | } | |
152 | ||
153 | double jval_d(Jval j) { | |
154 | return j.d; | |
155 | } | |
156 | ||
157 | void *jval_v(Jval j) { | |
158 | return j.v; | |
159 | } | |
160 | ||
161 | char *jval_s(Jval j) { | |
162 | return j.s; | |
163 | } | |
164 | ||
165 | char jval_c(Jval j) { | |
166 | return j.c; | |
167 | } | |
168 | ||
169 | unsigned char jval_uc(Jval j) { | |
170 | return j.uc; | |
171 | } | |
172 | ||
173 | short jval_sh(Jval j) { | |
174 | return j.sh; | |
175 | } | |
176 | ||
177 | unsigned short jval_ush(Jval j) { | |
178 | return j.ush; | |
179 | } | |
180 | ||
181 | unsigned int jval_ui(Jval j) { | |
182 | return j.ui; | |
183 | } | |
184 | ||
185 | int *jval_iarray(Jval j) { | |
186 | return j.iarray; | |
187 | } | |
188 | ||
189 | float *jval_farray(Jval j) { | |
190 | return j.farray; | |
191 | } | |
192 | ||
193 | char *jval_carray(Jval j) { | |
194 | return j.carray; | |
195 | } | |
196 |
qpkg/jval.h | ||
---|---|---|
1 | /* | |
2 | Libraries for fields, doubly-linked lists and red-black trees. | |
3 | Copyright (C) 2001 James S. Plank | |
4 | ||
5 | This library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
9 | ||
10 | This library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Lesser General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Lesser General Public | |
16 | License along with this library; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
18 | ||
19 | --------------------------------------------------------------------------- | |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ | |
21 | for instruction on how to use this library. | |
22 | ||
23 | Jim Plank | |
24 | plank@cs.utk.edu | |
25 | http://www.cs.utk.edu/~plank | |
26 | ||
27 | Associate Professor | |
28 | Department of Computer Science | |
29 | University of Tennessee | |
30 | 203 Claxton Complex | |
31 | 1122 Volunteer Blvd. | |
32 | Knoxville, TN 37996-3450 | |
33 | ||
34 | 865-974-4397 | |
35 | Fax: 865-974-4404 | |
36 | */ | |
37 | #ifndef _JVAL_H_ | |
38 | #define _JVAL_H_ | |
39 | ||
40 | /* The Jval -- a type that can hold any 8-byte type */ | |
41 | ||
42 | typedef union { | |
43 | int i; | |
44 | long l; | |
45 | float f; | |
46 | double d; | |
47 | void *v; | |
48 | char *s; | |
49 | char c; | |
50 | unsigned char uc; | |
51 | short sh; | |
52 | unsigned short ush; | |
53 | unsigned int ui; | |
54 | int iarray[2]; | |
55 | float farray[2]; | |
56 | char carray[8]; | |
57 | unsigned char ucarray[8]; | |
58 | } Jval; | |
59 | ||
60 | extern Jval new_jval_i(int); | |
61 | extern Jval new_jval_l(long); | |
62 | extern Jval new_jval_f(float); | |
63 | extern Jval new_jval_d(double); | |
64 | extern Jval new_jval_v(void *); | |
65 | extern Jval new_jval_s(char *); | |
66 | extern Jval new_jval_c(char); | |
67 | extern Jval new_jval_uc(unsigned char); | |
68 | extern Jval new_jval_sh(short); | |
69 | extern Jval new_jval_ush(unsigned short); | |
70 | extern Jval new_jval_ui(unsigned int); | |
71 | extern Jval new_jval_iarray(int, int); | |
72 | extern Jval new_jval_farray(float, float); | |
73 | extern Jval new_jval_carray_nt(char *); /* Carray is null terminated */ | |
74 | extern Jval new_jval_carray_nnt(char *); /* Carray is not null terminated */ | |
75 | /* For ucarray -- use carray, because it uses memcpy */ | |
76 | ||
77 | extern Jval JNULL; | |
78 | ||
79 | extern int jval_i(Jval); | |
80 | extern long jval_l(Jval); | |
81 | extern float jval_f(Jval); | |
82 | extern double jval_d(Jval); | |
83 | extern void *jval_v(Jval); | |
84 | extern char *jval_s(Jval); | |
85 | extern char jval_c(Jval); | |
86 | extern unsigned char jval_uc(Jval); | |
87 | extern short jval_sh(Jval); | |
88 | extern unsigned short jval_ush(Jval); | |
89 | extern unsigned int jval_ui(Jval); | |
90 | extern int *jval_iarray(Jval); | |
91 | extern float *jval_farray(Jval); | |
92 | extern char *jval_carray(Jval); | |
93 | ||
94 | #endif |
Branches:
master