Пример 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;
}

© Copyright А. Богатырев, 1992-95
Си в UNIX

Назад | Содержание | Вперед