Archive for the 'Code' Category

iPhone SDK on the way

A beta of the iPhone SDK was released this afternoon at about 1 CST. I immediately tried to get on the site, only to be greeted by a friendly page that said:

Safari can’t open the page “http://developer.apple.com/iphone/program/” because the server unexpectedly dropped the connection, which sometimes occurs when the server is busy. You might be able to open the page later.

This continued all afternoon until just about 10 minutes, when I was finally able to get through!
My downloads window

Using counting semaphores on Mac OS X

The POSIX runtime extension includes counting semaphores, specified by functions such as sem_wait, sem_post, and sem_create. Unfortunately, OS X does not implement sem_create for counting (unnamed) semaphores, only implementing it for named semaphores. This certainly creates quite an issue if you want the ease of use (or power in some cases), of a counting semaphore.

I thought I was at a loss for using them until I stumbled upon the Mach kernel primitive semaphores, which happen to be, thank goodness, counting semaphores. The Mach kernel specifies the following functions for using semaphores, as defined by <mach/semaphore.h> and <mach/task.h> (Note: I have only listed the important ones that have POSIX relatives):

kern_return_t semaphore_create(task_t task, semaphore_t *semaphore,
    int policy, int value)
kern_return_t semaphore_signal(semaphore_t semaphore)
kern_return_t semaphore_signal_all(semaphore_t semaphore)
kern_return_t semaphore_wait(semaphore_t semaphore)
kern_return_t semaphore_destroy(task_t task, semaphore_t semaphore)
kern_return_t semaphore_signal_thread(semaphore_t semaphore,
    thread_act_t thread_act)

By looking at them, you can probably guess what they do, and if you don’t, you can always look it up in the documentation, or click here to view it on Apple’s developer website.

You may however, be wondering what the task_t type is, and how you might possibly retrieve the correct task_t struct. But never fear, in <mach/task.h>, there are two methods for getting the current task: current_task and mach_task_self, which both return the current task, but in different forms. For user space programming, you should use mach_task_self, which returns a pointer to the kernel’s virtual memory map. If you are doing kernel programming, however, you would not want to use mach_task_self, and instead you want to use current_task. Do not attempt to use current_task in user-space programming, since linking of your code will fail since the symbol is only available to Kernel extensions.

Below is an example using the counting semaphore primitives. Basically, we are counting up and counting down a static variable by the same amount on two separate threads. With the semaphores, the final value should be zero. If you remove the semaphores, you will not get zero, and you will get some arbitrary value.

#include <stdio.h>
#include <pthread.h>

#include <mach/semaphore.h>
#include <mach/task.h>

static int x = 0;
semaphore_t sem = 0;

void * countUp(void *param)
{
    semaphore_wait(sem);

    unsigned i = 0;
    for (i = 0; i < 100000000; i++)
        x++;

    semaphore_signal(sem);
    return NULL;
}

void * countDown(void * param)
{
    semaphore_wait(sem);
    unsigned i = 0;
    for (i = 0; i < 100000000; i++)
        x--;

    semaphore_signal(sem);
    return NULL;
}

int main (int argc, const char * argv[])
{
    // Create our semaphore. SYNC_POLICY_FIFO is how we handle threads that are
    // waiting on the semaphore. I am pretty sure that POSIX uses FIFO, so I
    // think it is best to use that here, though there are other options defined
    // in .
    int initialValue = 1;
    semaphore_create(mach_task_self(), &sem, SYNC_POLICY_FIFO, initialValue);

    pthread_t up, down;
    pthread_create(&up, NULL, countUp, NULL);
    pthread_create(&down, NULL, countDown, NULL);

    pthread_join(up, NULL);
    pthread_join(down, NULL);

    printf(”%d\n”, x);  // Should print 0.

    return 0;
}

Now the only problem with this code is that it is not platform independent, and will not compile on Linux. If you wanted, you could make platform independent versions of semaphore creating, posting, and waiting functions, as implemented in the example below:

#ifdef __APPLE__
#include <mach/semaphore.h>
#include <mach/task.h>
#else
#include <semaphore.h>
#endif

void platform_sem_create(void * semStructure, int initialValue)
{
    #ifdef __APPLE__
    semaphore_create(mach_task_self(), (semaphore_t *)semStructure, SYNC_POLICY_FIFO, initialValue);
    #else
    int pshared = 0;
    sem_init((sem_t *)semStructure, pshared, initialValue);
    #endif
}

void platform_sem_signal(void * semStructure)
{
    #ifdef __APPLE__
    semaphore_signal(*((semaphore_t *)semStructure));
    #else
    sem_post((sem_t *)semStructure);
    #endif
}

void platform_sem_wait(void * semStructure)
{
    #ifdef __APPLE__
    semaphore_wait(*((semaphore_t *)semStructure));
    #else
    sem_wait((sem_t *)semStructure);
    #endif
}

Then in your code, just use platform_sem_create, platform_sem_signal, and platform_sem_wait instead of functions like sem_wait, semaphore_create, etc.

And that’s the magic to using counting semaphores on Mac OS X.

MPRuntime now has autorelease

I just finished implementing an autorelease pool opaque type for the MPRuntime, and to be honest, it’s pretty sweet. Basically an autorelease pool is a list that you put object pointers in, and then when you are done with the pool and you release it, it releases all of the objects in the pool. This can greatly reduce code size and also delay calling expensive memory free calls until a single moment.

Non-autorelease pool way:
Below is the old code for creating an array, and then adding 100 integers to it.

// Create an array and add a bunch of integers to it.
MPArrayRef array = MPArrayCreate(&kMPTypeArrayCallbacks);
for (unsigned i = 0; i < 100; i++)
{
    MPNumberRef num = MPNumberCreateWithUnsigned(i);
    MPArrayAppendValue(array, num);
    MPRelease(num);
}

// Release our array.
MPRelease(array);

As you can see, it’s quite a hassle to keep the pointer around so you can call release on it. The example above isn’t the greatest because there are no like nested function calls and such, but just imagine magnifying the number of MPRelease statements and how many pointers you would have to keep around. So instead, as in the example below, you can simply autorelease the object so you don’t have to keep that pointer around, and you can send created objects directly in as arguments to function calls and what not.

Autorelease pool way:

// Create the pool.
MPAutoreleasePoolRef pool = MPAutoreleasePoolCreate(0);

// Create an array and add a bunch of integers to it.
MPArrayRef array = MPAutorelease(MPArrayCreate(&kMPTypeArrayCallbacks));
for (unsigned i = 0; i < 100; i++)
    MPArrayAppendValue(array, MPAutorelease(MPNumberCreateWithUnsigned(i)));

// Release the pool, thus draining it.
MPRelease(pool);

Now that’s what I call sweet!

The files on the MPRuntime page contain the autorelease pool.

The MPRuntime

For an MP for class, I needed a data structure. I thought to myself, well, how would it be done at Apple? CoreFoundation. So I dug in and really tried to understand the CoreFoundation framework, and then implemented by own mini-version with many of the same paradigms. The system I came up with was the MPRuntime.

Here’s how it’s described on the MPRuntime page and in the header:

The MPRuntime API provides a set of opaque data types written in procedural C. The types are meant to make creating collections (such as lists and queues) as well as your own types much easier. The runtime presents a memory model that aids in preventing leakage, and takes after the paradigms of Apple’s CoreFoundation framework.

It should be noted that as of right now, the only opaque types implemented in the runtime include the runtime base (allocators, runtime instances), in addition to a strong array type and a number type for dealing with numbers. As more types become available, read their individual descriptions for usage.

Memory management with MPRuntime is done using reference counting. For every function that returns an object that has “Create” in the name, the object returned should be sent to MPRelease when you are done with the object. Similarly, if you want to keep an object around, you can call MPRetain to increase the retain count by one. You can read more about this at the following URL: http://en.wikipedia.org/wiki/Reference_counting.

Go ahead, download it and give it a try! See how easy data structures in C can really be.

Making CombSort ranged

I just made some tweaks to the combsort. Basically, my version will now sort over a range of the array. You give it a start index, and then you give it how many integers from that index (including that index) you want to sort. The new code looks something like this:

void combsort_ranged(int * input, unsigned start, unsigned len, int (*comparison)(int *s0, int *s1))
{
    unsigned end = start + len;
    unsigned gap = len;
    unsigned int swaps = 0xFFFF;

    while(gap > 1 || swaps != 0)
    {
        if (gap > 1)
        {
            gap /= 1.3;
            if (gap == 10 || gap == 9)
                gap = 11;
        }

        unsigned i = start;
        swaps = 0;

        while (i + gap < end)
        {
            if (comparison(&(input[i]), &(input[i + gap])) > 0)
            {
                // Swap input[i] and input[i + gap]
                int temp = input[i];
                input[i] = input[i + gap];
                input[i + gap] = temp;
                swaps = 1;
            }

            i++;
        }
    }
}

My CombSort logic error

When I wrote my CombSort algorithm yesterday, I started running into problems with arrays of small sizes. For example, the array {9, 2, 7, 4} would sort to {4, 2, 7, 9}. And then I realized, every time the last floor(count/1.3) elements failed comparison (meaning that they were already sorted), then the algorithm exited, leaving the middle of the array unsorted. With arrays of thousands or millions of integers, this was not a problem since the probability of this was miniscule. But, as the array size got smaller, this possibility rapidly increased, especially if the range of numbers was also decreased.

However, I just found my logic error, which occurred when testing to see if the algorithm should continue. I was reading that the algorithm should always run with a gap size of 1 (to ensure that it is sorted), even if the last pass didn’t sort anything. The condition for continuing should be if the gap is greater than one or the previous pass did not sort anything. Therefore, my original logic for testing this was flawed since it was the logical inverse.

The code should be:

while(gap > 1 || swaps != 0)

I have updated the original post to reflect this.

CombSort: The forgotten sorting algorithm

As I was working today on an MP, I needed a sorting algorithm that would work well with linked lists. For those of you who have ever written a linked list data structure of some kind, you will know that splitting and reallocated buffers and such is a pain. Sorting algorithms such as mergesort, heapsort, and quicksort use those kinds of techniques, making them very hard to implement on a linked list.

“But…”, you say, “mergesort and heapsort and quicksort all give us really good running times and memory usage!” Well my friends, do not fear, for there is another sorting algorithm I had never heard of until today: combsort. The idea of combsort is similar to that of bubblesort: going through the buffer linearly as many times as need, and the running comparisons on particular elements. No reallocation is done, no splitting, just the exchange of elements.

Yet again, bubblesort falls very short of the O(nlogn) running time of quick/merge/heapsort. But amazingly enough, combsort also runs in O(nlogn) as well! This makes combsort an extremely attractive option for a number of reasons:

  • O(nlogn) average and worst case running time which is right up there with merge/heap/quicksort.
  • O(1) memory usage.
  • Small code size.

Here is the C code for running combsort:

void combsort(int * input, unsigned count, int (*comparison)(int *s0, int *s1))
{
    unsigned gap = count;
    unsigned int swaps = 0xFFFF;

    while(gap > 1 || swaps != 0)
    {
        if (gap > 1)
        {
            gap /= 1.3; // Funky magic number
            if (gap == 10 || gap == 9)
                gap = 11;
        }

        unsigned i = 0;
        swaps = 0;

        while (i + gap < count)
        {
            if (comparison(&(input[i]), &(input[i + gap])) > 0)
            {
                // Swap input[i] and input[i + gap]
                int temp = input[i];
                input[i] = input[i + gap];
                input[i + gap] = temp;
                swaps = 1;
            }

            i++;
        }
    }
}

How does Combsort perform?:
When sorting the same buffer of 10,000,000 integers, I got the following average times for different sorting algorithms.

BubbleSort  > 24300.000 s  // Or about 6.75 hours.
HeapSort         14.518 s
CombSort         11.189 s
MergeSort         5.789 s
QuickSort         4.497 s

So as you can see, combsort performs pretty dang well.

Conclusion:
Basically, I love combsort and I intend on making it my choice sorting algorithm for linked list structures, or any other structures where I don’t want to have to allocate some memory. To read more about combsort, check out its Wikipedia page.

TeX: Making math more enjoyable

How many of you have ever looked at a Math test and wondered, “how did they type this up with all of the funky symbols and stuff. This must have taken hours to make!” Well, maybe only I do. But, I found out how they do do those Math tests, and it’s called TeX.

TeX is a basically a simple little markup-type language that allows you to do really powerful typesetting easily. It involves typing in some code, then using a utility to turn that code into a PDF, DVI, or PostScript file. The TeX code, also known as LaTeX code, is actually quite simple. Let’s take a look at an some examples.

To create a really simple article that has a title, an author, and a date, here is all the code that is necessary:

\documentclass[11pt]{article}

\begin{document}

\title{My Article}
\author{Kevin Cathey}
\date{Today}
\maketitle

\end{document}

However, we may want to have more control on our document, like adding margins, so we need to tell TeX that we want more control. We do this by bringing in more commands into the language that TeX has. These extensions are called packages. Anyone can write a package, and TeX has quite a rich environment of them. So to do page margins or other geometric functions, we are going to bring in the package called geometry:

\usepackage[left=0.75in,top=0.75in,right=0.75in,nohead,nofoot]{geometry}

But let’s get to the good stuff. You can do quite a variety of cool mathematical and scientific things in TeX with only one command.

Symbols:
Inserting those crazy symbols is easy with TeX, just write out the name of the symbol and put a “\” before it. The following code will print out quite a different taste of symbols:

We can do all kinds of symbols, like: $\delta, \varepsilon, \Sigma, \gamma, \Gamma, \rho_0, \mu^x$.

Assortment of symbols.

With this code, you should notice a few things. First of all, symbols appear between two “$”. This is TeX’s way of saying, “this is an equation”, and then it formats it with the italics and everything, for free! Also, notice that uppercase symbols start with an uppercase letter for the name, and lowercase symbols have lowercase first letters. And finally, if you put an underscore “_” after a symbol, it makes the next character subscript, and if you use a carrot “^”, it makes it superscript. It’s that easy.

Mathematical expressions:
You can also do all kinds of really nifty mathematic expressions like fractions, integrals, etc. For example, let’s say I want to take the integral of some fraction with powers and subscripts and greek letters. I would never be able to do that easily in a word processor, but TeX makes it easy:

$\displaystyle\frac{1}{4\pi}\oint_\Sigma\frac{1}{r}\frac{\partial U}{\partial n} (\frac{\delta_{\kappa^i}}{\varepsilon}) ds$

Crazy integral equation made easy with TeX.

How about trying to do Schrodinger’s equation in a word processor? Forget it! It TeX, no problem:

- \frac{{\hbar ^2 }}{{2m}}\frac{{\partial ^2 \psi (x,t)}}{{\partial x^2 }} + U(x)\psi (x,t) = i\hbar \frac{{\partial \psi (x,t)}}{{\partial t}}

Schrodinger's one-dimensional time-independent equation

Conclusion:
I’m just touching the tip of the iceberg here. Basically, TeX acts as a great tool for generating any documents that are going to need advanced typesetting for mathematics or science. If you are a student typing up their homework, or a teacher generating a math test, this technology is a great option. TeX has a great community that has put out modules to do almost anything. To make things easy for me when I write TeX, I use a program on the Mac called TeXShop. I recommend downloading it and at least playing with it. I think you will find it quite fun to play with. For someone who doesn’t like math, it makes it just slightly more enjoyable.

Additional resources:
Mathematical typesetting in TeX.
EquationSheet: pretty much any equation you can think of in TeX code.
Mathematical symbol reference.

Using the new NSDateFormatter

As of Tiger, a new NSDateFormatter has been introduced to Foundation, and within it are a few things that might take some getting used to. So I will outline the date formatter in its entirety, and how to understand how all of the pieces work together.There are two main modes, or behaviors, of the NSDateFormatter: Pre 10.4 and 10.4+ (these same labels are used in Interface Builder).

  • Pre 10.4 Mode (NSDateFormatterBehavior10_0)
    This mode was the only mode until Tiger was introduced, and it makes use of the the strftime-style format strings. The strftime format identifiers look like “%S” (seconds), “%m” (month number), and “%d” (day of month) to just name a few. Actually, the documentation for these identifiers is accurately described in Apple’s documentation that comes with Xcode or is found online at the ADC website.

    UsageSo how might I go about creating a date formatter that exhibits the old Pre 10.4 behavior? Well, it’s actually quite simple. When you create your instance of NSDateFormatter, use the initWithDateFormat:allowNaturalLanguage: initializer, instead of the usual init method.You should note:Once you create the Pre 10.4 date formatter with a format string, you cannot change it. Though NSDateFormatter has a method setDateFormat:, it only applies to the new date formatter behavior. You can however, convert the date formatter to the newer behavior by calling setDateFormatterBehavior: and passing in NSDateFormatterBehavior10_4.

    Sample code

        NSDateFormatter *df = [[[NSDateFormatter alloc] initWithDateFormat:@"%1m/%1d/%y"
                                                        allowNaturalLanguage:YES]
                                                        autorelease];
        // The following code will print something like 2/11/2007. Also notice how
        // putting the '1' before the 'm' and 'd' in our format string took the padding
        // zeros away.
        NSLog(@"%@", [df stringForObjectValue:[NSDate date]]);
    
  • 10.4+ Mode NSDateFormatterBehavior10_4
    Arguably the behavior you will want to use in your code is the 10.4+ Mode. This mode conforms to the Unicode TR35-4 standard, so it has a ton of features that the Pre 10.4 behavior just doesn’t have. For one, it uses different identifiers, the Unicode site at this link has all of the identifiers and how you can use them to construct date format strings. The documentation is mostly accurate except that though ICU claims three lower case e’s (”eee”) should evaluate to something like “Tues” or “Wed”, that isn’t reflected by the NSDateFormatter.

    Changing the date format string
    One of the really nice things about the new date formatter behavior is that you can set the date format string to something else after you create it. If you call setDateFormat: with some string, the changes are made immediately. This is nice if your date format string is dynamic.

    Date and Time Styles
    Another feature of the 10.4+ behavior is that you can tell it to ignore date format strings all together, and instead use the time styles defined by the user in System Preferences. These are set by each user on their own system in the International pane of System Preferences:

    You can set a date or time style such as short, medium, long, full, or none at all. The methods for doing this are setDateStyle: and setTimeStyle:. The tricky part about using these styles programmatically comes in the order that you call those methods. For example, if you call setDateStyle: or setTimeStyle:, it voids the effect of the date format string. However, if after calling setDateStyle: or setTimeStyle:, you set the date format string by calling setDateFormat:, it then voids the time and date styles you just applied. The general rule of thumb is that whatever you call last is what the date formatter uses. If you set the date or time style last, it uses that; if you set the date format string last, then it uses that. The code below illustrates these little quirks.

        // Create our date formatter and a sample date to work with
        NSDateFormatter *formatter = [[[NSDateFormatter alloc] init] autorelease];
        NSDate *date = [NSDate date];
    
        // This will produce a date such as "07/11/2007 22:15".
        [formatter setDateStyle:NSDateFormatterShortStyle];
        [formatter setTimeStyle:NSDateFormatterShortStyle];
        NSLog(@"%@", [formatter stringFromDate:date]);
    
        // This will produce a date such as "07/11/2007", notice, without the time.
        [formatter setTimeStyle:NSDateFormatterNoStyle];
        NSLog(@"%@", [formatter stringFromDate:date]);
    
        // This will produce a date such as "7 Nov 2007", thus nullifying the date
        // and time styles we set above.
        [formatter setDateFormat:@"d MMM yyyy"];
        NSLog(@"%@", [formatter stringFromDate:date]);
    
        // But now if I reset the date style, we nullify our date format string.
        // And though I didn't reset the time style, since I reset the date style,
        // the formatter assumes the use of both.
        [formatter setDateStyle:NSDateFormatterShortStyle];
        NSLog(@"%@", [formatter stringFromDate:date]);
    

The NSDateFormatter can be a tricky or intimidating class at first, but I think when you really unpack it, it is quite easy. Just remember:

  • Two modes: pre 10.4 (strftime-style, NSDateFormatterBehavior10_0) and 10.4+ (Unicode, NSDateFormatterBehavior10_4).
  • When using pre 10.4 behavior, use initWithDateFormat:allowNaturalLanguage: to create it. And remember, once you create it, you can’t change the format string.
  • When using 10.4+ behavior, uses standard init to create it. You can use a date format string or the date/time styles. And when setting these, remember that the last method you call is the style it uses (date format string versus date/time styles).
  • Check out the Apple and Unicode documentation for a complete list of identifiers.

Subclassing in Interface Builder 3

Probably the most common question asked about IB 3 is: how do you subclass something? In IB 2, it was easy, right? You could just go to the class browser, find the class you wanted to subclass (typically NSObject), subclass it with a name, and then instantiate an instance of that subclass. But, what happened to the class browser in IB 3? Interface Builder 3 goes back to the idea of M-V-C: model, view, controller. For those of you familiar with this concept, you can ignore this next sentence: model is where you write code pertaining to data, view is where you write code or make graphics for what users see, and then finally, controller is where you write code relating to the response of user events. Thanks to Cocoa, the interface code is all written for us, and we can benefit from just dragging objects out of a library in IB. Our typical use to subclass an object in IB is to create a controller object or something similar that our interface talks to.

Note: Interface Builder is not the place to write code, that is the role of Xcode. IB has the ability to generate code, but more for a traditional sense. So the idea is to create a class in Xcode, and then bring the knowledge of that class into IB. Thanks to the smarts of IB, you don’t have to do any work for this, since IB is in constant communication with the pieces of your project. If you create a class, IB knows about it the next time you switch to IB from Xcode.OK, enough talk, how do I do this? Here is a step-by-step guide to subclassing something to use in IB (the example below is creating a subclass of NSObject called AppController)

  1. Create your class in Xcode
    In your Xcode project, add a new Objective-C class file by choosing New File… from the File menu. Name the file AppController.m.
  2. Instantiate your class in IB
    The instantiation process is two-fold. First, switch over to IB, and from the Library, drag an instance of NSObject (which you can find using the filter text-field) into your Document Window.
    Library

    And your Document Window should look something like this now:

    So now you have just instantiated NSObject, but what about your subclass? To make the instance you just created descend from your subclass, select in the Document Window, and then open the Identity Inspector (you can do this from the Tools menu, or if you have the inspector open, it is the sixth segment with the little “i”). Once the identity inspector is open, at the top of inspector, there is a slice called “Class Identity”, and under that is a text-field labeled “Class”. In that text-field, start typing the name of your subclass. As you are typing, by the time you get to “App”, it should have auto-completed the text-field with the name of your subclass. Again, please understand here, you no longer have to tell IB about classes in your project because IB has automatic integration with your project.

    Identity Inspector

    And your document window should now look something like this, with the “Object” replaced by “App Controller”.
    New Document Window

    At this point you are done, but if you would like to add connectivity to your class, proceed to step 3.

  3. Add actions and outlets
    Now that you have an instance of your subclass to work with in IB, you may very well want to add some connectivity between it and the interface. To do so, you can add outlets(IBOutlet) and actions (IBAction) to your class’s header file. To do so, go back to Xcode, and enter them where desired. If you need more help on this, please see the Cocoa tutorials on connections. Once you have created your outlets and actions in Xcode, switch back to IB, and by the time you do so, IB already has parsed your source code and found all of the outlets and actions, and they are now readily available for you to use.

So to quickly recap:

  1. Create your class in Xcode
  2. Switch to IB and add an instance of NSObject from the Library
  3. Change the instances class name to your subclass using the Identity Inspector
  4. Add actions and outlets
  5. Realize that subclassing in IB 3 is a lot easier than in IB 2