Cześć,
byłbym wdzięczny, gdybyście zechcieli pomóc w zrozumieniu działania funkcji free (Język C, Kernighan i Ritchie).

Słowo wyjaśnienia: w dystrybutorze pamięci ich implementacji pamięć jest przydzielana w postaci bloków. Bloki te

tworzą łańcuch (blok n-1 przechowuje wskaźnik do bloku n-tego, ponadto ostatni blok zawiera wskaźnik do pierwszego

bloku). Jest to konieczne, gdyż ze względu na to, iż w ogólności bloki nie będą ułożone sekwencyjnie, nie możemy

polegać na zwykłej arytmetyce na wskaźnikach. Przed każdym blokiem znajduje się nagłówek zawierający informacje o

rozmiarze bloku, a także zapewniający (dzięki zastosowaniu unii), że przydzielana pamięć będzie spełniała wymogi

najbardziej rygorystycznego typu danych (autorzy arbitralnie przyjęli, że jest to long). Niżej cytuję resztę kodu

dystrybutora pamięci, gdyż prawdopodobnie zapoznanie się z treścią funkcji malloc i morecore pozwoli na znacznie

szybsze i dokładniejsze uchwycenie mechanizmu jego działania. Jeżeli chcecie dodatkowych informacji na temat ogólnej

zastosowanej tu koncepcji albo o działaniu którejś z poniższych funkcji, to piszcie, chętnie odpowiem (o ile będę

wiedział).

/*free: zwróć blok ap do łańcucha wolnych bloków*/
typedef long Align;

union header {
	struct {
		union header *ptr;
		unsigned size;
	} s;
	Align x;
};

typedef union header Header;

void free(void *ap)
{
    Header *bp, *p;
    bp = (Header*)ap-1; /*wskaż nagłówek*/
    for(p = freep; !(bp>p && bp < p->s.ptr); p=p->s.ptr;
        if(p>=p->s.ptr && (bp>p || bp <p->s.ptr))
            break; /*miejsce na jednym z końców łańcucha*/

    if(bp + bp->s.size == p->s.ptr) { /*połącz z następnym blokiem*/ 
        bp->s.size+=p->s.ptr->s.size;
        bp->s.ptr=p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p+p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    }
    else
        p->s.ptr
        p=freep; /* freep wskazuje na początek łańcucha wolnych bloków - zob. niżej (Paweł) */
}

Cytat z K&R:

W poszukiwaniu miejsca dla zwalnianego bloku przegląda ona [funkcja free - Paweł] łańcuch wolnych bloków,

rozpoczynając od freep. Miejsce to znajduje się albo między dwoma istniejącymi blokami, albo na jednym z końców

łańcucha. W każdym przypadku, jeżeli zwalniany blok przylega do któregokolwiek z sąsiadów, to przylegające bloki

zostaną sklejone. Jedynym problemem jest zapewnienie, aby wskaźniki poprawnie wskazywały na właściwe obiekty o

właściwych rozmiarach

Moje pytania:

  1. Co robi pętla for w powyższej funkcji? Analizując ten kod zastanawiałem się, dlaczego funkcja free nie zwolni po

prostu bloku związanego przez ap (wystarczyłoby zmienić rozmiar i wskaźnik ptr) i doszedłem do wniosku, że ma to na

celu zapewnienie bardziej spójnego rozmieszczenia bloków. Nie jestem jednak pewien, gdyż nie rozumiem tego fragmentu

kodu. Jak w ogóle należy rozumieć "miejsce dla zwalnianego bloku"? Zależy mi na szczegółowym przedyskutowania tego

zagadnienia.

  1. Dlaczego po ostatnim else mamy p->s.ptr=bp; ? (Inaczej: które wymagania stawiane w stosunku do przedstawionego

dystrybutora pamięci indukują konieczność takiego przypisania i czym w momencie wykonywania tej instrukcji jest p)?

static Header base;            /* pusty łańcuch na początek */
static Header *freep = NULL;   /* początek łańcucha */

/* malloc: ogólny dystrybutor pamięci */
void *malloc(unsigned nbytes)
{
  Header *p, *prevp;
  Header *morecore(unsigned);
  unsigned nunits; /*liczba żądanych porcji*/
  nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
  if ((prevp = freep) == NULL) {     /* pusty łańcuch */
    base.s.ptr = freep = prevp = &base;
    base.s.size = 0;
  }
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
    if (p->s.size >= nunits) { /* dostatecznie duży blok */
      if (p->s.size == nunits) /* dokładnie taki */
        prevp->s.ptr = p->s.ptr;
      else {     /* za duży: przydziel koniec */
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }
      freep = prevp;
      return (void *)(p+1);
    }
    if (p == freep) /* przeszukano cały łańcuch */
      if ((p = morecore(nunits)) == NULL)
        return NULL; /* brak pamięci */

  }
}
 

static Header *morecore(unsigned nu) {
    char *cp, *sbrk(int);
    Header *up;
    if (nu < NALLOC)
	nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));	
    if (cp == (char *) -1)		/* nie ma wolnej pamięci*/
	return NULL;
    up = (Header*) cp;
    up->s.size = nu;			
    free((void*)(up+1));		
    return freep;
}

Z góry dzięki za odpowiedzi,
Pozdrawiam.