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
1Copyright (C) 1991, 1999 Free Software Foundation, Inc.
259 Temple Place, Suite 330, Boston, MA 02111-1307 USA
3Everyone is permitted to copy and distribute verbatim copies
4of 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
444END 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
460one line to give the library's name and an idea of what it does.
461Copyright (C) year name of author
462
463This library is free software; you can redistribute it and/or
464modify it under the terms of the GNU Lesser General Public
465License as published by the Free Software Foundation; either
466version 2.1 of the License, or (at your option) any later version.
467
468This library is distributed in the hope that it will be useful,
469but WITHOUT ANY WARRANTY; without even the implied warranty of
470MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
471Lesser General Public License for more details.
472
473You should have received a copy of the GNU Lesser General Public
474License along with this library; if not, write to the Free Software
475Foundation, 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
484Yoyodyne, Inc., hereby disclaims all copyright interest in
485the library `Frob' (a library for tweaking knobs) written
486by James Random Hacker.
487
488signature of Ty Coon, 1 April 1990
489Ty 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
509References
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
1CFLAGS = -Wall -Wshadow -g
1CFLAGS = -Wall -Wshadow -g -O
22# -O, so that we get data flow analysis, which helps to find more bugs
3#LDFLAGS=-pg
34
4OBJS = gobble.o id.o prereq.o qpkg.o
5OBJS = gobble.o id.o prereq.o qpkg.o jrb.o jval.o
56
67all: qpkg
78
qpkg/README.jrb
1Libraries for fields, doubly-linked lists and red-black trees.
2Copyright (C) 2001 James S. Plank
3
4This library is free software; you can redistribute it and/or
5modify it under the terms of the GNU Lesser General Public
6License as published by the Free Software Foundation; either
7version 2.1 of the License, or (at your option) any later version.
8
9This library is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12Lesser General Public License for more details.
13
14You should have received a copy of the GNU Lesser General Public
15License along with this library; if not, write to the Free Software
16Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18---------------------------------------------------------------------------
19Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
20for instruction on how to use this library.
21
22Jim Plank
23plank@cs.utk.edu
24http://www.cs.utk.edu/~plank
25
26Associate Professor
27Department of Computer Science
28University of Tennessee
29203 Claxton Complex
301122 Volunteer Blvd.
31Knoxville, TN 37996-3450
32
33     865-974-4397
34Fax: 865-974-4404
qpkg/jrb.c
1/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 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
48static void mk_new_int(JRB l, JRB r, JRB p, int il);
49static JRB lprev(JRB n);
50static JRB rprev(JRB n);
51static void recolor(JRB n);
52static void single_rotate(JRB y, int l);
53static void jrb_print_tree(JRB t, int level);
54static 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
79static 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
91static 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
106static 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
137JRB 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
147JRB 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
157JRB 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
170JRB 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
198JRB 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
206JRB 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
230JRB 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
239JRB 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
263JRB 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
272JRB 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
300JRB 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
309static 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
342static 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
387static 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
431void 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
553void 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
578void 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
605int 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
620int 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
635void 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
648Jval jrb_val(JRB n)
649{
650  return n->val;
651}
652
653#if 0
654static JRB jrb_insert_a(JRB nd, Jval key, Jval val)
655{
656  return jrb_insert_b(nd->flink, key, val);
657}
658#endif
659
660JRB 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
669JRB 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
678JRB 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
687JRB 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/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 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
50typedef 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
63extern 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
70extern JRB jrb_insert_str(JRB tree, char *key, Jval val);
71extern JRB jrb_insert_int(JRB tree, int ikey, Jval val);
72extern JRB jrb_insert_dbl(JRB tree, double dkey, Jval val);
73extern 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
78extern JRB jrb_find_str(JRB root, char *key);
79extern JRB jrb_find_int(JRB root, int ikey);
80extern JRB jrb_find_dbl(JRB root, double dkey);
81extern 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
88extern JRB jrb_find_gte_str(JRB root, char *key, int *found);
89extern JRB jrb_find_gte_int(JRB root, int ikey, int *found);
90extern JRB jrb_find_gte_dbl(JRB root, double dkey, int *found);
91extern 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
99extern void jrb_delete_node(JRB node); /* Deletes and frees a node (but
100                                              not the key or val) */
101extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */
102
103extern Jval jrb_val(JRB node); /* Returns node->v.val -- this is to shut
104                                       lint up */
105
106extern int jrb_nblack(JRB n); /* returns # of black nodes in path from
107                                    n to the root */
108int 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/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 865-974-4404
36 */
37#include <stdio.h>
38#include <string.h>
39#include "jval.h"
40
41Jval JNULL;
42
43Jval new_jval_i(int i) {
44  Jval j;
45  j.i = i;
46  return j;
47}
48
49Jval new_jval_l(long l) {
50  Jval j;
51  j.l = l;
52  return j;
53}
54
55Jval new_jval_f(float f) {
56  Jval j;
57  j.f = f;
58  return j;
59}
60
61Jval new_jval_d(double d) {
62  Jval j;
63  j.d = d;
64  return j;
65}
66
67Jval new_jval_v(void *v) {
68  Jval j;
69  j.v = v;
70  return j;
71}
72
73Jval new_jval_s(char *s) {
74  Jval j;
75  j.s = s;
76  return j;
77}
78
79Jval new_jval_c(char c) {
80  Jval j;
81  j.c = c;
82  return j;
83}
84
85Jval new_jval_uc(unsigned char uc) {
86  Jval j;
87  j.uc = uc;
88  return j;
89}
90
91Jval new_jval_sh(short sh) {
92  Jval j;
93  j.sh = sh;
94  return j;
95}
96
97Jval new_jval_ush(unsigned short ush) {
98  Jval j;
99  j.ush = ush;
100  return j;
101}
102
103Jval new_jval_ui(unsigned int i) {
104  Jval j;
105  j.i = i;
106  return j;
107}
108
109Jval 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
116Jval 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
123Jval 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
134Jval new_jval_carray_nnt(char *carray) {
135  Jval j;
136
137  memcpy(j.carray, carray, 8);
138  return j;
139}
140
141int jval_i(Jval j) {
142  return j.i;
143}
144
145long jval_l(Jval j) {
146  return j.l;
147}
148
149float jval_f(Jval j) {
150  return j.f;
151}
152
153double jval_d(Jval j) {
154  return j.d;
155}
156
157void *jval_v(Jval j) {
158  return j.v;
159}
160
161char *jval_s(Jval j) {
162  return j.s;
163}
164
165char jval_c(Jval j) {
166  return j.c;
167}
168
169unsigned char jval_uc(Jval j) {
170  return j.uc;
171}
172
173short jval_sh(Jval j) {
174  return j.sh;
175}
176
177unsigned short jval_ush(Jval j) {
178  return j.ush;
179}
180
181unsigned int jval_ui(Jval j) {
182  return j.ui;
183}
184
185int *jval_iarray(Jval j) {
186  return j.iarray;
187}
188
189float *jval_farray(Jval j) {
190  return j.farray;
191}
192
193char *jval_carray(Jval j) {
194  return j.carray;
195}
196
qpkg/jval.h
1/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 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
42typedef 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
60extern Jval new_jval_i(int);
61extern Jval new_jval_l(long);
62extern Jval new_jval_f(float);
63extern Jval new_jval_d(double);
64extern Jval new_jval_v(void *);
65extern Jval new_jval_s(char *);
66extern Jval new_jval_c(char);
67extern Jval new_jval_uc(unsigned char);
68extern Jval new_jval_sh(short);
69extern Jval new_jval_ush(unsigned short);
70extern Jval new_jval_ui(unsigned int);
71extern Jval new_jval_iarray(int, int);
72extern Jval new_jval_farray(float, float);
73extern Jval new_jval_carray_nt(char *); /* Carray is null terminated */
74extern Jval new_jval_carray_nnt(char *); /* Carray is not null terminated */
75       /* For ucarray -- use carray, because it uses memcpy */
76
77extern Jval JNULL;
78
79extern int jval_i(Jval);
80extern long jval_l(Jval);
81extern float jval_f(Jval);
82extern double jval_d(Jval);
83extern void *jval_v(Jval);
84extern char *jval_s(Jval);
85extern char jval_c(Jval);
86extern unsigned char jval_uc(Jval);
87extern short jval_sh(Jval);
88extern unsigned short jval_ush(Jval);
89extern unsigned int jval_ui(Jval);
90extern int *jval_iarray(Jval);
91extern float *jval_farray(Jval);
92extern char *jval_carray(Jval);
93
94#endif

Archive Download the corresponding diff file

Branches:
master



interactive