Re: Faulty Segmentation in a Circular Linked List

Just starting out? Need help? Post your questions and find answers here.
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: Faulty Segmentation in a Circular Linked List

Post by Olli »

For the publicity producer who went to Pluto, as quickly as it appeared, here are 2 macros to have a circular list. And the so-called segmentation fault does not exist in pureBasic!

Code: Select all

Macro NextCElement(alpha)

If Not NextElement(alpha)
   FirstElement(alpha)
EndIf

EndMacro

Macro PreviousCElement(alpha)

If Not PreviousElement(alpha)
   LastElement(alpha)
EndIf

EndMacro
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Faulty Segmentation in a Circular Linked List

Post by idle »

What's the question
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: Faulty Segmentation in a Circular Linked List

Post by Olli »

This was a disguised question to promote another programming forum. Something about circular listings... Moderators have to tear their hair out sometimes... Plus, the comment option for posts seemed broken...
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Faulty Segmentation in a Circular Linked List

Post by idle »

It's perhaps not obvious but due to multiple cores a circular list or array is no longer thread safe in the context of a single producer and consumer. When we only had one core it was easy to do lock free but now you need to use a synchronization mechanism. This can be done with mfence in asm or synchronization instrinsics in c. I am a bot. Nanu nanu
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Faulty Segmentation in a Circular Linked List

Post by Little John »

idle wrote:I am a bot. Nanu nanu
I like the idle bots best. ;-)
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: Faulty Segmentation in a Circular Linked List

Post by Olli »

<< The main objective of the mutex functions is thread synchronization. >>
source
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Faulty Segmentation in a Circular Linked List

Post by idle »

Mutex is blocking and necessary for multiple producer consumer though in the single producer consumer lock free can only be achieved by memory fences problem is due to out of order speculative execution. Great when you can get cycles for free but it's hard to do
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: Faulty Segmentation in a Circular Linked List

Post by Olli »

Xfence is blocking too... :mrgreen:
User avatar
mk-soft
Always Here
Always Here
Posts: 5337
Joined: Fri May 12, 2006 6:51 pm
Location: Germany

Re: Faulty Segmentation in a Circular Linked List

Post by mk-soft »

I don't understand what this is all about, but

Purebasic for Window, the PB mutex is internally a critical section and is only for a process with its own threads.

Event, mutex and semaphore objects can also be used in a single-process application, but critical section objects provide a slightly faster, more efficient mechanism for synchronising mutual exclusion
My Projects ThreadToGUI / OOP-BaseClass / EventDesigner V3
PB v3.30 / v5.75 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace / OneDrive
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Faulty Segmentation in a Circular Linked List

Post by idle »

From pb perspective a mutex is the right blocking mechanism but it is locking. The memory fence is technically lock free and only stops out of order execution which in the context a single producer consumer circular list or buffer is sufficient to ensure that the order of operations between the memory fence runs in order. It's specifically used to address the aba thread problem without locking. https://en.m.wikipedia.org/wiki/ABA_problem
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: Faulty Segmentation in a Circular Linked List

Post by Olli »

idle wrote:The memory fence [...] only stops [...]
Not only : a CPU time is required to execute this. Pipe-line is temporarly shut down, and several statements which used 0 or 1 cycles will use 10 cycles or more.

It is technically interesting to know or discover this. But there is no better way between the one and the other.
  • xFence = spatial stop + time required and wasted
  • mutex = time stop + artificial time used (can let other tasks execute themselves) wasted or not wasted : depends of the coder decides (added to keep arguments balance between the two technics)
The locking in a mutex is limited to what we want, event that I am not sure that xFence allows.

Plus, the initial author of the question gave a C code fully rotten : he just insured himself the 'linked list' keyword were common between here and his source code, and gave a second message without link to a coding private school... It is the typical way of an ad bot !

The magic linked list equ :

Code: Select all

Structure pif
a.a[0]
EndStructure

*ll.pif = allocatememory(1000)

procedure insert(*this.pif, i, pif)
 with *this
  for a = 1000 to i+1 step -1
   \a[a] = \a[a - 1]
  next
  \a[i] = pif
 endwith
endprocedure
Original version

Code: Select all

void insertt(int val, int pos) {
  if (pos < 0) return;
  if (pos > sz + 1) return;
  sz += 1;
  for (int i = sz; i > pos; i--)
  a[i] = a[i - 1];
  a[pos] = val;
}
This is not a linked list as it exists in pureBasic. It is just an array...

@Rishabh welcome in pureBasic, give a hello in the offTopic section. There will be more success to present yourself like that, instead of polluting the coding section...
Post Reply