Juste une petite question, car je n'ai aucune idée de comment il faut s'y prendre : comment déclare-t-on, joliment, une FIFO circulaire en C ?
Mon idée j'en ai une toute petite, est de créer un tableau... Ou de créer une liste chainée...
Quelqu'un peut-il me sauver ?
Merci d'avance.
Forum Programmation.c Encore moi, je rame...
29
juil.
2004
# Commentaire supprimé
Posté par Anonyme . Évalué à 2.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: C'est quoi une "fifo circulaire" ?
Posté par Pierre Jacquier . Évalué à 1.
Ca fait de la circularité...
Merci beaucoup ...
# c'est simple
Posté par vincent LECOQ (site web personnel) . Évalué à 1.
ca marche tres bien, voire meme une liste doublement chainee circulaire
sinon le plus simple avec un tableau est de bien gerer tes indexs de boucles avec i%taille de ton tableau
[^] # Re: c'est simple
Posté par Pierre Jacquier . Évalué à 1.
[^] # Re: c'est simple
Posté par ham . Évalué à 1.
ensuite faire une fifo circulaire c'est surtout avec des tableau et des index bien géré:
c'est interessant d'avoir une strucutre qui boucle car on a pas a deplacer les éléments
0 1 2 3 4 X X
ajout -> 0 1 2 3 4 5 X
remove -> X 1 2 3 4 5 X
ajout -> X 1 2 3 4 5 6
ajout -> 7 1 2 3 4 5 6 -> fifo plein
remove -> 7 X 2 3 4 5 6 -> ok
Si tu fait avec des pointeurs du coup tu n'a plus besoin d'avoir de fifo circulaire, puisque tu peut juste mettre un element de debut et un de fin.
pour la form rendre une liste chainé circulaire (qui se mord la queue):
struct list_item_s {
struct list_item_s *next;
void * data
};
struct list_s {
struct list_item_s * head;
struct list_item_s * tail;
struct list_item_s * pool; // Cf le Offtopic
int pool_size;
unsigned int size; // pour la forme
}
et pour rendre circulaire la liste:
A->B->C->D->A
la structure list est la pour marquer un element comme le debut et pas partir dans des boucles infini.
L'avantage c'est si tu ne considere que le prochain element dans ton traitement, la gestion devient tres simple: tu prend le current->next.
par contre tu as toujours besoin de la structure de liste pour l'insertion des éléments dans l'ordre.
Offtopic, pour m'entrainer:
ensuite les listes chainée sont pénalisantes niveau allocation mémoire, ou alors il faut les allouer en bloc et en ajoutant un struct list_item_s * pool_start dqns la structure de liste;
alloc_pool() {
ptr = malloc(constante*sizeof(struct list_s));
// nettoyage
memset(ptr,0,constante*sizeof(struct list_s));
// mettre les pointeurs les un q lq suite des autres
for (i=0; i <constante-1;i++) {
temp_item =((struct...)ptr)[i];
temp_item->next=((struct...)ptr)[i+1];
}
//comme ca en mémoire si constante==5
A->B->C->D->E->
list->pool=((struct...)ptr);
list->pool_size=constante;
}
add_data(void * data) {
//add data to the end of the list
if (list->head == NULL) {
alloc_pool();
list->head = list->pool;
list->pool = list->pool->next;
list->head->next=list->head;
list->tail=list->head;
list->size=1;
return;
}
// go to the end
tail = list->tail;
if (list->pool == NULL) {
//pool exhausted
alloc_pool()
}
// list->pool != NULL
tail->next = list->pool; // on rajoute apres le dernier element
list->pool = list->pool->next;//on change le pool,
tail->next->next=list->head;//le nouveau dernier pointe vers la tete
list->tail=list->tail->next;// on update le tail
list->size=list->size+1;
return;
}
remove_data() {
//enleve la tete de liste
if list->head == NULL return NULL;
return_ptr = list->data;
element=list->head;.
if (list->head == list->tail) {
list->head=NULL;
list->tail==NULL;
list->size=0;
} else {
// update des pointeurs
list->head=list->head->next;
list->tail->next = list->head;
list->size = list->size -1;
}
// on manage le pool
// des fois il fqut liberer de la memoire
if (list->pool_size=constante) {
// dans pool: un pool entier
free (list->pool);
list->pool=NULL.
list->pool_size =0;
}
// on remet l'element enlever dqns le pool
element->next = list->pool;
list->pool_size= list->pool_size+1;
list->pool=element;
return returnn_ptr;
}
Et pour faire overkill, constante peut varier en fonction des stats, mais il fqut mettre des octets de gqrde avant et aprés le pool, et vérifer ces octets pour la libérqtion
# Cool, j'ai compris
Posté par Pierre Jacquier . Évalué à 1.
J'ai bien compris comment m'y prendre.
A plus tard pour de nouvelles aventures !!!
Jacouille la fripouille
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.