We are running a survey to help us improve the experience for all of our members. If you see the survey appear, please take the time to tell us about your experience if you can.
xdata struct EEPROM {
unsigned int Last_Data; struct EEPROM *Node; };
struct EEPROM xdata * xdata p; p = (struct EEPROM xdata *)0x0FF6; if i will print the following statement printf("Size of p = %d",(unsigned int)sizeof(*p));
then it will shows the 5,but actually it should show the 4 bytes
For any new element that we want to insert in sorted order I have, already stated that a LL may be the best way to "insert in sorted order" with the caveat that it probably will take too long to do this at the data collection point.
whether we use an array or a linked list, we have to do something to search the current data to find the point of insertion. For the array, maybe we use a binary-insertion search to speed things up, while for the list we just walk them linearly. At any rate, we have either an array index at which to insert an element, or a linked-list item after which we wish to insert.
From that point, the number of operations to insert a new item into the linked list is constant: yes, but the number of operations to get to that point is highly variable.
Again, I have several times stated that "insertion in place" is easier with a LL, but probably eventually will exceed alotted time in a '51 app, not just because of using a LL, but because of attempting a time consuming "insert in place" at the data collection point. This I have actually seen and when told the LL user stated "that should not be a problem" as any PC centric abuser of the '51 would.
Also, let me just mention that I've never used a linked list on the '51
Let me emphasize; I am not discussing LLs in general, I leave that to others, but LLs and the '51 (for which I can see no other app where LLs could be discussed than "insertion in place" of collected data). I am not really discussing LLs here, more am I discussing the seemingly widespread (just see Jacks posts) assumption that "C is C" and the fact that you apply it to a '51 is totally irrelevant.
Erik
If you (ab)use a '51 using it in a minicontroller app where time is irrelevant, that would not be discussing C and the '51, but discussing making a mistake which belong in a totally different forum.
yes, but the number of operations to get to that point is highly variable.
Again, I have several times stated that "insertion in place" is easier with a LL, but probably eventually will exceed alotted time in a '51 app,
Erik,
Your first sentence suggested you've very nearly realized what I'm trying to say, but I must not have driven it home properly. With a list, the number of operations to "get to that point" varies, while with an array, the number of operations AFTER "getting to that point" varies. For instance, you said in a previous post that it takes longer to insert at element 96 in a linked list than it does at element 2, and that is completely correct. The important point that you didn't mention is that it takes the same amount of time to insert at element 96 in a linked-list regardless of the list size. So, if the list of data you're working with is any larger than 2*96, the linked list will be faster (since the array would have to "visit" and shuffle over more than 96 elements at the end of the list).
And I don't find it that hard to imagine perfectly acceptable '51 applications that would be better suited to linked lists. For instance, imagine I'm making some sort of networked I/O device that collects data from sensors switches, etc. and then sends that data serially to a network master node. While the master is polling other nodes for information, the I/O point will have to store up a list of everything that's happened so that when it's queried it can send over that event. If this was the only description, then it suggests just an array be used to stored the data, perhaps treated as a FIFO or circular buffer. Imagine now, however, that we consider certain events to be more important than others. We might well want these to be inserted in the front of the list when they occur. If we expected this to happen regularly, I would naturally think of a linked-list since with an array, insertion at the beginning would become more and more costly as the size of the event buffer was scaled, whereas the linked list would suffer no performance impact whatsoever.
Well, all I've been suggesting is that occasions where inserting is a likely event suggests a linked list. You started the discussion with a blanket statement that one shouldn't use a linked list unless we wanted something about the "application slowing to a crawl." I was just pointing out that in the case of needing frequent insertions, you could make the same statement about arrays.
Also, I know that the "C is C" mentality is one that you rail against quite alot. I also know that you and Jack (or whoever he is) have had a bone to pick for some time. I don't think that's what this conversation is about, however. This is about data structures and the fact that a fundamental one like the linked list shouldn't be ruled out just because you're using a '51. Failure to consider it can lead to sub-optimal code (and overly-lengthy forum posts).
-Jay
Jay, We agree on almost all; the one area where we 'discuss' is about "a blanked satement" "use linked list" or "do not use linked list" is valid.
My contention is that in time critical applications and any REAL '51 app is, there is grave danger that someday in the future when the list grow you will have an 'unexpected" error. I can already hear "that will never happen" - famous last words. Why do I state "do not use linked list"? because the only valid use of a linked list is "sorted insert" and such as no place in the time critical device. It belongs at the final data (not event) processing device i.e. the PC at the end of the chain.
so, once more I have no problem, whatsoever, with linked lists on a microcontroller, but they have no place on a microprocessor. Of course, that assumes that this is not a case of misapplying a controller as a processor.
For your suggested use "more important records" I'd use a tag = no overhead.
But my previous example suggests that "sorted" could just mean divided into a few groups. For that same example, on a '51, I could create a linked list of a fixed maximum size (meaning we'll hold the last 1000 "events" or "data records" or whatever) that were generated. On each polling cycle, we can send a certain number of them and the master can go around round-robin requesting the list. If there are three "priority levels," then I just need to store the last element of each of the priority levels and I can insert into any of those points with no difference in time than tacking an item onto the end of the list. This is the sort of (admittedly contrived) application where linked lists really shine.
A tag does not have "no overhead." If you just tag each element with a priority, then when a request from the master comes in, you have to walk the list and first read out all the "highest priority" elements and continue doing that for each priority level until you've filled up a serial response. After that, since you probably still want to return items to the master in chronological order within their priorities, you'll need to go through and compact your array so that new items can be added at the end.
A method that would have no processing-time overhead would be to store a separate array for each priority level, but then you have to specify not only the maximum number of events that could occur in a given scan period(like the 1000 above), but rather then maximum of each type as well as the total.
Maybe you have access to the master node in which case you could design some smarter polling method, but maybe you don't.
We agree on almost all; the one area where we 'discuss' is about "a blanked satement" "use linked list" or "do not use linked list" is valid.
There, you are correct. I continue to believe that disallowing them for the '51 altogether is a bad idea, and I think it's a disservice to inexperienced people who read this forum to let them come away from this discussion with that impression.
I agree that there may be some 'exotic' cases where a LL could be applied to the '51 even in a control app. That, however, should not be the first approach for the very reason that the "find the slot" is of indeterminate timing which is the bane of countless control apps.
I guess that I have not realized, till now, that my objection to LLs in a '51 app is due to just that. LLs are particularily bad in this respect since the user is 'responsible for' how indeterminate it is.
I agree that there may be some 'exotic' cases where a LL could be applied to the '51 even in a control app.
Thank you . . . that is all. :)