Newsgroup: it.hobby.elettronica.digitale
Titolo: Implementazione liste in BeRTOS (Francesco?)

Stavo guardando l'implementazione delle liste nel sistema operativo
BeRTOS di Francesco Sacchi. Immagino sia tutto in list.h.
Non ho capito a cosa puntano i puntatori *succ e *pred della struttura
Node. Dovrebbero puntare ad un'altra struttura Node, ma, in alcuni
casi, viene usato un cast alla struttura dei dati.
Per esempio, in timer.c, si legge:
  node = (Timer *)node->link.succ;
L'unica spiegazione che mi sono dato è che nella struttura Timer il
primo field è proprio la struttura Node e quindi il puntatore a Timer
e a Node coincidono.
  typedef struct Timer
  {
    Node link;
    ticks_t _delay;
    ticks_t tick;
    Event expire;
    DB(uint16_t magic;)
  } Timer;
Immagino che, spostando il campo link di Timer in altra posizione,
l'implementazione della lista non funziona.
E' giusto il mio ragionamento?

 l'implementazione della lista non funziona.
Credo anch'io...

 E' giusto il mio ragionamento?
Esattamente, � proprio questo il trucco.
Siccome il campo link � il primo, un suo puntatore � anche un puntatore 
alla struttura.
Volendo � possibile mettere il nodo in qualunque posizione e usando 
delle macro (in altri posti le usiamo, cerca containerof()in macros.h) 
si pu� "upcastare" dal contenuto al contenitore.
Questo per� richiede di fare operazioni in pi�, quindi quando possibile 
usiamo questo approccio che � pi� veloce.
-- 
  _|/ Francesco Sacchi - Develer S.r.l., R&D dept.
   |\ 
http://www.develer.com/
 - 
http://www.bertos.org/

 usiamo questo approccio che è più veloce.
Chiaramente...

 Non capisco il vantaggio.
Se per lista classica ti riferisci all'implementazione in cui i nodi 
hanno un puntatore ai dati, ci sono diversi vantaggi:
- meno spazio occupato: � richiesto un puntatore in meno e su 
strutture di pochi byte, l'overhead di questo puntatore � pesante. 
Sulla struttura timer di sopra fa risparmiare il 20% di memoria per 
ogni nodo.
- velocit�: se il nodo � anche il payload c'� una indirezione in meno. 
Pu� sembrare poco, ma siccome le liste vengono usate in situazioni 
critiche (sotto IRQ, nel kernel, etc...) ogni ciclo � prezioso.
- Se nodo e dati sono separati vanno allocati separatamente, 
aumentando il rischio di bug e memory leak. In questo modo invece � 
possibile in un colpo solo allocare tutto quello che serve (anche 
perch� la struttura timer non serve a nulla senza nodo, quindi perch� 
dare la possibilit� di fare una cosa sbagliata?).
E per quanto riguarda la "sporcizia" questo trucco non � sporco, o per 
lo meno lo � tanto quanto l'implementazione classica.
Anche in essa infatti hai un puntatore ai dati che per forza di cose 
deve essere void *, quindi ti ritrovi tutte le volte a castarlo al 
tipo che hai linkato.
In effetti il cast che hai trovato tu � poco chiaro e risale a 
parecchi anni fa.
Adesso usiamo sempre la macro containerof() che aiuta la leggibilit� e 
non aggiunge overhead quando l'elemento � il primo (la sottrazione con 
0 viene ottimizzata via a compile time).
Secondo me quindi la lista classica � di fatto pi� complicata e pi� 
lenta rispetto a questa implementazione (che per inciso non ho scritto 
io, � stata fatta diversi anni fa da un mio collega, Bernie Innocenti, 
che a sua volta si � ispirato a come erano implementate nell'Amiga).
In realt� la lista classica ha una feature in pi�: essendo nodi e dati 
separati � teoricamente possibile inserire gli stessi dati in pi� 
liste: basta allocare pi� nodi che puntato agli stessi dati.
Devo dire per� che in tanti anni, sinceramente non ho mai avuto 
bisogno di questa funzionalit�.


 dare la possibilità di fare una cosa sbagliata?).
Questi vantaggi ci sono anche nella classica implementazione, penso.

 In questo modo non devi fare mai dei cast.
Questa soluzione � sporca quanto, se non pi� della nostra.
In questo modo i cast li hai nelle funzioni che gestiscono le liste, 
perch�  i puntatori sono specifici alla tua struttura MyList.
E in questo caso inoltre devi *per forza* dichiarare i puntatori ai nodi 
nella posizione e nell'ordine che hai stabilito, senza possibilit� di 
scampo.
-- 
  _|/ Francesco Sacchi - Develer S.r.l., R&D dept.
   |\ 
http://www.develer.com/
 - 
http://www.bertos.org/

 scampo.
Probabilmente tu ti riferisci ad una implementazione generica di una
linked list (indipendente dal tipo dei dati), mentre io stavo
considerando
l'implementazione di una particolare lista, conoscendone il tipo.
In altre parole la tua implementazione può essere usata più volte nel
tuo programma con più liste anche di diverso tipo; io dovrei
implementare
più volte la lista per ogni tipo.
Per la cronaca, hai visto questa implementazione?
http://sglib.sourceforge.net/

 
http://sglib.sourceforge.net/
Non la conoscevo, gli do un'occhiata, grazie!
