00001 00002 /*************************************************************************/ 00003 /* Doubly Linked DoublyLinkedList Management */ 00004 /* DoublyLinkedList.h */ 00005 /* */ 00006 /* Authors : Daniel Lacroix (Public Domain) */ 00007 /* Software by Daniel Lacroix 15/09/2006. */ 00008 /* Modification : Jean-Baptiste Silvy for compatibility with Scilab */ 00009 /* */ 00010 /*************************************************************************/ 00011 00012 00013 #ifndef _DOUBLY_LINKED_LIST_ 00014 #define _DOUBLY_LINKED_LIST_ 00015 00016 #include "BOOL.h" 00017 00018 /* pour les DoublyLinkedListes chainees */ 00019 typedef struct _DlDoublyLinkedList DoublyLinkedList; 00020 00021 struct _DlDoublyLinkedList { 00022 void * data; 00023 DoublyLinkedList *next; 00024 DoublyLinkedList *prev; 00025 }; 00026 00027 /* Cree une nouvelle DoublyLinkedListe chainee. */ 00028 /* DoublyLinkedList *List_new() */ 00029 #define DoublyLinkedList_new() NULL 00030 00031 /* Rajoute en tete de la DoublyLinkedListe pDoublyLinkedList l'element data. */ 00032 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00033 DoublyLinkedList *List_prepend(DoublyLinkedList *pDoublyLinkedList, void * data); 00034 00035 /* Rajoute en queue de la DoublyLinkedListe pDoublyLinkedList l'element data. */ 00036 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00037 DoublyLinkedList *List_append(DoublyLinkedList *pDoublyLinkedList, void * data); 00038 00039 /* Rajoute un element apres l'element before. Si l'element before */ 00040 /* n'est pas trouve alors le nouvel element sera rajoute a la fin. */ 00041 /* Renvoie ne nouveau point d'entree de la DoublyLinkedListe pDoublyLinkedList. */ 00042 DoublyLinkedList *List_insert_after_item(DoublyLinkedList *pDoublyLinkedList, void * before, void * data); 00043 00044 /* Concatene la DoublyLinkedListe p2 a la DoublyLinkedListe p1 (p1 devant, p2 derriere) */ 00045 /* Renvoie la nouvelle DoublyLinkedListe cree. p1 et p2 sont consideres comme detruites */ 00046 DoublyLinkedList *List_concat(DoublyLinkedList *p1, DoublyLinkedList *p2); 00047 00048 /* Empile data a la fin de la DoublyLinkedListe pDoublyLinkedList. */ 00049 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe pDoublyLinkedList. */ 00050 /* void List_push(DoublyLinkedList *pDoublyLinkedList, void * data); */ 00051 #define List_push(pDoublyLinkedList,data) List_append(pDoublyLinkedList,data) 00052 00053 /* Depile le dernier element de la DoublyLinkedListe pDoublyLinkedList. */ 00054 /* Le dernier est place dans data et est sorti de la DoublyLinkedListe */ 00055 /* List_pop renvoie le nouveau point d'entree de la DoublyLinkedListe pDoublyLinkedList. */ 00056 DoublyLinkedList *List_pop(DoublyLinkedList *pDoublyLinkedList, void ** data); 00057 00058 /* Renvoie une copie de la DoublyLinkedListe pDoublyLinkedList. Les pointeurs data sont copies */ 00059 /* pas le contenu pointe. Il s'agit d'une DoublyLinkedListe avec des "alias" sur */ 00060 /* les elements de la premiere DoublyLinkedListe. */ 00061 DoublyLinkedList *List_copy(DoublyLinkedList *pDoublyLinkedList); 00062 00063 /* Renvoie une copie de la DoublyLinkedListe pDoublyLinkedList. Les donnees contenu dans la DoublyLinkedListe sont copies */ 00064 /* avec la fonction copy_func. Elle recoit le pointeur de l'element d'origine et doit */ 00065 /* renvoyer un pointeur vers la copie. */ 00066 DoublyLinkedList *List_copy_full(DoublyLinkedList *pDoublyLinkedList, void * (* copy_func)(void * data)); 00067 00068 /* Libere la DoublyLinkedListe (pas les elements) */ 00069 void List_free(DoublyLinkedList *pDoublyLinkedList); 00070 00071 /* Libere la DoublyLinkedListe et appele la procedure free_func pour chaque elements */ 00072 void List_free_full(DoublyLinkedList *pDoublyLinkedList, void (* free_func)(void * data)); 00073 00074 /* Libere la DoublyLinkedListe et appele la procedure free (du C) pour chaque elements */ 00075 void List_free_full_simple(DoublyLinkedList *pDoublyLinkedList); 00076 00077 /* Libere un element de la DoublyLinkedListe (pas ce que l'element pointe si c'est un pointeur) */ 00078 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00079 DoublyLinkedList *List_free_item(DoublyLinkedList *pDoublyLinkedList, void * data); 00080 00081 /* Libere un element de la DoublyLinkedListe (pas ce que l'element pointe si c'est un pointeur) */ 00082 /* Si l'element a ete libere alors done == TRUE sinon FALSE. */ 00083 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00084 DoublyLinkedList *List_free_item_with_check(DoublyLinkedList *pDoublyLinkedList, void * data, BOOL *done); 00085 00086 /* Libere un element de la DoublyLinkedListe pDoublyLinkedList (pas la donnee pointe par data) */ 00087 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00088 DoublyLinkedList *List_free_chunk(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pToFree); 00089 00090 /* Renvoi le nombre d'element contenue dans la DoublyLinkedListe */ 00091 /* Cette operation est realisee par comptage. */ 00092 int List_nb_item(DoublyLinkedList *pDoublyLinkedList); 00093 00094 /* Renvoie l'element a la position item_nb dans la DoublyLinkedListe pDoublyLinkedList */ 00095 /* Si l'element item_nb n'exite pas, la fonction renvoi NULL. */ 00096 /* item_nb commence a 1. */ 00097 void * List_item(DoublyLinkedList *pDoublyLinkedList, int item_nb); 00098 00099 /* Renvoie la donnee correspondant a l'element de DoublyLinkedListe pDoublyLinkedList */ 00100 /* void * List_data(DoublyLinkedList *pDoublyLinkedList); */ 00101 #define List_data(pDoublyLinkedList) ((pDoublyLinkedList)?(pDoublyLinkedList)->data:NULL) 00102 00103 /* Renvoie l'element a la derniere position de la DoublyLinkedListe pDoublyLinkedList. */ 00104 /* Renvoie NULL si la DoublyLinkedListe est vide. */ 00105 /* DoublyLinkedList *List_last(DoublyLinkedList *pDoublyLinkedList); */ 00106 #define List_last(pDoublyLinkedList) ((pDoublyLinkedList)?(pDoublyLinkedList)->prev:NULL) 00107 00108 /* Renvoie TRUE si la DoublyLinkedListe pDoublyLinkedList est vide. Renvoie FALSE sinon. */ 00109 /* BOOL List_is_empty(DoublyLinkedList *pDoublyLinkedList); */ 00110 #define List_is_empty(pDoublyLinkedList) (pDoublyLinkedList == NULL) 00111 00112 /* Renvoie TRUE si pCurrentDoublyLinkedList est au dela du dernier */ 00113 /* element de la DoublyLinkedListe pDoublyLinkedList. Sinon renvoie FALSE */ 00114 /* BOOL List_is_end(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00115 #define List_is_end(pDoublyLinkedList,pCurrentDoublyLinkedList) (pCurrentDoublyLinkedList == NULL) 00116 00117 /* Renvoie TRUE si pCurrentDoublyLinkedList est le premier */ 00118 /* element de la DoublyLinkedListe pDoublyLinkedList. Sinon renvoie FALSE */ 00119 /* BOOL List_is_first(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList);*/ 00120 #define List_is_first(pDoublyLinkedList,pCurrentDoublyLinkedList) ((pCurrentDoublyLinkedList) == pDoublyLinkedList) 00121 00122 /* Renvoie TRUE si pCurrentDoublyLinkedList est le dernier */ 00123 /* element de la DoublyLinkedListe pDoublyLinkedList. Sinon renvoie FALSE */ 00124 /* BOOL List_is_last(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00125 #define List_is_last(pDoublyLinkedList,pCurrentDoublyLinkedList)\ 00126 ((pCurrentDoublyLinkedList != NULL) && (pDoublyLinkedList != NULL) && ((pCurrentDoublyLinkedList)->next == pDoublyLinkedList)) 00127 00128 /* Renvoie l'element apres pCurrentDoublyLinkedList dans la DoublyLinkedListe pDoublyLinkedList. */ 00129 /* Si on arrive au dela de la fin de la DoublyLinkedListe pDoublyLinkedList, renvoie NULL. */ 00130 /* DoublyLinkedList *List_next(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00131 #define List_next(pDoublyLinkedList,pCurrentDoublyLinkedList)\ 00132 (((pCurrentDoublyLinkedList)&&((pCurrentDoublyLinkedList)->next!=pDoublyLinkedList))?(pCurrentDoublyLinkedList)->next:NULL) 00133 00134 /* Renvoie l'element avant pCurrentDoublyLinkedList dans la DoublyLinkedListe pDoublyLinkedList. */ 00135 /* Si l'element precedent est avant le premier element, renvoie NULL. */ 00136 /* DoublyLinkedList *List_prev(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00137 #define List_prev(pDoublyLinkedList,pCurrentDoublyLinkedList)\ 00138 (((pCurrentDoublyLinkedList)&&((pCurrentDoublyLinkedList)!=pDoublyLinkedList))?(pCurrentDoublyLinkedList)->prev:NULL) 00139 00140 /* Deplace pCurrentDoublyLinkedList sur le prochain element de la DoublyLinkedListe pDoublyLinkedList */ 00141 /* Si on arrive a la fin pCurrentDoublyLinkedList devient NULL. */ 00142 /* void List_move_next(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00143 #define List_move_next(pDoublyLinkedList,pCurrentDoublyLinkedList) (pCurrentDoublyLinkedList = List_next(pDoublyLinkedList,pCurrentDoublyLinkedList)) 00144 00145 /* Deplace pCurrentDoublyLinkedList sur l'element precedent de la DoublyLinkedListe pDoublyLinkedList */ 00146 /* Si on arrive avant le premier element alors pCurrentDoublyLinkedList devient NULL. */ 00147 /* void List_move_prev(DoublyLinkedList *pDoublyLinkedList, DoublyLinkedList *pCurrentDoublyLinkedList); */ 00148 #define List_move_prev(pDoublyLinkedList,pCurrentDoublyLinkedList) (pCurrentDoublyLinkedList = List_prev(pDoublyLinkedList,pCurrentDoublyLinkedList)) 00149 00150 /* Trie la DoublyLinkedListe pDoublyLinkedList. La fonction cmp_func est utilise pour */ 00151 /* determine l'ordre. Elle doit renvoyer 0 si p1 pointe sur un */ 00152 /* element equivalent a p2. < 0 si p1 est inferieur a p2, >0 */ 00153 /* si p2 est superieur a p1. */ 00154 /* Renvoie la DoublyLinkedListe triee. */ 00155 DoublyLinkedList *List_sort(DoublyLinkedList *pDoublyLinkedList,int (* cmp_func)(void * p1, void * p2)); 00156 00157 /* Insere l'element data dans la DoublyLinkedListe pDoublyLinkedList de maniere trie */ 00158 /* d'apres la fonction cmp_func. Elle doit renvoyer 0 si p1 */ 00159 /* pointe sur un element equivalent a p2. < 0 si p1 est */ 00160 /* inferieur a p2, >0 si p2 est superieur a p1. */ 00161 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe. */ 00162 DoublyLinkedList *List_insert_sorted(DoublyLinkedList *pDoublyLinkedList,int (* cmp_func)(void * p1, void * p2), 00163 void * data); 00164 00165 /* Inverse l'ordre des elements de la DoublyLinkedListe pDoublyLinkedList */ 00166 /* Renvoie le nouveau point d'entree de la DoublyLinkedListe */ 00167 /* Cette operation peut ce faire pendant que l'on parcours */ 00168 /* (pas au sens multithreade du terme) */ 00169 /* la DoublyLinkedListe mais bien evidemment, le sens s'inverse. */ 00170 DoublyLinkedList *List_invert(DoublyLinkedList *pDoublyLinkedList); 00171 00172 /* Recherche l'element de DoublyLinkedListe qui contient la premiere donnee data */ 00173 /* Renvoie l'element de DoublyLinkedListe si trouve, NULL sinon. */ 00174 DoublyLinkedList *List_find(DoublyLinkedList *pDoublyLinkedList, void * data); 00175 00176 /* Recherche l'element de DoublyLinkedListe qui contient la premiere donnee pour laquelle la */ 00177 /* fonction find_func renvoie TRUE. La fonction find_func prend en parametre le */ 00178 /* pointeur contenu dans la DoublyLinkedListe et le pointeur your_data qui est donne par */ 00179 /* l'utilisateur (pour y stocker ce dont il a besoin pour la comparaison). */ 00180 /* Renvoie l'element de DoublyLinkedListe si trouve, NULL sinon. */ 00181 DoublyLinkedList *List_find_full(DoublyLinkedList *pDoublyLinkedList, void * your_data, BOOL (* find_func)(void * data, void * your_data)); 00182 00183 #endif /* _DOUBLY_LINKED_LIST_ */ 00184
1.5.5