merge sort, the eater of nodes

Published: 23 February 2010

I’m so tickled to have completed an assignment for my Linux kernel class. The specification was as follows:

Modify the algorithm that allocates a file descriptor for the open() and socket() calls. Implement a per-process variable availableFileDescriptor whose value is always the number of the first available file descriptor. Make sure that when a process closes a file descriptor and or a socket, availableFileDescriptor is properly updated. Use your driver harness to compare the performance of your modified kernel with the original kernel, both for situations in which the original algorithm should work fast and situations in which the original algorithm should not work fast. You might want to remove the restrictions in the kernel on the setrlimit(RLIMIT_NOFILE,...) call.

I banged around on that thing for almost two weeks, variously getting a modified kernel that would a) segfault immediately, b) fail to reach the login prompt and just kind of hang out, or c) reach the login prompt but fail to allow me to log in. Turned out one of my main problems was that the sorting function I was using, an implementation of merge sort that I had found posted on a Linux kernel mailing list, was eating my nodes instead of just sorting them. It would delete one at a time in a sneaky fashion. I thought I had checked the thing, and who knows, maybe it worked it at first and then I changed something that caused it to grow an appetite for my struct type. At any rate, I replaced the function with my own implementation of selection sort since it was quick and easy to implement. Upon doing that, things started to behave as I expected, and it was a short road to getting my modified kernel to work properly then.

Poor Jon was sick this past weekend and so he did a lot of sleeping and sniffling. This actually worked out okay for me because, while he slept, I worked on my Linux project. He still has to go to work this week, which sucks for him, and his job is in Cincinnati, which sucks even more because of the traffic. I’m hoping he’ll be well by this weekend so he’ll be back to his usual self, plus the two of us could then go to Carly’s birthday party.

Posted in Class, Daily life | Tagged , , | Leave a comment

big-blue-man date

Published: 11 February 2010

I was walking with Mark to our cars after class today and he told me about his plans for a date he has this Saturday. We go to cross the street and a couple girls walk in front of us, cutting us off. Mark, unperturbed by other matter occupying a space in which he wanted to be, keeps going at the same speed, so he and one of the girls bump into each other. Maybe one of the girls apologized, I don’t remember, but Mark, still plowing on, cries “Watch out people!” which, after a surprised pause, made me laugh. I mean sure, we all think such things or even grumble incoherently under our breath, but we don’t say them aloud. Or at least I don’t, because I worry people will think I’m rude or something. Mark didn’t sound annoyed-rude, more like dry, why-don’t-people-watch-where-they’re-going amused. One of the girls apparently heard Mark, because she looked back over her shoulder with this annoyed look on her face and I tried to not laugh so obviously for fear she’d think I was laughing at her. So after the girl looks back at us, though I don’t think Mark noticed, he cries “Big blue man coming through!” due to wearing a large, puffy UK-blue coat. We’re across the road at this point and I can’t stop laughing. As we branch off to go to our different cars, I continue our conversation about his upcoming date with “You do have a way with women, Mark.”

Posted in Funny | Tagged | Leave a comment | Current music Paradise Circus by Massive Attack

quick lesson in love and groceries

Published: 8 February 2010

Do not let your boyfriend convince you that he just loooooves eggnog and that three one-quart cartons of it in its various incarnations (e.g., Silk Nog, Custard Nog, and old-fashioned eggnog) is just barely enough; that yes, he’ll definitely drink all of it before its expiration date; that goodness! he’ll most likely drink it all within the next two days, in fact, because he just enjoys it so much. For if you do listen to your boyfriend and buy three quarts of *nog, you will surely regret it when that very evening said boyfriend drinks a swig of *nog and decides that it has been a while since he last had eggnog and, really, it isn’t as good as he remembered.  Moral of the story:  two months after listening to your boyfriend, you will find the *nog still sitting forlornly in your fridge, taking up space that other, tastier drinks could be occupying.

Posted in Daily life | Tagged , | 1 Comment | Current music Okami soundtrack

representing rational numbers in Smalltalk

Published: 7 February 2010

For my graduate-level programming languages class, I wrote this class that represents a rational number in Smalltalk. I figured I would share my source code with the interwebs for anyone else trying to learn the language. I release the code under the GNU General Public License v3.

Note for students: my professor requested I state that, should you be taking his programming languages class CS 655 at the University of Kentucky and you try to use this code, (1) you'll get in trouble for using someone else's work and (2) you have to include the GPL and my copyright notice, which would be a big hint that it's not entirely your work. ;)

Smalltalk

" Copyright 2009 Sarah Vessels
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>. "
Object subclass: #Rational.
Rational instanceVariableNames: 'numerator denominator'.
Rational comment: 'I represent a fraction'.

" Thanks to http://en.wikipedia.org/wiki/Euclidean_algorithm "
Rational class extend [
  getGCD: a other: b [
    |A B|
    A := a.
    B := b.
    [B ~= 0] whileTrue: [
      |tmp|
      tmp := B.
      B := A \\ B.
      A := tmp.
    ].
    ^A
  ]
]

" Rational instance methods "
Rational extend [
  " Given a numerator and a non-zero denominator, this will initialize the
    Rational. "
  init: num over: denom [
    |gcd|
    denom = 0 ifTrue: [
      self error: 'Cannot have a 0 denominator'
    ].

    (num isKindOf: Integer) ifFalse: [
      self error: 'Must have an Integer numerator'
    ].

    (denom isKindOf: Integer) ifFalse: [
      self error: 'Must have a nonzero Integer denominator'
    ].

    gcd := (Rational class new) getGCD: num other: denom.
    numerator := (num / gcd).
    denominator := (denom / gcd).
  ]

  " Given another Rational instance, this will return the Rational sum of this
    instance and the other instance. "
  add: other [
    |otherRat|
    (other isKindOf: Integer) ifTrue: [
      otherRat := (Rational new) init: (other * denominator) over: denominator
    ] ifFalse: [
      (other isKindOf: Rational) ifTrue: [
        otherRat := other
      ] ifFalse: [
        (self error: 'Do not know how to add ', ((other class) printString),
         ' to Rational')
      ]
    ].

    denominator = (otherRat getDenominator) ifTrue: [
      ^(Rational new) init: (numerator + (otherRat getNumerator)) over: denominator
    ] ifFalse: [
      |lcd scaledNum1 scaledNum2|
      lcd := self getLCD: otherRat.
      scaledNum1 := self scaleNumerator: lcd.
      scaledNum2 := otherRat scaleNumerator: lcd.
      ^(Rational new) init: (scaledNum1 + scaledNum2) over: lcd
    ]
  ]

  " Will approximate the decimal value of the Rational. "
  approximate [ ^(numerator * 1.0) / denominator ]

  " Given a Rational, compareTo compares this instance with the other Rational
    instance, returning -1, 0, or 1 depending on whether this instance is less
    than, equal to, or greater than the given instance, respectively. "
  compareTo: other [
    |otherDenom otherNum lcd|
    (self equals: other) ifTrue: [ ^0 ].

    (self isPositive) ifTrue: [
      (other isNegative) ifTrue: [ ^1 ]
    ].

    (self isNegative) ifTrue: [
      (other isPositive) ifTrue: [ ^-1 ]
    ].

    otherDenom := other getDenominator.
    otherNum := other getNumerator.

    denominator = otherDenom ifTrue: [
      numerator &gt; otherNum ifTrue: [ ^1 ]
      ifFalse: [
        numerator = otherNum ifTrue: [ ^0 ]
                             ifFalse: [ ^-1 ]
      ]
    ].

    numerator = otherNum ifTrue: [
      denominator &gt; otherDenom ifTrue: [ ^-1 ]
                               ifFalse: [ ^1 ]
    ].

    lcd := self getLCD: other.

    ((self scaleNumerator: lcd) &gt; (other scaleNumerator: lcd)) ifTrue: [
      ^1
    ] ifFalse: [
      ^-1
    ]
  ]

  " Given an Integer or Rational, this will divide this Rational by that
    value. "
  divide: other [
    |otherFrac reciprocal|
    (other isKindOf: Integer) ifTrue: [
      otherFrac := (Rational new) init: other over: 1.
    ] ifFalse: [
      (other isKindOf: Rational) ifTrue: [
        otherFrac := other
      ] ifFalse: [
        (self error: 'Do not know how to divide a Ratioanl by ',
          ((other class) printString))
      ]
    ].

    reciprocal := ((Rational new) init: (otherFrac getDenominator)
      over: (otherFrac getNumerator)).
    ^self multiply: reciprocal
  ]

  " Returns true if the given Rational equals this Rational, either as the same
    object or it represents the same fraction. "
  equals: other [
    self = other ifTrue: [
      ^true
    ] ifFalse: [
      numerator = (other getNumerator) ifTrue: [
        denominator = (other getDenominator) ifTrue: [
          ^true
        ] ifFalse: [
          ^false
        ]
      ] ifFalse: [
        ^false
      ]
    ]
  ]

  " Returns the denominator of the Rational. "
  getDenominator [ ^denominator ]

  " Given another instance of Rational, this will get the least common
    denominator (a.k.a. least common multiple) of the two denominators. "
  getLCD: other [
    |diff denominator2 product gcd|
    denominator2 := other getDenominator.
    diff := (denominator - denominator2) abs.

    1 = diff ifTrue: [ ^denominator * denominator2 ].
    0 = diff ifTrue: [ ^denominator ].

    product := (denominator * denominator2) abs.
    gcd := (Rational class new) getGCD: denominator other: denominator2.
    ^product / gcd
  ]

  " Returns the numerator of the Rational. "
  getNumerator [ ^numerator ]

  " Returns the reciprocal of this Rational. "
  getReciprocal [ ^(Rational new) init: denominator over: numerator ]

  " Returns true if this Rational is larger than the one given. "
  greaterThan: other [ ^(self compareTo: other) = 1 ]

  " Returns true if this Rational is larger than the one given, or has the
    same value. "
  greaterThanOrEqualTo: other [
    ^(self compareTo: other) &gt; -1
  ]

  " Will return true if this Rational is &lt; 0. "
  isNegative [
    ^self isPositive not
  ]

  " Will return true if this Rational number is &gt;= 0. "
  isPositive [
    numerator &gt; 0 ifTrue: [ denominator &gt; 0 ifTrue: [ ^true ] ].
    numerator &lt; 0 ifTrue: [ denominator &lt; 0 ifTrue: [ ^true ] ].
    numerator = 0 ifTrue: [ ^true ].
    ^false
  ]

  " Returns true if this Rational is smaller than the one given. "
  lessThan: other [
    ^(self compareTo: other) = -1
  ]

  " Returns true if this Rational is smaller than the one given, or has the
    same value. "
  lessThanOrEqualTo: other [
    ^(self compareTo: other) &lt; 1
  ]

  " Given an Integer, this will scale the Rational by that amount.  Given
    another Rational, this will return the product of this Rational and the one
    given. "
  multiply: other [
    |newNum newDenom|
    (other isKindOf: Integer) ifTrue: [
      newNum := numerator * other.
      newDenom := denominator
    ] ifFalse: [
      (other isKindOf: Rational) ifTrue: [
        newNum := numerator * (other getNumerator).
        newDenom := denominator * (other getDenominator)
      ] ifFalse: [
        self error: 'Do not know how to multiply by ', ((other class) printString)
      ]
    ].

    ^((Rational new) init: newNum over: newDenom)
  ]

  " Returns a string representation of the Rational. "
  printString [
    ^(numerator printString), '/', (denominator printString)
  ]

  " Given a least common denominator, this will return the numerator scaled up
    such that it pairs with the least common denominator. "
  scaleNumerator: lcd [
    denominator = lcd ifTrue: [
      ^numerator
    ] ifFalse: [
      |factor|
      factor := lcd / denominator.
      ^numerator * factor
    ]
  ]

  " Given another Rational, this will subtract the given Rational from this
    instance, returning the result as a Rational. "
  subtract: other [
    |negated negNum otherRat|
    (other isKindOf: Integer) ifTrue: [
      otherRat := (Rational new) init: (denominator * other) over: denominator
    ] ifFalse: [
      (other isKindOf: Rational) ifTrue: [
        otherRat := other
      ] ifFalse: [
        (self error: 'Do not know how to subtract ',
         ((other class) printString), ' from Rational')
      ]
    ].

    negNum := 0 - (otherRat getNumerator).
    negated := (Rational new) init: negNum over: (otherRat getDenominator).
    ^self add: negated
  ]
]

Posted in Programming | Tagged | Leave a comment

House of Leaves

Published: 6 February 2010

I bought a new book last night: House of Leaves by Mark Z. Danielewski. And by “new”, I mean new to me, not new as in it just came out. It apparently was published in 2000 but I just now heard about it (on Reddit, actually) and got intrigued so I bought it. Folks on Amazon were saying it’s the scariest book they’ve ever read, et cetera, and folks on Reddit said it’d be impossible to make into a movie. It’s supposed to be some crazy postmodern book and I didn’t even know what that meant; I now think I have an inkling just by flipping through the book when I picked it up at the store. There are pages with only a line of text, pages with square cut-outs missing from the paragraph, narrow columns written backward, chunks in German and Italian but the majority is in English, and so on. Apparently the book is supposed to be self-aware and it’s about a self-aware house. So, postmodern = freaky layout and ideas? Anywho, I’m enjoying it so far, though I like Zampanò’s book about the Navidson family more than Johnny’s three-page footnotes. So far, Johnny is a pretty boring character to me, telling lies to girls in bars and rambling about his water heater. I’m more interested in the Navidson family because of their freaky house; I like haunted-house books, especially The Haunting of Hill House by Shirley Jackson and The Shining by Stephen King.

The name of the book, “House of Leaves,” seemed familiar to me but I didn’t pay much attention to it. Then I noticed on the back the word “Poe” and it looked like the same logo the singer Poe uses but I thought it was a coincidence. Then I noticed the word “Haunted” in quotes above the logo, and that’s a song by Poe that I love (and to which I am currently listening) and thought “okay, there’s got to be a connection here.” Then when I started reading the book and saw the phrase “five and a half minute hallway” I just had to check into it. I’d never heard that phrase before except on Poe’s album “Haunted”: there’s a song titled 5 ½ Minute Hallway. Turns out the author, Mark Danielewski, is Poe’s brother and her album “Haunted” is meant to parallel the book House of Leaves. Neato.

Now I had the album “Haunted” back in high school and loved it but, like a dork, gave it away to a friend and all I have left are crappy MP3 rips. Even worse, several of the tracks on the album are dialogue and I didn’t care about them at the time so I didn’t rip them from the CD. Well, I’m thinking those tracks might be interesting now that I’m reading the book, and I wanted better quality audio than 128K, so I re-bought the album on Amazon MP3 just now. It’s nice to be rehearing it. As usual, I debated between getting it off iTunes or Amazon MP3. Both had the 18-track album with the extra Hey Pretty remix, but Amazon offered it for $8.99 while iTunes had it for $9.99. I’ve written about this before, but iTunes often loses out to Amazon for me when it comes to buying MP3s, all due to price.

I got P.S. I Love You in on Netflix yesterday and, for the life of me, I don’t know why. I mean, I intentionally put it on my Netflix queue, but I dunno why. I don’t normally go for romance movies and now poor old Jon’s going to sit through it with me, haha. Speaking of movies he’ll have to sit through, I’ve already told him that he may have avoided seeing New Moon in theaters with me, but he won’t get out of watching it when it comes out on DVD. It’s already in my Netflix queue, in fact. Listen at me, saying I don’t go for romance movies and then saying I’ll inflict New Moon upon my boyfriend! Let me clarify: I enjoy the Twilight movie series because I like the book series, even though the movies are really pretty terrible. Anyway, I’ll now discontinue this line of discussion since your opinion of my Twilight-liking intellect has sunk through the floor… In other news, the next movie on my Netflix queue is The Machinist!

Posted in Opinions | Tagged , , , , , | Leave a comment | Current music Haunted by Poe