Projet Informatique Théorique 2016
Instructions et Documentation
table.c
1 /*
2  * Ce fichier fait partie d'un projet de programmation donné en Licence 3
3  * à l'Université de Bordeaux.
4  *
5  * Copyright (C) 2014 Adrien Boussicault
6  *
7  * This Library is free software: you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation, either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This Library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this Library. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "table.h"
22 #include "outils.h"
23 #include "fifo.h"
24 #include "avl.h"
25 
26 #include <assert.h>
27 
28 #include <search.h>
29 #include <stdlib.h>
30 
31 typedef struct Table_association {
32  void (*supprimer_cle)(intptr_t cle);
33  intptr_t (*copier_cle)(const intptr_t cle);
34  int (*comparer_cle)(const intptr_t cle1, const intptr_t cle2);
35  intptr_t cle;
36  intptr_t valeur;
38 
39 struct Table {
40  int (*comparer_cle)( const intptr_t cle1, const intptr_t cle2 );
41  intptr_t (*copier_cle)( const intptr_t cle );
42  void (*supprimer_cle)(intptr_t cle);
43  struct avl_table * root;
44 };
45 
46 
47 intptr_t get_cle( Table_iterateur it ){
48  const Table_association * asso = ( const Table_association * ) avl_t_cur( &it );
49  return (const intptr_t) asso->cle;
50 }
51 
52 intptr_t get_valeur( Table_iterateur it ){
53  Table_association * asso = ( Table_association * ) avl_t_cur( &it );
54  return asso->valeur;
55 }
56 
57 Table_association * creer_table_association(
58  const Table* table, const intptr_t cle, intptr_t valeur
59 ){
60  Table_association * res = xmalloc(
61  sizeof( Table_association )
62  );
63  if( table->copier_cle && cle ){
64  res->cle = table->copier_cle( cle );
65  }else{
66  res->cle = cle;
67  }
68  res->valeur = valeur;
69  res->supprimer_cle = table->supprimer_cle;
70  res->copier_cle = table->copier_cle;
71  res->comparer_cle = table->comparer_cle;
72  return res;
73 }
74 
75 Table_association * copier_table_association( Table_association * asso ){
76  Table_association * res = xmalloc(
77  sizeof( Table_association )
78  );
79  *res = *asso;
80  if( asso->copier_cle && asso->cle ){
81  res->cle = asso->copier_cle( asso->cle );
82  }
83  return res;
84 }
85 
86 int compare_table_association( const void * pa1, const void * pb1, void* param ){
87  Table_association * pa = (Table_association *) pa1;
88  Table_association * pb = (Table_association *) pb1;
89  if( pa->comparer_cle ){
90  int r = pa->comparer_cle( pa->cle, pb->cle );
91  return r;
92  }else{
93  if( pa->cle < pb->cle )
94  return -1;
95  if( pa->cle > pb->cle )
96  return 1;
97  return 0;
98  }
99 }
100 
101 
102 void supprimer_table_association2( void* asso_tmp, void* data ){
103  Table_association * asso = (Table_association*) asso_tmp;
104  if( asso->supprimer_cle && asso->cle ){
105  asso->supprimer_cle( asso->cle );
106  }
107  xfree(asso);
108 }
109 
110 void supprimer_table_association( Table_association * asso ){
111  if( asso->supprimer_cle && asso->cle ){
112  asso->supprimer_cle( asso->cle );
113  }
114  xfree(asso);
115 }
116 
118  int (*comparer_cle)( const intptr_t cle1, const intptr_t cle2 ),
119  intptr_t (*copier_cle)( const intptr_t cle ),
120  void (*supprimer_cle)(intptr_t cle)
121 ){
122  Table* res = xmalloc( sizeof(Table) );
123  res->root = avl_create ( compare_table_association, NULL, NULL );
124 
125  res->supprimer_cle = supprimer_cle;
126  res->comparer_cle = comparer_cle;
127  res->copier_cle = copier_cle;
128  return res;
129 }
130 
131 void liberer_table( Table* table ){
132  assert( table );
133  avl_destroy ( table->root, supprimer_table_association2 );
134  xfree( table );
135 }
136 
137 void add_table( Table* table, const intptr_t cle, intptr_t valeur ) {
138  Table_association* asso = creer_table_association(table, cle, valeur);
139  void* val = avl_probe ( table->root, (void*) asso );
140  if( val == NULL ){
141  ERREUR( "Espace insuffisant" );
142  }
143  Table_association* asso_tree = *( Table_association** ) val;
144  if( asso_tree != asso ){
145  supprimer_table_association( asso );
146  asso_tree->valeur = valeur;
147  }
148 }
149 
150 intptr_t delete_table( Table* table, intptr_t cle ){
151  intptr_t valeur = (intptr_t) NULL;
152  Table_association* asso_tree = NULL;
153  Table_association* asso = creer_table_association(
154  table, cle, (intptr_t) NULL
155  );
156  void* val = avl_find( table->root, (void*) asso );
157  if( val ){
158  asso_tree = ( Table_association* ) val;
159  valeur = asso_tree->valeur;
160  }
161  avl_delete( table->root, (void*) asso );
162  if(asso_tree){
163  supprimer_table_association( asso_tree );
164  }
165  supprimer_table_association( asso );
166  return valeur;
167 }
168 
170  const Table* table,
171  void (* action)( const intptr_t cle, intptr_t valeur, void* data ),
172  void* data
173 ){
174  struct avl_traverser traverser;
175  void * item;
176  avl_t_init( &traverser, table->root );
177  while( (item = avl_t_next( &traverser )) ){
178  Table_association* asso = (Table_association *) item;
179  action( asso->cle, asso->valeur, data );
180  }
181 }
182 
183 typedef struct {
184  void (* supprimer_valeur)(intptr_t valeur );
186 
187 void action_pour_toute_valeur_table( const intptr_t cle, intptr_t valeur, void* data ){
189  d->supprimer_valeur( valeur );
190 }
191 
193  const Table* table,
194  void (* supprimer_valeur)(intptr_t valeur )
195 ){
197  data.supprimer_valeur = supprimer_valeur;
198  pour_toute_cle_valeur_table( table, action_pour_toute_valeur_table, &data );
199 }
200 
201 void vider_table( Table* table ){
202  avl_destroy ( table->root, supprimer_table_association2 );
203  table->root = avl_create ( compare_table_association, NULL, NULL );
204 }
205 
206 typedef struct {
207  void (*print_cle)( const intptr_t cle );
208  void (*print_valeur)( const intptr_t valeur );
210 
211 void print_association( const intptr_t cle, intptr_t valeur, void* data ){
213  if( d->print_cle ){
214  d->print_cle( cle );
215  }else{
216  printf("%ld", cle );
217  }
218  printf(" --> ");
219  if( d->print_valeur ){
220  d->print_valeur( valeur );
221  }else{
222  printf("%ld", valeur );
223  }
224  printf(", ");
225 }
226 
228  Table* table, void (*print_cle)( const intptr_t cle ),
229  void (*print_valeur)( const intptr_t valeur ),
230  const char* texte_de_fin
231 ){
232  data_print_table_t data;
233  data.print_cle = print_cle;
234  data.print_valeur = print_valeur;
235 
236  printf( "{ ");
237  pour_toute_cle_valeur_table( table, print_association, &data );
238  printf( " }%s", texte_de_fin );
239 }
240 
241 Table_iterateur trouver_table( const Table* table, intptr_t cle ){
242  Table_iterateur it;
243  Table_association* asso = creer_table_association(
244  table, cle, (intptr_t) NULL
245  );
246  avl_t_find( &it, table->root, (void*) asso );
247  supprimer_table_association( asso );
248  return it;
249 }
250 
252  Table_iterateur it;
253  avl_t_first( &it, table->root );
254  return it;
255 }
256 
257 Table_iterateur dernier_iterateur_table(
258  const Table_iterateur * iterator, Table* table
259 ){
260  Table_iterateur it;
261  avl_t_last( &it, table->root );
262  return it;
263 }
264 
266  return avl_t_is_null( &iterator );
267 }
268 
270  avl_t_next( &iterateur );
271  return iterateur;
272 }
273 
275  avl_t_prev( &iterateur );
276  return iterateur;
277 }
278 
279 int taille_table( Table* t ){
280  int res = 0;
281  Table_iterateur it1;
282  for(
283  it1 = premier_iterateur_table( t );
284  ! iterateur_est_vide( it1 );
285  it1 = iterateur_suivant_table( it1 )
286  ){
287  res += 1;
288  }
289  return res;
290 };
void vider_table(Table *table)
Supprime toutes les clés de la table.
Definition: table.c:201
Table_iterateur premier_iterateur_table(const Table *table)
Renvoie un itérateur positionné sur la première association de la table.
Definition: table.c:251
intptr_t get_cle(Table_iterateur it)
Renvoie la clé de l'association pointée par l'itérateur passé en paramètre.
Definition: table.c:47
int taille_table(Table *t)
Renvoie la taille de la table.
Definition: table.c:279
void pour_toute_cle_valeur_table(const Table *table, void(*action)(const intptr_t cle, intptr_t valeur, void *data), void *data)
La fonction passe en revue toutes les associaitons (clé, valeur) de la table, et apelle la fonction p...
Definition: table.c:169
void liberer_table(Table *table)
Cette fonction détruit une table. La mémoire qui a été allouée par la table pour stocker les clés son...
Definition: table.c:131
intptr_t delete_table(Table *table, const intptr_t cle)
Supprime une clé de la table. La mémoire de la clé est libérée et la valeur associée à la clé est per...
Definition: table.c:150
Definition: avl.h:56
Table_iterateur iterateur_suivant_table(Table_iterateur iterator)
Renvoie l'itérateur suivant.
Definition: table.c:269
intptr_t get_valeur(Table_iterateur it)
Renvoie la valeur de l'association pointée par l'itérateur passé en paramètre.
Definition: table.c:52
void pour_toute_valeur_table(const Table *table, void(*action)(intptr_t valeur))
La fonction passe en revue toutes les valeurs de la table passée en paramètre et apelle la fonction p...
Definition: table.c:192
void print_table(Table *table, void(*print_cle)(const intptr_t cle), void(*print_valeur)(const intptr_t valeur), const char *text_de_fin)
Affiche la table. Vous devez donner en paramètres de print_table, des fonctions pour afficher les clé...
Definition: table.c:227
Table_iterateur iterateur_precedent_table(Table_iterateur iterator)
Renvoie l'itérateur précédent.
Definition: table.c:274
int iterateur_est_vide(Table_iterateur iterator)
Renvoie 1 si l'itérateur passé en paramètre est vide. Renvoie 0 sinon.
Definition: table.c:265
Table_iterateur trouver_table(const Table *table, const intptr_t cle)
Renvoie un itérateur positionné sur l'association dont la clé est identique (pour la fonction de comp...
Definition: table.c:241
Definition: table.c:39
Table * creer_table(int(*comparer_cle)(const intptr_t cle1, const intptr_t cle2), intptr_t(*copier_cle)(const intptr_t cle), void(*supprimer_cle)(intptr_t cle))
Renvoie une nouvelle table.
Definition: table.c:117
void add_table(Table *table, const intptr_t cle, const intptr_t valeur)
La fonction add_table() ajoute une association entre une clé et une valeur. Pour cela, add_table(), crée une copie de la clé passée en paramètre, l'enregistre dans la table et l'associe à la valeur passée en paramètre. La mémoire de la copie de la clé est gérée par la table. La mémoire de la clé passée en paramètre reste à la charge de l'utilisateur.
Definition: table.c:137