|
Пример 10
/* Проблема: позволить делать вызов free(ptr)
* на данные, не отводившиеся malloc()-ом.
* Решение: вести список всех данных,
* отведенных malloc()ом.
* Возможно также отслеживание диапазона адресов,
* но последнее является машинно-зависимым решением.
*
* При большом количестве файлов эта программа - неплохой тест
* производительности машины!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _cell {
void *addr;
struct _cell *next;
} Cell;
typedef struct _entry {
int length;
int used;
Cell *list;
} Entry;
/* Хэшированная таблица */
#define NENTRIES 64
Entry aTab[NENTRIES];
/* Хэш-функция от адреса */
int aHash(void *addr){
unsigned long x = (unsigned long) addr;
x >>= 3; /* деление на 8, так как адреса из malloc()
обычно четные,
поскольку выровнены на границу double */
return(x % NENTRIES);
/* Тут к месту напомнить, что вычисление остатка от деления на степень двойки
* можно соптимизировать:
* x % (2**N) = x & 0b0001.....1 (N двоичных единиц)
* К примеру, x % 64 = x & 0x3F; (6-ая степень двойки)
*/
}
/* Выделить память, записать адрес в таблицу */
void *aCalloc(int n, int m){
void *ptr = calloc(n, m);
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;
for(p=ep->list; p; p=p->next)
if(p->addr == NULL){
/* Свободная ячейка: переиспользовать */
p->addr = ptr;
ep->used++;
return ptr;
}
/* Нет свободных, завести новую */
p = (Cell *) calloc(1, sizeof(Cell));
p->addr = ptr;
p->next = ep->list;
ep->list = p;
ep->length++;
ep->used++;
return ptr;
}
/* Освободить память */
int aFree(void *ptr){
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;
for(p=ep->list; p; p=p->next)
if(p->addr == ptr){
free(ptr);
p->addr = NULL;
/* Ячейка не удаляется, но метится как свободная */
ep->used--;
return 1;
}
/* Нет, такой указатель не отводился.
* Не делать free()
*/
return 0;
}
/* Выдать статистику об использовании хэша */
void aStat(){
int i;
int len_all;
int used_all;
for(i=len_all=used_all=0; i < NENTRIES; i++){
len_all += aTab[i].length;
used_all += aTab[i].used;
printf("%d/%d%s", aTab[i].used, aTab[i].length,
i==NENTRIES-1 ? "\n":" ");
}
printf("%d/%d=%g%%\n",
used_all, len_all,
(double)used_all * 100 / len_all);
}
/* ТЕСТ =================================================================*/
Cell *text;
/* Прочитать файл в память */
void fileIn(char *name){
char buf[10000];
FILE *fp;
if((fp = fopen(name, "r")) == NULL){
printf("Cannot read %s\n", name);
return;
}
while(fgets(buf, sizeof buf, fp) != NULL){
char *s;
Cell *p;
s = (char *) aCalloc(1, strlen(buf)+1);
strcpy(s, buf);
p = (Cell *) aCalloc(sizeof(Cell), 1);
p->addr = s;
p->next = text;
text = p;
}
fclose(fp);
}
/* Уничтожить текст в памяти */
void killAll(){
Cell *ptr, *nxtp;
ptr = text;
while(ptr){
nxtp = ptr->next;
if(!aFree(ptr->addr)) printf("No free(1)\n");
if(!aFree(ptr)) printf("No free(2)\n");
ptr = nxtp;
}
}
/* Удалить из текста строки, начинающиеся с определенной буквы */
void randomKill(int *deleted){
unsigned char c = rand() % 256;
Cell *ptr, *prevp;
unsigned char *s;
retry:
prevp = NULL; ptr = text;
while(ptr){
s = (unsigned char *) ptr->addr;
if(*s == c){ /* нашел */
if(!aFree(s)) printf("No free(3)\n");
/* исключить из списка */
if(prevp) prevp->next = ptr->next;
else text = ptr->next;
if(!aFree(ptr)) printf("No free(4)\n");
/* Заведомо неправильный free
if(!aFree(ptr+1)) printf("No free(5)\n");
*/
(*deleted)++;
goto retry;
}
prevp = ptr;
ptr = ptr->next;
}
}
int main(int ac, char *av[]){
int i, r, d;
char buffer[4098];
srand(time(NULL));
for(i=1; i < ac; i++){
printf("File: %s\n", av[i]);
fileIn(av[i]);
aStat();
d = 0;
for(r=0; r < 128; r++) randomKill(&d);
printf("%d lines deleted\n", d);
aStat();
}
killAll();
aStat();
if(!aFree(buffer))
printf("buffer[] - не динамическая переменная.\n");
return 0;
}
[Назад][Содержание][Вперед] |