|
Pointers and linked lists - Chapter 1 - by Aiwendil
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.
Oh well, that was the boring introduction... :)
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.
Pointers are useful when you don't know exactly where in memory everything is, and today that would only apply to a few hardcore, bare-metal coders which I would love to chat with someday.
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 knows more about programming than I know.
For the non-gurus I can only say... what did you learn? I would say that first of you learned how to search the manuals for your compiler, and second I would say that you learnt that you must store the bytes read somewhere between the reads and writes, that 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
that use pointers don't even know about 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 trough it.
VAR P : Pointer; - Tell the compiler we want a pointer
GetMem(P,SizeOf(W)); - Reserve as much memory as W takes up and make P point to that memory.
Move(W,P^,SizeOf(W)); - Copy what's in W to the area pointed to by P, the little ^ does indicate 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 memory taken 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.
This 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, (File In and File Out) that we work with}
Buffer : Pointer; {The buffer to use}
Count : Word; {The number of bytes read in each operation}
CONST BuffSize = 4096; {The size of the buffer, used for simplicity}
BEGIN
Assign(FIn,'test2.pas'); {Assign a filename to FIn}
Assign(FOut,'test2.bak'); {Assign a filename to FOut}
Reset(FIn,1); {Open FIn and set each "block" to 1 byte}
Rewrite(FOut,1); {Create/Overwrite FOut and do the same as above}
GetMem(Buffer,BuffSize); {Reserve memory and point to it}
REPEAT {We shall loop for a while...}
BlockRead(FIn,Buffer^,BuffSize,Count);
{Request BuffSize number of bytes from FIn to be places in the space
pointed at by Buffer and place the number of bytes read into Count}
BlockWrite(FOut,Buffer^,Count);
{Request to write Count number of bytes from the space pointed at by
Buffer to file FOut}
UNTIL Count<>BuffSize; {The loop ends when too few bytes has been read}
FreeMem(Buffer,BuffSize);
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. 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 byte 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 does now point at W;
WriteLn(P^) - Print whatever P points to.
P^:=80; - Change whatever P points to to the number 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 beacuse it is the same address they access.
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 use typed or untyped pointers.
End of part 1
/Aiwendil
Next part - Linked lists, double linked lists.
Back to previous page
|
