BBC BASIC for Windows
Programming >> Database and Files >> Linked Lists
http://bb4w.conforums.com/index.cgi?board=database&action=display&num=1411211320
Linked Lists
Post by Matt on Sep 20th, 2014, 11:08am

Hi,

Been absent for a while.

I've been trying to get to grips with linked lists again. The program I'm designing may well benefit significantly with this process. I've read the help and wiki articles on structures and linked lists, and I believe I understand the principal of them. However, there are a few gaps in my understanding.

Based on my understanding of the help, wiki and my own experiments, here are my thoughts and a few questions. Can someone confirm / deny them and help me further with my questions, please.

1. The new node.

Code:
DEF FNnewnode(RETURN n{})
LOCAL P%
DIM P% DIM(n{})-1
!(^n{}+4) = P%
= P%

In line 3 a new memory block is allocated the size of the Data Block - this in addition to that already allocated to node{}/n{}.

In line 4 a pointer to that memory block is set in the Data Block Address part of the structure's Header Block.

Should the Format Block not also be re-allocated as it and the new Data Block are now unlikely to be contiguous? Or is this an erroneous assumption? (I am unable to evaluate this by my testing apart from the fact that the Wiki program works fine.)

2. Retrieving the data.

Code:
DEF FNgetitem(RETURN n{}, n%)
IF n% = 0 THEN = ""
!(^n{}+4) = n%
= n.item$

The last line retrieves the datum via the structure member n.item$ and returns it to the calling line. As with the question above, with the Data Block not being contiguous with the Format Block, why does this not give an erroneous result? (Or, maybe as above, my assumption is erroneous.)

3. Deleting items.

The program in the Wiki article shows how to form a basic linked list. It is also easy to extrapolate the way to remove an item from the list by setting the previous node's 'next link' pointer to the same as the one being removed. However, this will leave an allocated memory block unused, wasting space. If the chain were only a few links long this might not be a problem. One could also assume that the unused one might be used at a later date, re-linking it - but it might not be. If the chain were to contain many thousands of links that are access and changed, and possibly deleted, there could be a significant build up of unused memory blocks. Is there a way to release the memory block and avoid wastage? (Is this what is called 'memory leakage'?)

4. Searching

In my program there may be tens of thousands of links. In an array, a binary search would be a simple process to run in order to find a particular item. However, I find it difficult to work out how to locate an item without running through the entire chain one link at a time. What would be the easiest, quickest way to search the list?

(Having written this, last bit, it occurs to me that the majority of my searches would necessarily be linear, anyway, but an answer might be interesting.)

Matt
Re: Linked Lists
Post by rtr2 on Sep 20th, 2014, 1:19pm

on Sep 20th, 2014, 11:08am, Matt wrote:
Can someone confirm / deny them and help me further with my questions, please.

I am hesitant to answer any technical questions here, because of the danger of creating 'troll bait'. However I will risk giving factual information without comment, in the hope that he will remain undisturbed.

Quote:
Should the Format Block not also be re-allocated as it and the new Data Block are now unlikely to be contiguous?

There is no requirement for them to be contiguous. If they were guaranteed to be so, only one pointer would be required rather than the two actually provided.

Quote:
Is there a way to release the memory block and avoid wastage?

Not built in, no (assuming the memory is allocated on the heap). The usual approach would be to maintain a linked list of 'free' blocks to which unallocated blocks are added, and from which new blocks are preferentially allocated.

Quote:
What would be the easiest, quickest way to search the list?

A linear search is the only way (usually). As it says in Wikipedia "This is one of the primary disadvantages of linked lists over other data structures".

It is interesting to note that BB4W uses both of the documented strategies to speed up finding variables. Firstly an index is used, based on the initial character of the variable name (there are 54 linked lists). Secondly the move-to-front heuristic is used so that the most-recently accessed variable (with a given initial character) is found very quickly.

Richard.
Re: Linked Lists
Post by Matt on Sep 20th, 2014, 2:37pm

Thanks for your response.

on Sep 20th, 2014, 1:19pm, g4bau wrote:
Not built in, no (assuming the memory is allocated on the heap). The usual approach would be to maintain a linked list of 'free' blocks to which unallocated blocks are added, and from which new blocks are preferentially allocated.

This was my initial guess - although, hoping otherwise. And thinking about it, if there is enough room for a full list, deleting some and placing them in a 'free' list will take up little or no more room. Assuming the memory is freed up upon the program's exit, this should not be a problem for the system either. Is that correct?

What will happen to the data area (numeric and string), as opposed to the format block, for the deleted item? I assume it will be re-used with the next inserted item, provided it uses one from the 'free' list.

Matt
Re: Linked Lists
Post by rtr2 on Sep 20th, 2014, 3:00pm

on Sep 20th, 2014, 2:37pm, Matt wrote:
What will happen to the data area (numeric and string), as opposed to the format block, for the deleted item?

I'm confused. I thought you were talking about the 'data area' when you were referring to a 'block'. My assumption is that all nodes of the linked list will have an identical format, and will therefore share the same 'format block' (just like a structure array does) which would never be 'deleted'.

String members (by which I mean, e.g., s$ not s&()) must of course be emptied before a data block is deleted. You can always use Jon Ripley's very clever PROC_ClearStruct to do it.

Richard.
Re: Linked Lists
Post by Matt on Sep 21st, 2014, 06:28am

on Sep 20th, 2014, 3:00pm, g4bau wrote:
I'm confused. I thought you were talking about the 'data area' when you were referring to a 'block'. My assumption is that all nodes of the linked list will have an identical format, and will therefore share the same 'format block' (just like a structure array does) which would never be 'deleted'.

Sorry. I understand your confusion. I'm not making myself clear - as well as being confused myself. I've played around with so much stuff concerning this, I've occasionally lost myself.

What I meant to ask was what happens to the area containing the actual string (the pointer of which is in the data area), the answer to which you have offered:
Quote:
String members (by which I mean, e.g., s$ not s&()) must of course be emptied before a data block is deleted. You can always use Jon Ripley's very clever PROC_ClearStruct to do it.

So when a record is deleted, the structure has to be passed to through the 'clearing' proc and then placed in the 'free' list. This will reduce the amount of used memory to a minimum, but still hold the structure's data area in the list, which can then be reused and refilled.

Still a little confused about the role of the format block. Correct me if I'm wrong. The header block contains the two pointers to the format block and the data block. The format block contains the details of the elements within the structure pointing to an offset in the data area. Is it true, then, that the offset is from the start of the data block wherever that happens to be (the location of which is taken from the header block), rather than the end of the format block - contiguation (if that is a word) would tend to be the norm rather than the rule. It, therefore, as you said, does not have to be contiguous. If this is true, it seems to make a lot more sense than my initial assumptions.

(There seems to be some complicated things things I find easy to grasp, and other simple things I find such hard work.)

Matt
Re: Linked Lists
Post by rtr2 on Sep 21st, 2014, 08:47am

on Sep 21st, 2014, 06:28am, Matt wrote:
contiguation (if that is a word) would tend to be the norm rather than the rule.

No, even in the simplest case there is a 75% chance that they will not be contiguous! For example consider this code:

Code:
    DIM struct{members}

The space for the 'format block' will be allocated and then the space for the 'data block' will be allocated. But the data block is guaranteed to be DWORD-aligned (i.e. at an address which is an exact multiple of four) so unless the format block happens by chance to finish at such an address there will be one or more bytes of padding between them.

Other ways of creating a structure guarantee that the format and data blocks will not be contiguous. For example:

Code:
      DIM struct{}=prototype{}

Here there is no necessity to allocate a format block at all (the format block of prototype{} is used) so again the format and data blocks will not be contiguous. Also:

Code:
      DIM structarray{(dims)members}

Here there is one format block (for the entire array) and multiple data blocks, so whilst the first data block might be contiguous with the format block the rest certainly aren't.

And then there is the case you cited, such as would be used for a linked list etc.:

Code:
      DIM struct{members}
      !(^struct{}+4) = new%

Here the original data block is discarded (leaked) and a new data block created elsewhere, so it won't be contiguous with the format block.

Richard.
Re: Linked Lists
Post by Matt on Sep 21st, 2014, 9:40pm

Thanks for the extensive examples.

Hopefully, this will all help with my project.

Matt
Re: Linked Lists
Post by Matt on Sep 25th, 2014, 7:39pm

Right. I think I understand the principal of the linked list program in the Wiki example. What I'm trying to do, though - and failing - is to import the records from a data file into a complex structure and then pass them into the linked list. I DIM the structure Detail{} including the member detail.link%, and then DIM Node{} = Detail{}. In the middle of the Wiki example it sets the node.item$ and node.misc to the word$ and index. What I tried to do was to copy the structure by using node{} = detail{} and then setting node.link% to the link pointer this%. However, through investigation, I find that when comparing the values in the first WHILE loop using detail.item$ rather than word$, it seems that the detail.item$ and the returning node.item$ are always the same. When I copy the structure one member at a time, it seems to work, but not by doing a straight copy in this way - yet the data pointers seem to be different.

As I realise, time and time again, understanding the basic principle and putting that into practice are two completely different things. (Or maybe I've just never understood the basic principle.)

If the explanation makes no sence, I appologise.

Matt
Re: Linked Lists
Post by rtr2 on Sep 25th, 2014, 8:17pm

on Sep 25th, 2014, 7:39pm, Matt wrote:
What I tried to do was to copy the structure by using node{} = detail{}

I wonder if you failed to take note of this warning in the BB4W manual:

"Do not copy structures containing string members; since only the string descriptor is copied, not the string itself, you are likely to confuse BASIC and may even crash it."

http://www.bbcbasic.co.uk/bbcwin/manual/bbcwin2.html#structcopy

Richard.
Re: Linked Lists
Post by Matt on Sep 26th, 2014, 4:06pm

on Sep 25th, 2014, 8:17pm, g4bau wrote:
I wonder if you failed to take note of this warning in the BB4W manual:

Err... I had forgotten. Taking note and remembering, for me, are two completely seperate things.

Irritatingly, when I'd first started experimenting with linked lists, I'd examined the format of structures and remember thinking about this. However, with all the fiddling around I was doing, it had completely slipped my mind.

I haven't tried adjusting the test program yet, but hopefully it will now work - although, I'll have to transfer the data one member at a time, and ther are a few members.

As you stated before, Jon Ripley's very clever PROC_ClearStruct enables clearing the structure. Is there any way, then, to quickly copy an entire structure - including string variables - without causing a problem? If not, is it because of the way BB4W adjusts the length/location of the string allocation, depending on its size. Would this cause a problem in a direct copy? Only curious.

Matt
Re: Linked Lists
Post by Matt on Sep 26th, 2014, 7:32pm

Hi,

I'm sorry. This is so frustrating. I get the impression there is something glaringly obvious that I'm not seeing. Here's a massivly cut down version of the testing that I'm doing. Can you tell me what on earth I'm missing?

As you can see, I've tried putting in printed items to see if I can work out what's going on. I've also tried running the 'Trace' and 'List all variables', and running step by step. I'm just missing what's wrong.

(The letters 'C', 'A', 'B', 'D' are specifically in that order to allow the first to be inserted in the first position, the second to be inserted into first infront of that one, the third to be inserted between the two, and the fourth to be inserted in at the end - all the different combinations of inserting I could think of.)

Code:
      File$ = @usr$ + "TestFile.dat"
      DIM Detail{ Category{ Main$ }, Link{ Next% } }
      DIM Node{} = Detail{}
      DIM ListPtr{ Details{ Used%, Free% } }
      PROC_CREATE_DATA_FILE
      F% = OPENIN(File$)
      WHILE NOT EOF#F%
        PROC_RECORD_INPUT(F%, Detail{})
        PRINT '"NEW DETAIL VALUE      = """; Detail.Category.Main$; """"
        PrevPtr% = 0
        ThisPtr% = ListPtr.Details.Used%
        C% = 0
        WHILE (ThisPtr% <> 0) AND (Detail.Category.Main$ > FN_GET_ITEM(Node{}, ThisPtr%))
          C% += 1 : PRINT "LOOP                  = ";C% : IF C% > 4 THEN STOP
          PrevPtr% = ThisPtr%
          ThisPtr% = Node.Link.Next%
        ENDWHILE
        NewPtr% = FN_NEW_NODE(Node{})
        PROC_COPY_STRUCTURE(Detail{}, Node{})
        Node.Link.Next% = ThisPtr%
        PRINT "ThisPtr%              = ";ThisPtr%
        IF PrevPtr% THEN
          PROC_SET_LINK(Node{}, PrevPtr%, NewPtr%)
        ELSE
          ListPtr.Details.Used% = NewPtr%
        ENDIF
        PRINT "ListPtr.Details.Used% = "; ListPtr.Details.Used%
      ENDWHILE
      CLOSE#F%
      END

      DEF PROC_SET_LINK(n{}, n%, l%)
      !(^n{}+4) = n%
      n.Link.Next% = l%
      ENDPROC

      DEF FN_NEW_NODE(RETURN n{})
      LOCAL P%
      DIM P% DIM(n{})-1
      !(^n{}+4) = P%
      PRINT "NEW NODE PTR          = "; P%
      = P%

      DEF FN_GET_ITEM(n{}, P%)
      IF P% = 0 THEN = ""
      !(^n{}+4) = P%
      PRINT "NODE VALUE            = """; n.Category.Main$; """"
      = n.Category.Main$

      DEF PROC_COPY_STRUCTURE(from{}, to{})
      to.Category.Main$ = from.Category.Main$
      ENDPROC

      DEF PROC_RECORD_INPUT(F%, rec{})
      LOCAL text$, key$, info$
      PROC_ClearStruct(rec{})
      REPEAT INPUT#F%, text$ : UNTIL INSTR(text$, "Start Record") > 0 OR EOF#F%
      INPUT#F%, text$
      IF EOF#F% THEN = FALSE
      WHILE INSTR(text$, "End Record") = 0 AND NOT EOF#F%
        IF ASC(text$) = 10 THEN text$ = MID$(text$, 2)
        key$  = LEFT$(text$, INSTR(text$, "="))
        info$ =  MID$(text$, INSTR(text$, "=") + 1)
        CASE key$ OF
          WHEN "Category Main=" : rec.Category.Main$ = info$
        ENDCASE
        INPUT#F%, text$
      ENDWHILE
      ENDPROC

      DEF PROC_ClearStruct(S{})
      LOCAL E{}, F{}
      DIM E{} = S{}, F{} = S{}
      E{} = S{} : S{} = F{}
      ENDPROC

      DEF PROC_CREATE_DATA_FILE
      LOCAL F%
      RESTORE +1
      DATA C, A, B, D
      F% = OPENOUT(File$)
      FOR I% = 0 TO 3
        READ Detail.Category.Main$
        PRINT#F%, CHR$10 + "[--Start Record--]"
        PRINT#F%, CHR$10 + "Category Main=" + Detail.Category.Main$
        PRINT#F%, CHR$10 + "[--End Record--]"
      NEXT
      CLOSE#F%
      ENDPROC


Sorry to be a pain.

Matt
Re: Linked Lists
Post by rtr2 on Sep 26th, 2014, 9:02pm

on Sep 26th, 2014, 4:06pm, Matt wrote:
Is there any way, then, to quickly copy an entire structure - including string variables - without causing a problem?

It rather depends on what the contents of the structure are. In an extreme case, when there is only one string member and all the others are numeric, you could write a relatively efficient copy routine as follows:

Code:
      temp$ = ""
      SWAP temp$, src.member$
      dst{} = src{}
      dst.member$ = temp$
      SWAP temp$, src.member$

This initially swaps out the string member and replaces it with an empty string, creating a structure which is safe to copy. The copy then takes place, and the string member of the destination structure is copied from the temporary variable. Finally the string is swapped back into the source structure.

As a procedure this might be:

Code:
      DEF PROCcopystructwithstring(dst{}, src{})
      LOCAL temp$
      SWAP temp$, src.member$
      dst{} = src{}
      dst.member$ = temp$
      SWAP temp$, src.member$
      ENDPROC

Richard.
Re: Linked Lists
Post by rtr2 on Sep 27th, 2014, 02:36am

on Sep 26th, 2014, 7:32pm, Matt wrote:
I get the impression there is something glaringly obvious that I'm not seeing.

I wouldn't say "glaringly obvious", although it would have been had you printed out the value of ThisPtr% inside your WHILE loop (it never changes)! You are missing a RETURN:

Code:
      DEF FN_GET_ITEM(RETURN n{}, P%)

Richard.