Author Archives: Dan Siemon

Memory efficient doubly linked list

Linux Journal has an article in the January 2005 issue that introduces a doubly linked list that is designed for memory efficiency.

Typically elements in doubly linked list implementations consist of a pointer to the data, a pointer to the next node and a pointer to the previous node in the list.

Picture of a typical linked list

The more memory efficient implementation described in the article stores a single offset instead of the next and previous pointers.

Diagram of the memory efficient linked list

The pointer difference is calculated by taking the exclusive or (XOR) of the memory location of the previous and the next nodes. Like most linked list implementations a NULL pointer indicates a non-existent node. This is used at the beginning and end of the list. For the diagram above, the pointer differences would be calculated as follows:

A[Pointer difference] = NULL XOR B
B[Pointer difference] = A XOR C
C[Pointer difference] = B XOR NULL

One nice property of XOR is that it doesn’t matter what order the operation is applied. For example:
A XOR B = C
C XOR B = A
A XOR C = B

The memory efficient linked list uses this property of XOR for traversals. The trick is that any traversal operation requires both the address of current node and the address of either the preceding or following node.

Using the example figure above, calculating the address of the B node from A looks like:
B = NULL XOR A[Pointer difference]

What is really interesting is that traversing the list operates exactly the same in both directions. As shown below calculating the address of node A or C from B is simply depends on which direction the traversal is going.

A = C XOR B[Pointer difference]
C = A XOR B[Pointer difference]

The original article presents some time and space complexity results. I won’t bother repeating them here.

Red Hat Magazine

Red Hat puts out a monthly publication called Red Hat magazine. It is usually worth looking at. Often they discuss new technologies that are entering RHEL or Fedora.

This month some of the articles include video presentations. However, the video is only available in Real Video or Quicktime. These codecs do not ship with Fedora; I’m not sure if they ship with RHEL.

Bad Red Hat!

Sin City

Last Friday Karen and I went to see Sin City. Since then I have made several attempts to write about it without success.

I’m still a little stunned by this movie. Its scary, disturbing but yet funny at times. The bad guys are sometimes just lowly hit-men out to make a buck; others include cannibals and child molesters. Make no mistake, this movie hits all the evil person buttons. The good guys are still bad guys but do bad things for mostly good reasons.

Sin City is violent but the violence forms a big part of the world so it doesn’t seem out of place.

About the only conclusive thing I can say about this movie is that it is the most unique movie I have ever seen. For that reason alone, you should go see it too.

Update: I forgot to add one of my favourite quotes from the movie.

”I love hitmen. No matter what you do to ’em, you never feel bad.”
— Marv (Mickey Rourke)

It’s been a long time..

Wow, it’s been a long time since I have posted. So here is a grab bag of what has been going on.

The last semester of my undergraduate degree is almost over. Less than two weeks left.

I handed in my undergraduate thesis last week; the presentation is this Tuesday. Fortunately, I was able to get the main work of the project done a couple of weeks ago which left me with lots of time to write the final report. This is good because I am a slow writer. At some point I’ll probably post a PDF version of the report here. If you are considering doing an undergraduate thesis I certainly recommend it. It is really great to be able to work on something personally interesting and get credit for it. Of course that is the catch, if your not interested in the topic, it is probably very hard to force yourself to do the required work.

After the thesis presentation on Tuesday the only course work I have left is two assignments: one for distributed systems and one for cryptography.

Also on the university front, I received my acceptance to the MSc program a few weeks ago.

Starting my MSc in September will be exciting but for now I’m just looking forward to four months with no homework. I’m pretty much at the burnout point.

One goal I have for the summer (besides being outside a lot) is to catch up on my reading. I tend to get quite far behind during the school year. In order to catch up I have to read: 6 issues Communications of the ACM, 5 issues of Linux Journal, 2 issues of IEEE/ACM Transactions on Networking, 5 issues of Queue and a few other miscellaneous magazines. Plus all of the unread books that have been accumulating.

And of course, some blogging!

Blog spam

The blog spam on my site has gotten so bad I decided to use WordPress 1.5’s new word black list feature. It seems that 90% of the spam I get is for online casinos. These posts always contain either “texas holdem” or “poker” so I have black listed “holdem” and “poker”. This is a pretty big stick that I don’t want to use but constantly deleting spam in the moderation queue is getting quite annoying.

LQL# HTB control

Now that LQL-Sharp has been released I thought I should put together a quick little demonstration of just how cool it is.

I have created a extremely simple GUI control that can modify the rate and ceiling parameters of a HTB class. This control should really subclass Gtk.Widget but it serves its purpose as is.

TC HTB Control

using System;
using Gtk;
using LQL;
class HTBControl {
	private LQL.ClassHTB klass;
	private LQL.Con con;
	private Gtk.SpinButton rateSpin;
	private Gtk.SpinButton ceilSpin;
	public HTBControl(LQL.ClassHTB klass, LQL.Con con)
	{
		this.klass = klass;
		this.con = con;
		Gtk.Window myWin = new Gtk.Window("TC GTK+");
		myWin.DeleteEvent += new DeleteEventHandler(WindowDelete);
		Gtk.VBox vbox = new Gtk.VBox(false, 3);
		Gtk.HBox hbox1 = new Gtk.HBox(false, 2);
		hbox1.Add(new Gtk.Label("Rate (bytes/sec): "));
		this.rateSpin = new Gtk.SpinButton(0, 10000000, 1);
		hbox1.Add(this.rateSpin);
		vbox.Add(hbox1);
		Gtk.HBox hbox2 = new Gtk.HBox(false, 2);
		hbox2.Add(new Gtk.Label("Ceiling (bytes/sec): "));		
		this.ceilSpin = new Gtk.SpinButton(0, 10000000, 1);
		hbox2.Add(this.ceilSpin);
		vbox.Add(hbox2);
		Gtk.Button modifyButton = new Gtk.Button("Modify");
		modifyButton.Clicked += new EventHandler(Modify);
		vbox.Add(modifyButton);
		rateSpin.Value = this.klass.Rate;
		ceilSpin.Value = this.klass.Ceiling;
		myWin.Add(vbox);
		myWin.ShowAll();
	}
	static void WindowDelete(object o, DeleteEventArgs args)
	{
		Gtk.Application.Quit();
		args.RetVal = true;
	}
	void Modify(object o, EventArgs args)
	{
		this.klass.Rate = (uint) this.rateSpin.Value;
		this.klass.Ceiling = (uint) this.ceilSpin.Value;
		this.klass.Modify(this.con);
	}
}
using System;
using Gtk;
using LQL;
class MainClass {
	public static void Main(string[] args)
	{
		Application.Init();
		LQL.Con con = new LQL.Con();
		LQL.Interface nIf = con.FindInterfaceByName("eth0");
		GLib.List classes = con.ListClasses(nIf);
		foreach (LQL.Class klass in classes) {
			if (klass is LQL.ClassHTB) {
				new HTBControl((LQL.ClassHTB) klass, con);
			}
		}
		Application.Run();
	}
}

Gay Marriage in Canada

On February 1, 2005 the Federal Government of Canada introduced legislation into the house of commons that would make gay marriage legal across the country. Courts in most provinces have already ruled that stopping gay marriages is unconstitutional so it should not be surprising that the federal government has taken this measure. Not only is it the right thing to do, any attempt to make gay marriage illegal would almost certainly be struck down by the supreme court based on the Charter of Rights and Freedoms anyway. Nothing but the lining of lawyers pockets and the wasting of tax payers money would be served by such an attempt.

None of this has stopped the usual bantering and idiotic arguments put forward by the “anti-gay marriage” people.

First of all, I think I am pretty unbiased on this issue. I’m not gay; I don’t know any gay people. No matter how this ends it will not change my day-to-day life one bit. What bothers me about this issue is the abuse of the principles involved and the complete lack of logic.

Most of the quotes below come from a CBC story called Cotler unveils ‘landmark’ same-sex law.

“If you’re going to throw open the definition of marriage so you destroy it in essence, how do you know you can ever draw the line any place? If I want two or three wives and want that considered legal marriage, who are you to tell me I can’t do that?” – Ontario MP Pat O’Brien, May 10, 2003.

This is nothing but fear mongering. Society can, and does, set limits all the time. Did lowering the drinking age from twenty-one to nineteen “throw open” the possibility of further lowering the drinking age to sixteen? Of course not.

“The Conservative party will fight to give a greater voice to Parliament. We will ensure that issues like marriage are decided by Parliament, not the courts.” – Party website.

Great plan. Lets have societies dominant elements decide for everyone else what is OK and what is not. That is a sure way to make sure everyone is treated fairly. Wake up! The Charter was created for exactly this reason. The elected representatives who, in a large part, represent the dominant groups of society cannot be trusted to enact legislation that protects minorities.

. . . no religious officials will be forced to perform marriages that are contrary to their beliefs.
– Justice Minister Irwin Cotler

Vic Toews, the Conservative party’s justice critic, disputed the Liberals‘ insistence that the law protects religious officials from having to perform gay-marriage ceremonies.
He also said there’s no protection for individual Canadians who don’t hold a church office but want the right to refuse to have anything to do with gay marriage.
. . .
Toews cited several examples of people and groups whom the bill wouldn’t protect:

  • Civil marriage commissioners in Saskatchewan and Manitoba, who have been told they must perform same-sex ceremonies or lose their jobs.
  • . . .

How is this any different than if a civil marriage commissioner refused to marry an inter-racial couple because of his or her beliefs? The answer? It’s not. The idea that an agent of the state should have discretionary privileges is absurd. Why even have laws if the people implementing them have the option to ignore the laws they do not agree with?

That’s why his party [Conservatives] will try to amend the bill, limiting marriage to one man and one woman while offering homosexual couples full rights under some other type of civil union.

Notice the word “full”. At least in this case they have not used the word equal. I always find people who say things like “We believe in equal rights . . . gays can have civil unions with the same privileges as marriage just not marriage proper” hilarious. You either believe in equal rights or you do not. Adding a qualification to any statement about equal rights means that you do not believe in equal rights, period.

“What we are seeing is a consistent pattern,” he said. “Whenever equality rights and religious rights collide, equality rights trump.” — Vic Toews

Again, I am dumbfounded by this person. Of course equality rights trump religion. Think about how absurd it would be if it were the other way around. Which religions views would would society take as ‘right’? What about religions whose views directly contradict each other?

The people fighting against gay marriage need to seriously think through their views. They should think about how the world remembers the active and vocal racists of not so long ago. For this is exactly how the world will remember the anti-gay marriage people in twenty years.

LQL#

Work has begun on the long promised Mono (C#) bindings for LQL. This little C# program will display traffic statistics for all of the queueing disciplines that are supported by the C LQL library.

using System;
using LQL;
class MainClass {
    public static void Main(string[] args) {
        Gtk.Application.Init();
        LQL.Con con = new LQL.Con();
        GLib.List ifList = con.ListInterfaces();
        foreach (LQL.Interface netInf in ifList) {
            GLib.List qdiscList = con.ListQdiscs(netInf);
            foreach (LQL.QDisc qdisc in qdiscList) {
                qdisc.UpdateStats(con);
                qdisc.PrintStats();
            }
        }
    }
}

Very exciting stuff!

LQL# is not nearly polished enough for a public release yet but I am quite happy with how the work is progressing.