AMOS PD CD/amospdcd.iso/351-375/apd372/jason_banks/list_procs.amos/list_procs.amosSourceCode

AMOS Source Code | 1991-06-13 | 10KB | 218 lines

'
' List Routines
'
' (c) 12/91 Jason Banks - Routines used to manipulate a double-linked list
'
' Notes - See _DOCS procedure for instructions
'
LISTBASE=0
' Normally this could be defined as a global variable
' BUT we will need more than one listbase, and this way we can avoid
' writing multiple routines to do the same job for each list-type
'
_NEXT=0 : _PREV=4 : Rem add in other data-pointers here.
'
Global _NEXT,_PREV
'
Procedure _ADDLIST[LISTBASE,ITEM]
' TAKES THE LOCATION OF A PRE-DEFINED DATA ELEMENT, AND ADDS IT INTO THE LIST
' usage is :: _ADDLIST[listbase,itemptr] : listbase=param
'
   NEWLISTBASE=ITEM
   Loke ITEM+_PREV,0
   If LISTBASE=0
      Loke ITEM+_NEXT,0
   Else
      Loke ITEM+_NEXT,LISTBASE
      TEMPITEM=LISTBASE
      Loke TEMPITEM+_PREV,ITEM
   End If
End Proc[NEWLISTBASE]
Procedure _INSERT[LISTBASE,ITEMPTR,ITEM]
' Inserts a data element in the list, before the itemptr passed as a pointer
' usage is :: _INSERT[Listbase,insertposition,itemptr] : listbase=param
'
   If Leek(ITEMPTR+_PREV)=0
   ' at start of list!
      _ADDLIST[LISTBASE,ITEM] : LISTBASE=Param
   Else
      PPTR=Leek(ITEMPTR+_PREV)
      Loke PPTR+_NEXT,ITEM : Loke ITEMPTR+_PREV,ITEM
      Loke ITEM+_NEXT,ITEMPTR : Loke ITEM+_PREV,PPTR
   End If
End Proc[LISTBASE]
Procedure _GETNEXT[ITEM]
' Returns the address of the next item in the list
' usage is :: _Getnext[item] : itemnext=param
   If ITEM=0
      NITEM=0
   Else
      NITEM=Leek(ITEM+_NEXT)
   End If
End Proc[NITEM]
Procedure _GETPREV[ITEM]
' Returns the address of the previous item in the list
' usage is :: _GetPrev[item]: itemprev=param
   If ITEM=0
      PITEM=0
   Else
      PITEM=Leek(ITEM+_PREV)
   End If
End Proc[PITEM]
Procedure _GETFIRST[ITEM]
' This can be used to find the start of a list, when the LISTBASE has been lost, or is unknown.
' a problem that can occur here, is that in a circular-linked list (one that does not have a start or end)
' this can possibly cause an infinite loop.
' usage _getfirst[item] : strt=param
'
   _GETNEXT[ITEM] : STP=Param
   While(Leek(ITEM+_PREV)<>0) and(ITEM<>STP)
      ITEM=Leek(ITEM+_PREV)
   Wend
End Proc
Procedure _GETLAST[ITEM]
' This can be used to find the end item of a lst.
' usage _getlast[item] : finish=param
'
   _GETPREV[ITEM] : STP=Param
   While(Leek(ITEM+_NEXT)<>0) and(ITEM<>STP)
      ITEM=Leek(ITEM+_NEXT)
   Wend
End Proc
Procedure _REMOVE[LISTBASE,ITEM,SIZE]
' can be used to delete a record from the list. Note that it is essential that you get all of the parameters
' correct - it always is, but this can crash the computer VERY VERY easily.
' Usage :: _Remove[Listbase,Itemptr,SizeofItem]
'
   NITEM=Leek(ITEM+_NEXT) : PITEM=Leek(ITEM+_PREV)
   _FREEMEM[ITEM,SIZE]
   If NITEM<>0 Then Loke NITEM+_PREV,PITEM
   If PITEM<>0 Then Loke PITEM+_NEXT,NITEM
   If PITEM=0 Then LISTBASE=NITEM
End Proc[LISTBASE]
Procedure _GETMEM[SIZE]
   Dreg(0)=SIZE : Dreg(1)=$10001 : PTR=Execall(-198)
End Proc[PTR]
Procedure _FREEMEM[PTR,SIZE]
   Dreg(0)=SIZE : Areg(1)=PTR : DUMMY=Execall(-210)
End Proc
Procedure _KILLLIST[LISTBASE,SIZE]
' This procedure kills an entire list, and thus free's the memory consumed by it.
' USAGE :: _KIlllist[listbase,sizeofitem]
'
   ITEM=LISTBASE
   While ITEM<>0
      NITEM=Leek(ITEM+_NEXT) : _FREEMEM[ITEM,SIZE] : ITEM=NITEM
      ' note that we are not using the _REMOVE procedure.
      ' this is because we do not need to use a "Safe" procedure,
      ' as we don't care what happens to the list once we've deleted it!
   Wend
End Proc
Procedure _DOCS
'               List Procs  - Jason Banks - 15th December 1991
'
'     This is a set of routines that should help you to create and
' manipulate a working double-linked list. A linked list, is a series
' of memory groups, that contain pointers to one another - the idea is
' that once you know the pointer to the START item, then you can follow
' the chain of pointers to the item that you require. This is quite simple
' to do in languages such as Pascal, C and Assembly code, as this is the
' only way that these languages can perform some data-intensive tasks. Amos
' and most other basics that I know of (I'm unsure about GFA Basic), do not
' allow you to use anything like this - there is not normally a need for it,
' that's why you're programming Basic and not in one of the other languages!
'
'     However, there are some very important advantages to using a linked list,
' the main one being that, unlike an array (the nearest Basic Equivalent), you
' only use as much memory as you have in data, while the array has to define and
' often waste large amount of memory - a list is a more "Pay as you go" type
' system. Other advantages are that there are some fairly advanced search techniques
' such as Binary-Trees which are much easier to implement when using a linked list.
' [B-Tree's are commonly used as indexes, especially in data-bases. The PC DBase
' and Fox-Base programs use what is called a BTree++, which combines the best features
' of both list techniques].
'
'     To implement a List, what we need to do is define a structure for it - write down
' what all of the data items will be, and what FORM of data they will take :-
' AMOS will allow us to use Byte, Word, Long Word, and a limited form of strings for a
' linked list. We must however, add two extra records to what ever else we define our
' data structure to look like - the LIST POINTERS. It's probally easier to explain with
' an example, so here goes for a (very) simple linked list design:-
'
' We Want to keep a list of files in memory, with the name of the file, and some simple
' data about each file. Therefore the initial data structure looks like:-
'
' Filename            -      String of 108 bytes
' Size                -      longword
'
' We then also need to add in the control data, giving us a final data structure of:-
'
' Pointer to Next Record     - Longword
' Pointer to previous record - Longword
' Filename                   - 108 bytes
' Size                       - Longword
'
' To initialise this item, we use the EXEC library call ALLOCMEM to reserve some memory
' and then we can initialise the record. If the record is the first (as in this case it is)
' then we need to set both of the record pointers to 0. So that we keep track of the item,
' we place it's address in the LISTBASE variable. Later, on once we have more than one
' record, we place the value of LISTBASE into next record pointer, and a 0 into the previous
' record pointer - we then update the previous record pointer OF THE NEXT ITEM IN THE LIST,
' to point backward to the new item, and thus maintain the links of the chain.
'
'      Items also, however, contain data. We Need some way of getting the data into the list.
'      Here are some of the methods used in different languages.
'
' PASCAL :-        ListItem^.Data := Value;
'
' C      :-        ListItem->Data = Value;
'
' 68000  :-        lea     ListItem,a0
'                  move.l  #Value, Data(a0)'
'
' The Amos Equivalent, is to use a Poke, Doke or Loke command to copy the data from 'Value' to the List
'
' Amos   :-        Loke    ListItem+Data,Value
'
'      This leaves us with a rather blunt method of copying data into list items, unlike the pascal or C variants
' where the ListItem is split into several subvariables. Unfortunately, while the C and Pascal version is a rather
' graceful method, we are left with a much less refined method - and one that has much less in the way of error
' checking built in - pascal will not allow you to store a string variable where a number should be, where the amos
' version will, and possibly more to the point, the pascal version has a great deal more meaning than the normal equivalent
' of loke windowptr+62,gdget (Store the pointer to a gadget in a window structure) as compared with
' windowptr^.FirstGadget := gdget; . This tells us that we need to improve the readability of our code, by defining a set of
' pre-defined pointer values. Therefore, taking the example of the filelist, our pointers would look like:-
'
' _NextPtr = 0  (this is the first item in the list)
' _PrevPtr = 4  (0 + 4 (size in bytes of a longword) = 4)
' _nameptr = 8  (4 + 4 = 8)
' _sizeptr = 116 (8+108 = 116)
' The final size of the structure = 116 + 4 (size of final record) = 120 bytes.
'
'      So, what do we do now? Well, to make the program run a little more smoothly, we're going to create a few
' global variables, to use a pointers within the procedures. These are ListBase [*]- the pointer to the first item in the list
' (* - you may need to create several LISTBASE type variables if you wish to have more than one list in use at a time)
' and the pointers to all of the items within the data structure. We shall also create some procedures which will manipulate all of this data
' These being:-
'
' AddItem -Add Item To List
' Insert - Add Item Into List [Add an item at a given position]
' GetNext - obtains the location of the next item
' GetPrev - obtains the location of the previous item
' GetFirst - obtains the location of the first item
' GetLast - obtains the location of the last item
' RemoveItem - removes an item from the list, and rebuilds the list about it
' Killlist - removes an entire list from memory
'
'
'
' Some Final Notes. Unfortunately, the way AMOS works, if you are not careful with your
' lists, you can find your programs gaining in size, as AMOS tags your data structures along with your actual program code.
' There are two methods to remedy this, which are:-
'
' 1) - Prevention is better than cure - make sure that every block of memory you reserve is freed after use.
' 2) - Removing the extra passengers - To get rid of such hangers on, you need to save your program as an ascii file.
'      If you opt for this method, make sure that all of your procedures are opened, and be prepared for a bit of a wait
'      while AMOS translates your Ascii code back into a conventional (and hopefully smaller!) program format.
'
End Proc