Пример 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 www.abyss-group.narod.ru
Си в UNIX