Saturday, August 22, 2009

Pointers and Link Lists in Free Pascal

Source : http://www.friends-of-fpc.org/articles/1040517/b/

      Hi and welcome... Today I will try to explain the mysterious art of pointers. Pointers have two kind of reputations. Either that they are the blessing to the programmers or that they are the curse of the programmers. This is the two sides of the same coin.

      Pointers are powerful, they are flexible, but the price you pay for that is difficulty to master and harder-to-catch bugs. Pointers, what are they. They are actually just a few bytes that contains the address to something, what they contain the address of (points to) is not of importance since the pointers only points to it.

      If we take the most basic form of a pointer and how to use them. Buffers and file-copying are a normal thing to train on so I'll take that as an example. Think about a file-copying program, what does it really do. It takes X bytes from file FIn and places them in FOut, right? But how do you get the bytes there? Do you read them directly from one file and puts it in the other file? How does that work? Try to solve that problem for a while...[Try it, c'mon]

      Welcome back, if you managed to do it as above I can only say congrats, you are in a full-feathered un*x-system and you have a great touch for it and probably know more about programming than I know.

      For the non-gurus I can only say... what did you learn? I would say that first you learned is how to search the manuals for your compiler, and second I would say that you learned that you must store the bytes read somewhere between the reads and writes... you need a buffer.

      So, the buffer, considering that discs are horribly slow at searches you want the buffer as big as possible so that you can read as much as possible at once. But how do you set up the buffer? Do you declare a static array and waste those bytes through the rest of the program as well? (If you responded yes to that you _really_ need to get a feeling for programming, every cycle and every byte is valuable if you want to write elegant and smooth-working programs.) No, you use a dynamic buffer, a buffer which you set up once the program is running, a buffer which most likely ends up in another part of the memory, in other words, a perfect thing to use a pointer for.

      So, paying with 'only needing to think better and plan better for something that will allow you to make more dynamic programs', is this the only price you have to pay? Sadly enough - no, you will also have to remember that the pointer itself takes up some memory, but that is so little that many programs that use pointers don't even notice it (on an x86 it is normally 32bits (4bytes) that every pointer takes, allowing you to address up to 4gigabyte of memory).

      But now, for the buffer. Let me take a small example:

VAR
P : Pointer;
W : Word;

BEGIN
Write('Enter a number between 0 and 65535: ');
ReadLn(W);
GetMem(P,SizeOf(W));
Move(W,P^,SizeOf(W));
FOR W:=1 TO 20 DO Write(W:4);
Move(P^,W,SizeOf(W));
WriteLn('You entered: ',W);
FreeMem(P,SizeOf(W));
END.

      Not very impressing, but straight to the point, you have freed up P, now this example is also a prime example of how not to use a pointer since it wastes memory for no good reason, but it explains the principle.

      To quickly walk through it.

VAR P : Pointer; - Tell the compiler we want a variable "P" to be a pointer.

GetMem(P,SizeOf(W)); - Reserve as much memory as the size of "W" takes up and make P point to that reserved memory.

Move(W,P^,SizeOf(W)); - Copy what's in "W" to the area pointed to by P, the little ^ indicates that we want to access what is pointed to instead of the pointer itself. At this point we can use W for whatever we want to.

Move(P^,W,SizeOf(W)); - Copy back to "W" what's in memory pointed at by P.

FreeMem(P,SizeOf(W)); - Free up the reserved memory taken (allocated) with GetMem, make sure that you free exactly the same amount of bytes as you reserved earlier.

      But now on to that file-copying program.

      >his will copy the file test2.pas to test2.bak (with no error-checking, so if test2.pas isn't there this will fail), if you want to try this program simply enough copy it and paste it into a file names test2.pas.

PROGRAM Test2;

VAR
FIn,FOut:File; // The files that we work with
Buffer:Pointer; // The temporary buffer to use
Count:Word; // The number of bytes read

CONST
BuffSize = 4096; // The size of the buffer

BEGIN
Assign(FIn,'test2.pas'); // Assign a filename to FIn
Assign(FOut,'test2.bak'); // Assign a filename to FOut
Reset(FIn,1); // Open FIn - 1=Byte Mode
Rewrite(FOut,1); // Create/Overwrite FOut
GetMem(Buffer,BuffSize); // Reserve "Buffer" memory
Repeat // We shall loop for a while
// BlockRead requests "BuffSize" number of bytes
// from FIn to be places in the space pointed at
// by Buffer and return the number of bytes read
// into Count
BlockRead(FIn,Buffer^,BuffSize,Count);
// BlockWrite requests to write Count number of
// bytes from the memory pointed at by Buffer to
// file FOut
BlockWrite(FOut,Buffer^,Count);
Until Count<>BuffSize; // End of loop
FreeMem(Buffer,BuffSize); // Free reserved memory
Close(FIn); // Close FIn
Close(FOut); // Close FOut
END.

      There, that was a better use of pointers...

      However all of the above was untyped pointers, pointers of no type at all (just RAW memory). There are another kind of pointers as well, typed pointers. Let me skip thru those as well.

VAR W : Word;
P : ^Word;

BEGIN
W:=10;
P:=@W;
WriteLn(P^);
W:=30;
WriteLn(P^);
P^:=80;
WriteLn(W);
END.

      Ok, and now for the explanation.

VAR P : ^Word; - Tell the compiler we want a pointer that will be treated as a Word (2 byte) type when it's memory is accessed.

P:=@W; - Assign the address of W (the @W says we want the address of W instead of the content of W) and put it into P. P now points at W;

WriteLn(P^) - Print whatever P points to -- displaying the value of W (10 and later 30).

P^:=80; - Change whatever P points to to the number 80. Thus, the Writeln(W) will display 80.

      As you can see any changes we make to W will appear in P^ and any changes done to P^ will appear in W. This is because it is the same memory address as defined by the "@" sign.

      Typed pointers are the more common type to use in any mid-level or high-level language since they are easier to work with, in any lowlevel language it is the same if one uses typed or untyped pointers.

      Linked lists and double-linked lists...

      A linked list, how should one explain them. A linked list is a structure of information that also contains a pointer to the next element in the list. Pretty much like a chain of structured information.

      Imagine that we have an element "A" that has the child "B". "A" and "B" are both pointers (typed pointers in most cases). "A" structure points to "B", which in turn can point to another child called "C", which can point to "D" and so on... This is called a list, in pascal we can declare a list structure as follows:

type
pItem = ^tItem;
tItem = record
Data : string;
Next : pItem;
end;

      For this to work it is important that pItem is declared in the source code before tItem, and that they are declared in the same "block". pItem is a typed pointer of the type tItem, tItem's element Next is of type pItem thus enabling it to point to itself or any identical data structures (actually it can point to anything, but the result can be pretty unpredictable if it doesn't point to another tItem).

      Now, let's demonstrate the use of a simple linked list.

type pItem = ^tItem;
tItem = record
Data : string;
Next : pItem;
end;

var S : string; // Temporary String, used for simplicity
FirstItem,
LastItem,
TempItem: pItem;
Count:Byte;// Only to make the user interface easier

begin
// Reset the pointers -- start
FirstItem:=Nil;
LastItem:=Nil;
// Reset the pointers -- done
WriteLn('Enter any number of lines of text');
WriteLn('End with a line only containing a dot (.)');
repeat
ReadLn(S);
If S<>'.' then begin
// Get memory for another tItem
New(TempItem);
// Store S to the Data field in the tItem
// structure pointed at by TempItem
TempItem^.Data:=S;
// Make sure that the field Next in TempItem is
// set to NIL. Believe me, if you make it a
// habit to set all unused pointers to NIL it
// will be _much_ easier to debug code later
TempItem^.Next:=Nil;
// Is the list empty? If so then make this item
// the first in list
If FirstItem=Nil then FirstItem:=TempItem
// or if it isn't, just let the element Next in
// the LastItem point to this item
else LastItem^.Next:=TempItem;
// And adjust the pointer to this item to that
// we can find the last item without having to
// step thru all items
LastItem:=TempItem;
end;
until S='.';
WriteLn;
WriteLn('You wrote');
WriteLn('--Start');
Count:=0;
// As long as there is a list that we point to
while FirstItem<>Nil do begin
// Make it so that LastItem points to the same
// as FirstItem
LastItem:=FirstItem;
// With indicates that we want to work with the
// data inside a record/structure
with FirstItem^ do begin
// Print what's in the buffer
WriteLn(Data);
// Make FirstItem point to whatever the element
// Next pointed to, in other words the following
// item
FirstItem:=Next;
end;
// Free the memory occupied by the old FirstItem
Dispose(LastItem);
if Count=9 then begin
WriteLn('Hit enter for the next ten lines');
ReadLn;
Count:=0;
end
else Inc(Count); // Like Count:=Count+1; Count++;
end;
WriteLn('--Stop');
end.

      Now, this maybe not look that useful, but as long as your OS allows you to get the memory you can write as many lines as you want. This program doesn't care if you write one line or if you write ten tousand lines. It will simply enough get more memory as it needs it. This is also why it is important to free up some memory.

      Now, this program does however have a major flaw, how do we search in it backwards (down-top)? Well, we would have to compare the Next until it is where we was before the search. This is where double-linked lists come handy. We declare them as follows:

type
pItem = ^tItem;
tItem = record
Data : string;
Next : pItem;
Prev : pItem;
end;

      As you can see it's the same as our linked list structure except that we now have a Prev pointer as well, it will point to the previous tItem in the chain.

      (I have copied in the previous program and modified it, in case you are curious about why it looks like I used the same program twice. And I also stripped out all the comments from the previous program)

type
pItem = ^tItem;
tItem = record
Data : string;
Next : pItem;
Prev : pItem; {new}
end;

var
S : string;
FirstItem,
LastItem,
TempItem : pItem;
Count : Byte;

begin
FirstItem:=Nil;
LastItem:=Nil;
WriteLn('Enter any number of lines of text');
Writeln('End with a line only containing a dot (.)');
repeat
ReadLn(S);
if S<>'.' then begin
New(TempItem);
with TempItem^ do begin {With is helpful}
Data:=S;
Next:=Nil;
// We set the previous pointer to point to
// the last item here already, since we will
// insert it right after the last item. As
// the first time the item is NIL
Prev:=LastItem; {new}
end;
if FirstItem=Nil then FirstItem:=TempItem
else LastItem^.Next:=TempItem;
LastItem:=TempItem;
end;
util S='.';
WriteLn;
WriteLn('Hit D and enter for reverse order anything');
WriteLn('else and enter for an forward order');
ReadLn(S); {new}
WriteLn('--Start');
Count:=0;
// If we are working in reversed order we
// start in the other end
if (S='D') or (S='d') then FirstItem:=LastItem;
while FirstItem<>Nil do begin
with FirstItem^ do begin
WriteLn(Data);
// If we are NOT working in a reversed order
// then go forward
if not ((S='D') ot (S='d')) then FirstItem:=Next
// otherwise, go backwards
else FirstItem:=Prev;
end;
if Count=9 then begin
Count:=0;
WriteLn('Hit enter for the next ten lines.');
ReadLn;
end
else Inc(Count);
end;
WriteLn('--Stop');
end.

      Oh, and most important of all... Never EVER try to play with the memory pointed at by a NIL or unitizialied pointer, that can cause some nasty side effects (in DOS, for an example, you will overwrite the IDT interrupt table if you do that, thus causing the computer to crash).

      Hope it helped an made any kind of sense --Aiw


Yahoo! Mail Kini Lebih Cepat dan Lebih Bersih. Rasakan bedanya sekarang!

1 Comments:

流浪汉 瑜伽 Yoga Tramp said...

Today (6.30am) the sky is still darkness but we already on the way to climbing mountain. This is a dangerous road , die the most cruel death if fall down overhanging . We can't see our hand, sometime we move left hand will touch owl, move right hand will touch snake. Sometime the cool wind is come, 14th July is due (chinese ghost day), i think is "brother & sister" follow us climbing mountain.