Compilers and Such

Since the last time I posted, a lot has happened in my development life.

At the moment, I have 3 main projects which I am working on:

• My hobby operating system (Mattise - http://mattise.sf.net/)
• The TI-Basic compiler, for Texas Instruments graphics calculators (http://tibasic.sf.net/)
• Neural Network System ('learning' AI)

Add in exams and school, and I'm pretty busy! So I decided to save myself a lot of time, and wrote a simple linked list class, that I'm going to post here.

//--------------- CLinkedList: Linked lists for any type ---------------//
// Copyright 2007 _____________
// Created 29-5-07
// License: GPL

//--------------- Includes ---------------//
#include
#include

//--------------- Class Definition ---------------//

/**
The CLinkedList class basically is a shell around a certain data
type. It allows linked lists to be created for any data type,
hence saving coding time.
**/

// main class
template<> class CLinkedList
{
public:

// initializes the list
CLinkedList();

// destroys all data in the list
~CLinkedList();

// dumps the list
void Dump();

// clears the list
void Clear();

// inserts data at the given offset, shifting everything else
int Insert( _T, int );

// pushes data onto the end of the list
int Push( _T );

// pops data off the end of the list
_T Pop();

// gets data from the list
_T Get( int );

// deletes an item
void Delete( int );

private:

// the list type
struct myType
{
_T data;
struct myType* next;
struct myType* prev;
};

// the start of the list
struct myType start;
};

template<> CLinkedList<_t>::CLinkedList()
{
// set the next and prev fields of start to null
start.next = start.prev = (struct myType*) NULL;
}

template<> CLinkedList<_t>::~CLinkedList()
{
// clear the list, free the memory
Clear();
}

template<> void CLinkedList<_t>::Dump()
{
// iterate through the list, displaying information about each item

// running pointer
struct myType* curr = start.next;

// running accumulator
unsigned int i = 0;

// delete each item
while( curr != (struct myType*) NULL )
{
// print it
cout << "LIST[" <<>data <<>

// get the next pointer
curr = curr->next;
}
}

template<> int CLinkedList<_t>::Push( _T d )
{
// find the end of the list, then append the data

// running pointers
struct myType* prev, *curr = &start;

// wait until curr is null
while( curr != (struct myType*) NULL )
{
// save the current pointer
prev = curr;

// load the next one
curr = curr->next;
}

// check that the one we want to add to isn't null
if( prev == (struct myType*) NULL )
{
// fail!
return -1;
}

// safe, so append - we need to make a structure first
struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
m->prev = prev;
m->next = (struct myType*) NULL;
m->data = d;

// fill it in
prev->next = m;

// success!
return 0;
}

template<> _T CLinkedList<_t>::Pop()
{
// find the end of the list, and remove it after saving its data

// running pointers
struct myType* prev, *curr = &start;

// wait until curr is null
while( curr != (struct myType*) NULL )
{
// save the current pointer
prev = curr;

// load the next one
curr = curr->next;
}

// check that prev isn't null
if( prev == (struct myType*) NULL )
{
// return start's data
return start.data;
}

// prev holds the data we want
_T ret = prev->data;

// now unlink prev (the previous one's next is NULL)
prev->prev->next = (struct myType*) NULL;

// and free the pointer
free( prev );

// return the data
return ret;
}

template<> _T CLinkedList<_t>::Get( int offset )
{
// loop through the list until we hit either NULL or the offset

// offset into the list
int o = 0;

// running pointer
struct myType* curr = start.next;

// keep on going
while( o++ != offset && curr != (struct myType*) NULL )
curr = curr->next;

// we've hit the offset or NULL
if( curr == (struct myType*) NULL )
return start.data;

// return the data
return curr->data;
}

template<> void CLinkedList<_t>::Delete( int offset )
{
// loop through the list until we hit either NULL or the offset
// then unlink it

// offset into the list
int o = 0;

// running pointer
struct myType* curr = start.next;

// keep on going
while( o++ != offset && curr != (struct myType*) NULL )
curr = curr->next;

// we've hit the offset or NULL
if( curr == (struct myType*) NULL )
return;

// unlink the item
curr->prev->next = curr->next;

// free the memory
free( curr );
}

template<> int CLinkedList<_t>::Insert( _T d, int offset )
{
// loop through the list until we hit either NULL or the offset
// then append data to it

// offset into the list
int o = 0;

// running pointer
struct myType* curr = start.next;

// keep on going
while( o++ != offset && curr != (struct myType*) NULL )
curr = curr->next;

// we've hit the offset or NULL
if( curr == (struct myType*) NULL )
return -1;

// create a new item
struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
m->data = d;
m->next = curr->next;
m->prev = curr;

// link it into the list
curr->next = m;

// success!
return 0;
}

template<> void CLinkedList<_t>::Clear()
{
// iterate through the list, freeing memory as we go

// running pointers - never start at 'start' because it isn't heap allocated
struct myType* savnext, *curr = start.next;

// delete each item
while( curr != (struct myType*) NULL )
{
// save this one's next
savnext = curr->next;

// delete this one
free( curr );

// get the next pointer
curr = savnext;
}

// and make sure start is setup properly
start.next = (struct myType*) NULL;
start.prev = (struct myType*) NULL;
}

It's extremely simple to use:
CLinkedList ll;
ll.Push( 5 );
ll.Push( 6 );
ll.Push( 7 );
ll.Delete( 1 );

You might say, 'what about std::vector?' The above class is more portable, and works without modification in my own OS.

I'm gearing up to post a multitasking tutorial someday, so keep your eyes peeled!

Bye for now, not forever!