From 18aa403d822ab6182bf58eca3e1b02fae2748e67 Mon Sep 17 00:00:00 2001 From: Michael Zucchi Date: Mon, 29 Apr 2019 14:48:40 +0930 Subject: [PATCH 1/1] initial libeze-2.0 import --- .gitignore | 2 + CHANGES | 50 ++++ COPYING | 674 ++++++++++++++++++++++++++++++++++++++++++++++++++ Makefile | 75 ++++++ README | 331 +++++++++++++++++++++++++ ez-bitset.c | 247 ++++++++++++++++++ ez-bitset.h | 97 ++++++++ ez-blob.c | 308 +++++++++++++++++++++++ ez-blob.h | 177 +++++++++++++ ez-list.h | 266 ++++++++++++++++++++ ez-node.h | 129 ++++++++++ ez-port.c | 117 +++++++++ ez-port.h | 73 ++++++ ez-set.c | 313 +++++++++++++++++++++++ ez-set.h | 240 ++++++++++++++++++ ez-tree.c | 474 +++++++++++++++++++++++++++++++++++ ez-tree.h | 207 ++++++++++++++++ test-bitset.c | 136 ++++++++++ test-blob.c | 274 ++++++++++++++++++++ test-list.c | 157 ++++++++++++ test-port.c | 120 +++++++++ test-set.c | 136 ++++++++++ test-tree.c | 477 +++++++++++++++++++++++++++++++++++ 23 files changed, 5080 insertions(+) create mode 100644 .gitignore create mode 100644 CHANGES create mode 100644 COPYING create mode 100644 Makefile create mode 100644 README create mode 100644 ez-bitset.c create mode 100644 ez-bitset.h create mode 100644 ez-blob.c create mode 100644 ez-blob.h create mode 100644 ez-list.h create mode 100644 ez-node.h create mode 100644 ez-port.c create mode 100644 ez-port.h create mode 100644 ez-set.c create mode 100644 ez-set.h create mode 100644 ez-tree.c create mode 100644 ez-tree.h create mode 100644 test-bitset.c create mode 100644 test-blob.c create mode 100644 test-list.c create mode 100644 test-port.c create mode 100644 test-set.c create mode 100644 test-tree.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..1905831 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +.deps +libeze.a diff --git a/CHANGES b/CHANGES new file mode 100644 index 0000000..17606dc --- /dev/null +++ b/CHANGES @@ -0,0 +1,50 @@ + +Version 2.0 24/5/2019 + +Changes + + * Fixed some aliasing issues with ez_list and an embarassing + and fatal bug in ez_list_remtail(). + + * Added a list test programme. + + * Tree API changed to take function pointers where necessary. + Removed _new() and _free and added a static initialiser. + +Details + + * Changed the list and node list pointers to volatile to avoid + some aliasing issues that generated bad code. + + * Reworked the insert functions to be more understandable. + ez_list_insert() was changed to insert before the given + node. ez_list_insert_after() implements the previous behavoiur. + + * Fixed ez_list_remtail() to use the correct tail pointer. + + * The tree no longer holds the function pointers, they are + supplied where necessary. + + + ez_tree_new(), ez_tree_free() removed. + + + ez_tree_clear() take a node free function. + + + ez_tree_get(), ez_tree_put(), ez_tree_remove() and + ez_tree_scan_init() take a node compare function. + + + Added a static initialiser macro EZ_INIT_TREE(tree) + + * Enabled ez_tree_scan_put(). It changes the current tree scan + node. + + * Internally the tree code now uses functions to access the + pointers rather than directly. + + * Added a bounds check to the functions which probe the tree + and parameterise it's madnitude. + + * Minor makefile and doc improvements. + +Version 1.0 24/1/2019-01 + + * Initial release. diff --git a/COPYING b/COPYING new file mode 100644 index 0000000..94a9ed0 --- /dev/null +++ b/COPYING @@ -0,0 +1,674 @@ + GNU GENERAL PUBLIC LICENSE + Version 3, 29 June 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU General Public License is a free, copyleft license for +software and other kinds of works. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. We, the Free Software Foundation, use the +GNU General Public License for most of our software; it applies also to +any other work released this way by its authors. You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you have +certain responsibilities if you distribute copies of the software, or if +you modify it: responsibilities to respect the freedom of others. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, receive +or can get the source code. And you must show them these terms so they +know their rights. + + Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + + For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + + Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the manufacturer +can do so. This is fundamentally incompatible with the aim of +protecting users' freedom to change the software. The systematic +pattern of such abuse occurs in the area of products for individuals to +use, which is precisely where it is most unacceptable. Therefore, we +have designed this version of the GPL to prohibit the practice for those +products. If such problems arise substantially in other domains, we +stand ready to extend this provision to those domains in future versions +of the GPL, as needed to protect the freedom of users. + + Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish to +avoid the special danger that patents applied to a free program could +make it effectively proprietary. To prevent this, the GPL assures that +patents cannot be used to render the program non-free. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Use with the GNU Affero General Public License. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + +Also add information on how to contact you by electronic and paper mail. + + If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + + Copyright (C) + This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, your program's commands +might be different; for a GUI interface, you would use an "about box". + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +. + + The GNU General Public License does not permit incorporating your program +into proprietary programs. If your program is a subroutine library, you +may consider it more useful to permit linking proprietary applications with +the library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. But first, please read +. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..3d0b6ce --- /dev/null +++ b/Makefile @@ -0,0 +1,75 @@ + +CPPFLAGS=-I. +CFLAGS=-O2 -fPIC -Wall -mtune=native +test_LDLIBS=-lpthread -lrt +ARFLAGS=rvsUc +VERSION=2.0 + +SRCS= \ + ez-bitset.c \ + ez-blob.c \ + ez-port.c \ + ez-set.c \ + ez-tree.c + +HEADERS = \ + ez-bitset.h \ + ez-blob.h \ + ez-list.h \ + ez-node.h \ + ez-port.h \ + ez-set.h \ + ez-tree.h + +test_SRCS=test-bitset.c test-blob.c test-port.c test-set.c test-tree.c test-list.c + +TESTS=$(test_SRCS:.c=) + +OBJS=$(SRCS:.c=.o) + +all: libeze.a($(OBJS)) + +libeze.a: libeze.a($(OBJS)) +tests: $(TESTS) +check: tests + for test in $(TESTS) ; do \ + echo $$test ; \ + ./$$test || exit 1; \ + done + +test-%: test-%.o + $(CC) $(CFLAGS) -o $@ $< libeze.a $(test_LDLIBS) + +test-bitset: libeze.a(ez-bitset.o) +test-blob: libeze.a(ez-blob.o) +test-port: libeze.a(ez-port.o) +test-set: libeze.a(ez-set.o) +test-tree: libeze.a(ez-tree.o) + +dist: libeze-$(VERSION).tar.gz + +libeze-$(VERSION).tar.gz: $(HEADERS) $(SRCS) $(test_SRCS) Makefile README CHANGES COPYING + tar -c \ + --transform=s@^@libeze-$(VERSION)/@ \ + -f $@ \ + -z \ + $^ + +clean: + rm -f libeze.a + rm -f *.o + rm -f $(TESTS) + rm -rf .deps + +.deps/%.d: %.c + @rm -f $@ + @install -d .deps $(@D) + @$(CC) -MM $(CPPFLAGS) $< > $@ || rm $@ + +# Without this the behavior of libeze.a($(OBJS)) changes when one includes the .d files. +.INTERMEDIATE: $(OBJS) +.NOTPARALLEL: + +ifeq ($(filter clean dist,$(MAKECMDGOALS)),) +-include $(patsubst %.c,.deps/%.d,$(SRCS) $(test_SRCS)) +endif diff --git a/README b/README new file mode 100644 index 0000000..4af8ae9 --- /dev/null +++ b/README @@ -0,0 +1,331 @@ + +INTRODUCTION +------------ + +A small basic static utility library. + +A couple of abstract data types (ADTs), a C struct serialiser and an +inter-thread IPC primitive. + +Goals: + + * Aim for best implementation of an algorithm; + * Clean readable source; + * Small source size; + * Small code size; + * Consistent api and features where it makes sense; + * No internal checking or assertions where it make sense; + * Low level, highly re-usable building blocks where it makes sense. + +Some functions were originally part of ezesdk +. + +See CHANGES for the release log. + +COMPILING & USING +----------------- + +Check the makefile for build options. + +$ make + +Will build libeze.a. + +$ make test + +Will build some test programs. They are just prototyping development +checks rather than formal tests. They confirm basic operation and +when run through valgrind check for memory leaks. + +To use include the relevant header files and add libeze.a to the link +line. If using ez_port() then the binary must be linked with -lrt. + +SOME DETAILS +------------ + +Copious comments in the header describe the interface. Liberal +comments in the source describe the implementation. + +The data types use void pointers for user types to avoid constantly +needing to cast, even though they have "super-type" requirements. +Deal with it. + +In general there is no sanity checking, bad inputs will lead to bad +outputs. Deal with that too. + +Reusability +- - - - - - + +The container data types work on the principal that the object being +contained also includes the space required by the implementation. +That is, they must derive from an 'entry' type. This allows most +operations to function without extra dynamic memory allocation and +thus cannot fail. It also means that objects can only directly belong +to one container at any given time. General purpose containers +allowing multi-membership can be trivally implemented atop these +primitives. + +As a result, in general, no valid operations can fail and invalid +usage results in undefined behaviour. Internally no checking is +performed to validate invalid usage, checking is only performed when +it falls outside of knowledge of the internal implementation. + +The container types share a compatible memory layout - that is they +require 2 pointer-sized struct members of space. This allows objects +to be moved betwen different containers rapidly and without memory +allocation. + +An outline of the basic types follows. The API is documented in the +header and the internal design decisions are documented in the source. + +Data Types +========== + +Mostly re-usable low-level components apart from the bit-set. + +ez_bitset +- - - - - + +A specialised set with 32-bit integer keys. + +The current implementation uses a 3-tier bitmap. This is not +particularly space efficient for large contiguous or very sparse +sets. But it is efficient for very large slightly sparse sets! + +It requires dynamic memory. Currently a memory allocation failure +during operation will result in undefined behaviour. + +ez_list +- - - - + +This is an AmigaOS "exec" style list (actually an exec 'min' list). +It is the original source of the idea of the containee supplying the +memory required for the container. Also of having small reliable and +reusable building blocks. + +It is implemented entirely as inline functions in the header file. + +It requires no dynamic memory for operation, not even for the list. + +ez_set +- - - + +A hashtable / set with dynamic re-hashing. + +The API is a `set' api but it supports general `hash table' operation, +only requiring that table entry also contain it's key, which is +typical. It is trivial to implement a general key+value map atop it. + +The current implementation is a basic chained hash table. It also +contains a few basic hashing functions. + +It requires dynamic memory for managing the chain table. But beyond +the initial allocation no allocation failure is fatal; it may only +degrade performance. + +ez_tree +- - - - + +This is a balanced binary tree. + +It is implemented as an AVL tree. + +Effort was been made to fit the nodes into 2 pointers. + +Further significant effort has been made to reduce the source-code +size (and to a lesser extent the binary text size). It is +approximately both half the source-code size and binary-text size of +libavl's avl tree implementation, whilst providing comparable +features. + +It requires no dynamic allocation for itself. Thus no operations can +fail (assuming the node_hash and node_equals functions cannot fail). + +I don't know why I wrote it, I never use trees. + +Inter-Process Communication +=========================== + +Routines for IPC or other related stuff. + +ez_blob +- - - - + +A table based C structure serialiser. + +The table should provide enough information to serialise most common C +data structures including nested and linked types. + +The implemented serialisation format is proprietary but it is possible +to implement others, for example BER, protocol buffers, IFF, etc. It +currently only implements forward-linked objects (trees with no parent +pointers or lists, no graphs). + +For some reason the compiler sometimes (but only sometimes?) does very +strange things when optimising this and produces about double the text +size. It does odd things like unroll and inline the free loop. + +ez_port +- - - - + +An inter-thread message passing primitive that supports poll(2). + +The current implementation uses posix message queues and expects mqd_t +to be a file descriptor. This is non-portable but is the case on +Linux and FreeBSD. + +Other implementations may be added in the future. + +It requires no dynamic memory for operation beyond the port. + +IDEAS +----- + +Some ideas on how to re-use the parts to extend the functionality. + +hash table +- - - - - + +To implements a general hash function, create a set with a node similar to this: + +struct hash_node { + struct ez_node hn; + void *key, *data; +}; + +And supply appropriate node_equals and node_hash callbacks. To +perform a lookup just initialise the key field of a node. + +linked hash table +- - - - - - - - - + +A linked hash table is a hash table that can be accessed randomly or +in insertion order. + +Add a list to the set. + +struct linked_table { + struct ez_set *set; + ez_list list; +}; + +Add a node to the node. + +struct linked_node { + struct ez_node hn; + struct ez_node link; +}; + +On insert, add the link node to the list. + +void *add(linked_table *table, linked_node *node) { + void *old = ez_set_put(table->set, node); + + ez_list_addtail(&table->list, &node->link); +} + +The list can be iterated normally but returns &linked_node.link rather +than linked_node. So to retrieve the linked node from the node link. + +void *get_node(const ez_node *link) { + return ((char *)link) - offsetof(struct linked_node, link); +} + +On remove, remove the link as well. + +void *remove(linked_table *table, linked_node *key) { + key = ez_set_remove(table->set, key); + if (key) + ez_node_remove(&key->link); +} + +A similar process can be used for multiple container membership, for +example a reverse list, trees, and so on. + +STATUS +------ + +Beta release. There are test programs but not proper tests. + +Most of the code is simple portable C but ez-port requires posix +message queues where mqd_t is a file descriptor (int). + +The tree requires that memory allocations and structure alignment is +to at least 4 bytes so that the bottom 3 bits of all pointers are 0. +This assumptions holds for any system i've ever touched. + +LINKS +----- + +Some links and references. + + o Directly related + - https://www.zedzone.space/software/libeze.html + Project page. + - https://www.zedzone.space/blog/tag/libeze + Related blog posts. + + o Exec Lists + - https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues + Nice overview of them. + + o AVL trees. + - `The Art of Computer Programming'' Volume 3, Chapter 6. Donald E. Knuth. + - http://adtinfo.org/ + GNU libavl has a good and very well documentated implementation. + - http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html + Badly formatted, hard to read. Can't say this was useful at all. + - https://en.wikipedia.org/wiki/AVL_tree + This is absolutely woeful, useless. It's worse than the page on Jesus. + + o Hash functions. + - https://www.burtleburtle.net/bob/hash/integer.html + Shift/add based integer hashes. + - https://github.com/skeeto/hash-prospector + Multiply/exclusiv-or based integer hashes. + - http://www.cse.yorku.ca/~oz/hash.html + Simple but decent string hash functions. + +LICENSE +------- + +The license for all source is the GNU General Public License, version 3 or later. + +COPYING for full details. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation, either version 3 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see + . + +The tree implementation took parts from libavl +so includes the Free Software Foundation Inc. as a copyright holder. + + Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc. + Copyright (C) 2019 Michael Zucchi + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 3 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. diff --git a/ez-bitset.c b/ez-bitset.c new file mode 100644 index 0000000..ae975fb --- /dev/null +++ b/ez-bitset.c @@ -0,0 +1,247 @@ +/* ez-bitset.c: Moderately Scalable set of 32-bit integers. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#include +#include +#include + +#include "ez-bitset.h" + +/** + * This implements a bitset using a 3-level sparse table. + * + * The final bits are stored as 32-bit integers. + * + * This is only moderately cpu and space efficient if large contiguous + * ranges are set. + */ + +/* ********************************************************************** */ +/* Private structs */ + +// L0B + L1B + L2B = 32 +#define L0B 9 +#define L1B 9 +#define L2B 14 + +#define L0 (1<l1; + struct level2 *l2 = scan->l2; + + while (scan->bits == 0 && scan->id0 < L0) { + if (l2) { + retrybit: + while (scan->id2 < L2) { + if ((scan->bits = l2->bits[scan->id2++])) { + scan->offset = (scan->offset & (~L2M << L2S)) | ((scan->id2-1) << L2S); + goto getbit; + } + } + } + + scan->id2 = 0; + + if (l1) { + retryl2: + while (scan->id1 < L1) { + if ((scan->l2 = l2 = l1->level2[scan->id1++])) { + scan->offset = (scan->offset & (~L1M<id1-1) << L1S); + goto retrybit; + } + } + } + + scan->id1 = 0; + + while (scan->id0 < L0) { + if ((scan->l1 = l1 = set->level1[scan->id0++])) { + scan->offset = (scan->offset & (~L0M << L0S)) | ((scan->id0-1) << L0S); + goto retryl2; + } + } + } + + if (scan->bits) { + int index; + getbit: + index = ffs(scan->bits) -1 ; + scan->bits &= ~(1<bit = index; + + return scan->offset + index; + } + + return ~0; +} + +/* ********************************************************************** */ + +ez_bitset *ez_bitset_new(void) { + return calloc(sizeof(ez_bitset), 1); +} + +void ez_bitset_free(ez_bitset *bs) { + ez_bitset_clear(bs); + free(bs); +} + +void ez_bitset_clear(ez_bitset *bs) { + for (int id0 = 0;id0level1[id0]; + + if (l1) { + for (int id1 = 0; id1 < L1; id1++) { + struct level2 *l2 = l1->level2[id1]; + + free(l2); + } + bs->level1[id0] = NULL; + free(l1); + } + + } + bs->count = 0; +} + +int ez_bitset_get(ez_bitset *bs, uint32_t bit) { + unsigned int id0 = (bit >> L0S); + unsigned int id1 = (bit >> L1S) & L1M; + unsigned int id2 = (bit >> L2S) & L2M; + unsigned int id3 = 1 << (bit & L3M); + + struct level1 *l1 = bs->level1[id0]; + + if (l1) { + struct level2 *l2 = l1->level2[id1]; + + if (l2) { + return (l2->bits[id2] & id3) != 0; + } + } + + return 0; +} + +int ez_bitset_set(ez_bitset *bs, uint32_t bit, int value) { + unsigned int id0 = (bit >> L0S); + unsigned int id1 = (bit >> L1S) & L1M; + unsigned int id2 = (bit >> L2S) & L2M; + unsigned int id3 = 1 << (bit & L3M); + struct level1 *l1 = bs->level1[id0]; + int old = 0; + + value = value != 0; + if (value) { + if (!l1) { + l1 = calloc(sizeof(*l1), 1); + bs->level1[id0] = l1; + } + struct level2 *l2 = l1->level2[id1]; + if (!l2) { + l2 = calloc(sizeof(*l2), 1); + l1->level2[id1] = l2; + } + old = (l2->bits[id2] & id3) != 0; + if (old ^ value) { + l2->bits[id2] |= id3; + bs->count += 1; + } + } else { + if (l1) { + struct level2 *l2 = l1->level2[id1]; + + if (l2) { + old = (l2->bits[id2] & id3) != 0; + if (old ^ value) { + l2->bits[id2] &= ~id3; + bs->count -= 1; + } + } + } + } + + return 0; + +} + +uint32_t ez_bitset_card(ez_bitset *bs) { + return bs->count; +} + +uint32_t ez_bitset_scan_init(ez_bitset *set, ez_bitset_scan *scan) { + memset(scan, 0, sizeof(*scan)); + scan->set = set; + return bitset_scan_next(set, scan); +} + +uint32_t ez_bitset_scan_next(ez_bitset_scan *scan) { + return bitset_scan_next(scan->set, scan); +} + +uint32_t ez_bitset_scan_remove(ez_bitset_scan *scan) { + struct level2 *l2 = scan->l2; + + l2->bits[scan->id2 - 1] &= ~(1<bit); + scan->set->count -= 1; + + return bitset_scan_next(scan->set, scan); +} diff --git a/ez-bitset.h b/ez-bitset.h new file mode 100644 index 0000000..75e69a3 --- /dev/null +++ b/ez-bitset.h @@ -0,0 +1,97 @@ +/* ez-bitset.c: Moderately Scalable set of 32-bit integers. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef _EZ_BITSET_H +#define _EZ_BITSET_H + +typedef struct ez_bitset ez_bitset; + +typedef struct ez_bitset_scan ez_bitset_scan; + +/** + * Scan state. + * + * This is public so it can be allocated on the stack, but the fields are opaque. + */ +struct ez_bitset_scan { + ez_bitset *set; + void *l1, *l2; + int id0, id1, id2; + uint32_t offset, bits, bit; +}; + +/** + * Allocate a new bitset. + */ +ez_bitset *ez_bitset_new(void); + +/** + * Clear all set bits from the bitset. + */ +void ez_bitset_clear(ez_bitset *bs); + +/** + * Free a bitset. + */ +void ez_bitset_free(ez_bitset *bs); + +/** + * Get a bit by index. + */ +int ez_bitset_get(ez_bitset *bs, uint32_t bit); + +/** + * Set a bit by index to a particular value. + * + * @return the previous value for this bit. + */ +int ez_bitset_set(ez_bitset *bs, uint32_t bit, int value); + +/** + * Return the cardinality of the set. The number of set bits. + */ +uint32_t ez_bitset_card(ez_bitset *bs); + +/** + * Initiate an iterative scan of all bits. Bits are scanned in order. + * + * If the bitset contains ~0 then a scan will ignore it. + * + * @return The first bit set. ~0 indicates none found. + */ +uint32_t ez_bitset_scan_init(ez_bitset *set, ez_bitset_scan *scan); + +/** + * Move to the next bit. + * + * @return the next set bit or ~0. + */ +uint32_t ez_bitset_scan_next(ez_bitset_scan *scan); + +/** + * Clear this bit and move to the next one. + * + * This must only be called when a set bit was found in a previous + * scan call. + * + * @return the next set bit or ~0. + */ +uint32_t ez_bitset_scan_remove(ez_bitset_scan *scan); + +#endif diff --git a/ez-blob.c b/ez-blob.c new file mode 100644 index 0000000..c6a914e --- /dev/null +++ b/ez-blob.c @@ -0,0 +1,308 @@ +/* ez-blob.h: Serialising description and serialiser. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#include +#include +#include + +#include + +#include "ez-blob.h" + +/* + This implements a basic 'high performance' serialisation based on the + descriptors. + + Fields are encoded in the same order as the descriptor with no + labelling. Therefore the same descriptor must be used on both ends. + Fields may be at arbitrary alignments. + + primitives + encoded in machine order at native size + + strings + 4-byte length followed by characters. No nul termination. A length + of ~0 indicates a null string pointer. + + arrays + 4-byte length followed by data. ** currently null pointer arrays with zero length are converted to a zero-length array. + + struct + 4-byte length followed by blob-encoded data. + + pointer + 4-byte length followed by blob-encoded data. A length of ~0 + indicates a null pointer. + +*/ + +static const int primitive_size[EZ_BLOB_FLOAT64+1] = { + 1, 2, 4, 8, + 4, 8 +}; + +size_t ez_blob_size(const ez_blob_desc *d, const void *p) { + size_t size = 0; + + for (;(d->bd_type != EZ_BLOB_END);d++) { + if (d->bd_type <= EZ_BLOB_FLOAT64) { + size += primitive_size[d->bd_type]; + } else { + const void *v = p + d->bd_offset; + switch (d->bd_type) { + case EZ_BLOB_STRING: { + char *s = ((char **)v)[0]; + size += s ? 4 + strlen(s) : 4; + break; } + case EZ_BLOB_ARRAY: + size += 4 + ((const struct ez_blob_array *)v)->size; + break; + case EZ_BLOB_STRUCT: { + const void *sp = v; + size += 4 + ez_blob_size(d->bd_table, sp); + break; } + case EZ_BLOB_POINTER: { + const void *s = ((const void * const *)v)[0]; + size += s ? 4 + ez_blob_size(d->bd_table, s) : 4; + break; } + default: + break; + } + } + } + + return size; +} + +void ez_blob_free_raw(const ez_blob_desc *d, void *p) { + for (;(d->bd_type != EZ_BLOB_END);d++) { + void *v = p + d->bd_offset; + + switch (d->bd_type) { + case EZ_BLOB_STRING: + free(((char **)v)[0]); + break; + case EZ_BLOB_ARRAY: + free(((struct ez_blob_array *)v)->data); + break; + case EZ_BLOB_STRUCT: + ez_blob_free_raw(d->bd_table, v); + break; + case EZ_BLOB_POINTER: + ez_blob_free(d->bd_table, ((void **)v)[0]); + break; + default: + break; + } + } +} + +void ez_blob_free(const ez_blob_desc *d, void *p) { + if (p) { + ez_blob_free_raw(d, p); + free(p); + } +} + +void *ez_blob_decode_raw(const ez_blob_desc *d, const char *b, size_t size, void *p) { + const char *be = b + size; + + memset(p, 0, d->bd_offset); + + for (;(d->bd_type != EZ_BLOB_END);d++) { + void *v = (p + d->bd_offset); + + if (d->bd_type <= EZ_BLOB_FLOAT64) { + int psize = primitive_size[d->bd_type]; + + if (b + psize > be) + goto fail; + memcpy(v, b, psize); + b += psize; + } else if (d->bd_type <= EZ_BLOB_LAST) { + uint32_t ss; + + if (b + 4 > be) + goto fail; + memcpy(&ss, b, 4); + b += 4; + + switch (d->bd_type) { + case EZ_BLOB_STRING: { + char *s = NULL; + + if (ss != ~0) { + if (b + ss > be) + goto fail; + if ((s = malloc((size_t)ss + 1)) == NULL) + goto fail; + memcpy(s, b, ss); + s[ss] = 0; + b += ss; + } + ((char **)v)[0] = s; + break; } + case EZ_BLOB_ARRAY: { + struct ez_blob_array *a = v; + + if (b + ss > be) + goto fail; + a->size = ss; + if ((a->data = malloc(ss)) == NULL) + goto fail; + memcpy(a->data, b, ss); + b += ss; + break; } + case EZ_BLOB_STRUCT: + if (b + ss > be) + goto fail; + + if (ez_blob_decode_raw(d->bd_table, b, ss, v) == NULL) + goto fail; + b += ss; + break; + case EZ_BLOB_POINTER: { + void *s = NULL; + + if (ss != ~0) { + if (b + ss > be) + goto fail; + if ((s = calloc(d->bd_table->bd_offset, 1)) == NULL) + goto fail; + if (ez_blob_decode_raw(d->bd_table, b, ss, s) == NULL) { + free(s); + goto fail; + } + b += ss; + } + ((void **)v)[0] = s; + break; } + default: + break; + } + } + } + if (b != be) + goto fail; + + return p; + fail: + ez_blob_free_raw(d, p); + return NULL; +} + +void *ez_blob_decode(const ez_blob_desc *d, const char *b, size_t size) { + void *p = calloc(d->bd_offset, 1); + + if (ez_blob_decode_raw(d, b, size, p) == NULL) { + free(p); + return NULL; + } + + return p; +} + +void ez_blob_encode_raw(const ez_blob_desc *d, const void *p, char *b, size_t size) { + char *be = b+size; + for (;(d->bd_type != EZ_BLOB_END);d++) { + const void *v = (p + d->bd_offset); + + if (d->bd_type <= EZ_BLOB_FLOAT64) { + int psize = primitive_size[d->bd_type]; + + assert(b+psize <= be); + memcpy(b, v, psize); + b += psize; + } else if (d->bd_type <= EZ_BLOB_LAST) { + uint32_t ss; + + switch (d->bd_type) { + case EZ_BLOB_STRING: { + char *s = ((char **)v)[0]; + if (s) { + ss = strlen(s); + assert(b+4+ss <= be); + memcpy(b, &ss, 4); + memcpy(b+4, s, ss); + b += 4 + ss; + } else { + ss = ~0; + assert(b+4 <= be); + memcpy(b, &ss, 4); + b += 4; + } + break; } + case EZ_BLOB_ARRAY: { + const struct ez_blob_array *a = v; + + ss = a->size; + assert(b+4+ss <= be); + memcpy(b, &ss, 4); + memcpy(b+4, a->data, ss); + b += 4 + ss; + break; } + case EZ_BLOB_STRUCT: + ss = ez_blob_size(d->bd_table, v); + + assert(b+4+ss <= be); + memcpy(b, &ss, 4); + ez_blob_encode_raw(d->bd_table, v, b+4, ss); + b += 4 + ss; + break; + case EZ_BLOB_POINTER: { + const void *s = ((const void **)v)[0]; + + if (s) { + ss = ez_blob_size(d->bd_table, s); + assert(b+4+ss <= be); + memcpy(b, &ss, 4); + ez_blob_encode_raw(d->bd_table, s, b+4, ss); + b += 4 + ss; + } else { + ss = ~0; + assert(b+4 <= be); + memcpy(b, &ss, 4); + b += 4; + } + break; } + default: + break; + } + } + } + assert(b == be); +} + +/** + * Encode blob to new buffer. + * + * @param p object to serialise. + * @param sizep size of encoded blob return pointer. + * @return a newly allocated blob of the correct size. + */ +char *ez_blob_encode(const ez_blob_desc *d, const void *p, size_t *sizep) { + size_t size = ez_blob_size(d, p); + char *b = malloc(size); + + ez_blob_encode_raw(d, p, b, size); + + *sizep = size; + return b; +} + diff --git a/ez-blob.h b/ez-blob.h new file mode 100644 index 0000000..e162f0b --- /dev/null +++ b/ez-blob.h @@ -0,0 +1,177 @@ +/* ez-blob.h: Serialising description and serialiser. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef _EZ_BLOB_H +#define _EZ_BLOB_H + +#include + +/** + * This is a C structure serialiser. + * + * It is table driven and can describe most common C data structures, + * including nested and linked structures. + * + * The implemented serialisation mechanism only supports + * forward-linked structures and will not perform well when + * marshalling deeply nested structures but other serialisation + * mechanisms are possible. + */ + +/** + * An array of ez_blob_desc is passed to ez_blob_encode/decode. The first + * entry must be of type EZ_BLOB_PK and it's 'offset' must be the size + * of the structure. The final entry must be of type EZ_BLOB_END. + * + * As an example: + * + * typedef struct dbdisk { + * int id; + * char *uuid; + * char *label; + * char *type; + * } dbdisk; + * + * Has a table such as this, using the init macros. + * + * static ez_blob_desc DISK_ENC[] = { + * EZ_BLOB_START(dbdisk), + * EZ_BLOB_STRING(dbdisk, 1, uuid), + * EZ_BLOB_STRING(dbdisk, 2, label), + * EZ_BLOB_STRING(dbdisk, 3, type), + * EZ_BLOB_END(dbdisk) + * }; + * + * The 'id' field (of ez_blob_desc) is currently unused by the blob + * serialiser but could be implemented for data versioning or partial + * serialisation. + * + */ +typedef struct ez_blob_desc { + unsigned short bd_type; // type of field + unsigned short bd_id; // used to tag encoded entries (currently unused) + unsigned int bd_offset; // offset into structure, if type == EZ_BLOB_PK then this is sizeof(struct) + union { + const struct ez_blob_desc *table;// embedded structure or pointer + } u; +#define bd_table u.table +} ez_blob_desc; + +/** + * Field type + */ +typedef enum ez_blob_desc_type { + EZ_BLOB_INT8, + EZ_BLOB_INT16, + EZ_BLOB_INT32, + EZ_BLOB_INT64, + EZ_BLOB_FLOAT32, + EZ_BLOB_FLOAT64, + EZ_BLOB_STRING, // normall c strring + EZ_BLOB_ARRAY, // embedded ez_blob_array for arbitrary bytes. + EZ_BLOB_STRUCT, // bd_table points to another descriptor list, object embedded + EZ_BLOB_POINTER, // bd_table points to another descriptor list, object pointer + EZ_BLOB_LAST = EZ_BLOB_POINTER, + EZ_BLOB_PK = 16, // MUST always be first element in descriptor and occur only once + EZ_BLOB_END +} ez_blob_desc_type; + +typedef struct ez_blob_array { + unsigned int size; + void *data; +} ez_blob_array; + +#define EZ_BLOB_START(s) { EZ_BLOB_PK, 0, sizeof(s) } +#define EZ_BLOB_INT8(s, id, f) { EZ_BLOB_INT8, id, offsetof(s, f) } +#define EZ_BLOB_INT16(s, id, f) { EZ_BLOB_INT16, id, offsetof(s, f) } +#define EZ_BLOB_INT32(s, id, f) { EZ_BLOB_INT32, id, offsetof(s, f) } +#define EZ_BLOB_INT64(s, id, f) { EZ_BLOB_INT64, id, offsetof(s, f) } +#define EZ_BLOB_FLOAT32(s, id, f) { EZ_BLOB_FLOAT32, id, offsetof(s, f) } +#define EZ_BLOB_FLOAT64(s, id, f) { EZ_BLOB_FLOAT64, id, offsetof(s, f) } +#define EZ_BLOB_STRING(s, id, f) { EZ_BLOB_STRING, id, offsetof(s, f) } +#define EZ_BLOB_ARRAY(s, id, f) { EZ_BLOB_ARRAY, id, offsetof(s, f) } +#define EZ_BLOB_STRUCT(s, id, f, other) { EZ_BLOB_STRUCT, id, offsetof(s, f), .u.table = other } +#define EZ_BLOB_POINTER(s, id, f, other) { EZ_BLOB_POINTER, id, offsetof(s, f), .u.table = other } +#define EZ_BLOB_END(s) { EZ_BLOB_END } + +/** + * Calculate the serialised blob size for a struct. + * + * @param d descriptor table matching struct. + * @param p struct. + */ +size_t ez_blob_size(const ez_blob_desc *d, const void *p); + +/** + * Marshal a struct to a blob. + * + * @param d descriptor table matching the struct. + * @param p structure. + * @param sizep return pointer for blob size, must not be null. + * @return the blob, it must be freed with free() when complete. + */ +char *ez_blob_encode(const ez_blob_desc *d, const void *p, size_t *sizep); + +/** + * Marshal a struct to a blob directly + * + * @param d descriptor table matching the struct. + * @param p structure. + * @param b target memory, must be as large as size + * @param size size of target memory, must be exactly ez_blob_size(). + * @return the blob, it must be freed with free() when complete. + */ +void ez_blob_encode_raw(const ez_blob_desc *d, const void *p, char *b, size_t size); + +/** + * Unmarshall a blob into a struct. + * + * @param d descriptor table matching blob. + * @param blob raw blob. + * @param size blob size. + * @return the decoded struct. May be freed using ez_blob_free(). + */ +void *ez_blob_decode(const ez_blob_desc *d, const char *blob, size_t size); + +/** + * Decode to pre-allocated buffer. + * + * @param b blob data + * @param size blob size + * @return p is returned on success. On failure NULL is returned and any internal pointers are freed. + */ +void *ez_blob_decode_raw(const ez_blob_desc *d, const char *b, size_t size, void *p); + +/** + * Free struct unmarshalled by ez_blob_decode(). + * + * @param d descriptor table matching struct. + * @param p decoded struct from ez_blob_decode(). + */ +void ez_blob_free(const ez_blob_desc *d, void *p); + +/** + * Free the contents of a structure, but don't free the container. + * + * @todo should this zero the structure too? + * @param p structure to free. p will not be freed. + */ +void ez_blob_free_raw(const ez_blob_desc *d, void *p); + +#endif diff --git a/ez-list.h b/ez-list.h new file mode 100644 index 0000000..5e67e6f --- /dev/null +++ b/ez-list.h @@ -0,0 +1,266 @@ +/* ez-list.h: Double-linked list implementation (aka 'exec lists') + + Copyright (C) 2010,2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ +#ifndef _EZ_LIST_H +#define _EZ_LIST_H + +#include + +/** + * ez-list is a low-level double-linked list implementation that works + * without memory allocation. + * + * o Adding to or removing from either end is an O(1) operation. + * o Removing any given node is an O(1) operation. + * o Nodes can only belong to a single list at any given time. + * o No operations can fail. + * o No pointers are checked. + * o The list is not thread-safe. + * + * All list functions are implemented as inline functions. + * + * This is how to iterate all elements in forward order: + + struct list_item { + struct ez_node ln; + // item data + } + + struct list list = EZ_INIT_LIST(list); + + struct list_item *work = ez_list_head(list); + struct list_item *next = ez_list_succ(list); + + while (next) { + + // operate on 'work'. + // ez_node_remove() may be called here + + succ = next; + next = ez_list_succ(list); + } + + * For reverse order simply use ez_list_tail() and ez_node_pred(). + * + * Functions use untyped pointers for nodes for convenience but they + * must start with struct ez_node. + * + * Historical note: this is a re-implementation of Amiga's kernel + * minimal lists. A minor change is that functions take and return + * untyped nodes. + */ + +typedef struct ez_list ez_list; + + +/** + * A list header. + * + * This represents two overlapping nodes which share a common pointer. + * It must be initialised using ez_list_init() or EZ_INIT_LIST() + * before use. + * + * tail is always NULL. + * + * The pointers are volatile to avoid aliasing issues with C99+. + */ +struct ez_list { + struct ez_node * volatile head; + struct ez_node * volatile tail; + struct ez_node * volatile tail_pred; +}; + +/** + * Initialise a list statically. + * + * struct ez_list list = EZ_INIT_LIST(list); + */ +#define EZ_INIT_LIST(l) { (struct ez_node *)&(l).tail, (void *)0, (struct ez_node *)&l } + +/** + * Initialise a list at runtime. + * + */ +static __inline__ void ez_list_init(struct ez_list *l) { + l->head = (struct ez_node *)&l->tail; + l->tail = (struct ez_node *)0L; + l->tail_pred = (struct ez_node *)&l->head; +} + +/** + * Add a node to the head of the list. + */ +static __inline__ void ez_list_addhead(struct ez_list *l, void *np) { + struct ez_node *n = np, *head = l->head; + + n->u.list.succ = head; + n->u.list.pred = (struct ez_node *)&l->head; + head->u.list.pred = n; + l->head = n; +} + +/** + * Add a node to the tail of the list. + */ +static __inline__ void ez_list_addtail(struct ez_list *l, void *np) { + struct ez_node *n = np, *tail_pred = l->tail_pred; + + n->u.list.pred = tail_pred; + n->u.list.succ = (struct ez_node *)&l->tail; + tail_pred->u.list.succ = n; + l->tail_pred = n; +} + +/** + * Remove a node from a list. + * + * The node must already belong to a list. + * + * This performs a software memory barrier after + * write do workaround aliasing issues with gcc. + */ +static __inline__ void ez_node_remove(void *np) { + struct ez_node *n = np, *pred = n->u.list.pred, *succ = n->u.list.succ; + + pred->u.list.succ = succ; + succ->u.list.pred = pred; +} + +/** + * Remove a node from the head of the list. + * + * @return the head node, or NULL if the list is empty. + */ +static __inline__ void *ez_list_remhead(struct ez_list *l) { + struct ez_node *n = l->head; + struct ez_node *s = n->u.list.succ; + + if (s) { + s->u.list.pred = (struct ez_node *)&l->head; + l->head = s; + return n; + } else + return 0L; +} + +/** + * Remove a node from the tail of the list. + * + * @return the tail node, or NULL if the list is empty. + */ +static __inline__ void *ez_list_remtail(struct ez_list *l) { + struct ez_node *n = l->tail_pred; + struct ez_node *p = n->u.list.pred; + + if (p) { + p->u.list.succ = (struct ez_node *)&l->tail; + l->tail_pred = p; + return n; + } else + return 0L; +} + +/** + * Insert a node after a given node. + * + * @param l list. + * @param n node to insert. + * @param p node that is already present in list, or NULL (insert after head). + */ +static __inline__ void ez_list_insert_after(struct ez_list *l, void *n, void *p) { + struct ez_node *nn = n; + struct ez_node *pp = p ? p : (struct ez_node *)&l->head; + struct ez_node *succ = pp->u.list.succ; + + nn->u.list.succ = succ; + nn->u.list.pred = pp; + succ->u.list.pred = nn; + pp->u.list.succ = nn; +} + +/** + * Insert a node before a given node. + * + * @param l list. + * @param n node to insert. + * @param p node that is already present in list, or NULL (insert before tail). + */ +static __inline__ void ez_list_insert(struct ez_list *l, void *n, void *p) { + struct ez_node *nn = n; + struct ez_node *pp = p ? p : (struct ez_node *)&l->tail; + struct ez_node *pred = pp->u.list.pred; + + nn->u.list.succ = pp; + nn->u.list.pred = pred; + pred->u.list.succ = nn; + pp->u.list.pred = nn; +} + +/** + * Find the length of the list. + * + * This is an O(n) operation, use ez_list_empty() to check for empty + * lists. + */ +static __inline__ int ez_list_size(struct ez_list *l) { + struct ez_node *w, *n; + int size = 0; + + for (w = l->head, n = w->u.list.succ; n; w = n, n = n->u.list.succ) + size += 1; + + return size; +} + +/** + * Check if the list is empty. + * + * @param returns true (1) if the list is empty. + */ +static __inline__ int ez_list_empty(struct ez_list *l) { + return l->tail_pred == (struct ez_node *)l; +} + +/** + * Retrieve the successor to the head node (the first user node). + */ +static __inline__ void *ez_list_head(struct ez_list *l) { + return (void *)l->head; +} + +/** + * Retrieve the predecessor of the tail node (the last user node). + */ +static __inline__ void *ez_list_tail(struct ez_list *l) { + return (void *)l->tail_pred; +} + +/* This is important for -Os. */ +static void ez_list_init(struct ez_list *l) __attribute__ ((always_inline)); +static void ez_list_addhead(struct ez_list *l, void *np) __attribute__ ((always_inline)); +static void ez_list_addtail(struct ez_list *l, void *np) __attribute__ ((always_inline)); +static void ez_node_remove(void *np) __attribute__ ((always_inline)); +static void *ez_list_remhead(struct ez_list *l) __attribute__ ((always_inline)); +static void *ez_list_remtail(struct ez_list *l) __attribute__ ((always_inline)); +static void ez_list_insert_after(struct ez_list *l, void *n, void *p) __attribute__ ((always_inline)); +static void ez_list_insert(struct ez_list *l, void *n, void *p) __attribute__ ((always_inline)); +static int ez_list_empty(struct ez_list *l) __attribute__ ((always_inline)); +static void *ez_list_head(struct ez_list *l) __attribute__ ((always_inline)); +static void *ez_list_tail(struct ez_list *l) __attribute__ ((always_inline)); + +#endif diff --git a/ez-node.h b/ez-node.h new file mode 100644 index 0000000..e605c74 --- /dev/null +++ b/ez-node.h @@ -0,0 +1,129 @@ +/* ez-node.h: General purpose node. + + Copyright (C) 2010,2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ +#ifndef _EZ_NODE_H +#define _EZ_NODE_H + +#include + +typedef struct ez_node ez_node; + +/** + * A list/tree/set node. + * + * All objects stored in the list/tree/set must begin with this + * structure. It does not need initialisation. + * + * Use the appropriate node accessors to navigate. They are only + * valid iff the node is a member of a container. + * + * The order of each is important. + */ +struct ez_node { + union { + struct { + struct ez_node * volatile succ; + struct ez_node * volatile pred; + } list; + struct { + intptr_t link[2]; + } tree; + struct { + struct ez_node *next; + unsigned int hash; + } set; + } u; +}; + +/** + * Direction of a tree node link. + */ +enum ez_node_link_t { + EZ_LINK_LEFT = 0, + EZ_LINK_RIGHT = 1 +}; + +typedef unsigned int (*ez_hash_fn)(const void *entry); +typedef int (*ez_equal_fn)(const void *a, const void *b); +typedef int (*ez_cmp_fn)(const void *a, const void *b); +typedef void (*ez_free_fn)(void *); + +/** + * Retrieve the list node successor. + * + * The end of the list is indicated by node.next == NULL, not by node + * == NULL. + */ +static __inline__ void *ez_node_succ(void *n) { + return (void *)((struct ez_node *)n)->u.list.succ; +} + +/** + * Retrieve the list node predecessorr. + * + * The start of the list is indicated by node.prev == NULL, not by node + * == NULL. + */ +static __inline__ void *ez_node_pred(void *n) { + return (void *)((struct ez_node *)n)->u.list.pred; +} + +/** + * Retrieve the left child tree node. + */ +static __inline__ void *ez_node_left(void *node) { + return (void *)(((struct ez_node *)node)->u.tree.link[0] & ~3); +} + +/** + * Retrieve the right child tree node. + */ +static __inline__ void *ez_node_right(void *node) { + return (void *)(((struct ez_node *)node)->u.tree.link[1] & ~3); +} + +/** + * Retrieve either the left or right child node. + */ +static __inline__ void *ez_node_link(void *node, enum ez_node_link_t i) { + return (void *)(((struct ez_node *)node)->u.tree.link[i] & ~3); +} + +/** + * Retrieve the next set hash chain bucket. + */ +static __inline__ void *ez_node_next(void *node) { + return ((struct ez_node *)node)->u.set.next; +} + +/** + * Retrieve the set hash bucket hash. + */ +static __inline__ unsigned int ez_node_hash(void *node) { + return ((struct ez_node *)node)->u.set.hash; +} + +static void *ez_node_succ(void *n) __attribute__ ((always_inline)); +static void *ez_node_pred(void *n) __attribute__ ((always_inline)); +static void *ez_node_left(void *node) __attribute__((always_inline)); +static void *ez_node_right(void *node) __attribute__((always_inline)); +static void *ez_node_link(void *node, enum ez_node_link_t i) __attribute__((always_inline)); +static void *ez_node_next(void *node) __attribute__((always_inline)); +static unsigned int ez_node_hash(void *node) __attribute__((always_inline)); + +#endif diff --git a/ez-port.c b/ez-port.c new file mode 100644 index 0000000..4743b30 --- /dev/null +++ b/ez-port.c @@ -0,0 +1,117 @@ +/* ez-port.c: A simple inter-thread IPC mechanism with poll() support. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +#include "ez-port.h" + +/** + * This implementation uses anonymous posix message queues. + * + * Internally it uses the message queue to store the message pointers + * directly. This should work in-thread. It might do funny things + * with valgrind and the like since they pointers escape the user + * address space. + * + * If two readers are reading at the time time, poll() may currently + * block as it doesn't use non-blocking i/o. + */ + +#define EZ_PORT_NAME "ez-port" + +struct ez_port { + mqd_t q; +}; + +ez_port *ez_port_new(int limit) { + ez_port *port = malloc(sizeof(*port)+ sizeof(void *) * limit); + struct mq_attr at; + char name[16 + strlen(EZ_PORT_NAME) + 4]; + + if (!port) + return port; + + // Port name includes uid to avoid permission issues if a stale port exists + sprintf(name, "/%s-%016lx", EZ_PORT_NAME, getuid() & 0xffffffffffffffffUL); + + at.mq_flags = 0; + at.mq_maxmsg = limit; + at.mq_msgsize = sizeof(void *); + + // Open a unqiue port anonymously, using O_EXCL and unlink(). + printf("open %s\n", name); + do { + mq_unlink(name); + port->q = mq_open(name, O_RDWR | O_CREAT | O_EXCL | O_CLOEXEC, 0600, &at); + } while (port->q == -1 && errno == EEXIST); + + if (port->q == -1) { + perror("mq_open"); + free(port); + return NULL; + } + mq_unlink(name); + + return port; +} + +void ez_port_free(ez_port *port) { + if (port) { + mq_close(port->q); + free(port); + } +} + +int ez_port_fd(ez_port *port) { + return port->q; +} + +int ez_port_put(struct ez_port *port, void *msg) { + return mq_send(port->q, (char *)&msg, sizeof(msg), 0); +} + +void *ez_port_poll(ez_port *port) { + struct mq_attr at; + + if (mq_getattr(port->q, &at) == 0 && at.mq_curmsgs > 0) + return ez_port_take(port); + + return NULL; +} + +void *ez_port_take(ez_port *port) { + void *tail; + ssize_t size; + + size = mq_receive(port->q, (char *)&tail, sizeof(tail), NULL); + if (size == sizeof(tail)) + return tail; + + return NULL; +} diff --git a/ez-port.h b/ez-port.h new file mode 100644 index 0000000..869a61e --- /dev/null +++ b/ez-port.h @@ -0,0 +1,73 @@ +/* ez-port.h: A simple inter-thread IPC mechanism with poll() support. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef _EZ_PORT_H +#define _EZ_PORT_H + +/** + * This is trivial multiple-writer / multiple-reader non-copying and + * blocking message queue with support for poll() and select(). + * + * It can only be used for in-process message passing, i.e. between + * threads. + */ + +typedef struct ez_port ez_port; + +/** + * Create a new port. + * + * @param limit maximum number of pending messages. + * @return the new port, or NULL if it cannot be created. errno will + * indicate the error. + */ +ez_port *ez_port_new(int limit); + +/** + * Free a port. + */ +void ez_port_free(ez_port *port); + +/** + * Retrieve a file descriptor that can be polled on. + */ +int ez_port_fd(ez_port *port); + +/** + * Put a new message onto the port. NULL is allowed. + * + * If the queue is full then this call will block. + * + * @return 0 on success, on failure errno indicates error. + */ +int ez_port_put(ez_port *port, void *msg); + +/** + * Retrieve the next message from the port if one is available. + */ +void *ez_port_poll(ez_port *port); + +/** + * Take the next message from the port, waiting if none are available. + * + * @return the next message, or NULL if none are available (or an error occured). + */ +void *ez_port_take(ez_port *port); + +#endif diff --git a/ez-set.c b/ez-set.c new file mode 100644 index 0000000..00ac3fc --- /dev/null +++ b/ez-set.c @@ -0,0 +1,313 @@ +/* ez-set.c: Low level hash table. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#include +#include +#include + +#include "ez-set.h" + +/** + * Pretty much a traditional chained hash table implementation. I've + * experimented with a few variations but as a general purpose table + * this is always competetive at worst. + */ + +static void *scan_next_chain(ez_set *h, ez_set_scan *scan, int idx) __attribute__((noinline)); +static void set_rehash(ez_set *h, int newsize) __attribute__((noinline)); + +/** + * Lookup an entry. + * + * Find the entry and return the previous node in the bucket chain. + * The previous node may be en entry in table. + * + * @param key key to lookup. + * @param pp return for the parent pointer. This will + * be a pointer to the table entry if the chain is empty. + * @return an entry if found. + */ +static ez_node *set_lookup(ez_set *h, const ez_node *key, unsigned int hash, ez_node **pp) { + unsigned int idx = hash & h->mask; + ez_node *scan = h->table[idx]; + ez_node *p = (ez_node *)&h->table[idx]; + + while (scan && !(hash == scan->u.set.hash && h->equals(key, scan))) { + p = scan; + scan = scan->u.set.next; + } + *pp = p; + + return scan; +} + +/** + * Rehash the table to a new size. + * + * This cannot fail. If the memory allocation fails for the table it + * just does nothing and the set will still function mayhaps with + * degraded performance. + */ +static void set_rehash(ez_set *h, int newsize) { + ez_node **table = calloc(sizeof(*table), newsize); + unsigned int mask = newsize - 1; + + if (!table) + return; + + // Move all entries to the new table + for (int i=0;i<=h->mask;i++) { + ez_node *e = h->table[i]; + + while (e) { + ez_node *n = e->u.set.next; + unsigned int nidx = e->u.set.hash & mask; + + e->u.set.next = table[nidx]; + table[nidx] = e; + + e = n; + } + } + + // update table + free(h->table); + h->table = table; + h->mask = mask; +} + + +/** + * Find the next non-empty chain. + */ +static void *scan_next_chain(ez_set *h, ez_set_scan *scan, int idx) { + ez_node *e = NULL; + + while (e == NULL && idx <= h->mask) + e = h->table[idx++]; + + scan->e = e; + scan->idx = idx; + scan->p = e ? (struct ez_node *)&h->table[idx-1] : NULL; + + return e; +} + +/* ********************************************************************** */ +/* Main api */ + +ez_set *ez_set_new(unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)) { + ez_set *h = malloc(sizeof(*h)); + + if (h) { + h->table = calloc(sizeof(ez_node), 16); + h->mask = 15; + h->hash = hash; + h->equals = equals; + h->free = efree; + h->count = 0; + + if (!h->table) { + free(h); + return NULL; + } + } + + return h; +} + +void ez_set_free(ez_set *h) { + if (h) { + ez_set_clear(h); + free(h->table); + free(h); + } +} + +void ez_set_clear(ez_set *h) { + for (int i=0;i<=h->mask;i++) { + ez_node *e = h->table[i]; + + while (e) { + ez_node *n = ez_node_next(e); + if (h->free) + h->free(e); + e = n; + } + h->table[i] = NULL; + } + h->count = 0; + + if (h->mask > 15) { + h->table = realloc(h->table, 16 * sizeof(ez_node)); + h->mask = 15; + } +} + +int ez_set_size(ez_set *h) { + return h->count; +} + +void *ez_set_put(ez_set *h, void *ep) { + ez_node *e = ep, *scan, *p; + + // Entries are only ever hashed once, here. + e->u.set.hash = h->hash(e); + scan = set_lookup(h, e, e->u.set.hash, &p); + + // insert new node, possibly unlinking old one + p->u.set.next = e; + if (scan) { + // link old node tail + e->u.set.next = scan->u.set.next; + } else { + // new node added + e->u.set.next = NULL; + h->count += 1; + if (h->count > h->mask) + set_rehash(h, (h->mask+1) * 2); + } + + return scan; +} + +void *ez_set_get(ez_set *h, const void *ep) { + const struct ez_node *e = ep; + struct ez_node *p; + unsigned int hash = ez_set_node_hash(h, e); + + return set_lookup(h, e, hash, &p); +} + +void *ez_set_remove(ez_set *h, const void *ep) { + const ez_node *e = ep; + struct ez_node *scan, *p; + unsigned int hash = ez_set_node_hash(h, e); + + scan = set_lookup(h, e, hash, &p); + if (scan) { + // unlink old node + p->u.set.next = scan->u.set.next; + h->count -= 1; + if (h->mask > 15 && h->count*2 < h->mask) + set_rehash(h, (h->mask+1)>>1); + } + + return scan; +} + +/* ********************************************************************** */ +/* Set iterator */ + +void *ez_set_scan_init(ez_set *h, ez_set_scan *scan) { + scan->set = h; + scan_next_chain(h, scan, 0); + + return scan->e; +} + +void *ez_set_scan_next(ez_set_scan *scan) { + if (scan->e) { + // advance e and p + scan->p = scan->e; + scan->e = scan->e->u.set.next; + + if (!scan->e) + return scan_next_chain(scan->set, scan, scan->idx); + } + + return scan->e; +} + +void *ez_set_scan_remove(ez_set_scan *scan) { + if (scan->e) { + // unlink e and advance but don't change p + scan->p->u.set.next = scan->e = scan->e->u.set.next; + scan->set->count -= 1; + + if (!scan->e) + return scan_next_chain(scan->set, scan, scan->idx); + } + + return scan->e; +} + +/* ********************************************************************** */ +/* App helpers */ + +/* + * Some hash functions. + * + * It's all a bit arbitrary in my experience and almost anything + * reasonable works well enough so long as you avoid really poor ones + * like `(int32_t)(intptr_t)pointer' or sum(char[]). + */ + +// http://www.cse.yorku.ca/~oz/hash.html +// djb2 +// Use the multiplier here and let the compiler shift-ize if it that's faster. +unsigned int ez_hash_string(const char *s) { + unsigned int hash = 5381; + + while (*s) + //hash = (*s++) + (hash << 5) + hash; + hash = hash * 33 + (*s++); + + return hash; +} + +// http://www.cse.yorku.ca/~oz/hash.html +// sdbm, used in berkeley db +// Use the multiplier here and let the compiler shift-ize if it that's faster. +unsigned int ez_hash_array(const void *sp, size_t size) { + unsigned int hash = 0; + const unsigned char *s = sp; + const unsigned char *se = s + size; + + while (s < se) + //hash = (*s++) + (hash << 6) + (hash << 16) - hash; + hash = hash * 65599 + (*s++); + + return hash; +} + +// https://www.burtleburtle.net/bob/hash/integer.html +// 'Thomas Wang's function' +// TBH fuck knows, an unbiased 32-bit reversible hash isn't necessarily +// great for a power of 2 hash table index. +unsigned int ez_hash_int32(uint32_t a) { + a += ~(a<<15); + a ^= (a>>10); + a += (a<<3); + a ^= (a>>6); + a += ~(a<<11); + a ^= (a>>16); + return a; +} + +unsigned int ez_hash_int64(uint64_t x) { + return ez_hash_int32(x ^ (x>>32)); +} + +unsigned int ez_hash_ptr(void *v) { + if (sizeof(v) == 8) + return ez_hash_int64((intptr_t)v); + else + return ez_hash_int32((intptr_t)v); +} diff --git a/ez-set.h b/ez-set.h new file mode 100644 index 0000000..d453db0 --- /dev/null +++ b/ez-set.h @@ -0,0 +1,240 @@ +/* ez-set.h: Low level hash table. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef _EZ_SET_H +#define _EZ_SET_H + +#include + +/** + * A basic set / hash table implementation. + * + * All entries must start with a struct ez_entry and contain enough + * information to caclulate the hash and equality. Entries may only be + * members of one set at a time. + * + * A general purpose hash table can be implemented with appropriate + * initialisation and using an entry like the following: + + struct ez_bucket { + struct ez_node bn; + void *key; + void *data; + }; + + * + * For simplicity the table automatically rehashes up on put at a load + * factor above 1.0 and down on remove at a load factor below 0.5. + */ + +typedef struct ez_set ez_set; +typedef struct ez_set_scan ez_set_scan; + +/** + * Base set structure. + */ +struct ez_set { + struct ez_node **table; // table of chains + int mask; // size of the table - 1 + int count; // number of entries in the set + + unsigned int (*hash)(const void *entry); + int (*equals)(const void *a, const void *b); + void (*free)(void *); +}; + +/** + * State data for iterator. + */ +struct ez_set_scan { + struct ez_set *set; + struct ez_node *e; + struct ez_node *p; + int idx; +}; + +/** + * Create a new set. + * + * @param h uninitialised set. + * @param hash function which hashes entries. + * @param equals function which compares entries for equality. + * @param efree used to free nodes. May be null. + */ +ez_set *ez_set_new(unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)); + +/** + * Free the set. + * + * The set will be cleared first. + */ +void ez_set_free(ez_set *h); + +/** + * Clear all entries and reset the internal size. + * + * If the set was initialised with a non-null free function, it will + * be invoked on all nodes. + */ +void ez_set_clear(ez_set *h); + +/** + * Get the number of entries in the set. + */ +int ez_set_size(ez_set *h); + +/** + * Calculate the hash of a node. + */ +static __inline__ unsigned int ez_set_node_hash(ez_set *h, const void *e) { + return h->hash(e); +} + +/** + * Compare nodes for equality. + */ +static __inline__ int ez_set_node_equals(ez_set *h, const void *a, const void *b) { + return h->equals(a, b); +} + +/** + * Free a node. If no node free function is set this is a nop. + */ +static __inline__ void ez_set_node_free(ez_set *h, void *e) { + if (h->free) + h->free(e); +} + +/** + * Put a table entry. + * + * @param h initialised set. + * @param e entry to put. + * @return the previous entry which equals e, if any. + */ +void *ez_set_put(ez_set *h, void *e); + +/** + * Get a table entry. + * + * @param h initialised set. + * @param key key describing the item to retrieve. + * @return the entry which equals e, if any. + */ +void *ez_set_get(ez_set *h, const void *key); + +/** + * Remove a table entry. + * + * @param h initialised set. + * @param key key of entry to remove. + * @return the entry removed, if any. + */ +void *ez_set_remove(ez_set *h, const void *key); + +/** + * Start an iterative scan of all set entries. + * + * The set must not be modified while the entries are being iterated + * other than through ez_scan_remove(). + * + * As with most hash tables, the iteration order is undefined. + * + * The scan can be abandoned at any time and @param scan does not need + * to be disposed. + * + * @param h set to iterate. + * @param scan uninitialised ez_set_scan structure. + * @return the first node, or null if none exists. + */ +void *ez_set_scan_init(ez_set *h, ez_set_scan *scan); + +/** + * Retrieve the current node. + * + * This is just scan->e. + */ +static __inline__ void *ez_set_scan_get(ez_set_scan *scan) { + return scan->e; +} + +/** + * Advance to the next node. + * + * Example to iterate all entries: + + ez_set *set = ...; + ez_set_scan scan; + struct entry_type *entry; + + for (entry = ez_scan_init(set, &scan); entry; entry = ez_scan_next(&scan)) { + ... work on entry ... + } + + * @return the next node or NULL. + */ +void *ez_set_scan_next(ez_set_scan *scan); + +/** + * Remove the current node and advance to the next node. + * + * The node is not freed allowing it to be moved to other sets. + * + * Example to iterate and remove all entries: + + ez_set *set = ...; + ez_set_scan scan; + struct entry_type *next; + + for (next = ez_scan_init(set, &scan); next;) { + struct entry_type *entry = next; + + next = ez_scan_remove(&scan); + + ... work on entry ... + } + */ +void *ez_set_scan_remove(ez_set_scan *scan); + +/** + * A basic string hash function. + */ +unsigned int ez_hash_string(const char *s); + +/** + * Simple array hash function. + */ +unsigned int ez_hash_array(const void *s, size_t size); + +/** + * 32-bit integer hash function. + */ +unsigned int ez_hash_int32(uint32_t v); + +/** + * 64-bit integer hash function. + */ +unsigned int ez_hash_int64(uint64_t v); + +static unsigned int ez_set_node_hash(ez_set *h, const void *e) __attribute__((always_inline)); +static int ez_set_node_equals(ez_set *h, const void *a, const void *b) __attribute__((always_inline)); +static void ez_set_node_free(ez_set *h, void *e) __attribute__((always_inline)); +static void *ez_set_scan_get(ez_set_scan *scan) __attribute__((always_inline)); + +#endif diff --git a/ez-tree.c b/ez-tree.c new file mode 100644 index 0000000..6b2482a --- /dev/null +++ b/ez-tree.c @@ -0,0 +1,474 @@ +/* ez-tree.c Balanced (avl) tree. + + Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc. + Copyright (C) 2019 Michael Zucchi + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 3 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. + +*/ + +#include +#include + +#include "ez-tree.h" + +/** + * This is an implementation of an AVL balanced binary tree optimised + * for code and memory size. The source itself is also intended to be + * concise. + * + * Each tree node takes only 2 pointers of overhead. The balance + * factor is stored in the lower 2 bits of the link pointers. This + * makes for some messy programming but the overhead isn't high. + * + * The code-size is reduced by using parameterisation and other small + * tricks. + * + * As with the other ez- containers normal operation involves no + * resource allocation. Operations cannot fail assuming valid + * program state. Likewise there is almost no checking of any + * state; the caller is entirely responsible for correct operation. + * + * The insert function was coded from Algorithm A in section 6.2.2 in + * ``The Art of Computer Programming'' Volume 3, Donald E. Knuth. + * + * Most of the the delete function was taken from GNU libavl 2.0. It + * was then parameterised and broken apart into reusuable components. + * + * The rest I just made up. + */ + +/* ********************************************************************** */ + +#define BALANCE0 0 + +/* + Balance is stored as a 2-bit signed integer in the 2 lsb bits of + link[0]. + + A constraint is that all nodes must be allocated to at least + 4-byte boundaries, which is always the case with any known memory + allocator. + + This is all a bit fiddly but will save at least 3 bytes per node on + 32-bit systems and 7 on 64-bit systems. + */ + +static __inline__ int node_balance(struct ez_node *n) __attribute__((always_inline)); +static __inline__ void node_set_balance(struct ez_node *node, int balance) __attribute__((always_inline)); +static __inline__ void *node_link(struct ez_node *n, int i) __attribute__((always_inline)); +static __inline__ void node_set_link(struct ez_node *n, int i, struct ez_node *link) __attribute__((always_inline)); + +static void *fail_depth(void) __attribute__((noinline)); + +static void *fail_depth(void) { + fprintf(stderr, "EZ_TREE_MAX_DEPTH=%d exceeded\n", EZ_TREE_MAX_DEPTH); + return NULL; +} + +static __inline__ int node_balance(struct ez_node *n) { + int i = n->u.tree.link[0]; + return i << 30 >> 30; +} + +static __inline__ void node_set_balance(struct ez_node *node, int balance) { + node->u.tree.link[0] = (node->u.tree.link[0] & ~3) | (balance & 3); +} + +static __inline__ void *node_link(struct ez_node *n, int i) { + return (void *)(n->u.tree.link[i] & ~3); +} + +static __inline__ void node_set_link(struct ez_node *n, int i, struct ez_node *link) { + n->u.tree.link[i] = (n->u.tree.link[i] & 3) | (intptr_t)link; +} + +/** + * Perform a single node rotation. + * + * See Knuth $6.2.3 expression (1) Case 1, where s is A, and r is B. + * The names s and r are also from Knuth $6.2.3 algorithm A. + * + * @param s is really A + * @param r is really B + * @param ai is the link direction one takes to go from A to B. It must be 0 or 1. + * @param a a balance factor to set on the nodes. This depends on + * other state, it must be -1, 0, or 1. + */ +static struct ez_node *node_rotate_single(struct ez_node * __restrict s, struct ez_node * __restrict r, int ai, int a) { + node_set_link(s, ai, node_link(r, ai ^ 1)); + node_set_link(r, ai ^ 1, s); + + node_set_balance(s, -a); + node_set_balance(r, +a); + + return r; +} + +/** + * Perform a double node rotation. + * + * See Knuth $6.2.3 expression (1) Case 2, where s is A, and r is B. + * The names s and r are also from Knuth $6.2.3 algorithm A. + * + * @param s is really A + * @param r is really B + * @param ai is the link direction one takes to go from A to B. It must be 0 or 1. + * @param a is the node comparision value matching ai. It must be -1 or +1. + */ +static struct ez_node *node_rotate_double(struct ez_node *s, struct ez_node *r, int ai, int a) { + struct ez_node *p = node_link(r, ai ^ 1); + int pb = node_balance(p); + + node_set_link(r, ai ^ 1, node_link(p, ai)); + node_set_link(p, ai, r); + node_set_link(s, ai, node_link(p, ai ^ 1)); + node_set_link(p, ai ^ 1, s); + + node_set_balance(s, pb == +a ? -a : 0); + node_set_balance(r, pb == -a ? +a : 0); + node_set_balance(p, 0); + + return p; +} + +/** + * Internal node remove function. + * + * This is much much nastier than it looks. The rebalance code was + * taken from libavl and paramterised etc. + * + * The stack is a list of all nodes navigated to @param p including + * the node link directions taken at each level. The stack includes + * the psuedo-root node at stack[0] and the node to remove at sp[-1]. + * + * @param stack stack base. + * @param sp stack pointer to one beyond the end of the stack. + */ +static void node_remove(struct ez_tree_scan_info *stack, struct ez_tree_scan_info *sp) { + struct ez_node *p = sp[-1].node; + struct ez_node *r = ez_node_right(p); + struct ez_tree_scan_info *si; + + if (!r) { + node_set_link(sp[-2].node, sp[-2].link, ez_node_left(p)); + sp -= 1; + } else { + struct ez_node *s = ez_node_left(r); + + if (!s) { + node_set_link(r, 0, ez_node_left(p)); + node_set_balance(r, node_balance(p)); + node_set_link(sp[-2].node, sp[-2].link, r); + sp[-1] = (struct ez_tree_scan_info) { r, 1 }; + } else { + struct ez_node *q; + struct ez_tree_scan_info *psp = sp; + + *sp++ = (struct ez_tree_scan_info){ r, 0 }; + while ((q = ez_node_left(s))) { + *sp++ = (struct ez_tree_scan_info){ s, 0 }; + r = s; + s = q; + } + + node_set_link(s, 0, ez_node_left(p)); + node_set_link(r, 0, ez_node_right(s)); + node_set_link(s, 1, ez_node_right(p)); + node_set_balance(s, node_balance(p)); + + node_set_link(psp[-2].node, psp[-2].link, s); + psp[-1] = (struct ez_tree_scan_info){ s, 1 }; + } + } + + // Rebalance tree + // basic code from libavl but paramterised as in Knuth + si = sp-1; + while (si > stack) { + struct ez_node *y = si->node; + int ai = si->link; + int aj = ai ^ 1; + int a = ai * 2 - 1; + int yb = node_balance(y); + + if (a == yb) + node_set_balance(y, 0); + else if (yb == 0) { + node_set_balance(y, -a); + break; + } else { + struct ez_node *x = node_link(y, aj); + int xb = node_balance(x); + struct ez_node *w; + + if (xb == a) + w = node_rotate_double(y, x, aj, -a); + else + w = node_rotate_single(y, x, ai ^ 1, xb == 0 ? a : 0); + + node_set_link(si[-1].node, si[-1].link, w); + + if (xb == 0) + break; + } + + si -= 1; + } + + stack[0].node->u.tree.link[0] -= 1; +} + +/** + * Recursive tree free operation. + * + * Doesn't update any nodes. + */ +static void tree_free(ez_tree *tree, struct ez_node *n, ez_free_fn node_free) { + while (n) { + struct ez_node *l = ez_node_left(n); + struct ez_node *r = ez_node_right(n); + + tree_free(tree, r, node_free); + node_free(n); + n = l; + } +} + +/* ********************************************************************** */ + +void ez_tree_init(struct ez_tree *t) { + t->root.u.tree.link[0] = 0; + t->root.u.tree.link[1] = 0; +} + +void ez_tree_clear(ez_tree *tree, ez_free_fn node_free) { + tree_free(tree, ez_tree_root(tree), node_free); + ez_tree_init(tree); +} + +void *ez_tree_get(ez_tree *tree, ez_cmp_fn node_cmp, const void *node) { + const struct ez_node *k = node; + struct ez_node *p = ez_tree_root(tree); + + while (p) { + int cmp = node_cmp(k, p); + + if (cmp) + p = node_link(p, cmp > 0); + else + break; + } + + return p; +} + +void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node) { + struct ez_node *k = node; + struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; + struct ez_tree_scan_info *sp = stack, *se = sp + EZ_TREE_MAX_DEPTH - 1; + + k->u.tree.link[0] = BALANCE0; // balance=0 + node_set_link(k, 1, 0); + + if (!tree->root.u.tree.link[1]) { + tree->root.u.tree.link[1] = (intptr_t)k; + tree->root.u.tree.link[0] += 1; + return NULL; + } + + // Search for node, keeping track of last non-balanced node in si + struct ez_tree_scan_info *si = stack+1; + int cmp = 1; + struct ez_node *p, *n; + + *sp++ = (struct ez_tree_scan_info){ &tree->root, 1 }; + n = p = ez_node_right(&tree->root); + while (n && cmp != 0) { + if (sp >= se) + return fail_depth(); + p = n; + cmp = node_cmp(k, p); + *sp++ = (struct ez_tree_scan_info){ p, cmp > 0 }; + n = node_link(p, cmp > 0); + if (n && node_balance(n)) + si = sp; + } + + // Matched, replace and return old node + if (cmp == 0) { + node_set_link(sp[-2].node, sp[-2].link, k); + *k = *p; + return p; + } + + // Insert new node + node_set_link(p, cmp > 0, k); + tree->root.u.tree.link[0] += 1; + *sp = (struct ez_tree_scan_info){ k, 0 }; + + // Fix balance factors between s and q + for (struct ez_tree_scan_info *pi = si+1;pi != sp; pi+=1) + node_set_balance(pi->node, pi->link * 2 - 1); + + // Balance + struct ez_node *s = si[0].node; + struct ez_node *r = si[1].node; + int ai = si->link; + int a = ai * 2 - 1; // map 0,1 to -1,+1 + int balance = node_balance(s); + + if (balance == 0) { + node_set_balance(s, a); + } else if (balance == -a) { + node_set_balance(s, 0); + } else { + struct ez_node *q; + + if (node_balance(r) == a) + q = node_rotate_single(s, r, ai, 0); + else + q = node_rotate_double(s, r, ai, a); + + node_set_link(si[-1].node, si[-1].link, q); + } + + return NULL; +} + +void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key) { + struct ez_node *p = ez_node_right(&tree->root); + struct ez_node *n = p; + struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; + struct ez_tree_scan_info *sp = stack, *se = sp + EZ_TREE_MAX_DEPTH; + int cmp = 1; + + *sp++ = (struct ez_tree_scan_info) { &tree->root, 1 }; + while (n && cmp != 0) { + if (sp >= se) + return fail_depth(); + p = n; + cmp = node_cmp(key, p); + *sp++ = (struct ez_tree_scan_info) { p, cmp > 0 }; + n = node_link(p, cmp > 0); + } + + if (cmp == 0) + node_remove(stack, sp); + + return p; +} + +void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t dir, ez_cmp_fn node_cmp, void *key) { + struct ez_node *p = ez_node_right(&tree->root); + int l = 0; + int cmp = 1; + + scan->tree = tree; + scan->node_cmp = node_cmp; + scan->stack[l++] = (struct ez_tree_scan_info) { &tree->root, 1 }; + + if (key) { + while (p && cmp != 0) { + if (l >= EZ_TREE_MAX_DEPTH) + return fail_depth(); + cmp = node_cmp(key, p); + scan->stack[l++] = (struct ez_tree_scan_info) { p, cmp > 0 }; + p = node_link(p, cmp > 0); + } + } else { + while (p) { + if (l >= EZ_TREE_MAX_DEPTH) + return fail_depth(); + scan->stack[l++] = (struct ez_tree_scan_info) { p, dir }; + p = ez_node_link(p, dir); + } + } + scan->level = l; + + if (l > 1) { + if (key) { + int c = (cmp > 0) - (cmp < 0); // -1 0 1 from compare + int a = dir * 2 - 1; // -1 x 1 from direction + + if (c == a) + return ez_tree_scan_next(scan, dir); + // same as: + //if ((cmp < 0 && dir == EZ_LINK_LEFT) + // || (cmp > 0 && dir == EZ_LINK_RIGHT)) + // return ez_tree_scan_next(scan, dir); + } + + return scan->stack[l-1].node; + } else + return NULL; +} + +void *ez_tree_scan_next(ez_tree_scan *scan, enum ez_node_link_t dir) { + int l = scan->level; + int nir = dir ^ 1; + struct ez_node *p = scan->stack[l-1].node; + struct ez_node *r = node_link(p, dir); + + if (r) { + scan->stack[l-1].link = dir; + do { + if (l >= EZ_TREE_MAX_DEPTH) + return fail_depth(); + scan->stack[l++] = (struct ez_tree_scan_info) { r, nir }; + r = node_link(r, nir); + } while (r); + scan->level = l; + return scan->stack[l-1].node; + } else { + while (l > 2 && scan->stack[l-2].link == dir) + l--; + scan->level = l - 1; + if (l > 2) + return scan->stack[l-2].node; + return NULL; + } +} + +void *ez_tree_scan_remove(ez_tree_scan *scan, enum ez_node_link_t dir) { + int l = scan->level; + struct ez_tree_scan_info *sp = scan->stack + l; + + if (l > 1) { + struct ez_node *last = sp[-1].node; + + node_remove(scan->stack, sp); + + // If node_remove could maintain the stack or indicate when it + // is still valid this could be avoided, but its messy. + + if (dir != -1) + return ez_tree_scan_init(scan->tree, scan, dir, scan->node_cmp, last); + } + return NULL; +} + +void *ez_tree_scan_put(ez_tree_scan *scan, void *node) { + struct ez_node *n = node; + struct ez_tree_scan_info *sp = scan->stack + scan->level; + struct ez_node *o = sp[-1].node; + + *n = *o; + sp[-1].node = n; + node_set_link(sp[-2].node, sp[-2].link, n); + + return o; +} diff --git a/ez-tree.h b/ez-tree.h new file mode 100644 index 0000000..327d65f --- /dev/null +++ b/ez-tree.h @@ -0,0 +1,207 @@ +/* ez-tree.h: Balanced (avl) binary tree. + + Copyright (C) 2019 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef _EZ_TREE_H +#define _EZ_TREE_H + +#include + +typedef struct ez_tree ez_tree; + +/** + * Tree structure. + * + * root is a dummy node used to avoid special cases in the code. Use + * ez_tree_root() to obtain the actual tree root node. + */ +struct ez_tree { + ez_node root; +}; + +/** + * Static initialiser for a tree. + * + * struct ez_tree tree = EZ_INIT_TREE(tree); + */ +#define EZ_INIT_TREE(t) { .root.u.tree.link[0] = 0, .root.u.tree.link[1] = 0 } + +typedef struct ez_tree_scan ez_tree_scan; + +/** + * Structure used to track search decisions when navigating the tree. + */ +struct ez_tree_scan_info { + struct ez_node *node; + int link; +}; + +/** + * Maximum depth of tree. + */ +#define EZ_TREE_MAX_DEPTH 33 + +/** + * Holds iterator state. Never holds any allocated resources. + * + * Public so it can be allocated on the stack. + */ +struct ez_tree_scan { + ez_tree *tree; + ez_cmp_fn node_cmp; + int level; + struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; +}; + +/** + * Initialise an empty tree. + * + * All tree entries must include an embedded ez_node as the first + * member. + * + * @param tree tree to initialise. + */ +void ez_tree_init(struct ez_tree *tree); + +/** + * Number of nodes in tree. + */ +static __inline__ int ez_tree_size(ez_tree *tree) { + // well if it's good enough for Knuth. + return tree->root.u.tree.link[0]; +} + +/** + * Retrieve the root node of the tree. + */ +static __inline__ void *ez_tree_root(ez_tree *tree) { + return (void *)tree->root.u.tree.link[1]; +} + +/** + * Remove all nodes from a tree. + * + * This will be substantially quicker than removing all nodes + * as there is no need to maintain the tree balance incrementally. + * + * Any nodes are freed using the node_free function. + * + * @param tree + * @param node_free free function. Must be supplied. + */ +void ez_tree_clear(ez_tree *tree, ez_free_fn node_free); + +/** + * Retrieve an item by key. + * + * @param tree + * @param node_cmp node compare function. + * @param key_node is of the same type as the entires in the tree but + * only needs to contain enough valid fields for node_cmp to function. + * @return an exact match for the key or NULL if no such key exists. + */ +void *ez_tree_get(ez_tree *tree, ez_cmp_fn node_cmp, const void *key_node); + +/** + * Put a new item into the tree. This will replace any existing + * item which matches. + * + * @param tree + * @param node_cmp node compare function. + * @param node a data node. The type must start with an ez_node. + * @return the previous node which matches the same key. + */ +void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node); + +/** + * Remove an item from the tree by key. + * + * @param tree + * @param node_cmp node compare function. + * @param key_node node who's quality indicates a match. + * @return a node matching key_node, or NULL if no such node exists. + */ +void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key_node); + +/** + * Initialise tree scanner for walking the tree in order. + * + * This initialises a general purpose iterator. Typical operations of + * FIRST, LAST, greater-or-equal, or less-or-equal are supported by + * choosing appropriate parameters. + * + * If a key is supplied in @param key_node then it is used as the + * reference point for the initialisation. EZ_LINK_LEFT will find the + * nearest node less than or equal to the key, and EZ_LINK_RIGHT will + * find the nearest node greater than or equal to the key. + * + * If no key is supplied then EZ_LINK_LEFT finds the left-most node in + * the whole tree (first), and EZ_LINK_RIGHT finds the right-most node + * (last). + * + * Note that the tree must not be modified in any way whilst the scanner + * is being used outside of the scanner functions. + * + * @param tree initialised tree. + * @param scan (un)initialised scan state. + * @param dir Direction to initialise in. + * @param node_cmp Node compare function. Must be supplised if + * key_node is supplied, or if ez_tree_scan_remove() is called with a + * valid direction. + * @param key_node optional key node. + * @return The found node if any is returned. + */ +void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t dir, ez_cmp_fn node_cmp, void *key_node); + +/** + * Move to the next node in the tree. + * + * @param dir The direction to move in. + * @return the next node, or NULL if the boundaries have been reached. + */ +void *ez_tree_scan_next(ez_tree_scan *scan, enum ez_node_link_t dir); + +/** + * Remove the current node. + * + * This removes the node and then moves to the next node based on the + * direction. If a value of -1 is used for @param dir then no + * movement will take place the the scan must be re-initialised for + * any further use. + * + * Nodes must not be freed until after they have been removed. + * + * @param dir The direction to move in next, or -1 to finish the scan. + */ +void *ez_tree_scan_remove(ez_tree_scan *scan, enum ez_node_link_t dir); + +/** + * Replace the current entry. + * + * Note that the node inserted must not break the ordering of the + * tree. + * + * @param node New entry. + * @return The previous entry at this location. + */ +void *ez_tree_scan_put(ez_tree_scan *scan, void *node); + +static int ez_tree_size(struct ez_tree *tree) __attribute__((always_inline)); +static void *ez_tree_root(struct ez_tree *tree) __attribute__((always_inline)); + +#endif diff --git a/test-bitset.c b/test-bitset.c new file mode 100644 index 0000000..2815d95 --- /dev/null +++ b/test-bitset.c @@ -0,0 +1,136 @@ + +#include +#include +#include +#include + +#include "ez-bitset.h" + +#include + +/* copy internal decl from ez-bitset.c */ +#define L0B 9 +#define L1B 9 +#define L2B 14 + +#define L0 (1<level1[id0]; + + if (l1) { + for (int id1 = 0; id1 < L1; id1++) { + struct level2 *l2 = l1->level2[id1]; + + if (l2) { + for (int id2=0;id2bits[id2]) + printf(" %4d.%4d.%4d %08x\n", id0, id1, id2, l2->bits[id2]); + } + } + } + } + } +} + +int main(int argc, char **argv) { + ez_bitset *bs = ez_bitset_new(); + int total = 0; + for (int i=1500;i<2060;i++) { + ez_bitset_set(bs, i, 1); + total ++; + } + + assert(ez_bitset_card(bs) == total); + + ez_bitset_scan scan; + uint32_t bit, check; + + + info(bs); + + check = 1500; + for (bit = ez_bitset_scan_init(bs, &scan); bit != ~0; bit = ez_bitset_scan_next(&scan)) { + //printf(" %d\n", bit); + assert(check == bit); + check++; + } + + //printf("card = %d\n", ez_bitset_card(bs)); + check = 1500; + for (bit = ez_bitset_scan_init(bs, &scan); bit != ~0; bit = ez_bitset_scan_remove(&scan)) { + //printf(" remove %d\n", bit); + assert(check == bit); + check++; + } + + assert(ez_bitset_card(bs) == 0); + //printf("card = %d\n", ez_bitset_card(bs)); + + check = 0; + for (bit = ez_bitset_scan_init(bs, &scan); bit != ~0; bit = ez_bitset_scan_next(&scan)) { + check++; + } + assert(check == 0); + + ez_bitset_free(bs); + + bs = ez_bitset_new(); + ez_bitset_clear(bs); + total = 0; + for (int i=65536;i<65536+(1<<20);i+=7) { + ez_bitset_set(bs, i, i); + total += 1; + } + assert(ez_bitset_card(bs) == total); + + //info(bs); + for (int i=65536;i<65536+(1<<20);i++) { + int v = (i-65536) % 7 == 0; + + assert(v == ez_bitset_get(bs, i)); + } + + ez_bitset_clear(bs); + for (int i=65536-65;i<65536+(1<<20)+65;i++) { + assert(0 == ez_bitset_get(bs, i)); + } + + ez_bitset_free(bs); + + return 0; +} + diff --git a/test-blob.c b/test-blob.c new file mode 100644 index 0000000..1024cb9 --- /dev/null +++ b/test-blob.c @@ -0,0 +1,274 @@ + +#include +#include +#include +#include +#include + +#include + +#include "ez-blob.h" + +struct simple { + char b; + short s; + int a; + float c; + double d; +}; + +static const ez_blob_desc simple_DESC[] = { + EZ_BLOB_START(struct simple), + EZ_BLOB_INT8(struct simple, 1, b), + EZ_BLOB_INT16(struct simple, 2, s), + EZ_BLOB_INT32(struct simple, 3, a), + EZ_BLOB_FLOAT32(struct simple, 4, c), + EZ_BLOB_FLOAT64(struct simple, 5, d), + EZ_BLOB_END(struct simple) +}; + +struct arrays { + uint32_t count; + char *string; + ez_blob_array array; +}; + +static const ez_blob_desc array_DESC[] = { + EZ_BLOB_START(struct arrays), + EZ_BLOB_STRING(struct arrays, 1, string), + EZ_BLOB_ARRAY(struct arrays, 2, array), + EZ_BLOB_END(struct arrays) +}; + +struct embedded { + struct simple s; + struct arrays a; +}; + +static const ez_blob_desc embed_DESC[] = { + EZ_BLOB_START(struct embedded), + EZ_BLOB_STRUCT(struct embedded, 1, s, simple_DESC), + EZ_BLOB_STRUCT(struct embedded, 2, a, array_DESC), + EZ_BLOB_END(struct embedded) +}; + +struct tree { + struct tree *left; + struct tree *right; + + char *s; +}; + +static const ez_blob_desc tree_DESC[] = { + EZ_BLOB_START(struct tree), + EZ_BLOB_STRING(struct tree, 1, s), + EZ_BLOB_POINTER(struct tree, 2, left, tree_DESC), + EZ_BLOB_POINTER(struct tree, 3, right, tree_DESC), + EZ_BLOB_END(struct tree) +}; + +static void dumphex(const char *data, size_t size, const char *prefix) { + for (int i=0;ibd_type != EZ_BLOB_END);d++) { + const void *u = a + d->bd_offset; + + printf("%s [type=$%02x, offset=$%04x]", x, d->bd_type, d->bd_offset); + + switch (d->bd_type) { + case EZ_BLOB_INT8: + printf(" .%d = %d\n", d->bd_id, *(uint8_t *)u); + break; + case EZ_BLOB_INT16: + printf(" .%d = %d\n", d->bd_id, *(uint16_t *)u); + break; + case EZ_BLOB_INT32: + printf(" .%d = %d\n", d->bd_id, *(uint32_t *)u); + break; + case EZ_BLOB_INT64: + printf(" .%d = %ld\n", d->bd_id, *(uint64_t *)u); + break; + case EZ_BLOB_FLOAT32: + printf(" .%d = %f\n", d->bd_id, *(float *)u); + break; + case EZ_BLOB_FLOAT64: + printf(" .%d = %f\n", d->bd_id, *(double *)u); + break; + case EZ_BLOB_STRING: + printf(" .%d %p = `%s'\n", d->bd_id, *((char **)u), *((char **)u)); + break; + case EZ_BLOB_ARRAY: { + const struct ez_blob_array *ua = u; + + printf(" .%d %p [%d] = {\n", d->bd_id, ua->data, ua->size); + dumphex(ua->data, ua->size, x); + printf("%s }\n", x); + break; } + case EZ_BLOB_POINTER: { + void *up = *((void **)u); + if (up) { + printf(" .%d %p = {\n", d->bd_id, up); + blob_print(d->bd_table, up, depth+4); + printf("%s }\n", x); + } else { + printf(" .%d %p\n", d->bd_id, up); + } + break; + } + default: + printf("\n"); + } + } + + return e; +} + +static int blob_equals(const ez_blob_desc *d, const void *a, const void *b) { + int e = 1; + for (;e && (d->bd_type != EZ_BLOB_END);d++) { + const void *u = a + d->bd_offset; + const void *v = b + d->bd_offset; + + switch (d->bd_type) { + case EZ_BLOB_INT8: + e &= (*(uint8_t *)u) == (*(uint8_t *)v); + break; + case EZ_BLOB_INT16: + e &= (*(uint16_t *)u) == (*(uint16_t *)v); + break; + case EZ_BLOB_INT32: + e &= (*(uint32_t *)u) == (*(uint32_t *)v); + break; + case EZ_BLOB_INT64: + e &= (*(uint64_t *)u) == (*(uint64_t *)v); + break; + case EZ_BLOB_FLOAT32: + e &= (*(float *)u) == (*(float *)v); + break; + case EZ_BLOB_FLOAT64: + e &= (*(double *)u) == (*(double *)v); + break; + case EZ_BLOB_STRING: + e &= strcmp((*(char **)u), (*(char **)v)) == 0; + break; + case EZ_BLOB_ARRAY: { + const struct ez_blob_array *ua = u; + const struct ez_blob_array *va = v; + + e &= ua->size == va->size + && memcmp(ua->data, va->data, ua->size) == 0; + break; } + } + } + + return e; +} + +static void test_basics(const ez_blob_desc *d, void *src) { + void *blob, *blob2; + void *t; + size_t size, size2; + size_t dsize = d->bd_offset; + char tmp[dsize + 64] __attribute__ ((aligned(64))); + + printf("source\n"); + blob_print(d, src, 4); + + blob = ez_blob_encode(d, src, &size); + + // check decode equals + t = ez_blob_decode(d, blob, size); + assert(t != NULL); + assert(blob_equals(d, t, src)); + + dumphex(blob, size, "serial: "); + + printf("decoded\n"); + blob_print(d, t, 4); + + // check encode-decoded equals source + blob2 = ez_blob_encode(d, t, &size2); + assert(size == size2); + assert(memcmp(blob, blob2, size) == 0); + free(blob2); + + ez_blob_free(d, t); + + // check raw decode stays within bounds of struct + memset(tmp, 0xbe, sizeof(tmp)); + t = ez_blob_decode_raw(d, blob, size, &tmp[32]); + //assert(t != NULL); + //assert(blob_equals(d, tmp+32, src)); + dumphex(tmp, sizeof(tmp), "object: "); + + for (int i=0;i<32;i++) { + assert((tmp[i] & 0xff) == 0xbe); + assert((tmp[i + 32 + dsize] & 0xff) == 0xbe); + } + ez_blob_free_raw(d, tmp+32); + free(blob); +} + +static void test_simple(void) { + struct simple src = { + 'z', 0xff0f, 1, 3.14159f, 5644941221133 + }; + const ez_blob_desc *d = simple_DESC; + + test_basics(d, &src); +} + +static void test_arrays(void) { + char data[7] = { 1, 2, 3, 4, 5, 6, 7 }; + struct arrays src = { + 32, + "Bob was here.", + .array.size = 7, + .array.data = data + }; + const ez_blob_desc *d = array_DESC; + + test_basics(d, &src); +} + +static void test_tree(void) { + struct tree src[6] = { + { &src[1], &src[3], "root" }, + { NULL, &src[2], "left" }, + { NULL, NULL, "left-right" }, + { &src[4], &src[5], "right" }, + { NULL, NULL, "right-left" }, + { NULL, NULL, "right-right" }, + }; + const ez_blob_desc *d = tree_DESC; + + test_basics(d, &src); +} + +int main(int argc, char **argv) { + test_simple(); + test_arrays(); + test_tree(); +} diff --git a/test-list.c b/test-list.c new file mode 100644 index 0000000..15c0c54 --- /dev/null +++ b/test-list.c @@ -0,0 +1,157 @@ + +#include + +#include "ez-list.h" + +#include + +struct node { + struct ez_node ln; + int value; +}; + +int scan_list(struct ez_list *list) { + int count = 0; + for (struct node *w=ez_list_head(list), *n=ez_node_succ(w);n;w=n,n=ez_node_succ(n)) { + count++; + } + return count; +} + +void node_remove(struct ez_node *n) { + ez_node_remove(n); +} + +void list_addtail(struct ez_list *list, struct ez_node *n) { + ez_list_addtail(list, n); +} + +static void check_list(struct ez_list *list, int max) { + struct node *w, *n; + int j; + struct node *order[32]; + + assert(list->tail == NULL); + j = 0; + for (w=ez_list_head(list), n=ez_node_succ(w);n;w=n,n=ez_node_succ(n)) { + order[j++] = w; + assert(j <= max); + } + for (w=ez_list_tail(list), n=ez_node_pred(w);n;w=n,n=ez_node_pred(n)) { + assert(order[--j] == w); + assert(j >= 0); + } + assert(j == 0); +} + +static void check_16(struct ez_list *list) { + struct node *w, *n; + int j; + + check_list(list, 16); + assert(ez_list_size(list) == 16); + + j = 0; + for (w=ez_list_head(list), n=ez_node_succ(w);n;w=n,n=ez_node_succ(n)) { + assert(ez_node_pred(n) == w); + assert(j++ == w->value); + } + assert(j == 16); +} + +int main(int argc, char **argv) { + struct node nodes[16]; + struct ez_list list; + + for (int i=0;i<16;i++) + nodes[i].value = i; + + ez_list_init(&list); + for (int i=0;i<16;i++) + ez_list_addtail(&list, &nodes[i]); + check_16(&list); + for (int i=0;i<16;i++) { + struct node *n; + n = ez_list_remtail(&list); + assert(n->value == 15-i); + check_list(&list, 16-i); + } + assert(ez_list_size(&list) == 0); + assert(ez_list_empty(&list)); + + for (int i=0;i<16;i++) + ez_list_addhead(&list, &nodes[15-i]); + check_16(&list); + for (int i=0;i<16;i++) { + struct node *n; + n = ez_list_remhead(&list); + assert(n->value == i); + check_list(&list, 16-i); + } + assert(ez_list_size(&list) == 0); + assert(ez_list_empty(&list)); + + for (int i=0;i<16;i++) + ez_list_addtail(&list, &nodes[i]); + + ez_node_remove(&nodes[15]); + check_list(&list, 16); + assert(ez_list_size(&list) == 15); + + ez_node_remove(&nodes[0]); + check_list(&list, 16); + assert(ez_list_size(&list) == 14); + + ez_node_remove(&nodes[7]); + check_list(&list, 16); + assert(ez_list_size(&list) == 13); + + ez_node_remove(&nodes[8]); + check_list(&list, 16); + assert(ez_list_size(&list) == 12); + + ez_list_insert(&list, &nodes[8], &nodes[9]); + check_list(&list, 16); + assert(ez_list_size(&list) == 13); + + ez_list_insert_after(&list, &nodes[7], &nodes[6]); + check_list(&list, 16); + assert(ez_list_size(&list) == 14); + + ez_list_insert(&list, &nodes[15], NULL); + check_list(&list, 16); + assert(ez_list_size(&list) == 15); + + ez_list_insert_after(&list, &nodes[0], NULL); + check_list(&list, 16); + check_16(&list); + + + ez_list_init(&list); + for (int i=0;i<16;i++) + ez_list_addtail(&list, &nodes[i]); + int j; + j = 0; + while (!ez_list_empty(&list)) { + struct node *n = ez_list_head(&list); + + ez_node_remove(n); + assert(n->value == j++); + check_list(&list, 16); + } + assert(ez_list_size(&list) == 0); + + for (int i=0;i<16;i++) + ez_list_addtail(&list, &nodes[i]); + j = 16; + while (!ez_list_empty(&list)) { + struct node *n = ez_list_tail(&list); + + ez_node_remove(n); + assert(n->value == --j); + check_list(&list, 16); + } + + + return 0; +} diff --git a/test-port.c b/test-port.c new file mode 100644 index 0000000..f8c4fc0 --- /dev/null +++ b/test-port.c @@ -0,0 +1,120 @@ + +#include +#include +#include +#include + +#include + +#include "ez-port.h" + +/* This is really not much of a test */ + +static void *start(void *d) { + ez_port *port = d; + char *msg; + + do { + msg = ez_port_take(port); + printf("got: %s\n", msg); + sleep(1); + } while (strcmp(msg, "quit") != 0); + + return port; +} + +int main(int argc, char **argv) { + pthread_t tid; + ez_port *port = ez_port_new(4); + + pthread_create(&tid, NULL, start, port); + + for (int i=0;i<10;i++) { + printf("send: bob\n"); + ez_port_put(port, "bob"); + } + sleep(20); + for (int i=0;i<10;i++) { + printf("send: jane\n"); + ez_port_put(port, "jane"); + sleep(2); + } + ez_port_put(port, "quit"); + + pthread_join(tid, NULL); + + ez_port_free(port); + + return 0; +} + + +#if 0 + +// This is an implementation of a bounded message queue for threads +// but doesn't allow poll() or select(). +// probably not worth it + +typedef struct ez_port ez_port; +typedef struct ez_msg ez_msg; + +struct ez_port { + ez_list list; + pthread_mutex_t mutex; + pthread_cond_t cond_take; + pthread_cond_t cond_put; + unsigned int limit; + volatile unsigned int size; +}; + +void ez_port_init(ez_port *port, int limit) { + ez_list_init(&port->list); + pthread_mutex_init(&port->mutex, NULL); + pthread_cond_init(&port->cond_take, NULL); + pthread_cond_init(&port->cond_put, NULL); + port->limit = limit; + port->size = 0; +} + +void *ez_port_poll(ez_port *port) { + ez_msg *m; + int signal; + + pthread_mutex_lock(&port->mutex); + signal = port->size == port->limit; + m = ez_list_remhead(&port->list); + pthread_mutex_unlock(&port->mutex); + if (signal) + pthread_cond_signal(&port->cond_put); +} + +void *ez_port_take(ez_port *port) { + ez_msg *m; + int signal; + + pthread_mutex_lock(&port->mutex); + signal = port->size == port->limit; + while ((m = ez_list_remhead(&port->list)) == NULL) + pthread_cond_wait(&port->cond_take, &port->mutex); + pthread_mutex_unlock(&port->mutex); + if (signal) + pthread_cond_signal(&port->cond_put); + + return m; +} + +void ez_port_put(ez_port *port, void *m) { + int signal; + + pthread_mutex_lock(&port->mutex); + while (port->size == port->limit) + pthread_cond_wait(&port->cond_put, &port->mutex); + signal = port->size == 0; + ez_list_addtail(&port->list, m); + pthread_mutex_unlock(&port->mutex); + + if (signal) + pthread_cond_signal(&port->cond_take); +} + +#endif diff --git a/test-set.c b/test-set.c new file mode 100644 index 0000000..32b210a --- /dev/null +++ b/test-set.c @@ -0,0 +1,136 @@ + + +#include +#include +#include + +#include "ez-set.h" + +struct entry { + ez_node en; + char *value; +}; + +static unsigned int entry_hash(const void *d) { + const struct entry *e = d; + + return ez_hash_string(e->value); +} + +static int entry_equals(const void *d, const void *e) { + const struct entry *a = d; + const struct entry *b = e; + + return strcmp(a->value, b->value) == 0; +} + +static void entry_free(void *d) { + struct entry *a = d; + + free(a->value); + free(a); +} + +int main(int argc, char **argv) { + FILE *fp = fopen("/usr/share/dict/words", "r"); + char word[256]; + ez_set *set; + int count = 0; + + set = ez_set_new(entry_hash, entry_equals, entry_free); + + while (fgets(word, 256, fp)) { + size_t len = strlen(word); + if (len > 0) { + struct entry *e = malloc(sizeof(*e)); + + word[len-1] = 0; + e->value = strdup(word); + + e = ez_set_put(set, e); + if (e) { + printf("duplicate! %s\n", e->value); + } + count += 1; + } + } + fclose(fp); + + // calc some stats + int min = 1000, max = 0; + int n = 0, t = 0; + int hist[64] = { 0 }; + for (int i=0;i<=set->mask;i++) { + int c = 0; + for (ez_node *e = set->table[i];e;e=ez_node_next(e)) + c++; + min = c < min ? c : min; + max = c > max ? c : max; + if (c != 0) { + n += 1; + t += c; + } + if (0 && c > 4) { + printf(" %5d:", i); + for (ez_node *e = set->table[i];e;e=ez_node_next(e)) { + char *value = ((struct entry *)e)->value; + printf(" %08x '%s'", set->hash(e), value); + } + printf("\n"); + } + hist[c < 64 ? c : 63] += 1; + } + printf("chains %d length %d - %d ave %f (> 0)\n", set->mask+1, min, max, (float)t / n); + max = max < 64 ? max : 63; + for (int i=0;i<=max;i++) { + printf(" %5d: %d\n", i, hist[i]); + } + printf("\n"); + + { + struct entry *e; + struct entry key = { + .value = "Abner" + }; + e = ez_set_get(set, &key); + printf("lookup %s = %p %s\n", key.value, e, e->value); + key.value = "fuckwit"; + e = ez_set_get(set, &key); + printf("lookup %s = %p %s\n", key.value, e, e ? e->value : ""); + } + + ez_set_scan scan; + + // iterate + int ncount = 0; + for (struct entry *n = ez_set_scan_init(set, &scan); n ; n = ez_set_scan_next(&scan)) { + ncount ++; + } + printf("size %d insert count %d scan count %d\n", ez_set_size(set), count, ncount); + + printf("set_clear\n"); + ez_set_clear(set); + printf(" size %d\n", ez_set_size(set)); +#if 0 + + // iterate and clear all + struct entry *e; + e = ez_set_scan_init(set, &scan); + int rcount = 0; + while (e) { + struct entry *p = e; + + e = ez_set_scan_remove(&scan); + rcount ++; + + //printf(" %s\n", p->value); + + free(p->value); + free(p); + } + printf("size %d rcount %d\n", ez_set_size(set), rcount); +#endif + + ez_set_free(set); +} + diff --git a/test-tree.c b/test-tree.c new file mode 100644 index 0000000..768cd44 --- /dev/null +++ b/test-tree.c @@ -0,0 +1,477 @@ + +#include +#include +#include + +#include + +#include "ez-tree.h" + +/* + Another bunch of shitty tests. + */ + +struct node { + struct ez_node tn; + + int value; +}; + +struct lnode { + struct ez_node tn; + + int value; +}; + +static int node_cmp(const void *a, const void *b) { + const struct node *c = a, *d = b; + return c->value - d->value; +} + +static __inline__ int node_balance(struct ez_node *n) __attribute__((always_inline)); + +static __inline__ int node_balance(struct ez_node *n) { + int i = n->u.tree.link[0]; + return i << 30 >> 30; +} + +static int check_balance(struct ez_node *n) { + if (n) { + int l = check_balance(ez_node_left(n)); + int r = check_balance(ez_node_right(n)); + int b = node_balance(n); + + assert(r-l == b); + return 1 + (l > r ? l : r); + } else + return 0; +} + +static int count_nodes(struct ez_node *n) { + int c = 0; + while (n) { + c += 1; + c += count_nodes(ez_node_left(n)); + n = ez_node_right(n); + } + return c; +} + +static void get_none(ez_tree *t, int i) { + struct node k = { .value = i }; + assert(ez_tree_get(t, node_cmp, &k) == NULL); +} + +static void get_exists(ez_tree *t, int i) { + struct node k = { .value = i }; + struct node *n; + + n = ez_tree_get(t, node_cmp, &k); + assert(n != NULL); + assert(n->value == i ); +} + +static void del_exists(ez_tree *t, int i) { + struct node k = { .value = i }; + struct node *n; + + n = ez_tree_remove(t, node_cmp, &k); + assert(n != NULL); + assert(n->value == i ); + free(n); +} + +static void put_new(ez_tree *t, int i) { + struct node *n = malloc(sizeof(*n)); + + n->value =i; + + assert(ez_tree_put(t, node_cmp, n) == NULL); +} + +struct word { + ez_node node; + int index; + char *word; +}; + +static int word_cmp(const void *ap, const void *bp) { + const struct word *a = ap, *b = bp; + + return strcmp(a->word, b->word); +} + +static void word_free(void *ap){ + struct word *a = ap; + + free(a->word); + free(a); +} + +static ez_tree *read_words(struct word ***array, int *asize) { + FILE *fp = fopen("/usr/share/dict/words", "r"); + char word[256]; + int count = 0; + ez_tree *tree = malloc(sizeof(*tree)); + + ez_tree_init(tree); + + if (array) { + *asize = 16384; + *array = malloc((*asize) * sizeof(void *)); + } + + while (fgets(word, 256, fp)) { + size_t len = strlen(word); + if (len > 0) { + struct word *e = malloc(sizeof(*e)); + + word[len-1] = 0; + e->word = strdup(word); + + if (array) { + if (count >= *asize) { + *asize = *asize * 2; + *array = realloc(*array, *asize * sizeof(void *)); + } + e->index = count; + (*array)[count] = e; + } + + e = ez_tree_put(tree, word_cmp, e); + if (e) { + printf("duplicate! %s\n", e->word); + word_free(e); + } + count += 1; + } + } + fclose(fp); + + *asize = count; + + return tree; +} + +void words(void) { + int count; + ez_tree *tree = read_words(NULL, &count); + + assert(count_nodes(ez_tree_root(tree)) == count); + assert(count_nodes(ez_tree_root(tree)) == ez_tree_size(tree)); + check_balance(ez_tree_root(tree)); + + ez_tree_clear(tree, word_free); + free(tree); +} + +void words2(void) { + int count = 0; + struct word **words; + ez_tree *t = read_words(&words, &count); + + int limit = count / 3; + int seen =0; + ez_tree_scan scan; + struct word key = { .word = "bullshit" }; + + for (struct word *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, word_cmp, &key); n && seen < limit; seen++) { + struct word *w = n; + + n = ez_tree_scan_remove(&scan, EZ_LINK_LEFT); + + words[w->index] = NULL; + word_free(w); + } + check_balance(ez_tree_root(t)); + assert(count_nodes(ez_tree_root(t)) == count - seen); + assert(count_nodes(ez_tree_root(t)) == ez_tree_size(t)); + + free(words); + ez_tree_clear(t, word_free); + free(t); +} + +int main(int argc, char **argv) { + ez_tree tree = EZ_INIT_TREE(tree); + ez_tree *t = &tree; + + get_none(t, 0); + assert(ez_tree_root(t) == NULL); + assert(ez_tree_size(t) == 0); + + for (int i=0;i<7;i++) { + put_new(t, i); + } + assert(ez_tree_root(t) != NULL); + assert(ez_tree_size(t) == 7); + assert(count_nodes(ez_tree_root(t)) == ez_tree_size(t)); + + check_balance(ez_tree_root(t)); + for (int i=-10;i<10;i++) { + if (i >= 0 && i < 7) + get_exists(t, i); + else + get_none(t, i); + } + + ez_tree_clear(t, free); + assert(ez_tree_size(t) == 0); + assert(ez_tree_root(t) == NULL); + + for (int i=0;i<1027;i++) { + put_new(t, i); + } + assert(ez_tree_root(t) != NULL); + assert(ez_tree_size(t) == 1027); + check_balance(ez_tree_root(t)); + + for (int i=-10;i<1030;i++) { + if (i >= 0 && i < 1027) + get_exists(t, i); + else + get_none(t, i); + } + ez_tree_clear(t, free); + + // + int count, c; + + count = 0; + ez_tree_init(&tree); + for (int i=0;i<1027;i++) { + put_new(t, i); + count++; + } + for (int i=37;i<301;i++) { + del_exists(t, i); + get_none(t, i); + count--; + } + check_balance(ez_tree_root(t)); + assert(count == ez_tree_size(t)); + assert(count_nodes(ez_tree_root(t)) == ez_tree_size(t)); + + // + ez_tree_scan scan; + int j; + j = 0; + c = 0; + for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_LEFT, NULL, NULL); n ; n = ez_tree_scan_next(&scan, EZ_LINK_RIGHT)) { + assert(j == n->value); + if (j == 36) + j = 301; + else + j++; + c++; + } + assert(c == count); + + j = 1026; + c = 0; + for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, NULL, NULL); n ; n = ez_tree_scan_next(&scan, EZ_LINK_LEFT)) { + assert(j == n->value); + if (j == 301) + j = 36; + else + j--; + c++; + } + assert(c == count); + + // + ez_tree_clear(t, free); + for (int i=0;i<100;i++) { + put_new(t, i * 7); + } + for (int i=0;i<100;i++) { + struct node k = { .value = i }; + struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, node_cmp, &k); + + assert(n != NULL); + assert(n->value >= i); + assert(n->value < i + 7); + } + for (int i=0;i<100;i++) { + struct node k = { .value = i }; + struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_LEFT, node_cmp, &k); + + assert(n != NULL); + assert(n->value <= i); + assert(n->value > i - 7); + } + ez_tree_clear(t, free); + + // + words(); + words2(); + + return 0; +} + + + + + + +// this is a known working version for comparison + +#if 0 + + +void *ez_tree_removex(ez_tree *tree, const void *key) { + struct ez_tree_scan_info stack[32]; + struct ez_tree_scan_info *sp = stack; + ez_tree_node *p = (void *)tree->root.link[1]; + struct ez_tree_scan_info *si; + + // Find node, record how we got there + + *sp++ = (struct ez_tree_scan_info){ &tree->root, 1 }; + while (p) { + int cmp = tree->node_cmp(key, p); + int cmpi = cmp > 0; + + *sp++ = (struct ez_tree_scan_info){ p, cmpi }; + + if (cmp == 0) + break; + else + p = node_link(p, cmpi); + } + + if (!p) + return NULL; + +#ifdef SPEW + si = stack; + printf("pre-remove stack: p=%p\n", p); + while (si < sp) { + printf(" %p [%p %p %d] %d\n", si->node, ez_node_left(si->node), ez_node_right(si->node), node_balance(si->node), si->link); + si += 1; + } + fflush(stdout); +#endif + // Binary tree remove and adjust balance factors + ez_tree_node *r = ez_node_right(p); + + if (!r) { + node_set_link(sp[-2].node, sp[-2].link, ez_node_left(p)); + sp -= 1; + } else { + ez_tree_node *s = ez_node_left(r); + + if (!s) { + node_set_link(r, 0, ez_node_left(p)); + node_set_balance(r, node_balance(p)); + node_set_link(sp[-2].node, sp[-2].link, r); + sp[-1] = (struct ez_tree_scan_info) { r, 1 }; + } else { + ez_tree_node *q; + struct ez_tree_scan_info *psp = sp; + + *sp++ = (struct ez_tree_scan_info){ r, 0 }; + while ((q = ez_node_left(s))) { + *sp++ = (struct ez_tree_scan_info){ s, 0 }; + r = s; + s = q; + } + + node_set_link(s, 0, ez_node_left(p)); + node_set_link(r, 0, ez_node_right(s)); + node_set_link(s, 1, ez_node_right(p)); + node_set_balance(s, node_balance(p)); + + node_set_link(psp[-2].node, psp[-2].link, s); + psp[-1] = (struct ez_tree_scan_info){ s, 1 }; + } + } + +#ifdef SPEW + si = stack; + printf("post-remove stack: \n"); + while (si < sp) { + printf(" %p [%p %p %d] %d\n", si->node, ez_node_left(si->node), ez_node_right(si->node), node_balance(si->node), si->link); + si += 1; + } + //printf("tree\n"); + //dump(tree->root.link[1], 1); +#endif + + // Rebalance tree + // basic code from libavl but paramterised as in Knuth + si = sp-1; + while (si > stack) { + struct ez_tree_node *y = si->node; + int ai = si->link; + int aj = ai ^ 1; + int a = ai * 2 - 1; + int yb = node_balance(y); + +#ifdef SPEW + printf("y %p [%p %p] balance=%d ai=%d a=%d\n", y, ez_node_left(y), ez_node_right(y), node_balance(y), ai, a); + fflush(stdout); +#endif + if (a == yb) + node_set_balance(y, 0); + else if (yb == 0) { + node_set_balance(y, -a); + break; + } else { + struct ez_tree_node *x = node_link(y, aj); + int xb = node_balance(x); + +#ifdef SPEW + printf("x %p [%p %p] balance=%d\n", x, ez_node_left(x), ez_node_right(x), node_balance(x)); + fflush(stdout); +#endif + if (xb == a) { + // double rotate + struct ez_tree_node *w = node_link(x, ai); + int wb = node_balance(w); +#ifdef SPEW + printf("w %p [%p %p] balance=%d\n", w, ez_node_left(w), ez_node_right(w), node_balance(w)); + fflush(stdout); +#endif + x->link[ai] = node_link(w, aj); + w->link[aj] = (intptr_t)x; + y->link[aj] = node_link(w, ai); + w->link[ai] = (intptr_t)y; + + node_set_balance(y, wb == -a ? +a : 0); + node_set_balance(x, wb == +a ? -a : 0); + node_set_balance(w, 0); + + node_set_link(si[-1].node, si[-1].link, w); + } else { + // single rotate + y->link[aj] = node_link(x, ai); + x->link[ai] = (intptr_t)y; + node_set_link(si[-1].node, si[-1].link, x); + if (xb == 0) { + node_set_balance(x, +a); + node_set_balance(y, -a); + break; + } else { + node_set_balance(x, 0); + node_set_balance(y, 0); + } + } + } + + si -= 1; + } + + //si = stack; + //printf("stack: \n"); + //while (si < sp) { + // printf(" %p %d\n", si->node, si->node->value); + // si += 1; + //} + //printf("tree\n"); + //dump(tree->root.link[1], 1); + + return p; +} + +#endif -- 2.39.5