Need help in RPN calculator

[Lost__Soul]

I developed a program that is an rpn calculator. For those who dont know what an RPN calculator is,it works similar to assembly programming language. An input file would look like this:
PUSH 1
PUSH 2
POP abc
PUSH 2323
ADD
MUL
POP xyz
JUMP 2
...
The program is working fine,i just have to improve efficiency. I´m using fscanf to read each line and then i have a function that computes each command (ADD, MUL,...). The problem is with the JUMP function:
In this example,the program would jump to line 2(PUSH 2). I have a program counter that stores the current line number. But, when i have to jump, 2 things can happen:
1. The line is before the current line: i use rewind(file) then program counter =0, read the commands again until i find the one i want;
2. The line is after the current line: in this case, i just keep reading lines until i find the one i want.
This works,but its not very fast,specially in very large inputs. So,i was thinking in storing the commands in memory while i was reading then and then read the memory instead of the file. The only thing i dont know is what data struture should i use to store things in memory. My teachers talked about an hash table,ok, that would be good, i just dont have any idea of how to hash the lines. They also told me that inserting a line in each position of the array will eventually result in a segmentation fault(the inputs will have millions of commands).
So, i hope someone could give some ideas!

[R.Stiltskin]

How 'bout an array (or a vector) of strings? You can load the commands sequentially into the array, and then you can jump directly to the one you need. Also, you can easily build in procedures to prevent jumping beyond the limits of the array.

[XSquared]

>> (or a vector)
This is C, not C++. No vectors.

A linked list would work well here though.

[R.Stiltskin]

Sorry. Forgot where I was on the board.

But I still like the array idea better than a linked list - allows for directly accessing the desired command. So, an array of pointers to char strings. Either declare an array of a fixed size long enough to accomodate some predetermined maximum number of commands, or use malloc to allocate an appropriate array size for the particular input file.

[XSquared]

With this program you're stepping through the commands in order, so a linked list would be perfect. You don't need to jump around a whole lot.

If you do decide to use an array, make sure you allocate it on the heap, not on the stack. Otherwise you will run outta memory fast.

[Lost__Soul]

There´s no "predetermined maximum number of commands". Like i said, the array option will have a memory problem, billions of commands would require an array with billions of positions...And the linked list is not an option, since it would require to read everything in the list,which would take a lot of time.

[DavT]

... But if you implement a fifo buffer and limit the distance that you allow for jumps - maybe think about making jumps relative (assuming you have some kind of control over the language definition) so that the code you had becomes:

PUSH 1
PUSH 2
POP abc
PUSH 2323
ADD
MUL
POP xyz
JUMP -6
...

I know this limits how far you can jump, but to honest I consider that a good thing!

[Lost__Soul]

Well, that would be good, but i cant limit the jump...

[Lost__Soul]

The advantage of 2 and 4 is that you only parse the line once - assuming that you've separated the 'parse' from the 'execute' in your code.

I´ve parsed the line.

Compared to what - keeping it all in a file and using lots of file commands (like fseek()) to shuffle backwards and forwards?

Well, the list would have as many ~elements as the commands. Imagine i want to access the 1,500,000º command, i would have to read 1,499,999 commands before i find the one i want. The program shouldnt take more than 1 minute to return the result, so the list would be too slow.

Will be a very big file!!!

yup, its serious, how do i build a cache?

[Lost__Soul]

This places an upper limit on the size of your file - simply reading a huge file will take a long time.

Believe me,it doesnt...In my university we got used to find the most eficient solution, and since i was told that the program wont take more than a minute,even with the big files, i have to make it work like that.

I´ll do some search for caches and if i have any doubt i´ll post them here...

[Lost__Soul]

Tried a search in google but found no "implementable" algorhitm...Can you give me some idea of what i have to do? i dont need any code, just some ideas. The cache would work similar to an hash table,right?

[Lost__Soul]

Well,thnks a lot, this is way to advanced for a begginner like me so i have to read it carefully.

[WaltP]

Another option is to
1) read the entire file (or as much as is feasable),
2) preprocess the file by adding each line (0th byte and every byte that follows a CRLF) to a pointer array
3) change the preceeding CRLF to \0

Now you have the file by line in memory. Your JUMP 2 then simply goes to the pointer array.

For files that are too large to read in one pass, you'll have to work out how to process pages as mentioned previously.

[XSquared]

If there are 'billions' of commands, you're dealing with a multi-gigabyte file.

Also, is a jump command dealt with once, then ignored? If not, if it is jumping to a position before itself, it will just go into an infinite loop.

[Lost__Soul]

The jump can be conditional, for example, JUMPZERO number
The program will only jump to line "number" if the top of the stack is 0. The JUMP is never ignored, so this kind of input file will not be tested(it would enter an infinite cycle).

I´m trying to solve the problem with fseek and with an array to store the position(in bytes) of each line. If this doesnt solve the effiency problem, then i´ll have to work with the cache thing.