Hello everyone, I am studying link list in c I have a project in which I have lookup table of rpm (clocks used to load the timer used for motor). This rpm table, I am taking in an array Now I want to implement a link list which will access the rpm from table and load it to timer of clock used for running the motor Is it possible Because as I am studying the link list, in that it is mentioned that link list is used instead of array Is it possible to access an array elements using link list ? If yes, then pls suggest me some link for it Correct me if I am wrong Thank u all
I have a project in which I have lookup table of rpm (clocks used to load the timer used for motor).
Linked lists are usually used for dynamic data structures, i.e. when you're adding and removing elements during the run-time of the program. I don't think that usual lookup-tables do this.
Is it possible
It's possible, but in this case it looks like the completely wrong tool for the job at hand. The linked list will take up more memory and have a longer access time than a straight lookup table using an array.
Because as I am studying the link list, in that it is mentioned that link list is used instead of array
If you want to study linked lists, then you should also study when it's appropriate and advantageous to use them. A lookup table doesn't really fit the bill here.
"A lookup table doesn't really fit the bill here."
I think you meant "A linked list doesn't really fit the bill here."
For this specific case - translations of RPM into specific settings for a '51 chip - a sorted table is probably the best container type available, since it allows quick direct lookup in a minimum of memory.
With the '51 architecture, linked lists (dynamically allocated or not) are murder, whereas with e.g. the XA, they can be the best solution. A list like you describe will, I assume be in XDATA, just make a linked list of 3 entries and look at the generated assembler then count the cycles to get to the 3rd entry. Then visualize the time to get to the umpteenth entry.
OK, it may be that you have all the time in the world, so to save the sardine from responding, if you want to totally ignore efficiency, go ahead and link your list.
Erik
"...if you want to totally ignore efficiency, go ahead and link your list."
'scuse me ... But I have used linked lists on an 8052.
You must learn to realise that efficiency is a relative term.
On the project in question, we considered acceptability of execution time at the project start, negotiated requirements with the customer and found, for the requirement that access to the list was considered acceptable when the list contained no more than 750 records.
If it is acceptable to the customer, then the code is sufficiently efficient.
Hint: Try taking off your blinkers - You might see a whole new world!
Of course. Mistakes like that happen when I post before the first cup of coffee in the morning.
But did you use them for something that's most likely a static, ordered data structure ?
"But did you use them for something that's most likely a static, ordered data structure ?"
No, the data was dynamic, stored in a fixed area of memory (i.e., no use of malloc or the like), had records of variable length, written relatively infrequently and read relatively more frequently.
The point for us was that, when a search was needed, the required record was found in an acceptable time frame.
No, the data was dynamic,
Well, then you used the right tool for the job.
stored in a fixed area of memory (i.e., no use of malloc or the like),
As far as I've read the docs, the C51 implementations of malloc et al do exactly that - you give them a fixed area of memory and they hand out/free small chunks of it when asked.
Regardless of whether you use malloc or have rolled your own memory allocation functions, you may still run into things like memory fragmentation, though.
"As far as I've read the docs, the C51 implementations of malloc et al do exactly that - you give them a fixed area of memory and they hand out/free small chunks of it when asked."
Sorry, I didn't explain that so clearly. We just used our own simple allocation strategy of the fixed area.
For fragmentation control, we would mark blocks as free and then coalesce the free space at suitable and appropriate times. It was done as a background, interruptable and low priority operation - Again, within acceptable constraints specified by our customer.
Oh dear - There YOU go again! you decide with no such knowledge that effciency does not matter to the OP.
On the project in question, we considered acceptability
If the OP (I was not posting for you) want to ignore efficiency and decide that such is what he wants, what did I say to stop him.
The advantage with skipping malloc() is that you "know" all there is to know about the memory and any extra book-keeping information.
If the allocated blocks are fixed size, then there can never be any memory fragmentation.
But with variable-sized blocks, it is possible (when the same program has a complete overview of all memory blocks) to write compactation code that scans through all allocated blocks and moves any block that isn't adjacent to it's neighbour.
With the simple data structures normally used in smaller embedded systems, this can normally be done with quite simple code, and need not consume much time. All of the compactation need not be done at the same time. As long as the compactaction code has a capacity to move at least one memory block for every performed memory release it will keep up. With a bit of over-capacity on the heap, then short burst of allocations/releases can be allowed without bothering with any compactation. Especially since most allocations are low-term and will have either been allocated early, or will - by the compactor - float down towards the start of the heap.
This kind of compactation is hard to do with an existing malloc() since it isn't obvious how malloc()/free() stores block sizes and chains togeter used and free memory blocks.
Anyway: A list is an excellent information container and should not be ignored for any size of processor. But it is best for information that is dynamically added/removed in the middle, or that have some form of chained property to iterate forwards and/or backwards on. It's quite common to store the information in an array, but then have one or more static sorted chains as linked lists.
Finding the next table entry by index is trivial, but finding the next table entry sorted on one of the non-sorted attributes is very expensive.
"Oh dear - There YOU go again! you decide with no such knowledge that effciency does not matter to the OP."
And YOU do ???
"With the '51 architecture, linked lists (dynamically allocated or not) are murder"
NO NO NO - Maybe for your one dimensional projects, but for others it can be a real boon.
"On the project in question, we considered acceptability"
It was an attempt to indicate that just because someone gives a response in an apparent authoritative manner, it does not indicate it is the one/only/correct viewpoint.
I just hope the OP is more open minded!
*** Blink, blink - Mr Ego - Blink, blink ***
Erik: A short note. Embedded != Real-time-critical.
Embedded _may_ be real-time critical, but need not be.
Think about a programmable timer used to turn on/off the light in the garden. It is definitely an embedded application.
Please tell why the time needed to walk a linked list - even a quite long one - would matter for a device responible for turning on/off a load with one-minute programmable resolution?
A huge number of applications are of this type: They need to work, but they do not do anything requiring efficiency. Walking a list may consume a number of extra clock cycles, but the amount of extra machine instructions needed (code size) are so small that it hardly affects the price of the chip.
The extra clock cycles needed often doesn't matter - neither for the time, or for the extra energy consumption. Why fight so save a mW in an application that is used to control kW?
A passage control system that reads a magnetic strip or RFID tag shouldn't be affected by a number of ms of extra decision time before deciding if the electronic lock should be opened or not.
Tell people that there may be faster structures if hard real-time is needed, but then let the requester decide what is acceptable. You can't design their systems, just as I - or anyone else here - can't jump iin and design your systems.
All we can do, is give a number of positive and/or negative facts about a solution, and then let the OP do the weighting. If the OP decides to ignore facts, then so be it. The OP may be right, having deduced that the negative facts really are no problem while the positive facts may be really important.
On my spare time, I try to get time to work with a raytracer I have written. In a raytracer, just about everything is time-critical. Some evaluations may take a number of ns, but when the inner loops may be run 10^10 times or more, then every little optimization may represent seconds or minutes of total runtime.
Does it use linked lists? Yes, where applicable. Why? Because they are applicable. Yes, I know that a top-of-the-line PC processor are many magnitudes faster than a '51 chip, but so what. The amount of work I try to do is also many magnitudes more demanding than most embedded applications ever strive for.
Always allow people their right to a free will. You may guide, but give them a chance to make the final decision themselves. Then, they may come back and ask more questions, giving you the chance to give more advice. Forcing someones hand means that they leave this forum permanently, and also removes all future chances you may have of trying to suggesting/guiding them.
Remember school. How much did you like a teacher who always "knew best" and always demanded in detail exactly what you should do - instead of letting you try your own wings?
the point I made was that linked lists kill efficiency (which nobody has denied).
If anyone can find in my posts(s) that I said "regardless of the need for efficiency do not use linked lists" I'll buy that person a beer.
I specifically said "OK, it may be that you have all the time in the world, if you want to totally ignore efficiency, go ahead and link your list."
But what does "if you want to totally ignore efficiency" mean?
To me it does mean: "Anyone using linked lists are stupid."
People don't have to ignore efficiency just because they use lists. A list is the most efficient way of being able to add a new entry in the middle.
Also remember that lists need not represent pointers.
typedef struct { unsigned char next_idx; unsigned char prev_idx; unsigned char up_idx; unsigned char first_idx; unsigned char* *cmd; unsigned char flags; } entry_t; entry_t entries[] = {...}
The above can be seen as an array. The above can be seen as a single-linked list (from leaf to root, or from root down through left-most branch) The above can be seen as a double-linked list between elements on the same level.
Can you suggest any more efficient way of navigating such information?
The reason we learn all these container object types in school is just that every problem isn't identical. Because of this, the word efficient isn't really meaningful unless specifically qualified. Efficient for what? Efficient to implement in few lines of code? Efficient for finding random data? Efficient for finding spatially related data? Efficient for inserting data? Efficient for removing data? Efficient memory usage? Efficient to sort? Efficient to debug? Efficient to extend?
You are ignoring efficiency if you do not consider the cases where a linked list (indexed or with pointers) spanks an ordered or unordered array. An array is extremely inefficient for some jobs. Ever thought about the old flat databases? Relational databsaes or object-oriented databases has almost killed off all flat databases except for storing your contact information in Outlook. Why? Because they where not efficient...
In this specific case, it seems that the OP is working with a project where a table would be the best - or at least a very good - solution. But that is not a general case. A table, queue, hash, tree, trie, list, ringbiffer - All different concepts, sometimes being more efficient and sometimes less efficient.
Ever thought about flash file systems? Often done as tree-branching lists. Why? Because it is efficient, and you want to keep down on number of writes when performing an update.
How many RTOS do you think uses linked lists for keeping track of pending and waiting tasks? Why? Because the low cost of inserting and removing! They didn't ignore efficiency. They selected an efficient structure.
Erik, I DON'T want to annoy you, but a while ago I have posted this in response to one of your post (here: http://www.keil.com/forum/docs/thread12822.asp):
with all due respect, if that does not fit into your perception of efficiency - then you must have a great time rewriting just about anything to win a pico-second here and there. no thanks...
hell, if this guy wants to do it with lists, lets wish him all the best. I just finished a control program for a machine that uses polling only (I deliberately excluded interrupts for the control part) based on a C167CS processor, where the response time error doesn't matter that much (as long as it is plus minus 250 milliseconds). It's not like a GPS system - all it needs to do is control a couple of hydraulic valves and read position sensors. The real challenge was dealing with the trashy legacy software and to make it comply with safety standards. If it had not required rather extensive communication (interrupt based CAN, serial...) I think it could have been done with an 8 bitter as well. This is a typical non time-critical embedded application. It needs to work, be safe and comply with the requirements - not fight to squeeze every CPU cycle (unless they are included in the requirements, of course!).