1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#include <stdlib.h>
#include <stdio.h>
#include "amb.h"
#define AMB_BLOCSIZE 30
#define NBLOCS 1024
/* Definition d'un bloc libre. */
typedef struct free_bloc
{
int nb_free_bloc;
int next_free_bloc;
} free_bloc_s;
/* Definition d'un bloc quelconque. */
typedef union bloc
{
int nalloue;
free_bloc_s bloc_free;
char bloc[AMB_BLOCSIZE];
} bloc_u;
static bloc_u membloc[NBLOCS];
static int first_free_blk =1;
int amb_init(void)
{
free_bloc_s bloc_free;
bloc_u init_blk;
/* Init du premier bloc libre */
bloc_free.nb_free_bloc = NBLOCS;
bloc_free.next_free_bloc = -1;
/* Wrap le premier bloc libre */
init_blk.bloc_free = bloc_free;
/* On renseigne ce blocs dans le tableau correspondant à la mémoire. */
membloc[0] = init_blk;
return 1;
}
// Algorithme du first-it
void * amb_newbloc(unsigned int nbloc)
{
int cnext = 0;
/* Ajout du bloc permettant de connaitre la taille. */
nbloc++;
/* Boucle sur les blocs libres */
for (int c = first_free_blk; c != -1;)
{
/* On a trouvé zone libre candidate. */
if (membloc[cnext].bloc_free.nb_free_bloc >= nbloc) {
/* Mise à jour de la liste des blocs libres. */
/* Cas ou la partition libre est plus grande que l'allocation */
if (membloc[cnext].bloc_free.nb_free_bloc > nbloc) {
/* On retire les nalloue premier bloc libre. */
membloc[cnext].bloc_free.nb_free_bloc -= nbloc;
/* On deplace le bloc libre au nouvel index */
membloc[cnext + nbloc] = membloc[cnext];
/* On met à jour le pointeur suivant du bloc courant. */
membloc[c].bloc_free.next_free_bloc += nbloc;
} else {
/* Cas ou la partition libre est égale au nombre de blocs. */
membloc[c].bloc_free.next_free_bloc = membloc[cnext].bloc_free.next_free_bloc;
}
// Allocation
membloc[cnext].nalloue = nbloc;
}
/* Mise à jour des indexs courant et courant_suivant pointant sur les blocs libres. */
c = cnext;
cnext = membloc[c].bloc_free.next_free_bloc;
}
return membloc[cnext + 1].bloc;
}
/*
* Libere le bloc
* La stratégie de cette méthode est assez naive.
* En effet, elle libére les blocs sans verifier s'ils sont déjà libres.
* Ceci entraine potentiellement une corruption de la liste des blocs libres, ajout de cycle notament.
* Un autre problème viens du fait que cela entraine une fragmentation de la mémoire.
* Il y a par contre un avantage à ceci, c'est la performance en temps de calcul.
*/
int amb_freebloc(void *bloc)
{
int blc = *((int *)bloc);
blc --;
if (blc < 0 && blc >= NBLOCS) {
return 0; /* Adresse invalide */
}
/* On recupere les blocs libres */
membloc[blc].bloc_free.nb_free_bloc = membloc[blc].nalloue;
/* Ajout en tête */
membloc[blc].bloc_free.next_free_bloc = membloc[first_free_blk].bloc_free.next_free_bloc;
first_free_blk = blc;
return 1; /* Renvoie toujours vrai */
}
int check(void * b1,void * b2)
{
if (b1 == b2){
printf("Equal\n");
return 1;
}
printf(" different\n");
return 1;
}
int main(void)
{
printf("Begin\n");
amb_init();
void *b1 = amb_newbloc(9);
void *b2 = amb_newbloc(12);
check(b1,b2);
amb_freebloc(b1);
amb_freebloc(b2);
void *b3 = amb_newbloc(90);
void *b4 = amb_newbloc(13);
check(b3,b4);
amb_freebloc(b3);
amb_freebloc(b4);
printf("GG\n");
return 0;
} |
