No.

It was love at first sight. It was fall. The leaves were changing color. The air was cool and crisp, and my head was still reeling from reading about the Composite Pattern. I turned the page on my copy of the GOF, and there the Singleton was in his black button-up-parka and scarf saying:

"Use me to restrict initiation of a Class to a single Object. Use me to guarantee that one and only one instance of a given class exists during run-time."

And that was it. That was all he said. He was a straight-shooter, a maverick. He wasn't snobby or pretentious. Definitely not an elitist. His world-view was simple, concise. Not like any other pattern I had met before.

OK. Just to be clear. I'm not that type of programmer. I mean, I took it slow at first. First we just went Logging together and then we took a weekend trip to the serial port. But before I knew it, we were joined at the hip. We were going everywhere together.

"Oh Singleton," I exclaimed one day after instantiating him from my constructor (not passed, mind you) of a helper class of methods, "You're too good to be true."

Well, I think that kind of freaked Singleton out.

I knew something was up the day I tried to extend him and he barked at me and headed for the door. I found out he started seeing other people (he did have global access to all my classes now that I think about it — I knew I gave him too much space when I allowed him to control his own creation and life-cycle.)

I hired a Unit-Test to track him down, but that guy couldn't do anything. When I finally did get a hold of him, he told me everything — all the gritty details. His state, after all that time, had of course been retained. I yelled and screamed and told him I didn't want to hear any more. But he was relentless. Unceasing.

It was at that moment that I ended my relationship with the Singleton.

I told him, "Singleton, I love you. But you're bringing me down."

Single(ton), again.

Who among us hasn't smuggled into the break-room to nibble on a Singleton newton? I, like you, drank the Singleton kool-aid. At first Singletons were used appropriately. Then, they were used inappropriately. Then they were used really inappropriately. And somewhere between the appropriate and the inappropriate, you, like me, probably realized that something was amiss. Something was aloof, a little bit off.

Then I, like you, read "Singletons Considered Stupid" by Steve Yeggee:

Why is the Singleton so attractive? I'll be the first to admit: I liked it too. No, scratch that - I loved the Singleton. It felt like an old friend from the moment I laid eyes on it. It was simple and beautiful.

I'll tell you why: it's because the Singleton pattern is a throwback to non-OO programming. It's a lifeline for people who didn't understand a single word that the Gang of Four were trying to say. It's almost exactly the way I programmed back when I didn't know jack squat about OOP. The only significant difference is that instead of having a file with a bunch of global functions in it, I have a file with a CLASS that has a bunch of global functions. No need to worry my little head about how many of them to have, since you only need one! It's OOP made easy.

And my heart was broken.

Then I read article after article about why the Singleton was a piss poor Design Pattern.

I learned that Singletons were actually referred to as something called a "code smell." I didn't know if the smell was good or bad, but we figured it was bad.

I learned that Singletons violated something called the 'Single Responsibility Principle' which states that every class you create should do one thing and one thing only because a Singleton has two distinct responsibilities: policing the instances of itself and providing configuration information.

I learned that Singletons were bad for memory management. If no one uses it for awhile, its just going to sit and twiddle its thumbs.

I learned that the state of the Singleton never goes away. Persistent state is the enemy of unit testing. One of the things that makes unit testing effective is that each test has to be independent of all the others.

I learned that Singleton's are kind of impossible to sub-class because they are static methods and static methods are about "as flexible as granite."

I learned that Singletons are (mostly) used as glorified globals and if you use them in your project, your project becomes almost impossible to unit-test because your "objects can secretly get hold of things which are not declared in their APIs, and, as a result, Singletons make your APIs into pathological liars." Basically, when objects use Singletons they hide their dependencies.

I learned that maybe, just maybe you'll realize somewhere down the line that you actually need TWO instances of the Singleton. Then what, buddy?

So I did what any completely sane Programmer would do. I ripped RIPPED the Singleton Pattern out of GOF and burned the pages while doing a triple hail mary and beat on, boat against the current, swearing never NEVER to use another Singleton for as long as I shall live.

Then, three weeks later, after I sobered up, I realized that all the stuff I learned about why Singletons were the devil incarnate was actually a form of "abstinence only" Design Pattern Education. I knew that I could avoid all the aforementioned problems by simply abstaining completely from using Singletons, but what I didn't know was what happened on the day when I wanted to use a single instance of a class and thought that the Singleton might be the best tool for the job?

Fine. Go ahead, use it.

First, before I answers the question posed above, let me address you. I know you. You're stubborn. You're going to use that Singleton until someone rips it from your cold, dead claws. If this is you, then just read on a little while longer then you can get back to uploading your favorite programming cartoon to stackoverflow.

If you do use Singletons, try to use dependency injection instead of calling getInstance() from the constructor.

Use this:

public MyConstructor(Singleton singleton) {
    this.singleton = singleton;
}

rather than this:

public MyConstructor() {
    this.singleton = Singleton.getInstance();
}

At the very least, using dependency injection allows you to do some unit testing of the class by adhering to good encapsulation principles. Using dependency injection might also stop Misko Hevrey from calling your API a pathological liar. But probably not.

Check yo-self.

For all the rest of you still reading, before using a Singleton ask yourself, "is a Singleton really the best tool for the job?"

On my quest for the truth I discovered that there are actually very few "acceptable" reasons to use a Singleton.

One reason that tends to come up over and over again on the internets is that of a "logging" class. In this case, a Singleton can be used instead of a single instance of a class because a logging class usually needs to be used over and over again ad nauseam by every class in a project. If every class uses this logging class, dependency injection becomes cumbersome.

Logging is a specific example an "acceptable" Singleton because it doesn't affect the execution of your code. Disable logging, code execution remains the same. Enable it, same same. Misko puts it in the following way in Root Cause of Singletons, "The information here flows one way: From your application into the logger. Even though loggers are global state, since no information flows from loggers into your application, loggers are acceptable."

I'm sure there are other valid reasons as well. Alex Miller, in "Patterns I Hate", talks of service locators and client side UI's also being possibly "acceptable" choices.

Single Instance Of A Class

In most cases, though, you probably got it wrong when you went to the ole' Singleton toolbox. What you probably wanted was a simple single instance of a class instead of a Singleton. There is absolutely nothing wrong with only wanting a single instance of a class. There are, however, way better ways of managing these instances then a "glorified global".

How do you achieve a Single Configuration Object without using a Singleton? Neal Ford in "The Productive Programmer" suggests "using a plain object plus a factory and delegating the individual responsibilities to each. The factory is responsible for the instance policing and the plain object deals only with configuration information and behavior." By using this technique, your code no longer smells as it now adheres to the Single Responsibility Principle.

Misko Hevrey (who does testing for google) goes into much greater detail about this technique in his two fantastic blog posts entitled "How to Think About the 'new' Operator with Respect to Unit Testing" and "Where Have All the Singletons Gone?"

The idea is to have either classes with logic or classes with the new operator (factories). When you need a single instance of a logic class, you call on the factory to build that class. Using this technique, all the dependencies are automatically injected into this single instance in proper order and returned to you. All objects of a similar lifetime are grouped into this single factory.

Misko uses the example of building a "House."

class House {
  private final Kitchen kitchen;
  private final Bedroom bedroom;
  private boolean isLocked;
 
   public House(Kitchen kitchen, Bedroom bedroom) {
    this.kitchen = kitchen;
    this.bedroom = bedroom;
  }
 
  private boolean isLocked() {
    return isLocked;
  }
 
  private boolean lock() {
    kitchen.lock();
    isLocked = true;
  }
}

Notice that in the House class, there are no instances of "new." Remember, don't mix new and logic, baby. Like J-Lo and Puffy. All the dependencies needed to build a "House" are injected into the constructor. All the "new" stuff is in the HouseFactory (seen below).

class HouseFactory {
  House build() {
 
     Sink sink = new Sink;
     Dishwasher dishwasher = new Dishwasher;
     Refrigerator refrigerator = new Refrigerator;
     Kitchen kitchen = new Kitchen(sink, dishwasher, refrigerator);
 
	Bed bed = new Bed;
     Dresser dresser = new Dresser;
     Bedroom bedroom = new Bedroom(bed, dresser);
 
	House house = new House(kitchen, bedroom);
 
    return house;
 
  }
}
 
class Main {
  public static void(String...args) {
    House house = new HouseFactory().build();
    house.lock();
  }
}

In the "house" factory, when build() is called, kitchen is created and composed of sink, dishwasher, and refrigerator objects. Bedroom is created and composed of created bed and dresser objects. House is created, composed of kitchen and bedroom objects, then returned to the user.

Using this technique, you can see how easy it will be to achieve a single configuration object without the use of a Singleton. A single instance of HouseBuilder is instantiated in the main and with that comes single instances of house, kitchen, bedroom, sink, dishwasher, refrigerator, bed, and dresser.

Using this technique solves the issue of global state because "there is no global state at all. Every object only has references to what it needs directly! No passing around of objects which are not directly needed by the code. Dependencies are obvious since each object only asks for what it needs."

Using this technique solves the issue of memory management. All classes will be created and used when needed. No more Singletons sitting around and taking up memory while doing nothing at all.

Using this technique you can extend any of the classes you desire. Static methods are nowhere. No-sir.

Using this technique you can Unit-Test without fear of a wolf attack.

Plus, Misko adds:

If an object needs a reference to a new dependency it simply declares it. This change only affects the corresponding factory, and as a result, it is very isolated.

All of the new operators end up in the factories; application logic is devoid of new operators.

You group all of the objects with the same lifetime into a single factory (If the factory gets too big you can break it up into more classes, but you can still think of it as a single factory)

Look Lisa, I'm learnding

I loved Singletons.
Then I loved Singletons a bit too much.

Then I read Steve Yegge.
He broke my heart.

I sought answers.

If you are going to use Singletons I urge you to use Dependency Injection.
But really you should know that their are very few reasons to actually use a Singleton.
I think what you probably want is: a single instance of a class!
If this is true: try using an object plus a factory.
and Don't mix the "new" with the "logic" baby.

The following is a brief overview of Lecture 6 of the ‘Programming Paradigms,” a programming class taught at Standford University. Screenshots and Code are included from the lecture. The ‘Programming Paradigms’ lectures can be found in iTunes. The link is on the Open Standford Website. The following lecture covers Implementing an Int Specific and Generic Stack in C/C++.

Int Specific Stack

stack.h
 
typedef struct{
	int * elems;
	int loglength;
	int alloclength;
} stack;
 
void StackNew(stack * s)
void StackDispose(stack * s)
void StackPush(stack * s, int value)
int  StackPop(stack * s)

The last lecture was left off with header file for a int specific stack being defined which includes a strcut called 'stack' and four functions. This lecture begins with defining StackNew and StackDispose for an int specific stack.

void StackNew(stack * s)
{
	s->loglength = 0;
	s->alloclength = 4
	s->elems = malloc(4 * sizeof(int))
	assert(s->elems != NULL);
}

When a new stack is allocated, the length is set originally to zero (because the stack is empty). Space is made for 4 elements, then malloc is used to allocate memory for those four elements. Malloc goes to the heap and finds 16 bytes of space, puts a "little halo" around the space, and then returns the base address of the memory. Assert confirms that elem is not equal to NULL just incase malloc fails for some reason. Asserts should be used to you clearly know where the program failed.

void StackDispose(stack * s)
{
	free(s);
}

StackDispose is trivial. The opposite of malloc, free is used. This gives the memory back to the heap.

void StackPush(stack * s, int value)
{
	if(s->loglength == s->alloclength){
		s->alloclength *= 2;
		s->elems = realloc(s->elems, s->alloclength * sizeof(int));
		assert(s->elems != NULL);
	}
 
	s->elemns[s->loglength] = value;
	s->loglength++;
}

In the function StackPush, you first want to check if you are out of memory to actually push value onto the Stack. If the current length of the stack is already equal to the allocated length, more memory will have to be allocated for the stack, else bad things will happen.

Actually, we want to go ahead and re-allocate the array. The previously allocated amount of memory is doubled. Then realloc is called. Realloc only exists in C, it doesn't exist in C++. Jerry says that he'll explain in a few weeks why realloc doesn't exist in C++. Realloc first sees if the memory can be allocated in place, meaning that realloc checks to see if the memory that comes after the previously allocated space in the heap is in use. If it isn't, it uses that memory. If it can't resize it in place, it copies all the elements over to a different block of memory, frees the old memory, and returns the address of the new memory.

If realloc is called with the first parameter being equal to NULL, it functions the same as a malloc command. This is useful if you don't want to call malloc once, then realloc every single time after that.

The doubling strategy is really popular because it only comes up once every 2^n times. 512 bytes of memory not big enough? Ok, let's allocate 1024. And so on.

int StackPop(stack *s)
{
	assert(s->loglength> 0);
	s->loglength--;
	return s->elems[s->loglength];
}

First, make sure that their is at least one object on the stack. Subtract one for loglength (the length of the stack), then return the new address of the stack which simulates the discarding of the last element on the stack.

Stack Using Generics

Next, the exact same stack functions will be implemented generically, not just for stack integers.

stack.h
typdef struct {
    void * elems;
    int elemSize;
    int loglength;
    int alloclength;
    ?? - Suspense Element
} stack;
 
void StackNew(stack * s, int elemSize);
void StackDispose(stack * s);
void StackPush(stack * s, void * elemAddr);
void StackPop(stack * s, void * elemAddr);

The above is the setup for the stack functions that will be implemented generically. Note that not all the information has yet been given as suspense element will be added later to the stack struct. 70% of the code for the generic stack functions is the same as the int specific stack functions.

void StackNew(stack * s, int elemSize)
{
	assert(s->elemSize > 0);
	s->length = 0;
	s->alloclength = 4;
	s->elemSize = elemSize;
	s->elems = malloc(4 * elemSize);
	assert(s->elems != NULL);
}

The second parameter (elemSize) tells the length of a single element, so malloc is used to pre-allocate 4 elements on the stack of size elemSize. Assert is used to make your life easier. It checks to make sure actual memory was allocated and to make sure elemSize was not accidentally set to zero.

void StackDispose(stack * s)
{
	free(s->elems);
 
}

StackDispose is again trivial.

void StackPush(stack *s, void * elemAddr)
{
	if(s->loglength == s->alloclength)
		StackGrow(s);
 
	void * target = (char *) s->elems + s->loglength * s->elemSize;
	memcpy(target, elemAddr, s->elemSize);
	s->loglength++;
 
}

In StackPush, if the stack needs more memory allocated, StackGrow() is called to allocate that memory. Target points to the block of memory already pre-allocated in the stack where the element will be copied.. Memcpy is used to do the actual copying of the element to that address. Remember to cast s->elems as a char * to trick the compiler because it cannot cast as a void *.

The word static has like 80 or 85 meanings in C++. Here is one more. When you see the word static decorating the prototype of a c or c++ function such as:

stack void StackGrow(stack *s)

This means that it is a private function that should not be advertised outside this file. In companies like Microsoft which deal with programs with tens of thousands of files, many times function names will conflict with each other if not made static.

static void StackGrow(stack *s)
{
	s->alloclength *=2;
	s->elems = realloc(s->elems, s->alloclength * s->elemSize);
}

StackGrow re-allocates double the amount of memory just like the int specific version.

void StackPop(stack *s, void * elemAddr)
{
	void * source = (char*) s->elems + (s->loglength - 1) * s->elemSize;
	memcpy(elemAddr, source, s->elemSize)
	s->loglength--;
}

In StackPop(), source points to the last chunk of data in memory on the stack. Memcpy copies that memory to the memory address, then the length of the stack is decremented thus "popping" off the memory from the stack.

When dealing with generics, it is very easy to get the program to compile because the compiler looks at all the void * declarations and stamps them as "good." However, when running a program implementing generics, it is very likely to crash.

"When all you have is a hammer, everything looks like a nail."

I was recently working on an application that sent and received messages over Ethernet and Serial. I was then tasked to add the monitoring of DIO discretes. I throught,

"No reason to interrupt the main thread which is involved in message processing, I'll just create another thread that monitors DIO."

This decision, however, proved to be poor. Sometimes the main thread would be interrupted between a Send and a Receive Serial message. This interruption would disrupt the timing and alas, messages would be lost (forever).

So I found another way to monitor the DIO without using another thread, and Ethernet and Serial communication were restored to their correct functionality.

The whole fiasco, however, got me thinking. Are their any general guidelines about when not to use multiple-threads?

I asked my friends at stack-overflow and scoured the internet for information. The results may surprise you.

Think twice, no three times before even thinking about using threads

I heard this advice time and time again on blog after blog. Before you thread, think.

I think the old programming wives tale puts it best: A Programmer had a problem. He thought, 'I know, I'll use threads' Now the programmer has two problems.

Many think that if multiple threads are used, old-man-trouble gonna come round the corner and knock the sweet bejesus outta you. There is good reason to fear old-man-trouble. Using multiple threads adds a whole new layer of complexity to your code. If something, somewhere goes wrong with you code down the line, that new layer of complexity makes your code just that much harder to debug and maintain. Not to mention that multiple-threaded code is a good bit harder to scale.

In a recent project, I used two threads to implement a command processing routine. Thread One sent Thread Two a command. Thread Two executed that command. Thread Two said to Thread one, "Give me another command." Thread one sent Thread two another command. And so on and so forth. It took me a long time and many lines of code to get the two threads playing nicely.

Several weeks later, the code broke. I stared at that code for — I kid you not — two hours trying to figure out exactly what I had originally done. Code should just not be that complex. Remember, keep it simple. I could have easily performed the same functionality with a single thread.

As Thomee on StackOverflow put it, "Don't use threads, unless there's a very compelling reason to use threads."

So, when it comes to threads, ignore Bob Dylan's sweet sweet crooning, "Don't think twice it's alright…."

When it comes to everything else through, Dylan should prevail.

Absolutely Never

Fifel, in 'An American Tale' made his sentiments on the word 'never' as his little mice lungs wailed, "Never, say never, say never my friend." While I try to never adhere to absolutes, there are several cases where multiple-threads should absolutely never be used.

When bound by a single resource

Multiple threads should never be used when each thread is just going to be battling it out for the same single resource. In his blog entry, "When to use Threads", skeet expresses the pointlessness of using multiple-threads when sharing a single resource.

"If your application is bound by a single resource (i.e. the disk, or the CPU) and all the tasks you would use multiple threads for will all by trying to use that same resource, you'll just be adding contention."

When I was in elementary school, I certainly knew about the contention stemming from vying for the same resource. Each day after P.E., we would all come pouring back into the building from being outside in the 99 degree heat for the last 30 minutes. We were hot, sweaty, and thirsty, but our elementary school only had a single drinking fountain. There was always a race to the fountain.

When we arrived, we would push, shove, grope, kick — anything to get a drink of that cool refreshing beverage. But no matter how hard we battled each other, ultimately only one person could drink at a time. We were bound by a single resource. And battling each other for water only slowed the process down. A teacher would arrive 30 seconds later and make us form a single-file line. Standing in line, we would tap our feet and clear our throats when we felt someone was taking just a little bit too long, drinking a little bit too much. But in a short period of time everyone got their fill.

A few years ago, I was in the process of moving a large amount of music from one hard drive to another. I selected all the folders at once (all 2000 or so of them) and dragged them over to the second drive. The Windows File Copy routine booted up and showed '45 minutes' as the estimated amount of time to complete the job.

Well, I was in a rush. And thinking that I was clever, I decided to cancel the operation and instead tried to parallel-ize the copying job. As fast as I could click, I copied and pasted 10 folders at a time into the new drive. When I got about 500 folders in, all the processes ground . to . a . halt. The hard drive head was seeking all over the place and never making any progress on the copy operation.

At this point, I realized my stupidity. The operation was bound by a single resource — the disk! The hard-drive was my metaphorical elementary school water fountain. And each copy process was pushing, shoving, and grouping for that single resource.

Understand how the resources you are using are bounded, and if those resources only have a single point of entry, there is absolutely no point in trying to use multiple-threads to complete the task at hand.

Sequential Code

Multiple Threads should also never be used when each step being executed relies heavily on the results from previously executed steps. For example, the steps to drive a car are as follows:

1. Turn On The Ignition
2. Put the car into 'Drive
3. Hit the Gas

To drive a car, you must complete the above steps in order.
Each step must be completed before the next step can be executed.
If you try to complete any of these steps out of order, the results will not be what you desired.
You simply cannot put the car into 'drive' without first turning on the ignition.

I guess you could technically reverse steps two and three by hitting the gas, then put the car into 'Drive', but only if you were filming a remake of Smokey and the Bandit or something. Regardless, you would never try to complete all three steps at once. That would be foolish.

starting with a
b = functionX(a)
c = functionY(b)
d = functionZ(c)

Take a look at the code above. I think we can agree that most code is sequential in nature. You start with A. You plug A into functionX, it returns B. You plug B into functionY, it returns C. You plug C into function Z, it returns D. Each step leads into the next. FunctionY cannot be executed before B is computed. FunctionZ cannot be executed before C is computed. Trying to implement the above code with multiple-threads is like trying drive a car without turning on the ignition. It is pointless.

If your code must be completed sequentially, using multiple-threads is worthless.

When to (Maybe) Use Threads

GUI Programming - Keeping a Process Responsive

One place multi-threading does actually come in handy is when programming a Graphical User Interface (GUI). Multiple-Theads are sometimes used in GUIs to keep them responsive while the computer is chewing on user input.

For example, say you have a program that did nothing but compute the digits of pi. Next, you add a GUI to the program that had a single Big Button that toggled between "Compute Digits of Pi" and "Stop Computing Digits of Pi." After clicking on "Computer Digits of Pi" and starting the program, if multiple threads are not employed to keep the GUI active while computation is taking place by the processor, "Stop Computing Digits of Pi" would never be able to be clicked. The program could never be stopped. The GUI would be frozen, indefinitely churning out digits of pi until the universe came to an end.

A Threading Rule Of Thumb: When programming a GUI, if the user input takes longer then one to two seconds to compute, consider using a second thread.

Keeping the GUI responsive is very important and contributes to usability. Skeet delves more into this sentiment on 'When To Use Threads' when he says that "the UI can easily become very unresponsive, which gives a horrible user experience. (GUI) threading isn't used to get the job done quickly - it's used to get the job done while keeping the user satisfied with responsiveness. You might be surprised just how quickly a user can notice an app becoming unresponsive. Even if the user can't actually do anything but close the program or move the window around while they wait it gives a much more professional feel to a program if you don't end up with a big white box when you pass another window over it."

But, again let me emphasize that you should always think twice about using multiple-threads even in GUI applications. Earlier this year, I developed a QT GUI application that interacted over Ethernet with big-hunking piece of hardware. I would send a command to this hardware, the hardware would execute that command, then, after executing the command, the hardware would send back a response saying "Everythings OK!" or "FAIL!" The hardware could take up to five minutes to respond to certain commands.

If I didn't want my GUI to freeze up while waiting for the hardware's response, one option would have been to spin the command/response process onto a separate thread. But another less complex option would have been to use non-blocking calls to the ethernet API functions and a timer to periodically monitor the status of the ethernet ports to see if a message had been received or not. Easy Right?

Whether or not you understand what non-blocking calls are, my point is this: There is almost always more then one way to skin a cat. Think about that cat. Wait, is the cat the thread? Never-mind.

Data Analysis (Algorithm Processing) on Multi-Core Machines When Performance Matters

If you are working with multiple-processors, with data computation that can be parallelized, and are in the business of getting things done quickly, then guess what? Multiple-threads are something you should consider.

With more than one processor, multi-threading is truly multi-threading — meaning that two tasks can be (for-real) executed at the same time. One task on each core (processor). On a single core machine, multi-threading is a scam (a farce!). The scheduler plays a game of red-light, green-light with the threads when more than one thread is used. It decides which which task executes when. If you set break points and watch the scheduler switch back and forth between threads, it seems totally random. You can give the scheduler general guidelines as to which thread is more important, but exactly when each thread executes is mostly out of your control. Multiple-Cores give you much more control over schedule execution.

Data computation that can be parallelized is the opposite of the sequential code processing that was talked about above. Parallel tasks can be divvied up and divided between multiple-cores. The ordering of the execution does not matter. If thread 4 finishes execution before thread 3, this is OK. Think parallel complex data processing algorithms. Think complex math stuff.

When coding-up these parallel data processing algorithms, something that you have try to be careful about is creating too many threads. Say you get excited about your multiple-cores and parallel processes and start spinning threads off all over the place unbounded. Then, instead of resource contention, you suffer from thread contention and your CPU's spend more time switching between threads then it does processing them. Put an upper limit on the number of threads you create. Google 'Thread Pools.'

But remember just because you have multi-core machine and are working with data computation that can be parallelized doesn't mean you should use multiple-threads. Try it single threaded first. Not fast enough? Try two threads? Still not fast enough? Try three. Take it slow. Only add more complexity when absolutely necessary.

So, what have we learned?

1. Try not to use threads.
2. Think.
3. Keep it simple.
4. Sharing a single resource? Don't use threads.
5. Sequential Code? Don't use threads.
6. GUI programming? Try not to use threads, but keep the GUI responsive.
7. Multiple-Cores? Parallel Data Computation? Don't use threads.
8. Multiple-Cores? Parallel Data Computation? The need for speed? Use Threads.

The last few days I've been working with CyberResearch's HDIO ISO32LU Low Profile PCI Digital I/O Board. My mission? Easy. Read and Write a few bits of DIO. How hard can it be right? I thought that because I was familiar with CyberResearch's PCIDAQ1210, getting up and going with the HDIO would be easy. I thought 30 minutes, max. It's DIO. How hard can it be? Hard enough it seems.

Bad Programming Examples

The HDIO software provides you with a multitudinous number of programming examples.  Great, right?  Surely there’s a simple console programming example for reading and/or writing a single BIT to the card with the DIO card because I’m quite certain that 90% of people/companies using the card are ONLY going using it for simple reads and writes.  OK, let’s see.  Well, first we have to translate the cryptic programming example folder naming scheme.

DI_INT
DI_PATTN
DI_SOFT
DI_SOFT-DWORD

Are they only given DOS machines to work with over at CyberResearch?  Come on guys, XP gives you 255 characters in which to name filenames and folders.  Let’s be a little more specific shall we?  With new technologies, the learning curves are already high enough.  Give us a break.

I finally figured out that DI is short for “DIO”.  INT is short for “interrupt”.  Pattn short for pattern.  Soft is short for…?  Software?  It’s a mystery.  Opening a few of these examples yields bloated ugly laberinthian MFC GUI code with a tiny bit of actual API calls to the DIO demonstating advanced card functionality that most people probably will never use.  Listen guys, I don’t care to look at your ugly GUI code ESPECIALLY if it hides the actual real functionaity of the code.   Give Me a Text Based Example.  You aren’t teaching us how to use MFC.  You are teaching us how to use the DIO card.

To add insult to injury, after running these examples, I had no idea what a single one of them were actually trying to do.

So I turned to “Driver.chm” document provided by the installed software (c:/ProgramFiles/CyberResearch/ADSAPI/Manual) which contains a list of all API commands.   In the document, I found that the command for reading a single BIT was “DRV_DioReadBit.”  I did a serach for this phrase in all the examples and yielded zero results.  There were no programming examples which showed me how to read a simple BIT from DIO.

(ASIDE:  Microsoft Help files (.chm) are gastly.  I don’t care if they are industry standard.  They are hard to navigate, difficult to search, and impossible to print out the entire thing.  Give me an Online API or a PDF please).

The irony is that CyberResearch actually provides a test program where you can simply toggle or read a single bit and view the results.  But for some reason, they don’t feel like it’s important enough to give you the code for that application.  Just another example of a  company not being in touch with their customer.

Not the same API Commands (not even close)

Another thing that perturbs me about the H-Series DIO API calls, is that the call to Read a Single BIT is nothing like PCIDAQ 1210’s API calls. Well, actually, they are exactly alike.  But you wouldn’t know it just by looking at the API.

The API call to Read a Bit on the HDIO ISO32LU:

FTYPE DRV_DioReadBit(LONG DriverHandle, LPT_DioReadBit lpDioReadBit);

The API call to Read a Bit on the PCIDAQ 1210:

I16 DI_ReadLine(U16 CardNumber, U16 Port, U16 Line, U16 * state);

To perform the exact same functionality, these two cards have two completely different function names.  These two functions also take different data types and have a few different variable names for the exact same information.  Let me show you how the two translate:

‘DriverHandle’ on the IDO32LU = ‘CardNumber’ on the DAQ

LPT_DioReadBit lpDioReadBit is a structure with the following elements:  Port, Bit and State.

Port = Port
Line = Bit (confusing)
State = State

How easy would it be to use a universal naming structure between API’s for different cards CyberResearch?

Reading and Writing with the HDIO IDO32LU

Open a Device

OK, enough of me ranting and raving about CyberResarch rediculousness. I know why you are here. You want to know how to simply Read and Write a single Bit. The first thing you need to do if open the Device you intend to use. A call to DRV_DeviceOpen returns a DriverHandle which will be used in the API calls to Read and Write a single BIT.

LRESULT        ErrCde;
char          szErrMsg[80];
static ULONG  dwDeviceNum;
static LONG   DriverHandle = (LONG)NULL; 
 
ErrCde = DRV_DeviceOpen(dwDeviceNum, (LONG far *)&DriverHandle);
if (ErrCde != SUCCESS) {
    DRV_GetErrorMessage(ErrCde,(LPSTR)szErrMsg);
    cout << ErrCde << endl; return 0; }

Writing a Bit

To write a single BIT to the DIO card, declare a new instance of the structure PT_DioWriteBi and define the port, bit, and state in that structure. Then, just pass the address of the structure to the API call DRV_DioWriteBit along with the DriverHandle. If case you are wondering about which port to use, Port 0 refers to IDO0 through IDO7 on the IDO32LU. Port 1 refers to IDO8 through 15. You can see the pin-outs on page 25 of the manual provided to you by CyberResearch.

 PT_DioWriteBit lpDIOWriteBit;
 lpDIOWriteBit.port = 0;
 lpDIOWriteBit.bit = 0;
 lpDIOWriteBit.state = 1;
 
 ErrCde = DRV_DioWriteBit(DriverHandle, (LPT_DioWriteBit)&lpDIOWriteBit );
 if (ErrCde != SUCCESS) {
   DRV_GetErrorMessage(ErrCde,(LPSTR)szErrMsg);
   cout << ErrCde << endl; return 0; }

Reading a Bit

Reading is a little ticker. In order to Read a BIT, you again provide a Driver Handle, but this time provide an address to a declared PT_DioReadBit structure. The real tricky part? Remembering to allocate memory of size USHORT that will hold the state information once it has been populated by the call to DRV_DIOReadBit. Below, rbvalue is declared of type USHORT, then this memory is pointed to by the state variable in the declared 'PT_DioReadBit' structure. If you forget to allocate that memory, prepare for your program to crash. If case you are wondering about which port to use, Port 0 refers to IDI0 through IDI7 on the IDO32LU. Port 1 refers to IDI8 through IDI15.

PT_DioReadBit lpDIOReadBit;
USHORT rbValue;
lpDIOReadBit.port = 0;
lpDIOReadBit.bit = 5;
lpDIOReadBit.state = (USHORT far *)&rbValue; 
 
ErrCde = DRV_DioReadBit( DriverHandle, (LPT_DioReadBit)&lpDIOReadBit );
if (ErrCde != SUCCESS) {
   DRV_GetErrorMessage(ErrCde,(LPSTR)szErrMsg);
   cout << ErrCde << endl; return 0; } 
 
 USHORT state = *lpDIOReadBit.state;

In my opinion, having to allocate your memory for the state variable is unnecessary complexity that could have been side-stepped by CyberResearch in the programming of the API for the IDO32LU. Especially with the newest generation of programmers being so unfamilar with C, I find they could have been a wee bit more user friendly.

In Conclusion

I wrote this entry to save you a little bit of time. It took me three hours to figure out how to read and write a bit to the DIO card. Maybe I'm just dumb. Or maybe, it was a little bit harder then it should of been. I normally don't take the time to write scathing reviews of products, but I firmly believe that DIO is fundamental and should be one of the easiest tasks to complete. I should be able to call a function called WriteBit(int Port, int Bit, int State) and it should write the BIT. I should be able to call a function ReadBit(int Port, int Bit, int * state) and it should return the state. It should be this easy. These two functions would be printed on the front cover of my manual of the DIO card I'm trying to sell. If not in the manual, they should be in simple text based console programming examples entitled 'Reading a Bit From the DIO' and 'Write a single BIT to the DIO.' If not in an example, they should be in an online API or pdf. Am I asking for too much? I don't think so. Get with the program CyberResearch.

The last couple days I have been working on Serial Communications (RS-422 and RS-485) between a Windows PC and an Embedded FPGA Processor. From start to finish, synchronizing the data transfer between the two systems only took about half a day. When I first started using serial communications a few years ago, it took me a week to establish a good working link. Between then and now, I've noticed a few tips and tricks along the way which has helped get communication between two devices up-to-speed more quickly.

Not a Perpetual Motion Machine

What makes serial a bit difficult to work with is that it is (in general) not plug-and-play. The code used to communicate to one type of board, won't work straight-out-of-the-box with another type of board. Like snowflakes, no two serial-com links are alike. There is no perpetual motion machine. Each has individual timing constraints and quirks. Sometimes you can read about these timing constraints in the spec, but most times a good link is established only after a big battle of trial-and-error. This also makes it hard to do serial comm research on the Internet. Copying and pasting serial code from a website you find on google rarely works. It can help you get the gist of what is going on, but unfortunately, prepare to put in some legwork.

Know the baud-rate, parity, stop-bit, and byte-size

This is essential. Before even getting started make sure you know the baud-rate, parity, stop-bit, and byte-size information of the device you are trying to communicate to. If you have this information wrong, you are pretty much dead in the water from the get-go. Nothing will work. Check and double check this information. I don't know how many times I've ported serial code from one project to the other, ran it, then hit my head against a wall for a few hours before realizing that, duh, the last FPGA that I was communicating to was in 19200 the new FPGA is in 9600. These variables should be the first to be modified when programming serial in the windows environment.

DCB properties;
 
GetCommState(hCom, &properties);
properties.BaudRate = CBR_19200;
properties.Parity = ODDPARITY;
properties.StopBits = ONESTOPBIT;
properties.ByteSize = 8;
SetCommState(hCom, &properties);

Auto-Toggle or Manual? Know your serial card.

Oh Auto-Toggle. How we love thee. Let me count the ways. Auto-Toggle is a function that is built into certain serial cards that automatically toggles the transmit lines when bytes are sent then immediately toggles back to the recieve line to await bytes from the device to whom you were talking. The problem is that most serial cards don't have Auto-Toggle and sometimes even when they have it doesn't operate properly. Make sure you know to which camp you belong. Know your serial card. If your card has auto-toggle, verify that it works using an oscilloscope (we'll talk about that later). If it doesn't, know that you have to manually toggle the transmit and receive lines.

Enabling RTS_CONTROL toggles the transmit line and allows the user to transmit data over serial. When RTS_CONTROL has been enabled, the user cannot recieve any data over serial.

GetCommState(m_hCom, &properties);
properties.fRtsControl = RTS_CONTROL_ENABLE;
SetCommState(m_hCom, &properties);

Diabling RTS_Control toggles the recieve line and allows the user to recieve data over serial. When RTS_CONTROL has been disabled, the user cannot send any data over serial.

GetCommState(m_hCom, &properties);
properties.fRtsControl = RTS_CONTROL_DISABLE;
SetCommState(m_hCom, &properties);

If you are working with RS-485, and auto-toggle isn't an option, manually controlling the transmit/recieve lines is very necessary as RS-485 is half-duplex (which means that the transmit/receive lines are shared). If working with RS-422, which is full-duplex, transmit and receive are not being shared (both have separate lines) and toggling the transmit/receive lines should not be necessary. However, just this week I was working with a RS-422 and communication would not work unless I still toggled transmit/receive - go figure.

Give the WriteFile command time to breathe

After transmitting bytes using the WriteFile command, proper time must be given after executing WriteFile and before RTS_CONTROL is disabled. Unfortunately, the WriteFile command doesn't (properly) verify that all bytes are written to the transmit line. If RTS_CONTROL is disabled too quickly after WriteFile, bytes can actually be chopped off the end of your message. If you are losing bytes, simply insert something I like to call a 'for loop to nowhere' after the WriteFile command. It just wastes a little time before you disable RTS_CONTROL and makes sure all bytes are transmitted.

DCB properties;
 
GetCommState(m_hCom, &properties);
properties.fRtsControl = RTS_CONTROL_ENABLE;
SetCommState(m_hCom, &properties);
 
BOOL ok = ::WriteFile(m_hCom,(void *)buffer,bytes_to_send,&bytesSent,NULL);
 
for(int i = 0; i < 200000; i++); //waste a little time
 
GetCommState(m_hCom, &properties);
properties.fRtsControl = RTS_CONTROL_DISABLE;
SetCommState(m_hCom, &properties);

Use an Oscilloscope! ! !

Before I go any further, I'd like to urge you, no, gently prod you to use what I consider the number one best way to get serial communications up and running: the Oscilloscope. Using the Oscilloscope you can really nail down the timing of your sent and received messages over serial communications. You can measure the time it takes to send and receive one byte. You can measure the time between when the last byte is sent by the WriteFile command and when a response is seen on the receive line. You can actually SEE (I spy with my little eye) that you are disabling the RTS_CONTROL line too early and thus cutting off bytes. The Oscilloscope will save you time and thus head-banging hair-wrencing frustration. I guarantee it. I recommend setting two trigger points if using RS-422. One on the receive and one on the transmit line.

Free Serial Port Monitor

Another tool that I use constantly while working on Serial Programming is the Free Serial Port Monitor. This program allows you to monitor a specific COM port and shows you exactly what you have written and what you have read on that COM port. The tool is perfect when you are just getting started if you just want to know if you are writing anything at all. Sometimes, if you aren't using an Oscilloscope, it is difficult to tell if any bytes are being written correctly. Also, this tool shows you exactly how many bytes are being read and what bytes are being read with the ReadFile command. This helps you debug your serial read calls because you can see if you are chopping your message in half with the ReadFile command and adjust accordingly.

Reading when you know what to expect

If you are working on a command and response based serial system, one in which you issue and command and expect back a response of a certain length — reading on serial is a cinch. You just have to know three little bits (or should I say bytes?) of information. The first is the maximum time interval between the characters you are receiving in milliseconds. This can be found in your spec (if you are given a spec) or can be found with an Oscilloscope. The second is the number of bytes you expect back. The third is the time it takes to send one character (this can be found with a simple math equation). I'll tell you how to use this information below after I drop a big lump of code on you.

DWORD Serial_Controller_Class::Receive_Message(unsigned char * Msg_Ptr,
int ExpectedNumberOfBytes, int MaxTimeBetweenChar, int MaxTimeToSendSingleChar) { 
 
    DWORD bytesRead = 0;
 
   COMMTIMEOUTS comTimeOut;
   comTimeOut.ReadIntervalTimeout = MaxTimeBetweenChar;
   comTimeOut.ReadTotalTimeoutMultiplier = ExpectedNumberOfBytes;
   comTimeOut.ReadTotalTimeoutConstant = MaxTimeToSendSingleChar;
   SetCommTimeouts(m_hCom,&comTimeOut); 
 
   BOOL ok = ::ReadFile(m_hCom,Msg_Ptr, ExpectedNumberOfBytes,&bytesRead,NULL); 
 
  FlushFileBuffers(m_hCom);
  return bytesRead;
}

The Receive Message method above has four elements passed to it. The first, MsgPtr, is used to hold the message received. ExpectedNumberOfBytes contains the number of bytes you expect to be returned based on the message you sent out on serial. The variables MaxTimeBetweenChar and MaxTimeToSendSingleChar are, in my opinion, pretty self explanatory. This passed data then can be used to set things called "Comm Timeouts." Comm Timeouts are used to control the amount of time that ReadFile will sit and wait for a message to be recieved. This is called "blocking" in the biz which means that all other processes are esentially "blocked" until ReadFile has finished executing. This is why setting CommTimeouts correctly are extreamly important. We don't want to "block" for longer then necessary. Each Comm Timeout is explained in detail below.

DWORD ReadIntervalTimeout - sets max period of time (in milliseconds) allowed between two sequential characters being read from the line of commutation. During the 'read' operation the time period countdown takes its start when the first character is received. When the interval between two sequential characters exceeds the given value the 'read' operation finishes and all the data accumulated in the buffer are transmitted to the programme. Zero value of this member indicates that this timeout isn't used.

DWORD ReadTotalTimeoutMultiplier- sets the multiplier (in milliseconds) used to calculate general timeout of the 'read' operation. In every case this value is multiplied by the quantity of the characters requested for reading.

DWORD ReadTotalTimeoutConstant - sets a constant (in milliseconds) used to calculate the general timeout of the operation. In case of every 'read' operation this value is added to the result of multiplying ReadTotalTimeoutMultiplier by the quantity of the characters requested for the reading. ReadTotalTimeoutMultiplier and ReadTotalTimeoutConstant mean that general timeout for 'read' operation isn't used.

Here's how to calculate MaxTimeToSendSingleCharacter.  If we transfer one character at 19200 baud, 8 bits per byte, plus parity complement and one stop bit, then there will be 11 bits total per character.

MaxTimeToSendSingleCharacter =  11x(1/19200) = .057 milliseconds (which can be rounded up to 1 milliscond).

Imagine that we read 100 characters at a rate of 19200 bps. If 8 bits per character, parity complement and one stop bit are used, then there will be be 11 bits (including the start bit) per character in the physical line. So 100 characters at a rate 19200 bit/s will be received as

100×11x(1/19200)=0.0572916 sec

or approximately 57.2 milliseconds. If there is no interval between receiving multiple characters.   If the interval between the characters is about a half time of one character transmission, i.e. 0.25 milliseconds, the reception time is calculated as

100×11x(1/19200)+(99×0.00025)=0.00820416 sec

or give or take 82 milliseconds. If the reading process has amounted to longer then 82 milliseconds, we can suppose there's been an external device error and stop the 'read' operation to anymore program blockage.  Phew.

"No More Math!  No More Math!"  I hear you chant.  Fear not, we are done.

Reading when you have no idea

When you have no idea how many bytes to expect back, the best thing to do is to follow the steps above with one exception.  Hopefully you know the maximum number of bytes that can be sent at any given time.  If you know that, just use that number for ExpectedNumberOfBytes.

Thats it!

These are my tricks.  OK, maybe they are really tricks.  Maybe they are just a better explanation of the dry-and-boring RS-232 specification that you've been starting at and scratching your head over for the past week or so.  Regardless, I hope some of these tidbits helped.

Project Euler “is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.”

I've been working through some of the projects on the website to help teach myself Ruby in my space time.

Problem 4 of Project Euler states the following:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Just doing some simple calculations, the smallest number that can be generated by two 3 digits numbers multiplied together is:

100 * 100 = 10,000 which is a five digit number.  
An example of a five digit palindrome is 10101

The largest number is:

999 x 999 = 998,001 which is a six digit numbers.
An example of a six digit palindrome is 101101.

With this information in mind, the solution I came up with in Ruby is below.

class Palendromes
 
  def initialize
    @Solutions = []
  end
 
def FindPalendromes
 
  for x in 100..999
    for y in 100..999
 
      a = x * y
      a = a.to_s
      next if(a.length % 2 != 0)  
 
      b = []
      a.scan(/[0-9]/) do |z|
        b << z
      end
 
     @Solutions << a if(isPalendome?(b)) 
 
    end
  end
 
  @Solutions.sort
 
end
 
def isPalendome?(array)
 
  reversearray = array.reverse
  for x in 0..array.length
    return false if array[x] != reversearray[x]
  end
 
  return true
 
end
 
end
 
a = Palendromes.new
solutions = a.FindPalendromes
puts solutions

Starting at the bottom, a is set equal to a new instance of class Palindromes which is initialized with a call to the new method which in turn calls the initialize method which declares a new array called 'Solutions' where all the possible palindromes will be stored.  To find the palindromes, the 'FindPalindromes' method is deployed.  

FindPalindromes creates two loops from 100 to 999 so that every product of two three digit combination of numbers will be checked.  Entering the double for loop, x and y are multiplied together and stored in 'a'.  'a' is converted to a string so it can be more easily manipulated and it's length is checked.  If a is a five digit number and not a six digit number, a is discarded because it is obviously not the 'largest palindrome.'  

Next, using Regular Expressions,  each individual number is extracted from a (which is one long string) and put in individual elements in an newly created array b.  

For example the following conversion is made if a is equal to the string  '123456.'

b = {1, 2, 3, 4, 5, 6} 

This is done so that array functions can be used to check if the number is actually a palindrome.  

Next, b is sent to the method isPalindrome() which checks if the numbers contained in b are of a palindromic nature.  The isPalindrome() method is simple.  The method reverses b and stores the results in 'reversearray,' then, it loops through the length of the array comparing each element.  If an element doesn't match up, it returns false and nothing happens.  If however, every element matches, the isPalindrome method returns true and a is pushed into the Solutions array.

When the double for loop has exhausted every possible triple digit product combination, the solution array is sorted and returned to be printed to the screen.  

The answer is: 906609

My solution, while yielding the correct answer, is not the most elegant solution I discovered (not to my surprise as I am still learning the intricacies of the Ruby Programming language).  On the Project Euler forum, Olathe posted the following code:

max = 0
100.upto(999) { |a|
  a.upto(999) { |b|
    prod = a * b
    max = [max, prod].max if prod.to_s == prod.to_s.reverse
  }
}
puts "Maximum palindrome is #{ max }."

This code is sick (in a good way). He creates two for loops, finds the product of two three digit numbers, and converts the answer to a string — which is what I did in my code, but this is where the similarities end. Instead of extracting single digits into an array, he simply compares the product string to a reversed product string. If they match (if the number is a palindrome), he compares the number to the previous maximum number stored in the 'max' variable. If bigger then the previous max, he stores the number in match. If less, he discards it. Yes. Very Nice.

Linear Search with Generics

void * lserach(void * key, void * base, int n, int elemsize, int(*cmpfn)(void*, void*) )
{
 
  for(int i = 0; i < n; i++) {
      void * elemAddr = (char *) base + i * elemSize;
      if( cmpfn(key, elemAddr) == 0 )
          return elemAddr;
  }
 
  return NULL;
 
}

The linear serach takes five parameters.  Key is a pointer to a searched for item, base is a pointer to the base of the array, n is the number of elements in the array, elemsize is the size of an element in the array, and cmpfn is a function pointer to a compare function.  We loop through the array one element at a time.  The cmpfn returns zero if the elements are equal, and lsearch returns a pointer to that element.  If nothing is found, NULL is returned.

Implementing lsearch with ints

int array {} = {4, 2, 3, 7, 11, 7, 6};
int size = 6;
int number = 7;
 
int * found = lserach(&number, array, 6, sizeof(int), intcmp);
     if(found == NULL) :(
     else                     :)

When calling lsearch above, the address of 'array' doesn't have to be passed because when one sends in 'array,' it implicitly passes in the address of the zero(th) element.  The 'intcmp' function that is passed into lsearch needs to be coded for the above to work.

int IntCmp(void * elem1, void * elem2) {
   int * ip1 = elem1;
   int * ip2 = elem2;
 
  return *ip1 - *ip2;
}

The compare function returns a negative value if ip1 is less than ip2, zero if the elements are equal, or a positive value if ip1 is greater than ip2.  Because it is known that the elemnts we wish to search for are of type int, we can make the compare function passed to lserach an specific type of compare ala int. 

There are definetely better ways to implement generics in other languages.  These languages have learned from the mistakes in C.  C has been in existence for 35 years which is pretty old in computer time.

Implementing lsearch with CStrings

On this example, an array of CStrings is searched.  The array is searched for the string 'EFlat'.  All the character elements are NULL terminated ('\0′).  This example is tricky because we are working with type char star star (char **) or double pointers.

char * notes[] = { "AFlat", "FSharp", "B", "GFlat", "D" };
char * favoriteNote = "EFlat"
 
char ** found = lsearch(&favoriteNote, notes, 5, sizeof(char *), StrCmp);
 
int StrCmp(void * vp1, void * vp2)
{
   char * s1 = * (char **) vp1;
   char * s2 = * (char **) vp2;
 
   return strcmp(s1, s2);
}

Vp1 and vp2 are cast to the types they really are which are double pointers.  After that, the value of vp1 and Vp2 are derefereced to s1 and s2.   Vp1 is of type void * so it can't be deferenced as a void * so it must be cast as what it is which is a char **.  A C standard library function can then be used to compare s1 and s2 which takes two char pointers.

The difference between functions and methods

The difference between functions and methods.  Funtions are independent of Objects.  Methods are functions that exist inside Objects.  Methods have invisible (this) pointers lying around, where functions actually have to have everything passed to it.

Generic Data Structures (Stacks)

We are going to implement a stack using ints first before a generic version will be attempted.

stack.h

typedef struct {
   int * elems;
   int logicallen;
   int alloclenth;
} stack;
 
void StackNew(stack * s);
void StackDispose(stack * s);
void StackPush(stack * s, int value);
void StackPop(stack * s);
 
stack s;

This allocates a block of memory for stack, but doesn't actually initialize the data.

StackNew(&s);

A call to StackNew receives the address of the previously allocated stack s.  StackNew initializes the actual elements in stack s.  

for(int i = 0; i < 5; i++)
{
    StackPush(&s, i); 
}

The above call pushes the numbers zero through 4 onto the stack.

StackDispose(&s); 

And finally, the stack is disposed of.  Other details need to be implemented as well, but those details were not provided in this lecture.  For example, initially the elems pointer only pointed to an array of size 4.  This array, however, gets filled up after the number '3′ is pushed onto the stack.  More memory then has to be allocated to fit the number 4.  

void StackNew(stack * s)
{
 
    s->logicallen = 0;
    s->;alloclen = 4;
    s->elems = malloc(4 * sizeof(int));
 
   assert(s->elems != NULL);
 
}

In C, malloc goes out to the heap, finds a block of memory that is 4 * sizeof(int) wide (or 16 bytes) and returns the address of that block of memory to elems.   The assert function, if evaluated to false, declares an assertion at that call (ends the program) and tells you at what line the program ended.  If malloc isn't able to find the memory on the heap, it will return NULL and the assert will be triggered.  If not caught, a segmentation fault is called, but you don't know where it was called.

The following is a brief overview of Lecture 4 of the ‘Programming Paradigms,” a programming class taught at Standford University.  Screenshots and Code are included from the lecture.  The ‘Programming Paradigms’ lectures can be found in iTunes.  The link is on the Open Standford Website.  The following lecture covers implementation of Swap using Generics.

Implementation of Swap using Templates

void swap( void * vp1, void * vp2){
  void temp = *vp1;
  *vp1 = *vp2;
  *vp2 = temp;
}

The above Swap function takes a generic pointer type (void * ).  This means that it points to something that it doesn't have any type information about, so Vp1 and Vp2 are pointing to addresses in memory that it knows nothing about.  Furthermore, there is a problem with the above implementation.  One cannot declare temp or a variable to be of type void.  Also, one isn't allowed to dereference a void * variable because it doesn't know how to go out and embrace an unknown number of bytes.

void swap (void * vp1, void * vp2, int size){
 
  char buffer[size];
  memcpy(buffer, vp1, size);
  memcpy(vp1, vp2, size);
  memcpy(vp1, buffer, size);
 
}