trafi

tfm.c (6612B)

---

 #include <assert.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 
 #include "tfm.h"
 #include "tampex.h"
 
 #define TAMPON_LNGR_DEF 64 /* Longueur par défaut des tampons. */
 
 /* Tester la cohérence d’un tfm. */
 #define TFM_COHERENT(tfm) \
 	/* Le pointeur n’est pas NULL. */ \
 	assert((tfm)); \
 	/* Le pointeur vers le tampex des états n’est pas NULL. */ \
 	assert((tfm)->etats); \
 	/* Le pointeur vers le tampex des transitions n’est pas NULL. */ \
 	assert((tfm)->trans); \
 	/* Le pointeur vers le tampex des symboles n’est pas NULL. */ \
 	assert((tfm)->symbs);
 
 /* Chercher un symbole symb de longueur lngr dans le tampon te.
  * Renvoie la position du symbole dans tfm->symbs, ou -1 s’il ne s’y trouve
  * pas. */
 static ssize_t tfm_symb_chercher(char *te, char *symb, size_t lngr);
 
 /* Trier les transitions d’un état.
  * Renvoie 0, ou -1 en cas d’erreur. */
 static void trier_etat(struct tfm *tfm, size_t ietat);
 
 /* Comparer deux transition pour les trier.
  * Renvoie -1 si t1 est supérieur t2, 0 s’ils sont égales et 1 si t2 est
  * supérieure à t1. */
 static int trans_comparer(struct tfm *tfm, size_t t1, size_t t2);
 
 struct tfm *
 tfm_init(void)
 {
 	struct tfm *tfm;
 
 	if ((tfm = malloc(sizeof(struct tfm))) == NULL)
 		return NULL;
 
 	/* Initialiser les tampex. */
 	if ((tfm->etats = tampex_init(TAMPON_LNGR_DEF,
 		    sizeof(struct etat))) == NULL)
 		goto erreur1;
 	if ((tfm->trans = tampex_init(TAMPON_LNGR_DEF,
 		    sizeof(struct trans))) == NULL)
 		goto erreur2;
 	if ((tfm->symbs = tampex_init(TAMPON_LNGR_DEF,
 		    sizeof(char))) == NULL)
 		goto erreur3;
 
 	tfm->trie = 1;
 
 	TFM_COHERENT(tfm);
 
 	return tfm;
 
 erreur3:
 	tampex_libr(tfm->trans);
 erreur2:
 	tampex_libr(tfm->etats);
 erreur1:
 	free(tfm);
 	return NULL;
 }
 
 void
 tfm_libr(struct tfm *tfm)
 {
 	TFM_COHERENT(tfm);
 
 	tampex_libr(tfm->symbs);
 	tampex_libr(tfm->trans);
 	tampex_libr(tfm->etats);
 	free(tfm);
 }
 
 int
 tfm_ajt(struct tfm *tfm, size_t es, size_t ed, ssize_t se, ssize_t ss)
 {
 	ssize_t itrans; /* Identifiant de transition. */
 
 	TFM_COHERENT(tfm);
 
 	/* Assurer que l’état source existe. */
 	if (tampex_minim((void **)&tfm->etats, es) < 0)
 		return -1;
 	if (!tfm->etats[es].existe) {
 		tfm->etats[es].existe = 1;
 		tfm->etats[es].trans = -1;
 	}
 
 	/* Ajouter une transition. */
 	if ((itrans = tampex_empl((void **)&tfm->trans)) < 0)
 		return -1;
 
 	/* Construire la nouvelle transition. */
 	tfm->trans[itrans].se = se;
 	tfm->trans[itrans].ss = ss;
 	tfm->trans[itrans].ed = ed;
 	tfm->trans[itrans].prch = tfm->etats[es].trans;
 
 	/* Mettre à jour l’état. */
 	tfm->etats[es].trans = itrans;
 	tfm->etats[es].ntrans++;
 	tfm->etats[es].trie = 0;
 
 	/* Mettre à jour le tfm. */
 	tfm->trie = 0;
 
 	TFM_COHERENT(tfm);
 
 	return 0;
 }
 
 ssize_t
 tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr)
 {
 	size_t i;
 	ssize_t id;
 
 	TFM_COHERENT(tfm);
 	assert(symb);
 	assert(lngr > 0);
 	assert(lngr <= TFM_TLL_SYMB_MAX);
 
 	/* La longueur de l’identifiant doit pouvoir entrer dans un octets. */
 	assert(TFM_TLL_SYMB_MAX <= 0xFF);
 
 	if ((id = tfm_symb_chercher(tfm->symbs, symb, lngr)) < 0) {
 		/* Le symbole n’a pas été trouvé: l’ajouter. */
 		i = id = tampex_nelem(tfm->symbs);
 		if (tampex_minim((void **)&tfm->symbs, i + lngr) < 0)
 		    return -1;
 		tfm->symbs[i++] = lngr;
 		memcpy(tfm->symbs + i, symb, lngr);
 	}
 
 	assert(id >= 0);
 	TFM_COHERENT(tfm);
 
 	return (id << 1) | TFM_SNORMAL;
 }
 
 ssize_t
 tfm_symb_obt(struct tfm *tfm, size_t id, char *symb, size_t max)
 {
 	unsigned char lngr;
 
 	TFM_COHERENT(tfm);
 	assert(symb);
 	assert(max > 0);
 	assert((id & 0x01) == TFM_SNORMAL);
 	assert(tampex_dedans(tfm->symbs, id >> 1));
 
 	id >>= 1;
 
 	lngr = *(tfm->symbs + id);
 
 	assert(lngr != 0);
 
 	/* Le symbole doit rentrer dans le tampon. */
 	if (lngr > max)
 		return -1;
 
 	/* Copier le symbole. */
 	memcpy(symb, tfm->symbs + id + 1, lngr);
 
 	return lngr;
 }
 
 int
 tfm_mfinal(struct tfm *tfm, size_t ietat)
 {
 	TFM_COHERENT(tfm);
 
 	/* Obtenir, modifier, puis écrire l’état. */
 	if (tampex_minim((void **)&tfm->etats, ietat) < 0)
 		return -1;
 	tfm->etats[ietat].final = 1;
 
 	TFM_COHERENT(tfm);
 
 	return 0;
 }
 
 int
 tfm_tfinal(struct tfm *tfm, size_t ietat)
 {
 	TFM_COHERENT(tfm);
 
 	if (tampex_minim((void **)&tfm->etats, ietat) < 0)
 		return -1;
 	return tfm->etats[ietat].final;
 }
 
 void
 tfm_trier(struct tfm *tfm)
 {
 	size_t ietat;
 
 	TFM_COHERENT(tfm);
 
 	if (tfm->trie)
 		return;
 
 	for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) {
 		if (!tfm->etats[ietat].trie && tfm->etats[ietat].existe) {
 		    trier_etat(tfm, ietat);
 		    tfm->etats[ietat].trie = 1;
 		}
 	}
 }
 
 /* Inspiré du programme de Simon Tatham disponible au
  * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c */
 static void
 trier_etat(struct tfm *tfm, size_t ietat)
 {
 	TFM_COHERENT(tfm);
 
 	ssize_t liste, dern; /* Liste et son dernier élément. */
 	size_t listel; /* Longueur de la liste. */
 	size_t ts; /* Taille des segments. */
 	ssize_t s1, s2; /* Deux segments de la liste. */
 	size_t ts1, ts2; /* Taille des deux segments. */
 	size_t trans;
 	size_t i;
 
 	liste = tfm->etats[ietat].trans;
 	listel = tfm->etats[ietat].ntrans;
 	ts = 1;
 
 	while (ts < listel) {
 		s1 = s2 = liste;
 		liste = dern = -1;
 
 		while (s1 != -1) {
 		    ts1 = 0;
 		    for (i = 0; i < ts; i++) {
 		        ts1++;
 		        if ((s2 = tfm->trans[s2].prch) == -1)
 		            break;
 		    }
 
 		    ts2 = ts;
 
 		    while ((ts1 > 0) || ((ts2 > 0) && (s2 != -1))) {
 		        if (ts1 == 0) goto des2;
 		        if (ts2 == 0 || s2 == -1) goto des1;
 		        if (trans_comparer(tfm, s1, s2) <= 0) {
 		        des1:
 		            trans = s1;
 		            s1 = tfm->trans[s1].prch;
 		            ts1--;
 		        } else {
 		        des2:
 		            trans = s2;
 		            s2 = tfm->trans[s2].prch;
 		            ts2--;
 		        }
 
 		        if (dern != -1) {
 		            tfm->trans[dern].prch = trans;
 		        } else {
 		            liste = trans;
 		        }
 		        dern = trans;
 		    }
 		    tfm->trans[dern].prch = -1;
 
 		    s1 = s2;
 		}
 
 		ts *= 2;
 	}
 
 	tfm->etats[ietat].trans = liste;
 }
 
 static int
 trans_comparer(struct tfm *tfm, size_t t1, size_t t2)
 {
 	TFM_COHERENT(tfm);
 
 	if (tfm->trans[t1].se > tfm->trans[t2].se) return -1;
 	if (tfm->trans[t1].se == tfm->trans[t2].se) return 0;
 	return 1;
 }
 
 static ssize_t
 tfm_symb_chercher(char *ti, char *symb, size_t lngr)
 {
 	size_t pos;
 	unsigned char n;
 
 	assert(ti);
 	assert(symb);
 	assert(lngr > 0);
 
 	for (pos = 0; tampex_dedans(ti, pos); pos += n) {
 		n = ti[pos++];
 		if (lngr == n && memcmp(symb, ti + pos, n) == 0)
 		    return pos - 1;
 	}
 
 	return -1;
 }