Have you ever lamented the absence of queues, stacks, and trees from the Cocoa API? How many times have you considered writing your own, or scoured the web to see if someone else had? Well, look no further, the work has been done for you!
CHDataStructures is a library of standard data structures which can be used in any Objective-C program, for educational purposes, or as a foundation for other data structures to build on. Data structures in this library adopt Objective-C protocols that define the functionality of and API for interacting with any implementation thereof, regardless of its internals.
For details about the project, consult the ReadMe file.
You can also see statistics for the project on https://ohloh.net. If you use the framework, consider registering on the site and adding your rating.
There is currently not a packaged binary release of the framework. However, you can download the code and build it yourself in Xcode, or just view the files online.
The repository itself is hosted at:
The repository may also be browsed via WebSVN at:
To check out latest version of the project, type this command in Terminal:
svn checkout http://dysart.cs.byu.edu/chsvn/trunk/ CHDataStructures
|NOTE: If the SVN repository is currently not working, please use the Github repo below. Thank you for your patience.|
For those of you who prefer working with the Git source control system, an official clone is located on Github:
To clone the latest version of the project, type this command in Terminal:
git clone https://github.com/davedelong/CHDataStructures.git CHDataStructures
Using the Library
CHDataStructures now builds for both Mac OS X (as a framework) and iOS (as a static library, since third-party frameworks are not supported). The following directions assume that you have either built the appropriate library form (framework or static library) from source, or are using a binary distribution. (When building from source, compile the All target in the Release configuration, which produces a disk image containing the binaries.)
NOTE: If you get a "Declaration does not declare anything" compiler warning when using this library, change the C Language Dialect (
GCC_C_LANGUAGE_STANDARD) build setting in your Xcode target to
GNU99 [-std=gnu99]. This is necessary because parts of CHDataStructures uses anonymous structs and unions, a feature not supported by the
Using the framework in a Mac application
- Open the Xcode project for your Mac application.
CHDataStructures.frameworkto your project by dragging it to the "Groups & Files" pane.
- Expand the appropriate target and use a "Copy Files" build phase to copy the framework to the
Contents/Frameworks/directory in your application bundle. (The executable path in the framework binary expects this location.)
#import <CHDataStructures/CHDataStructures.h>where necessary in your code.
For details or clarification about frameworks, consult the Framework Programming Guide.
Using the static library in an iOS app
- Open the Xcode project for your iOS app.
libCHDataStructures.aand the library header files to your project by dragging them to the "Groups & Files" pane. (You can organize the headers in their own physical directory and sidebar group to prevent clutter.)
- Expand the appropriate target and drag
libCHDataStructures.ainto the "Link Binary With Libraries" build phase.
#import "CHDataStructures.h"where necessary in your code.
If you have any issues with this approach, you can opt to drag
CHDataStructures-iOS.xcodeproj into the "Groups & Files" pane and use the
libCHDataStructures.a product from that project. In this case, you must also include
PATH_TO_CHDATASTRUCTURES/source in Header Search Paths (
HEADER_SEARCH_PATHS) for your target.
Documentation for the project (auto-generated after each commit) is available online at this link:
It can also be auto-generated from the Xcode project via the Documentation target. This requires that Doxygen be installed, and that the
doxygen binary executable be on your path.
For the extremely curious and/or cautious, it can be nice to know if you can really expect the code to work. Accordingly, the latest coverage report for the unit tests (which can also be generated from Xcode) is posted here:
Let's just say it: no software is perfect. It would be foolish (and a lie) to claim that this framework is flawless. There are several things that need to be improved, and admitting you have a problem is the first step....
Please know that it is not my intent to leave the hard things "as an exercise to the reader." (Believe me, writing a generic, iterative, state-saving tree traversal enumerator was no walk in the park!) However, I would love to draw on the talents of others who can provide solutions which currently evade me, or which I haven't had time to implement yet. If you have ideas (or even better, a fix) for one of these items, email me and we'll talk. Thanks!
Known bugs are documented in the code, and are available in the online documentation at this link:
Currently, the biggest issue is that the
-[CHRedBlackTree removeObject:] method is reeeeaaaaaly slow. You may notice that the time complexity increases exponentially, not linearly. It turns out that implementing a non-recursive remove for Red-Black trees is non-trivial, and the current solution works correctly but needs work. (For now, I suggest using CHAVLTree or CHAnderssonTree instead.)
A number of desired future improvements are documented in the code, and are available in the online documentation at this link:
I've made an attempt to track the more significant issues in a bug database, since it remembers better than I do. You can browse it here:
This framework is is licensed under a variant of the ISC license, an extremely simple and permissive free software license approved by the Free Software Foundation (FSF) and Open Source Initiative (OSI). The license for this framework is included in every source file, and is repoduced in its entirety here:
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
The software is provided "as is", without warranty of any kind, including all implied warranties of merchantability and fitness. In no event shall the authors or copyright holders be liable for any claim, damages, or other liability, whether in an action of contract, tort, or otherwise, arising from, out of, or in connection with the software or the use or other dealings in the software.
This license is functionally equivalent to the MIT and two-clause BSD licenses, and replaces the previous use of the GNU Lesser General Public License (LGPL), which is much more complex and frequently misunderstood. In addition, using GPL-style licenses (which are generally unfriendly towards commercial software) makes little sense for Mac developers, whether open-source or proprietary.
If you contribute source code to the framework, you may keep your copyright or assign it to me, but you must agree to license the code under this license.
Contributing to the Framework
All contributions (including bug reports and fixes, optimizations, new data structures, etc.) are welcomed and encouraged. In keeping with this project's goals, new features are subject to consideration prior to approval—there are no guarantees of adoption. Modifications that are deemed beneficial to the community as a whole will fit with the vision of this project and improve it. However, not all potential contributions make sense to add to the framework. For example, additions or enhancements that only apply for a specific project would be more appropriate to add as categories or subclasses in that code.
Please email Quinn Taylor if you're interested in contributing to the project, discussing improvements or additions you'd like to see, or even just letting him know that you're getting some use from it.