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
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.
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."
Erik
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!).
But what does "if you want to totally ignore efficiency" mean? exatclly what it says. If I make a one off I will want to ignore anything that will increase developement costs. If I make something that is to be produced in huge numbers (my 'record' is 680,000) I will want to ignore anything that will increase unit cost. If I make something where throughput is critical I will want to ignore anything that is not the fastest possible code in areas where it matters. 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? none of the above, but efficient for the processor (i.e. throughput). There would be no other reason to have 'architecture' in the title.
I DON'T want to annoy you you are absolutely not, different opinions is the very purpose of a forum. I state my opinion, you state yours. There is, in your post, NOTHING that even reading it 10 times (I did not) could be construed as a personal attack.
The very point that has been totally missed in this whole discourse is that nobody knows if the OPs project is time critical (i.e. requiring 'efficiency') or not, and if you read my post that started this whole shebang you will see that I specifically say "if you do not care about efficiency, go ahead and use the linked list"
Neither you nor I can know if the OP cares about efficiency, but because of my post he is warned if he does.
By the way, this brings up a different issue, where so many posts fail to state "what for". The best solution for a rocket is not necessarily the best soultion for a toy (expression 'stolen' from Patryk www.cygnal.org/.../002723.html )
"none of the above, but efficient for the processor (i.e. throughput). There would be no other reason to have 'architecture' in the title."
But my point: "Efficient for finding random data" does mean efficient for the processor.
But my point: "Efficient for finding spatially related data" does mean efficient for the processor.
But my point: "Efficient for inserting data" does mean efficient for the processor.
But my point: "Efficient for removing data" does mean efficient for the processor.
But my point: "Efficient memory usage" does mean efficient for the processor.
But my point: "Efficient to sort" does mean efficient for the processor.
It is all about architecture. For some situations, lists are the #1 champ. They are 100% perfect for some operations. A ring-buffer allows perfect inserts in one end and perfect removals in the other end. But try inserting or removing in the middle.
A dual-linked list can be spliced in constant time. Suggest any alternative that can beat a list for splicing in the middle!
They are marvelous for sorted priority queues.
A trie - a special form of tree/linked list - is a champ at allowing log-n search (the best you can get with the exception of a direct lookup) while at the same time supporting optimum forward and backward iteration. A hash can do constant-time searches, but try to iterate a hash table in sorted order...
Maybe you call lists inefficient because you apply your concept of a list on some virtual (for us unknown) problem that may not be suitable for a list. But for a large class of problems, there are no other solution that can do better, i.e. be more efficient for your little processor, than a list.
All CS programs has at least one course where abstract data types are covered, and where they are compared when it comes memory usage and how fast they are for different operations. A sequential scan of a list is O(N) - the worst - but an insert directly after a known element is O(1) - the best. But the O(N) to locate an item in a list may directly become O(log N) if the list is formed as a trie. That is the best you can manage in a sorted vector too. Except that a sorted vector takes O(N) amortized time to insert a random element. The trie does it in O(log N), totally spanking a vector.
Small processor or supercomputer doesn't matter. O(N), O(log N) or O(1) does matter, and it takes a problem description and design work to figure out if a list will be the perfect choice or not. But never call it inefficient unless you specify a usage where it really is inefficient compared to another data structure. That is the same as saying a 8051 is inefficient! Or an ARM is inefficient. Or an Opteron is inefficient. Or English is inefficient. They all are, depending on criteria.
all correct IF a linked list is the right choice to what the OP is doing". What you mention can, when using the '51 architecture in many cases be done much more effcient with an array of pointers. Since we do not know what the OP is dealing with, I include a part of my previous post By the way, this brings up a different issue, where so many posts fail to state "what for".
so, we are discussing different approaches - which is fine - however which is the best depend on the (OPs) application.
Erik,
Did you actually bother reading my post?
I'll repeat it here:
"You must learn to realise that efficiency is a relative term."
And your follow on:
"the point I made was that linked lists kill efficiency (which nobody has denied)."
THAT IS SIMPLY NOT TRUE FOR ALL SITUATIONS.
I clearly demonstrated, by way of describing a working design, that the code which contained a linked list was efficient; i.e., it fully satisfied the customers requirement.
I'll repeat it again:
Now ... You try repeating it.
I clearly demonstrated, by way of describing a working design, that the code which contained a linked list was efficient; i.e., it fully satisfied the customers requirement if "fully satisfied the customers requirement" is your definition of 'effcient' then we are totally talking past each other.
efficiency, as I stated, can be many things but the efficiency in the case of processor 'throughput' is an absolute.
If I have made na error in the post that started this rigamarole it is that I used 'efficiency' in the meaning it has to my current (since 8 years) environment, I see from the hoolabaloo that Ishould have said "murder to processor efficiency" or some such.
If you are making a one-off efficiency in my use is totally irrelevant. if you need $100 worth of 'iron' to save $1000 in design cost, that, of course, is the right approach, but not 'efficient' in my use of the term.
if "fully satisfied the customers requirement" is your definition of 'effcient' then we are totally talking past each other.
NO NO NO - That is NOT my definition.
At the risk of sounding boring, I'll repeat it yet again:
*** Blink, blink - Mr Ego - Blink, blink ***
I deny that!
In the example I cited, I suggested a linked-list precisely because the alternative was so cumbersome!
" needs to be easily re-ordered, and/or items need to be easily added to & removed from the list.
Of course, using a linked-list where a straightforward lookup table (array) is a more appropriate solution is stupid; but that's a fault in choosing the wrong tool for the job - not a fault with linked-lists per se.
In the example I cited, I suggested a linked-list precisely because the alternative was so cumbersome! for you or for the processor?
NO NO NO - That is NOT my definition then what is?
"efficiency in the case of processor 'throughput' is an absolute."
Not really.
The "processor throughput" depends upon the task at hand:
Using a linked-list where a simple lookup table would do the job is obviously an inefficent way of achieving the goal;
But using a linked-list to manage a large number of timers may well be a more efficient approach than any others available - so, in that case, the Linked list is an efficient solution to the problem at hand.
So, efficiency is relative!
NB: The Linked-list approach to the timers is particularly efficient when there is a large total number of timers, but only a few are actually running at any particular time.