/* Copyright (c) 1992 by AT&T Bell Laboratories. */
/* Advanced C++ Programming Styles and Idioms */
/* James O. Coplien */
/* Fixed by Andy Piper - Cambridge University Engineering Department */
/* All rights reserved. */

#include <stddef.h>
#include <memory.h>

class LAPD {
    friend class LAPDMemoryManager;
  public:
    void *operator new(size_t);
    void operator delete(void *);
    LAPD(char *const);
    virtual ~LAPD() {}
  protected:
    LAPD() { /* no-op */ }
    
  private:
  int:8;
    struct {
	unsigned char flag;
	unsigned int sapi:6;
	unsigned int commandResponse:1;
	unsigned int zero:1;
	unsigned int tei:7;
	unsigned int ext:1;
	unsigned char control;
    } header;
    struct {
	LAPD *linkf, *linkb;
	unsigned short logSize;
    } minfo;
  protected:
    union {
	unsigned char tag;   // minfo system allocated tag
	size_t	size;
    };
    void performCRCCheck() { /* . . . */ }
};

#define round(a,b) (((a+b-1)/b)*b)

class LAPDMemoryManager {
    friend LAPD;
  private:
    enum { MessageBufSize=8192, Log2MessageBufSize=13 };
    unsigned char availBuf[
	(1+Log2MessageBufSize)*round(sizeof(LAPD),4)];
    LAPD *avail;
    unsigned char buf[MessageBufSize];
    LAPD *buddy(int k, LAPD *l) {
        unsigned char *cp = (unsigned char *) l;
        return (LAPD*)(buf+(long(cp-buf) ^ (1<<k)));
    }
  public:
    LAPDMemoryManager();
    int savej;
    LAPD *largestBlock();
    void allocateResizeBlock(int ktemp);
    void deallocateBlock(LAPD *l, int k);
};

LAPDMemoryManager::LAPDMemoryManager() {
    LAPD* buf = (LAPD*)this->buf;
    avail = (LAPD*)availBuf;
    avail[Log2MessageBufSize].minfo.linkf = 
	avail[Log2MessageBufSize].minfo.linkb = buf;
    buf[0].minfo.linkf = buf[0].minfo.linkb =
	&avail[Log2MessageBufSize];
    buf[0].tag = 1;		/* unused */
    buf[0].minfo.logSize = Log2MessageBufSize;
    for (int k = 0; k < Log2MessageBufSize; k++) {
	avail[k].minfo.linkf = avail[k].minfo.linkb =
	    (LAPD*)&avail[k];
	
    }
}
LAPD * LAPDMemoryManager::largestBlock() {
    for (int k = Log2MessageBufSize; k >= 0; --k) {
	if (avail[k].minfo.linkf != &avail[k]) {
	    savej = k;
	    return avail[k].minfo.linkf;
	}
    }
    return 0;
}
void LAPDMemoryManager::allocateResizeBlock(int ktemp) {
    int k, j = savej;
        // Round up to next 2**n
    for (int i = 1; i < Log2MessageBufSize; i++) {
	k = 1 << i;
	if (k > ktemp) break;
    }
    LAPD *l = avail[j].minfo.linkf;
    avail[j].minfo.linkf = l->minfo.linkf;
    l->minfo.linkf->minfo.linkb = &avail[j];
    for(l->tag = 0; j - i; ) {
	--j;
	LAPD *p = (LAPD*)(((char *)l) + (1 << j));
	p->tag = 1;
	p->minfo.logSize = j;
	p->minfo.linkf = p->minfo.linkb = &avail[j];
	avail[j].minfo.linkf = avail[j].minfo.linkb = p;
    }
}

void LAPDMemoryManager::deallocateBlock(LAPD *l, int ktemp) {
    int i;
    for (int k = 0; k < Log2MessageBufSize; k++) {
	i = 1 << k;
	if (i >= ktemp) break;
    }
    for(;;) {
	LAPD *p = buddy(k,l);
	if (k==Log2MessageBufSize || p->tag == 0 || p->minfo.logSize != k) {
	    break;
	}
	p->minfo.linkb->minfo.linkf = p->minfo.linkf;
	p->minfo.linkf->minfo.linkb = p->minfo.linkb;
	++k;
	if (p < l) l = p;
    }
    l->tag = 1;
    l->minfo.linkf = avail[k].minfo.linkf;
    avail[k].minfo.linkb = l;
    l->minfo.logSize = k;
    l->minfo.linkb = &avail[k];
    avail[k].minfo.linkf = l;
}

static LAPDMemoryManager manager;

// this operator allows one object in the LAPD
// hierarchy to overlay itself with an instance
// of one of its derived classes

inline void *operator new(size_t, LAPD* l) { return l; }

class X25: public LAPD {
    friend LAPD;
  private:
    struct X25PacketBody {
	unsigned char rep[128];
    };
    ~X25() { if (!size) size = sizeof(X25); }
    X25(char *const m): LAPD() {
        manager.allocateResizeBlock( sizeof(X25) );
        ::memcpy(&body, m, sizeof(body));
    }
    X25PacketBody body;
    
};

class EIN: public LAPD {
    friend LAPD;
  private:
    struct EINPacketBody {
	unsigned char rep[256];
    };
    ~EIN() { if (!size) size = sizeof(EIN); }
    EIN(char *const m): LAPD() {
        manager.allocateResizeBlock( sizeof(EIN) );
        ::memcpy(&body, m, sizeof(body));
    }
    EINPacketBody body;
};

void *
LAPD::operator new(size_t /* unused */) {
    return manager.largestBlock();
}

void
LAPD::operator delete(void *l) {
    manager.deallocateBlock((LAPD*)l, ((LAPD*)l)->size);
}

LAPD::LAPD(char *const bits) {
    ::memcpy(&header, bits, sizeof(header));
    performCRCCheck();
    
	// Determine type of message based on address
    switch(bits[0]) {
      case 'a':
        (void) ::new(this) X25(bits); break;
      case 'b':
        (void) ::new(this) EIN(bits); break;
      default:
	    // error("invalid message"); break;
        ;
    }
}

int main() {
    LAPD *m, *n, *o, *p;
    m = new LAPD("abcdefg");
    n = new LAPD("badfljk;adsflkj;asldf");
    delete n;
    n = new LAPD("aadflkj;sadf");
    o = new LAPD("aad;sflkj;lsdf");
    p = new LAPD("bb");
    delete p;
    delete m;
    delete n;
    delete o;
}