pointeur de liste

Vous débutez et vous avez besoin d'aide ? N'hésitez pas à poser vos questions
G-Rom
Messages : 3626
Inscription : dim. 10/janv./2010 5:29

Re: pointeur de liste

Message par G-Rom »

je souhaite creer une structure dont l'un des champs serait une liste chainee.

j'ai besoin que cette liste soit globale,

Code : Tout sélectionner

Structure mystruct
  id.i
  name.s
  List lnum.i()
EndStructure
Impossible, ta liste étant dans la structure, elle ne peut être globale & partagée entre toute les variable de type mystruct ( pb ne supporte pas les membres statique ), chaque variable de type mystruct aura donc sa propre version de liste chainée.
la solution la plus simple, déclaré la liste en dehors de la structure et la rendre globale.

Edit :

PB est livré avec le SDK, il y a le header des liste chainée si tu veut jouer avec :

Code : Tout sélectionner

/* === Copyright Notice ===
 *
 *
 *                  PureBasic source code file
 *
 *
 * This file is part of the PureBasic Software package. It may not
 * be distributed or published in source code or binary form without
 * the expressed permission by Fantaisie Software.
 *
 * By contributing modifications or additions to this file, you grant
 * Fantaisie Software the rights to use, modify and distribute your
 * work in the PureBasic package.
 *
 *
 * Copyright (C) 2000-2010 Fantaisie Software - all rights reserved
 *
 */

#ifndef PB_LINKEDLIST_H
#define PB_LINKEDLIST_H

#include <PureLibrary.h>
#include <Object/Object.h>

// for MoveElement()
//
#define PB_List_First  1
#define PB_List_Last   2
#define PB_List_Before 3
#define PB_List_After  4

typedef struct PB_ListHeader
{
  struct PB_ListHeader *Next;
  struct PB_ListHeader *Previous;
} PB_ListHeader;

typedef struct PB_ListPosition
{
  struct PB_ListPosition *Next;
  PB_ListHeader *Element;
} PB_ListPosition;

struct PB_ListObject;

typedef struct PB_List
{
  PB_ListHeader *First;
  PB_ListHeader *Last;
  PB_ListHeader *Current; // Don't move it, as it is used internally by the compiler
  PB_ListHeader **CurrentVariable;
  
  integer NbElements;
  integer Index;
  integer *StructureMap;
  
  // Every List has its private allocator, so we can call ClearAll() for a fast ClearList()
  // Also this way Lists in separate threads work without a lock for allocation
  PB_BlockAlloc *Allocator;
  
  // see PushListPosition.c
  PB_ListPosition *PositionStack;

  struct PB_ListObject *Object;

  integer ElementSize;      // moved here for better alignment on X64
  int ElementType;
  char IsIndexInvalid;
  char IsDynamic;
  char IsDynamicObject;
}
PB_List;


/* In PB, a list is a combo of the real list and the current element, to have a fast access to it.
 */
typedef struct PB_ListObject
{
  PB_List *List;
  PB_ListHeader *CurrentElement;
}
PB_ListObject;


typedef struct
{
  PB_ListHeader Header;
	union
	{
  	int   Long;
		char *String;
	} Type;
} PB_ListElement;

M_PBFUNCTION(PB_List *) PB_NewList(integer ElementSize, PB_ListObject *ListObject, integer *StructureMap, int ElementType);
M_PBFUNCTION(void *)  PB_AddElement(PB_List *List);     // Returns PB_ListHeader * (we use void * to avoid lot of cast when using it in C source (OS X))
M_PBFUNCTION(void *)  PB_CurrentElement(PB_List *List); // Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_FirstElement(PB_List *List);   // Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_InsertElement(PB_List *List);  // Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_LastElement(PB_List *List);    // Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_NextElement(PB_List *List);    // Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_PreviousElement(PB_List *List);// Returns PB_ListHeader *
M_PBFUNCTION(void *)  PB_SelectElement(PB_List *List, integer Index); // Returns PB_ListHeader *
M_PBFUNCTION(void)    PB_ResetList(PB_List *List);
M_PBFUNCTION(void)    PB_ChangeElement(PB_List *List, int NewElement);
M_PBFUNCTION(void)    PB_ChangeCurrentElement(PB_List *List, void *Element);
M_PBFUNCTION(integer) PB_ListSize(PB_List *List);
M_PBFUNCTION(void *)  PB_DeleteElement(PB_List *List);
M_PBFUNCTION(void *)  PB_DeleteElement2(PB_List *List, int Flags);
M_PBFUNCTION(void)    PB_FreeList(PB_List *List);
M_PBFUNCTION(void)    PB_ClearList(PB_List *List);
M_PBFUNCTION(integer) PB_ListIndex(PB_List *List);
M_PBFUNCTION(integer) PB_CopyList(const PB_List *List, PB_List *DestinationList);
M_PBFUNCTION(integer) PB_CopyList2(const PB_List *List, PB_List *DestinationList, int Clear);
M_PBFUNCTION(void)    PB_SwapElements(PB_List *LinkedList, PB_ListHeader *FirstElement, PB_ListHeader *SecondElement);

// define macros for the alloc/free functions to better test, debug and benchmark the optimized allocation
//
// #define M_AllocateElement(List)      ((PB_ListHeader *)M_Alloc(((PB_List *)(List))->ElementSize))
// #define M_FreeElement(List, Element) M_Free((char *)(Element))

#define M_AllocateElement(List)      ((PB_ListHeader *)PB_Object_BlockAlloc(((PB_List *)List)->Allocator))
#define M_FreeElement(List, Element) PB_Object_BlockFree(((PB_List *)List)->Allocator, (void *)(Element))

// define this only if there is a faster free method than calling M_FreeElement() on all items separately
#define M_FreeAllElements(List)      PB_Object_BlockClearAll(((PB_List *)List)->Allocator)

#endif

Avatar de l’utilisateur
djes
Messages : 4252
Inscription : ven. 11/févr./2005 17:34
Localisation : Arras, France

Re: pointeur de liste

Message par djes »

nico a écrit :Je ne comprend pas la solution que tu suggères, elle ne semble pas répondre à la question; tu pourrais poster un code qui illustre complètement ce qui est recherché.
C'est vrai, et ton code, comme les autres est excellent, et en plus G-Rom donne toutes les clés nécessaires pour compléter au mieux la réponse.

Ce que je dis, comme d'autres, est que la réponse est souvent dans la question, et qu'une meilleure formulation du problème suffit parfois à l'éliminer.

Concrètement, il a des graphs et cherche à utiliser un pointeur dans chacun d'entre eux (voir ici http://www.purebasic.fr/english/viewtop ... 67#p521367) pour récupérer des infos globales.

On sent l'approche objet dans sa démarche : tout verrouiller, faire des objets indépendants, mais qui doivent accéder à des paramètres communs. Bref, il se tord l'esprit, alors qu'en procédural, ce genre de problème n'existe pas.

Il suffit de mettre tous les paramètres dans une ou plusieurs listes globales, voire dans un fichier de préférences, et d'y accéder selon les besoins.

Inutile de tout verrouiller, l'espace mémoire du programme est protégé, et l'espace mémoire de chaque objet, si on utilise une liste chaînée ou une map est réduit au minimum, donc, inutile de s'en préoccuper.

Au pire, on peut utiliser un pointeur vers l'élément souhaité, ce qui n'est absolument pas dangereux si l'on se fait des petites procédures adhoc.

Bref, un sujet qui a le mérite de nous faire réfléchir.
G-Rom
Messages : 3626
Inscription : dim. 10/janv./2010 5:29

Re: pointeur de liste

Message par G-Rom »

Je dérive un peu, mais Djes parle de "verrouillage" , cela m'amène a ceci : il est possible en purebasic d'avoir des fonctions à l'intérieur des structures, c'est pas de la poo hein, il faut passé la structure en paramètre de la fonction pour joué avec et initialisé le tout avant utilisation, un exemple ou il est possible de n'appeler qu'une seule fois la procédure, l'adresse de la fonction étant dynamique, il n'est pas possible d'appeler 2x cette procédure, juste un exemple bateau qui démontre cela :

Code : Tout sélectionner

ProcedureC Nothing(*o,a,b)
EndProcedure

PrototypeC.i MaFonction(*object,A,B)

Structure MaStruct
  MaFonction.MaFonction
  result.i
EndStructure


ProcedureC MaFonction(*A.MaStruct, valA, valB)
  *A\result = valA + valB
  *A\MaFonction = @Nothing() ; on redirige vers une fonction qui ne fait rien !
EndProcedure


A.MaStruct : A\MaFonction = @MaFonction()
A\MaFonction(@A,5,10)
Debug A\result
A\MaFonction(@A,5,10)
Debug A\result
C'était juste une petite parenthèse qui n'a rien a voir avec le sujet.
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Re: pointeur de liste

Message par nico »

@Grom
Très intéressant comme info, merci, ça me servira dans le futur.


@djes
Je vois très bien ce que tu veux dire mais avec ce sujet j'ai appris pas mal de truc.
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: pointeur de liste

Message par Ollivier »

Un exemple simple : 50 millions d'éléments, et le besoin d'aller picorer au hasard pour modifier, insérer ou supprimer des éléments.

Il faut se substituer à SelectElement() qui va ramer, d'où un accès étagé. Aussi un accès indirect permet de pointer des listes différentes donc des types de données différents.

Il y a

Code : Tout sélectionner

*x.Struc = AllocateStructure(Struc)
qui comprend AllocateMemory et InitializeStructure.
Avatar de l’utilisateur
Zorro
Messages : 2185
Inscription : mar. 31/mai/2016 9:06

Re: pointeur de liste

Message par Zorro »

Ollivier a écrit :Un exemple simple : 50 millions d'éléments, et le besoin d'aller picorer au hasard pour modifier, insérer ou supprimer des éléments.

Il faut se substituer à SelectElement() qui va ramer, d'où un accès étagé. Aussi un accès indirect permet de pointer des listes différentes donc des types de données différents.

Il y a

Code : Tout sélectionner

*x.Struc = AllocateStructure(Struc)
qui comprend AllocateMemory et InitializeStructure.
ben non !! :roll:

"Un exemple simple : 50 millions d'éléments" n'est pas un exemple simple !
je vais etre fidele a ma devise (voir signature )

si t'a 50 millions d'elements, c'est pas les listes qu'il faut utiliser !!!
mais les Map par exemple qui sont fait pour ça puisque indexé par leur nom

ou bien la RAM (peek,poke) , ou un disque dur SSD (base de données) ... bref, il n'y a pas que les lists faut pas déconner non plus
chacun sait ici qu'elles ont un acces séquentiel et qu'elles ne sont pas faite pour gérer des millions d'elements.... :roll:

ce serai comme remplir une image de 45000x45000 points par points en utilisant Plot() ....

un exemple simple, qu'il dit :lol:
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: pointeur de liste

Message par Ollivier »

Ben reste fidèle à ta devise, en évitant de zapper

Code : Tout sélectionner

Define *X.Struc = AllocateStructure(Struc)
qui simplifie

Code : Tout sélectionner

Define *X.Struc = AllocateMemory(SizeOf(Struc) )
InitializeStructure(*X, Struc)
et qui équivaut à

Code : Tout sélectionner

Define X.Struc
mais en permettant plus de souplesse en mémoire (Je crois que c'est FreeStructure() si ça existe pour effacer correctement), et en évitant des copies mémoire non nécessaires pour l'utiliser comme un global.
Répondre