Discussion :

[boboss123]

Bonjour,

Je fais un programme sur un µControlleur donc je suis assez limité en RAM et en puissance de calcul.

J'ai 2 listes (list1, list2) à créer dans une zone mémoire de taille fixe.
La taille de chaque élément pour une liste donnée est fixe mais les éléments de list1 n'ont pas la même taille que ceux de list2 (7 octets et 11 octets).

La list1 fait référence à des éléments qui sont dans la list2. Je dois régulièrement ajouter/supprimer/modifier des éléments (je n'ai pas besoin que la gestion de l'affichage de tous mes éléments soit rapide car je ne le ferais pas souvent) :Il me semble donc que pour facilement la recherche d'éléments, il faut que je range mes liste par ordre croissant (en fonction de certains champs).

Quelle méthode me conseillez-vous de faire pour gérer ces deux listes (il faut que l'ajout/suppression/recherche d'élément soit le plus rapide possible) ? comment gérer ma zone mémoire (c'est un tableau static d'unsigned char) ?

merci d'avance,

[matafan]

C'est beaucoup trop vague pour qu'on puisse t'aider. En quoi consiste l'insertion d'élément ? La recherche d'élément ?

[boboss123]

Bonjour,

C'est pour faire une table d'adressage MAC. Je dois affecter chaque adresse MAC dans un groupe en fonction de certains paramètres. Et je dois supprimer un groupe s'il ne contient plus d'adresse MAC.
Chaque adresse MAC à un timeout : une fois le timeout écoulé, je la supprime de la liste (le timeout peut être remis à jour).
=> c'est pour faire du filtrage (c'est très spécifique)

=> je pensais partir sur une liste doublement chainée et reclasser ma liste a chaque ajout d'une nouvelle entrée (je ne sais pas si c'est la meilleur méthode)

[saad.hessane]

En fait tout dépend de ce que tu veux entendre par recherche. Les listes sont adaptés pour faire des FIFO ou LIFO. Donc insertion et suppression en tête ou en queue très rapide. Mais pour la recherche c'est pas très top. Si le nombre de tes données est assez significatif tu pourrais te tourner vers une structure en arbre (b-tree) ou table de hashage.

[boboss123]

merci mais ça me semble un peu lourd pour ce que je veux faire : j'aurais moins de 1000 éléments à trier.

Ce que je veux faire c'est simplement ajouter/supprimer des éléments (la clef sera l'adresse MAC) dans un groupe (la clef sera une adresse IP) et supprimer/créer des groupes.
Chaque élément à une propriété que je dois mettre à jour régulièrement => c'est l'action qui sera faite le plus souvent.
=> je cherche à faire celà le plus rapidement possible

----------------------------------------
Chaque groupe a une propriété "TimeOut"
Chaque adresse MAC a une propriété "Count"

1- à un instant t, j'initialise "TimeOut" pour un groupe donné et "Count" pour toutes les adresse MAC associées (un groupe aura au maximum 64 adresses MAC associées)
=> si le groupe n'existe pas, je le crée (pas d'adresses MAC associées) et j'initialise "TimeOut"

2- régulièrement je dois mettre le "TimeOut" à jours de tous mes groupes
=> une fois un des "TimeOut" terminé, je dois récupérer la valeur de "Count" de toutes les adresses MAC associées. S'il n'y a pas d'adresse MAC associé au groupe, je dois le supprimer.

3- pendant ce temps, je peux avoir des demandes d'ajout/suppression d'un élément "adresse MAC" à un groupe ou de la mise à jour de la valeurs "Count"