Monthly Archives: February 2012

Heap Emulation

This week in OOP we began focusing on type casting in C++ as well as allocation strategies and data storage strategies.

The type casting of C++ is a bit more verbose than it is in most other languages, the reason being is that often when typecasting data is truncated and latter we find that this data was needed, so since errors sometimes result C++ has taken to making typecasting easy to spot by giving it an overly verbose form. An example of this is the following:

int& view(char& c) const{
return *reinterpret_cast<int*>(&c);

The allocation and data storage strategies we reviewed were the following:

  • in C++ most systems interpret a char as 1 byte, as such it is a lightweight way to store general byte data.
  • to denote free space in a heap we can create sentinel values as int values(aka: 4 bytes), often these values might get overwritten accidentally, so to provide some minor error checking store two copies of each sentinel required.
  • to denote active/taken blocks use a negative value to distinguish between free blocks(positive values)

By using this information as well as some unit tests developed on the native heap manager we hope to achieve a similar heap manager that allows us more granular control of the data it has allocated, this is stricly for educational purposes of course.


performance and backing of data structures and c++ iterators

In the days that lead up to the test I found that most of my time was spent trying to chase down an off-by-one bug and in class brushing up on data structures and iterators. The earlier problem was resolved by spending roughly 5 hours running through the code inserting statements to help us see how the code was breaking and then exploring how to get GDB working with the eclipse CDT plugin. The latter was an exercise in note taking.

To recap the 5 common C++ iterators and the operators they provide are:

  • Input: !=, ==, *(read only), ++
  • Output: *(write only), ++
  • Forward: all of input’s and it can read or write on *
  • Bidirectional: all of forward’s and —
  • Random Access: all of bidirectional’s and [], +, -, <, >, <=, >=

As such if you want to make a method which accepts the most iterators you should only expect the operators provided by input or output and no others. However, < tends to be more robust as it will terminate in the case of the begining and the end iterator getting mixed up where inputs != won’t.

In the data structures discussed we looked at cost of selecting, removing, and adding elements which belong to various structures…. most of this discussion was review to me but the discussion continued to the different underlying data structures that could be used to build stacks, queues, and priority structures and this was something that I had not thought about. In summary the subcomponents were vectors, linked lists, and tree structures and stacks can use any of these, queues can use any but vectors, and priority queues can use any but linked lists.

Exceptions, Pointers, and Reference

As my weeks seem to grow increasingly short I find myself this week between interviews and assignments brushing up on some of the old lecture notes from the classes previous two weeks in the hopes that I will be ready for the test. I felt in terms of value the last week has been one of the more enlightening in terms of long term impact. The focus had been on Exceptions and C++: pointers, and references.

Exceptions had been mostly a review but I found several fine points which I had yet to encounter. One of the first points was that in Java you can catch the exception if the heap/stack overflows where as C++ there is no nice way to do this. Another point that I hadn’t considered was in the case that you caught an exception but found you couldn’t handle the exception, in this case you can re-throw the exception caught and it will propagate up the call stack until the same exception is caught in the callers.

On the pointer/reference side of things I had always found that these constructs had been the source of many a bug in my code so it was nice to go through them again. The highlights were:

  • pointers can have the address they point to changed references can not(although both can have the value they point to changed if it is mutable)
  • pointers must be dereferenced(use * to access the value they point to rather than the address) to have there value manipulated where references do not need to be dereferenced
  • references are useful as aliases in the same function scope this does not serve much purpose but this proves useful to abstract out the complexity from the programmer in function argument passing(as compared to pass by pointer)
  • non-dynamic arrays are much like pointers, in fact you can dereference the pointer and select its zero-th value to prove this, however the sizeof function will return the total size of a non-dynamic array where as it will only return the size of the pointer argument on a dynamic array/pointer. In addition the allocations of the stack(non-dynamic arrays) must only have one name for the reference.
  • dereferencing the array + n is the same as a[n] if a is the array(aka: *(a+n) == a[n] for all integer values of n in which n is less than  the array length)

Second Week in OOP

Motivated by my lack of understanding of the all too common buzz word ‘eXtreme Programing(XP) ‘and Jeff’s Post from last week, I figured I would follow suite and provide a synopsis of Kent Beck’s Episode 37: eXtreme Programming Pt 1. I found that overall XP is a set of best practices for working effectively and feeling valued as a team member. The collective opinion was that XP is the ‘least amount you should do in any given project’, I assume the opinion is derived from the fact that XP promotes productivity, error free code, and the value of the team members.

In expressing what XP is the conceivers found that it was necessary to separate the ideas into categories: values, principles, and practices — with the values being the most abstract, the principles admittedly having the potential to be contradictory, and the practices being concrete and implementable. The values of the XP discipline have remained unchanged from their original authoring but the principles have been elaborated on and changed, as such this summary will largely focus on the first rendition of the principles as the secondary principles seem more open to interpretation as they ranged from equality to economics.

The values of XP where:

  • Communication – traditionally thought to be the managers job, XP encourages the whole team to take ownership of this role.
  • Feedback  – promoted by good testing and involvement of the whole team
  • Simplicity – implement the simplest solution that solves the problem
  • Courage – largely be courageous in adopting XP, but also know when to scrap a solution that is not making progress in favor of one that will.

The principles of XP:

  • quality work – enforced by Pair Programing and required for any non-trivial task to find a resolution.
  • incremental changes(babby steps) – re-enforced by unit testing
  • embrace change – because the business requirements can be rapidly changing

Practices of XP:

  • Sit together – makes it easy to communicate about a problem, although this requires restraint from all team members as this can easily lead to rogue conversations and idle chat/jokes.
  • whole team together – often times teams become seperated by function, XP encourages small teams and heterogeneous mixing of managers and all positions on the team to provide accessibility to the members.
  • organize workspace – use resources as best as possible, encourages constructing whiteboards if they are lacking and use of post-it notes
  • energized work(40 hr week) – work at a sustainable pace, don’t over-exert.
  • Pair Programming – as discussed in class and in Pair Programming A and Pair Programming B with the basics being: have 2 programmers taking turns at one keyboard with the non-driver critiquing the code written to reduce the bugs introduced, and the driver should change every couple of hours. This reduces ‘cowboy programming’ (aka: reduces the acquisitions and finger-pointing) as well as increasing the ‘truck factor'(how many people can get hit by a truck before the project goes under)
  • Test First(Test Driven Development[TDD])- write a failing test for code and then implement the code to cause the test to pass. Similarly when a bug is found write a test that fails because of the bug then fix the bug. Advocated as a way to design a system not only regression test.

After realizing that I already followed many of the practices of XP I found that I was no longer in the dark and glad that I had a name to put to the collective set of skills that I had been using. As such I look forward to my future XP experiences in this class.