tag:blogger.com,1999:blog-11788780.post3237449566578906588..comments2023-12-29T13:22:33.104-08:00Comments on JJinuxLand: Computer Science: Offset-based Linked Listsjjinuxhttp://www.blogger.com/profile/03270879497119114175noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-11788780.post-40285440749324862332008-03-05T21:00:00.000-08:002008-03-05T21:00:00.000-08:00Windows, internally, has used the same idea for ma...Windows, internally, has used the same idea for many years. Look at <A HREF="http://msdn2.microsoft.com/en-us/library/ms802001.aspx" REL="nofollow">CONTAINING_RECORD</A> and <A HREF="http://msdn2.microsoft.com/en-us/library/aa489548.aspx" REL="nofollow">LIST_ENTRY</A>, which are defined in <A HREF="http://www.krugle.org/examples/p-IhtOQP7pOpruokyH/ntdef.h" REL="nofollow">ntdef.h</A>. LIST_ENTRYs are used heavily in the Windows source code, though it's only exposed to general developers in driver code.George Reillyhttps://www.blogger.com/profile/18041563653888119954noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-21745135086784554802008-02-22T18:19:00.000-08:002008-02-22T18:19:00.000-08:00> #define LINKSHOW(object) linkshow(((void *) obje...> #define LINKSHOW(object) linkshow(((void *) object.next) - ((void *) object), \<BR/>((void *) object.prev) - ((void *) object), object)<BR/><BR/>Very nice ;)jjinuxhttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-17463230072028264212008-02-21T16:59:00.000-08:002008-02-21T16:59:00.000-08:00Interesting that you mention macros, and passing o...Interesting that you mention macros, and passing offsets... However, if you consistently name the next/prev pointers, you can combine the two into a macro that calls the underlying function with the offsets for the specific struct. For example:<BR/><BR/>#define LINKSHOW(object) linkshow(((void *) object.next) - ((void *) object), \<BR/> ((void *) object.prev) - ((void *) object), object)<BR/><BR/>so you can just call "LINKSHOW(object)" which then calls linkshow(nextOffset, prevOffset, object)<BR/><BR/>The magic of macros effectively implement C++-like code templates.<BR/><BR/>SeanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-11788780.post-78110632289021882022008-02-21T00:14:00.000-08:002008-02-21T00:14:00.000-08:00> I thnk that the Scott Meyers of Effective C++ is...> I thnk that the Scott Meyers of Effective C++ is into training and consulting<BR/><BR/>Ah, not the same guy.jjinuxhttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-74040679031218257912008-02-18T10:30:00.000-08:002008-02-18T10:30:00.000-08:00Yet another case of "why I didn't I think of it be...Yet another case of "why I didn't I think of it before?". A very simple approach to take advantage of obvious commonalities in existing code. .<BR/><BR/>I thnk that the Scott Meyers of Effective C++ is into training and consulting <A HREF="http://www.aristeia.com/" REL="nofollow">http://www.aristeia.com/</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11788780.post-90229472932720885992008-02-18T00:06:00.000-08:002008-02-18T00:06:00.000-08:00Wow, thanks for the great comments, everyone! I w...Wow, thanks for the great comments, everyone! I was taking a risk posting something outside my realm of experience, but, man, what interesting responses!jjinuxhttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-34621463788868650522008-02-18T00:03:00.000-08:002008-02-18T00:03:00.000-08:00> This is off topic, but that wouldn't happen to b...> This is off topic, but that wouldn't happen to be the Scott Meyers of Effective C++ fame would it?<BR/><BR/>Embarrassingly, I don't know. I don't know him all that well. I do know he's a brilliant hacker, and he's the manager of the graph database team at Metaweb.jjinuxhttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-49148980558079685312008-02-18T00:02:00.000-08:002008-02-18T00:02:00.000-08:00Ian, thanks for your comment.Ian, thanks for your comment.jjinuxhttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-25055860288596176432008-02-17T18:29:00.000-08:002008-02-17T18:29:00.000-08:00Hey JJ, just wanted to add that I've seen versions...Hey JJ, just wanted to add that I've seen versions of the BSD queue.h macros that used offsets from a known base rather than pointers for the next/previous links. The advantage is that you can then put the linked objects in a shared memory segment (the segment may have a different base address in each process).<BR/><BR/>There was <A HREF="http://ml.osdir.com/os.freebsd.architechture/2002-11/msg00054.html" REL="nofollow">a proposal to add them to FreeBSD</A> back in 2002 which includes the source code.Kelly Yanceyhttps://www.blogger.com/profile/08648597728708472240noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-84932406528584013782008-02-17T02:45:00.000-08:002008-02-17T02:45:00.000-08:00The entire Amiga operating system was built around...The entire Amiga operating system was built around a linked list structure - every object started with the linked list struct, and the OS provided functions for navigating round them, even from assembler. Everything else was referenced by offsets to one of these structs - by convention data was at positive offsets and pointers to functions were at negative offsets. This enabled consistent object oriented programming, even from assembler.<BR/><BR/>In many ways the Amiga was way ahead of its time.Dave Kirbyhttps://www.blogger.com/profile/05692608289845036146noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-59658322451022326562008-02-16T19:04:00.000-08:002008-02-16T19:04:00.000-08:00Huh... I've done similar things in the past, but m...Huh... I've done similar things in the past, but my generic list functions mostly take a next pointer offset, which is computed with a macro. Something like:<BR/><BR/>#define NEXTOFFSET(list) ((unsigned long)((list)->next) - (unsigned long)(list))<BR/><BR/>Then,<BR/>list = list_sort(list, NEXTOFFSET(list), comparison_function);<BR/><BR/>I guess building a framework to organize that isn't too bad an idea.mike bartonhttps://www.blogger.com/profile/06703251205556257197noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-82117191037406603172008-02-16T18:22:00.000-08:002008-02-16T18:22:00.000-08:00This is off topic, but that wouldn't happen to be ...This is off topic, but that wouldn't happen to be the Scott Meyers of <A HREF="http://www.amazon.com/Effective-C%2B%2B-Addison-Wesley-Professional-Computing/dp/0321334876" REL="nofollow">Effective C++</A> fame would it?Josephhttps://www.blogger.com/profile/07097826327266682983noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-35942860304986972222008-02-16T18:00:00.000-08:002008-02-16T18:00:00.000-08:00Alan Kay described what he considers the first obj...Alan Kay described what he considers the first object programming similarly. I can't remember enough keywords to look it up. But basically it was in filesystems -- people wrote different filesystems for tapes, but this caused problems as new filesystems appeared or old filesystems were forgotten about. So some unnamed programmer made a system where the tape contained the code to access the records on the tape at known offsets. So, say, the get-record routine was at offset 0 (or maybe a pointer? Or maybe enough room to just jump to where the routine was held), set-record at offset 10, etc. <BR/><BR/>Similarly the linked list routines are just one step away from being a dynamically typed system -- if you put the struct describing offsets in the original struct itself then you'd have a type.Ian Bickinghttps://www.blogger.com/profile/10921115783730718101noreply@blogger.com