#include <stdio.h>
#include <string.h>

#define MAGIC (Header *)1111

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

static Header base;             /* Anfangs-Header */
static Header *freep = NULL;    /* Einstiegspunkt in Free-Liste */

void* mymalloc(unsigned nbytes)
{
    Header *p, *prevp;
    static Header *morecore(unsigned);
    unsigned nunits;

    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

    if ((prevp = freep) == NULL)           /* Erster Aufruf, Initialisierung */
        {
        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)           /* Block gross genug */
            {
            if (p->s.size == nunits)       /* Block passt genau */
                prevp->s.ptr = p->s.ptr;
            else
                {
                p->s.size -= nunits;       /* Block wird geteilt */
                p += p->s.size;            /*Pointer auf abgeschnittenes Ende*/
                p->s.size = nunits;
                }
            freep = prevp;

            p->s.ptr=MAGIC;             /* da *ptr nur in free gebraucht wird,
                                            Magic zur Ueberpruefung von free */

            return (void*) (p+1);       /* zeigt auf Speicherblock,nicht *H  */
            }

        if ( p == freep)                /* p wieder beim Anfang,dh kein Platz*/
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

#define NALLOC  512    /* 512 * Header = 4 KB */

/* Eine static-Funktion ist ausserhalb ihres Files nicht sichtbar       */

static Header *morecore(unsigned nu)
{
    void *cp, *sbrk(int);
    void myfree(void*);
    Header *up;
    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)              /* sbrk liefert -1 im Fehlerfall */
        return NULL;
    up = (Header*) cp;
    up->s.size = nu;                    /* Groesse wird eingetragen     */
    up->s.ptr = MAGIC;                  /* damit sich free nicht beschwert */
    myfree((void*)(up+1));               /* Einbau in Free-Liste         */
    return freep;
}

void myfree(void *ap)                   /* Rueckgabe an Free-Liste      */
{
    Header *bp, *p;

    bp = (Header*) ap - 1;              /* Hier ist der Header des Blocks */

        /* Die Liste wird durchmustert, der Block soll der
           Adressgroesse nach richtig eingefuegt werden,
           um Defragmentierung zu ermoeglichen.                         */

    if (bp->s.ptr!=MAGIC) {
        printf("bad magic number in pointer at %08lX %lu\n",ap,ap);
        return ;
        }
    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;      /* bp liegt vor Block mit kleinster oder hinter
                           Block mit groesster Adresse */

    if (bp + bp->s.size == p->s.ptr)
        {                       /* Vereinigung mit oberem Nachbarn      */
         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 ) {
                                /* Vereinigung mit unterem Nachbarn     */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}

void* myrealloc(void *oldp,unsigned newsize)
{
  void *newp ;
  Header *h ;
  unsigned oldsize ;

  if (oldp==NULL)
        return ( mymalloc(newsize) ) ;

  h = (Header *)oldp - 1 ;
  if (h->s.ptr!=MAGIC) {
        printf("bad magic number in pointer at %08lX %lu\n",oldp,oldp);
        return (NULL);
        }

  oldsize = h->s.size * sizeof(Header) - sizeof(Header) ;   /* size in bytes */
  printf("Pointer oldsize=0x%08lX %lu\n",oldsize,oldsize);

  myfree(oldp);
  newp = mymalloc(newsize);
  if  (newp==NULL)
        return NULL ;
  if (newp!=oldp)
        memcpy(newp,oldp,(newsize < oldsize) ? newsize : oldsize ) ;
  return (newp) ;
}

void* mycalloc(unsigned nelem,unsigned size)
{
  void *p = mymalloc(nelem*size) ;

  if (p) bzero(p,nelem*size) ;
  return p ;
}

printfree()
{
  Header *p ;

  for (p=&base ; ; p=p->s.ptr)
        {
        printf("base=%08lX size=%5d\n",(char *)p,p->s.size*sizeof(Header));
        if (p->s.ptr==&base) break ;
        }
}

void bfree(void* p,unsigned int n)  /* p-> Block ; n=sizeof block */
{
Header *bfreeheader ;   /* header fuer block */
unsigned int units ;

if ( freep == NULL)           /* Erster Aufruf, Initialisierung */
        {
        base.s.ptr = freep = &base;
        base.s.size = 0;
        }

units= (n-1)/sizeof(Header) + 1 ;

if (n % sizeof(Header) ) units-- ;      /* falls blocksize % 8 nicht 0
                                        sollen die letzten Bytes nicht
                                        verwendet werden */
bfreeheader=(Header*)p;

bfreeheader->s.ptr  = MAGIC ;
bfreeheader->s.size = units ;

myfree( (void *)(bfreeheader+1));
}

static int a[1024];
int* allocstatic()
{
if ( freep == NULL)           /* Erster Aufruf, Initialisierung */
        {
        base.s.ptr = freep = &base;
        base.s.size = 0;
        }
return a;
}


int main()
{
    char c;
    int bool ;
    unsigned n,b;
    void *p ;

    while (1){
        bool=1;
        printf("\n(m)alloc (c)alloc (f)ree (r)ealloc (s)tatic (b)free (q)uit : ");

        fflush(stdin);
        scanf("%c",&c);
        fflush(stdin);

        switch(c)
        {
        case 'm' : printf("Wieviel Bytes : ");
                   scanf("%d",&n);
                   p=mymalloc(n);
                   printf("Pointer zeigt auf Adresse 0x%08lX %lu\n",p,p);
                   break;

        case 'c' : printf("Wieviel Elemente und Groesse der Elem. : ");
                   scanf("%d %d",&n,&b);
                   p=mycalloc(n,b);
                   printf("Pointer zeigt auf Adresse 0x%08lX %d\n",p,p);
                   break;

        case 'f' : printf("Welche Addresse : ");
                   scanf("%d",&n);
                   p=(void *)n;
                   myfree(p);
                   break;

        case 'r' : printf("Welche Addresse und wieviel Bytes : ");
                   scanf("%d %d",&n,&b);
                   p=(void *)n;
                   p=myrealloc(p,b);
                   printf("Pointer zeigt auf Address 0x%08lX %lu\n",p,p);
                   break;

        case 's' : p=(void *)allocstatic();
                   printf("static Pointer zeigt auf 0x%08lX %lu\n",p,p);
                   break;

        case 'b' : printf("Welche Addresse und wieviel Bytes : ");
                   scanf("%d %d",&n,&b);
                   p=(void *)n;
                   bfree(p,b);
                   break;
        case 'q' :
                    printf("exit prg\n");
                    return(0) ;
        default : bool=0;
                  break;
        }
        if (bool)
            printfree();
    }
}