jess@gn.ecn.purdue.edu (Jess M Holle) (06/10/91)
I missed the discussion on linked list implementation awhile back. I now need to implement a linked list on the Mac (or similar structure) and would really appreciate a summary of the posts back then if somebody has one still. I am going to be using a lot of small objects (~200 objects of say 296 bits a piece) if this helps any. Jess Holle
jtgorman@cs.arizona.edu (J. Taggart Gorman) (06/10/91)
In article <1991Jun10.002416.5656@gn.ecn.purdue.edu> jess@gn.ecn.purdue.edu (Jess M Holle) writes: >I now need to implement a linked list on the Mac (or similar structure) and >would really appreciate a summary of the posts back then if somebody has >one still. Hey mark me down on this list, too. I have been avoiding dynamically allocated structures in my game I'm working on like the plague. Is the solution a Handle, ie.. dataStruct **dataHandle; ????? | J. Taggart Gorman Jr. | "I'm a no rust build up man myself." | | -Christian Slater | jtgorman@caslon.cs.arizona.edu | in 'Heathers'
hairston@henry.ece.cmu.edu (David Hairston) (06/10/91)
[jess@gn.ecn.purdue.edu (Jess M Holle) writes:] [] I now need to implement a linked list on the Mac (or similar structure) and [] would really appreciate a summary of the posts back then if somebody has [] one still. [jtgorman@cs.arizona.edu (J. Taggart Gorman) writes:] [] Hey mark me down on this list, too. I have been avoiding dynamically [] allocated structures in my game I'm working on like the plague. [] [] Is the solution a Handle, ie.. [] [] dataStruct **dataHandle; there is no "the solution"! it depends!! however there is no substitute for understanding the issues involved (i'm not trying to be arrogant, just helpful)!!! in many cases, a dynamic linked list should be implemented as (unlocked) handles with the handles data containing a handle to the next element. this lets the memory manager take care of keeping the list "out of the way". in some cases, handles are too slow (i.e. double dereference) and in other cases you want to have better control over your heap allocation so you go with pointers. using pointers requires more attention to detail on your part so that you avoid heap fragmentation, if that is a problem to you, and so on. the best solution is whatever is most appropriate in your case. btw, the Memory Manager chapters in Inside Mac should be of some assistance in this matter. -dave- hairston@henry.ece.cmu.edu
palmer@nntp-server.caltech.edu (David Palmer) (06/11/91)
hairston@henry.ece.cmu.edu (David Hairston) writes: >[jess@gn.ecn.purdue.edu (Jess M Holle) writes:] >[] I now need to implement a linked list on the Mac (or similar structure) and >[] would really appreciate a summary of the posts back then if somebody has >[] one still. >there is no "the solution"! it depends!! however there is no >substitute for understanding the issues involved (i'm not trying >to be arrogant, just helpful)!!! >in many cases, a dynamic linked list should be implemented as >(unlocked) handles with the handles data containing a handle to >the next element. this lets the memory manager take care of >keeping the list "out of the way". If you do this, you should make sure you call 'MoreMasters' enough at the start of your program. It all depends on how large a linked list you are trying to make (among other things.) -- David Palmer palmer@gap.cco.caltech.edu ...rutgers!cit-vax!gap.cco.caltech.edu!palmer "Operator, get me the number for 911" --Homer Simpson
jess@gn.ecn.purdue.edu (Jess M Holle) (06/11/91)
Well, I received this response by e-mail and was asked to post it.
Here it is:
------------------------------------------------------------------
typedef struct MyLinkedListType {
struct MyLinkedListType * * next ;
char data [ DATASIZE ] ;
} MyLinkedListType ;
void
InsertAfter ( char * data , MyLinkedListType * * * head )
{
MyLinkedListType * * it = ( MyLinkedListType * * ) NewHandle
( sizeof ( * * it ) ) ;
if ( ! it ) {
SeriousOSErr ( outOfMemory ) ;
}
/* BlockMove doesn't move memory, so we don't have to
lock the handle */
BlockMove ( data , ( * it ) -> data , DATASIZE ) ;
if ( * head ) {
( * it ) -> next = ( * * head ) -> next ;
( * * head ) -> next = it ;
} else {
* head = it ;
( * it ) -> next = NULL ;
}
}
----------------------------------------------------------------
Jess Hollefrancis@zaphod.uchicago.edu (Francis Stracke) (06/11/91)
In article <1991Jun10.170415.24845@nntp-server.caltech.edu> palmer@nntp-server.caltech.edu (David Palmer) writes: >hairston@henry.ece.cmu.edu (David Hairston) writes: >>[jess@gn.ecn.purdue.edu (Jess M Holle) writes:] >>[] I now need to implement a linked list on the Mac (or similar structure) and >>[] would really appreciate a summary of the posts back then if somebody has >>[] one still. >>there is no "the solution"! it depends!! however there is no >>substitute for understanding the issues involved (i'm not trying >>to be arrogant, just helpful)!!! My favorite solution is to declare an array type, then allocate a handle to such an array, and resize it dynamically. That way you can do it with only one handle (though you may want to have an array of handles, if your records are large), and you can index into the array rather than searching the list. Credits: I got this idea from the TObjectList class in the ObjectDraw sample app of ThP 2.0. If you're using the TCL, of course, you can use CCluster or CList. -- /============================================================================\ | Francis Stracke | My opinions are my own. I don't steal them.| | Department of Mathematics |=============================================| | University of Chicago | Welcome to the Real World. Enjoy the | | francis@zaphod.uchicago.edu | show. | \============================================================================/
casseres@apple.com (David Casseres) (06/12/91)
In article <FRANCIS.91Jun10150034@math.uchicago.edu>, francis@zaphod.uchicago.edu (Francis Stracke) writes: > My favorite solution is to declare an array type, then allocate a > handle to such an array, and resize it dynamically. > > That way you can do it with only one handle (though you may want to > have an array of handles, if your records are large), and you can > index into the array rather than searching the list. This works fine but it isn't a linked list -- it's a dynamically sized array. It's good as long as all you will do is add elements at the end or remove them from the end, but it doesn't allow you to add elements in the middle, or remove them from the middle and reclaim their storage space. David Casseres
scasterg@magnus.acs.ohio-state.edu (Stuart M Castergine) (06/13/91)
In article <14026@goofy.Apple.COM> casseres@apple.com (David Casseres) writes: >In article <FRANCIS.91Jun10150034@math.uchicago.edu>, >francis@zaphod.uchicago.edu (Francis Stracke) writes: > >> My favorite solution is to declare an array type, then allocate a >> handle to such an array, and resize it dynamically. >> >> That way you can do it with only one handle (though you may want to >> have an array of handles, if your records are large), and you can >> index into the array rather than searching the list. > >This works fine but it isn't a linked list -- it's a dynamically sized >array. It's good as long as all you will do is add elements at the end >or remove them from the end, but it doesn't allow you to add elements >in the middle, or remove them from the middle and reclaim their storage >space. > >David Casseres Here's something I learned long ago in a Pascal Class at OSU. I don't program enough to remember the code, but it went something like this in english: pointer item record item pointer prev real data pointer next Then you can dynamically create lists of any size, by having the pointers in each item point to the previous and next items. You can even make your list circular by having the end point back around to the beginning. The routines for navigating through the list are pretty simple, as I remember. You just have a "thumb" that you use to point to your current record, and maybe the first record, so you don't get lost :-) I suspect you could have multiple thumbs. You can easily add items anywhere in the list by creating a pointer to a new record and changing the pointers of the surrounding items to refer to it. I'd like to get back in the habit of programming enough to actually remember this stuff (see my previous post). -- scasterg@magnus.acs.ohio-state.edu Stuart M Castergine "Step by step they were led to practices which disposed to vice -- the lounge, the bath, the elegant banquet. All this in their ignorance they called civilisation, when it was but part of their servitude."
wolf@piquet.cipl.uiowa.edu (Michael J. Wolf) (06/13/91)
In article <14026@goofy.Apple.COM> casseres@apple.com (David Casseres) writes: >In article <FRANCIS.91Jun10150034@math.uchicago.edu>, >francis@zaphod.uchicago.edu (Francis Stracke) writes: > >> My favorite solution is to declare an array type, then allocate a >> handle to such an array, and resize it dynamically. >> >> That way you can do it with only one handle (though you may want to >> have an array of handles, if your records are large), and you can >> index into the array rather than searching the list. > >This works fine but it isn't a linked list -- it's a dynamically sized >array. It's good as long as all you will do is add elements at the end >or remove them from the end, but it doesn't allow you to add elements >in the middle, or remove them from the middle and reclaim their storage >space. > >David Casseres If you wanted to not have empty sapces in the 'array' and wanted to do true insertions so that your 'array' is always progressive, you could have your insert routine use a temphandle, set that handle to point to the array item number where you wish to insert, then do a HandtoHand copy, resize the List handle to add another item, then add the item at the insertion point (just write over the original items data) then do a HandTohand copy from the temp handle back to the List handle. This would be virtually the same for deleting items also. In this scheme you would not need to have a next or previous pointer since the array is always progressive. Just a thought... Michael
laf@mitre.org (Lee Fyock) (06/14/91)
In article <14026@goofy.Apple.COM>, casseres@apple.com (David Casseres) writes: > > In article <FRANCIS.91Jun10150034@math.uchicago.edu>, > francis@zaphod.uchicago.edu (Francis Stracke) writes: > > > My favorite solution is to declare an array type, then allocate a > > handle to such an array, and resize it dynamically. > > > > That way you can do it with only one handle (though you may want to > > have an array of handles, if your records are large), and you can > > index into the array rather than searching the list. > > This works fine but it isn't a linked list -- it's a dynamically sized > array. It's good as long as all you will do is add elements at the end > or remove them from the end, but it doesn't allow you to add elements > in the middle, or remove them from the middle and reclaim their storage > space. For adding or deleting elements from the middel of an array that has been allocated as a handle, use Munger! For example, given that filesH is a handle to an array of handles and fileIndex is the index (into the array) of the handle you want to delete from the array, errLong = Munger(filesH, fileIndex * sizeof(Handle), NULL, (long) sizeof(char **), 1L, NULL); will delete the fileIndex'th (:-) handle from the array. Munger is documented in IM I, pages 468-470. Lee Fyock laf@mitre.org
time@ice.com (Tim Endres) (06/14/91)
In article <6455@ns-mx.uiowa.edu>, wolf@piquet.cipl.uiowa.edu (Michael J. Wolf) writes: > If you wanted to not have empty sapces in the 'array' and wanted to do true insertions > so that your 'array' is always progressive, you could have your insert routine use a > temphandle, set that handle to point to the array item number where you wish to insert, > then do a HandtoHand copy, resize the List handle to add another item, then add the item > at the insertion point (just write over the original items data) then do a HandTohand copy > from the temp handle back to the List handle. This would be virtually the same for deleting > items also. > > In this scheme you would not need to have a next or previous pointer since the array is > always progressive. > > Just a thought... Have you thought about the time it takes to do tens of thousands of BlockMove()'s of say 50 KBytes? Arrays are wonderful for things like ptr's, but if my data structure is large, and I have many of them, then array insertion and deletion is unacceptable. ------------------------------------------------------------- Tim Endres | time@ice.com ICE Engineering | uupsi!ice.com!time 8840 Main Street | Voice FAX Whitmore Lake MI. 48189 | (313) 449 8288 (313) 449 9208
d88-jwa@byse.nada.kth.se (Jon W{tte) (06/14/91)
> laf@mitre.org (Lee Fyock) writes: > This works fine but it isn't a linked list -- it's a dynamically sized > array. It's good as long as all you will do is add elements at the end > or remove them from the end, but it doesn't allow you to add elements > in the middle, or remove them from the middle and reclaim their storage > space. For adding or deleting elements from the middel of an array that has been allocated as a handle, use Munger! For example, given that filesH is a handle to an array of handles and fileIndex is the index (into the array) of the handle you want to delete from the array, Come on guys ! What's wrong with people these days ? You can't do that as a general case since the memory move would take forever when put to some serious use. The suggested method of a handle with offsets in the record, and a free list, seems OK. You could have a compaction routine that purged the free list and resized the handle on idle time. -- Jon W{tte h+@nada.kth.se - Speed !
laf@mitre.org (Lee Fyock) (06/14/91)
In article <D88-JWA.91Jun14085334@byse.nada.kth.se>, d88-jwa@byse.nada.kth.se (Jon W{tte) writes: > > > laf@mitre.org (Lee Fyock) writes: > > > This works fine but it isn't a linked list -- it's a dynamically sized > > array. It's good as long as all you will do is add elements at the end > > or remove them from the end, but it doesn't allow you to add elements > > in the middle, or remove them from the middle and reclaim their storage > > space. > > For adding or deleting elements from the middel of an array that has > been allocated as a handle, use Munger! For example, given that filesH > is a handle to an array of handles and fileIndex is the index (into the > array) of the handle you want to delete from the array, > > Come on guys ! What's wrong with people these days ? You > can't do that as a general case since the memory move would > take forever when put to some serious use. The suggested > method of a handle with offsets in the record, and a free > list, seems OK. You could have a compaction routine that > purged the free list and resized the handle on idle time. Chill out! The first guy didn't give any conditions about what he wanted to use the list for. The array method works spiffy keen (and is very clean) for lists that aren't altered much. BTW, what's this list going to be used for? Maybe we can kick around some hashed B-tree implementations for a while! :-) Lee Fyock laf@mitre.org
strasser@psych.psy.uq.oz.au (Michael Strasser) (06/14/91)
I have looked at the code for the TList class in MacApp 2.0b9. It sets up a pseudo-linked list (which is really a variable- sized array in memory) with methods for insertion, deletion etc., and an Each method which is used to perform operations on each element in turn. All the elements must be the same size (which might be a limitation to you). Anyway (if I remember correctly), the coding uses SetHandleSize to change the size of the chunk of memory, and Munger to shift things around. During an Each "loop", any deletions are not made completely, but elements are marked as deleted, and actually tidied up at the end of all Each "loops" (which may be nested). I hope this helps you a bit. -- Mike Strasser Psychology Dept The University of Queensland
aries@rhi.hi.is (Mimir Reynisson) (06/21/91)
As has been noted "billions" of times before which method suits you best depends on what you intend to do (that is probably why there are some many different storage and retrieval methods available to-day). Anyways, here's my 0.02$ Below you'll find a brief summary of which method suits which data, my list is of course far from complete, but it should suffice to give an idea of these structures. One note before we start, I'm not really into hashing so I didn't include it here. There are quite a lot of reasons for discussing hashing, but as Clint Eastwood says: "right now I can't think of one" :) Fast access methods: Ordered Binary trees Very fast tree structure as long as the tree doesn't get too unbalanced. It the tree get's unbalanced it will be no better than a sequential search through a linked list. However, it's probably the simplest tree to implement and most of the time more than enough. Insertion and deletion are quite fast, so it should be very good for procedures that require fast insertion, deletion, and retrieval of relatively randomly entered data. Good for variable tables of simple language compilers, cross reference generators, and other tables of random size, which require fast insertion, deletion, and retrieval. 2-3 trees 2-3 trees are basically binary trees, except they can have 3 and sometimes 4 nodes instead of the usual 2. This as far as I can remember reduces the likely-hood of unbalanced trees. Haven't used this one in a long time, so I'm not quite sure. Balanced trees The complexity of the balancing operations suggests that balanced trees should be used only if infromation retrievals are considerably more frequent than insertions. This is particualarily true because the nodes of such search trees are usually implemented as densely packed records in order to economize storage. The problem is that empirical evaluations show that balanced trees lose much of their appeal if tight record packing is mandatory. It is indeed difficult to beat th straightforward, simple tree insertion algorithm :) Optimal trees Optimal search trees are hard to describe accuratly because as far as our consideration of data structure here goes, they have all based on the assumption that frequency of access is equal for all nodes, that is, all keys are equally probable to occur in a search. However, sometimes (really the exceptional cases) in which data about the probabilities of access to individual keys is available. If you have that data you should look into this structure; otherwise, this isn't a good place to look. B Trees and B+ Trees Quite an efficent data structure if the data is resonably random and most importantly that the data requires to be stored on an external storage device, like a hard-disk. It's really silly-as far as I'm concerned-to create a B Tree or a B+ Tree just for a memory resident data and not to mention horrible inefficent. B Trees are disk based data structures and quite good disk based data structure, but disk based data structures all the same. Look at 2-3 trees or binary trees if you need a memory based tree structure. Good for database index files and other disk based data. Sorted arrays Excellent for data that doesn't grow in size or if it does contains few items on the whole, because the entire array will have to be sorted or at least some part of it moved around in memory. Not ordered Static arrays Contains information that is of a fixed size or below the maximum size. Good for data that doesn't require a lot of space such as character strings, static tables, etc ... Should preferably not be used for structures that require searching unless the array has few items or the search is a rare procedure. Searching sequentially through 200 - 500 is not noticable unless the search is all the more frequent. Above 500 things start to get a little slow. Dynamic arrays Contains information that might grow or shrink over a period of time. Good for structure that don't have a lot of items, such as window record storage lists, but are added to irregularily or randomly and might cause heap fragmentation by other means. Slow access methods: Linked-lists Linked lists or linear lists are the simplest way to interrelate or link a set of elements. Insertion and deletion is fast. Searching, however, is linear except in the case of ordered list. The biggest disadvantage to this method is that it consumes a lot of pointers or handles if your each element is large. So if you have a list with few elements and each element isn't very large, a dynamic array is probably a better bet. A simple solution to solve heap fragmenation is to allocate your own heap and take care of the free-list yourself. This could be very fast if all the elements are of a fixed size and you somehow manage to resize your heap intelligently. Remember that the minimum number of a dynamically allocated block is 12 bytes, regardless of whether you use all these 12 bytes. So a linked list of integers whould be wasteful. Sets Sets are special structures that require that there be only one of each elements. They are usually a composition of several structure unless it is a bit set. I just thought I should mention them, since I was on a roll anyway. Bags (heaps) Since I mention sets I decided I should mention bags too :) Bags are sets basically, except for a minor detail. Bags are not sets, that is, they are allow multiple cases of the same key (or element). --- Hope this helps a little bit :) Mimir (aries@rhi.hi.is) Aries Software, Inc.