subdiv.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "subdiv.h"
  5. /* --- Fonctions privées traitement valeurs --- */
  6. /**
  7. * Indique si une chaine est la clef d'un noeud
  8. * @param node* Le noeud
  9. * @param char* La mémoire
  10. * @param char* La clef
  11. * @return true - Oui/false - Non
  12. */
  13. boolean is_key(node* n, char* mem, char* key) {
  14. int i, length = strlen(key);
  15. //Verif que la clef correspond à celle en param
  16. for (i = 0; i < length; i++) {
  17. if (mem[i + n->start] != key[i]) {
  18. return false;
  19. }
  20. }
  21. //Verif que le caractere suivant est bien un =
  22. if (mem[i + n->start] != '=') {
  23. return false;
  24. }
  25. return true;
  26. }
  27. /**
  28. * Cherche une clef
  29. * @param subdiv* Le gestionnaire de mémoire par subdivision
  30. * @param char* La mémoire
  31. * @param char* La clef
  32. * @return La node correspondante ou NULL si introuvable
  33. */
  34. node* find_key(subdiv* sd, char* mem, char* key) {
  35. int length = strlen(key) + 2; //Clef + = + taille min mot
  36. node* n = NULL;
  37. //Cherche la clef
  38. for (int i = 0; i < MEM_SIZE / 2; i++) {
  39. if (sd->use[i] && sd->mem[i].type == MEMSET && sd->mem[i].length >= length) {
  40. //Regarde si la clef correspond
  41. if (is_key(&sd->mem[i], mem, key)) {
  42. n = &sd->mem[i];
  43. break;
  44. }
  45. }
  46. }
  47. return n;
  48. }
  49. /**
  50. * Récupère la valeur d'un noeid
  51. * @param node* La noeud
  52. * @param char* La mémoire
  53. */
  54. char* parse_val(node* n, char* mem) {
  55. int pos = 0;
  56. //Cherche la postion du =
  57. while (mem[pos + n->start] != '=') {
  58. pos++;
  59. }
  60. pos++;
  61. //Creation chaine
  62. char* str = mem + n->start + pos;
  63. char* val = malloc(sizeof (char) * (n->length - pos + 1));
  64. memset(val, 0, n->length - pos + 1);
  65. strncpy(val, str, n->length - pos);
  66. //Retour
  67. return val;
  68. }
  69. /* --- Fonctions privées nodes --- */
  70. boolean div_node(subdiv* sd, node* n) {
  71. node* newn = NULL;
  72. int i;
  73. //Verif que la node à diviser est bien libre
  74. if (n->type != MEMEMPTY) {
  75. return false;
  76. }
  77. //Cherche une node libre
  78. for (i = 0; i < MEM_SIZE; i++) {
  79. if (sd->use[i] == 0) {
  80. newn = &sd->mem[i];
  81. break;
  82. }
  83. }
  84. //Plus de place
  85. if (newn == NULL) {
  86. return false;
  87. }
  88. //Setup node
  89. newn->index = i;
  90. newn->start = n->start + (n->length / 2);
  91. newn->end = n->end;
  92. newn->length = n->length / 2;
  93. newn->type = MEMEMPTY;
  94. newn->prev = n->index;
  95. newn->next = n->next;
  96. //Modifie node suivant la nouvelle
  97. if (n->next != -1 || n->next == n->index) {
  98. sd->mem[n->next].prev = newn->index;
  99. }
  100. //Modifie node origine
  101. n->end = n->start + (n->length / 2);
  102. n->length /= 2;
  103. n->next = newn->index;
  104. //Indique que la node est utilisé
  105. sd->use[i] = true;
  106. return true;
  107. }
  108. boolean fusion_node(subdiv* sd, node* n) {
  109. //Verif que la node et la node suivante sont vide
  110. if (!(n->type == MEMEMPTY && n->next != -1 && sd->mem[n->next].type == MEMEMPTY)) {
  111. return false;
  112. }
  113. node* n2 = &sd->mem[n->next];
  114. //Verif qu'elles ont la meme taille
  115. if (n->length != n2->length) {
  116. return false;
  117. }
  118. //Met à jour la node
  119. n->end = n2->end;
  120. n->length *= 2;
  121. n->next = n2->next;
  122. if (n2->next != -1 || n2->next == n2->index) {
  123. sd->mem[n2->next].prev = n->index;
  124. }
  125. //Indique que l'autre node n'est plus utilisée
  126. sd->use[n2->index] = false;
  127. return true;
  128. }
  129. /* --- Fonctions publiques --- */
  130. void ini_subdiv(subdiv* sd) {
  131. sd->mem[0] = (node){0, 0, MEM_SIZE, MEM_SIZE, MEMEMPTY, -1, -1};
  132. sd->use[0] = true;
  133. for (int i = 1; i < MEM_SIZE / 2; i++) {
  134. sd->use[i] = false;
  135. }
  136. }
  137. boolean add_data_subdiv(subdiv* sd, char* mem, char* key, char* data) {
  138. //Recup taille data
  139. int length = strlen(data) + strlen(key) + 1;
  140. //Cherche un espace ou mettre la données
  141. node* n = &sd->mem[0];
  142. while (n != NULL) {
  143. if (n->type == MEMEMPTY && n->length >= length) {
  144. break;
  145. }
  146. //Charge le prochain noeud
  147. if(n->next == -1 || n->next == n->index){
  148. n = NULL;
  149. } else {
  150. n = &sd->mem[n->next];
  151. }
  152. }
  153. //Si plus de place
  154. if (n == NULL) {
  155. return false;
  156. }
  157. //Si on peut diviser par deux la place libre et stocker dedans
  158. if ((n->length / 2) >= length) {
  159. //On divise la zone en 2
  160. if (!div_node(sd, n)) {
  161. return false;
  162. }
  163. return add_data_subdiv(sd, mem, key, data);
  164. }
  165. //Genere chaine à mettre en mémoire
  166. char* str = malloc(sizeof (char) * (length + 1));
  167. memset(str, 0, length + 1);
  168. snprintf(str, length + 1, "%s=%s", key, data);
  169. //On maj la node
  170. n->type = MEMSET;
  171. n->length = length;
  172. //On met dans la mémoire
  173. for (int i = 0; i < length; i++) {
  174. mem[i + n->start] = str[i];
  175. }
  176. //Nettoyage
  177. free(str);
  178. return true;
  179. }
  180. boolean add_fdata_subdiv(subdiv* sd, char* mem, char* data) {
  181. //Recup taille data
  182. int length = strlen(data);
  183. //Cherche un espace ou mettre la données
  184. node* n = &sd->mem[0];
  185. while (n != NULL) {
  186. if (n->type == MEMEMPTY && n->length >= length) {
  187. break;
  188. }
  189. //Charge le prochain noeud
  190. if(n->next == -1 || n->next == n->index){
  191. n = NULL;
  192. } else {
  193. n = &sd->mem[n->next];
  194. }
  195. }
  196. //Si plus de place
  197. if (n == NULL) {
  198. return false;
  199. }
  200. //Si on peut diviser par deux la place libre et stocker dedans
  201. if ((n->length / 2) >= length) {
  202. //On divise la zone en 2
  203. if (!div_node(sd, n)) {
  204. return false;
  205. }
  206. return add_fdata_subdiv(sd, mem, data);
  207. }
  208. //On maj la node
  209. n->type = MEMSET;
  210. n->length = length;
  211. //On met dans la mémoire
  212. for (int i = 0; i < length; i++) {
  213. mem[i + n->start] = data[i];
  214. }
  215. return true;
  216. }
  217. char* get_data_subdiv(subdiv* sd, char* mem, char* key) {
  218. node* n = find_key(sd, mem, key);
  219. //Si pas trouvé la clef
  220. if (n == NULL) {
  221. return NULL;
  222. }
  223. //Recup valeur
  224. return parse_val(n, mem);
  225. }
  226. boolean remove_data_subdiv(subdiv* sd, char* mem, char* key) {
  227. node* n = find_key(sd, mem, key);
  228. //Si pas trouvé la clef
  229. if (n == NULL) {
  230. return false;
  231. }
  232. //Marque la node comme vide
  233. n->length = n->end - n->start;
  234. n->type = MEMEMPTY;
  235. //Tente la fusion des noeuds (Algo imparfait)
  236. n = &sd->mem[0];
  237. while (n != NULL) {
  238. //On fusionne avec celui d'après si celui d'avant à une taille différente
  239. if (n == &sd->mem[0]) {
  240. if (fusion_node(sd, n)) {
  241. n = &sd->mem[0];
  242. } else {
  243. //Charge le prochain noeud
  244. if(n->next == -1 || n->next == n->index){
  245. n = NULL;
  246. } else {
  247. n = &sd->mem[n->next];
  248. }
  249. }
  250. } else if (sd->mem[n->prev].length != n->length) {
  251. if (fusion_node(sd, n)) {
  252. n = &sd->mem[0];
  253. } else {
  254. //Charge le prochain noeud
  255. if(n->next == -1 || n->next == n->index){
  256. n = NULL;
  257. } else {
  258. n = &sd->mem[n->next];
  259. }
  260. }
  261. } else {
  262. //Charge le prochain noeud
  263. if(n->next == -1 || n->next == n->index){
  264. n = NULL;
  265. } else {
  266. n = &sd->mem[n->next];
  267. }
  268. }
  269. }
  270. return true;
  271. }
  272. void show_subdiv(subdiv* sd) {
  273. node* n = &sd->mem[0];
  274. while (n != NULL) {
  275. printf("Deb : %d, Fin : %d, Length : %d, Real length : %d, Use : %d\n", n->start, n->end, n->length, n->end - n->start, (int) n->type);
  276. //Charge le prochain noeud
  277. if(n->next == -1){
  278. n = NULL;
  279. } else {
  280. n = &sd->mem[n->next];
  281. }
  282. }
  283. }
  284. void show_data_subdiv(subdiv* sd, char* mem){
  285. boolean vide = true;
  286. node* n = &sd->mem[0];
  287. while (n != NULL) {
  288. if(n->type == MEMSET){
  289. vide = false;
  290. char* str = malloc(sizeof(char) * (n->length + 1));
  291. char* deb = mem + n->start;
  292. memset(str, 0, n->length + 1);
  293. strncpy(str, deb, n->length);
  294. printf("%s\n", str);
  295. free(str);
  296. }
  297. //Charge le prochain noeud
  298. if(n->next == -1 || n->next == n->index){
  299. n = NULL;
  300. } else {
  301. n = &sd->mem[n->next];
  302. }
  303. }
  304. //Si vide
  305. if(vide){
  306. printf("Aucune variable en mémoire\n");
  307. }
  308. }