[LinkedList] ExtractElement

[grabiller]

Hi,

I would be great to have a 'ExtractElement' for LinkedList.

It would return the pointer to the memory allocated for an element, and remove its reference from the list but without deallocating its memory.

We would have to free the element memory ourself of course.

This would allow very fast FIFO/LIFO etc.. implementation. Because currently, we have to:
(granted we have a procedure with a pointer to a structure of element type as argument)
1) Go the the first/last element
2) Copy the element structure data to a provided structure pointer.
3) Remove the element from the list.

This is not very efficient, especially if our structure contains complicated sub-elements to copy.

With ExtractElement we could just:
1) Extract the element at position p & Return it

Code: Select all

; Lets say we have this structure:
Structure MyData
  x.f
  y.f
  z.f
EndStructure

Global NewList MyList.MyData()

; Currently we have to do:
Procedure PopElement( *p.MyData )

  Protected *t.MyData = FirstElement(MyList())

  *p\x = *t\x
  *p\y = *t\y
  *p\z = *t\z

  DeleteElement(MyList(),1)

EndProcedure

; With ExtractElement we could do:
Procedure.i PopElement()

  ; return element at position 0 and remove its reference from the list
  ProcedureReturn ExtractElement(MyList(),0)

EndProcedure

[grabiller]

Just to add:

With 'ExtractElement', it would also be much more efficient in multi-threaded contexts as we would not have to lock the list during the entire copy operation, but just at extraction time.

[STARGÅTE]

We would have to free the element memory ourself of course.

how?

PopElement() returns the pointer to the element, but the linked list can not free the space!
And you can not free it with FreeMemory() because the pointer not allocate with AllocateMemory().
Also the Element can have Strings, Lists, and Maps itself, so you need always a ClearStructure().
Also, if you have free the space, the linkedlist don't know it, so the memory is still blocked.

Note: linked list allocate a block of space for multiple elements.

If you write a FIFO, write it self, and not with linked list, of only with a Pointer-List:

Code: Select all

Global NewList *Element()

Procedure PushElement(*Address)
	AddElement(*Element())
	*Element() = *Address
EndProcedure

Procedure PopElement()
	Protected *Address.Integer = LastElement(*Element())
	DeleteElement(*Element())
	ProcedureReturn *Address\i
EndProcedure


Structure MyData
  x.f
  y.f
  z.f
EndStructure

A.MyData\x = 123
B.MyData\x = 456

PushElement(B)
PushElement(A)
PopElement()
*C.MyData = PopElement()
Debug *C\x