typedef struct _MemHeapRec{
    MemHeap *heap;
    struct _MemHeapRec *next;
}MemHeapRec;
static MemHeapRec *heapList = NULL; 

void *New(MemHeap *x, size_t size) //返回从内存堆x分配大小为size的新元素指针

{
    void *q;
    BlockP newp;
    size_t num,bytes,*ip,chdr;
    Boolean noSpace;
    Ptr *pp;
    /*检查当前堆是否创建，只有没有创建的堆才会elemSize = 0*/
    if (x->elemSize <= 0)
        HError(5174, "New: heap %s not initialised",
               (x->name==NULL) ? "Unnamed" : x->name);
    switch(x->type)
    {
        case MHEAP:
 			// ATTENTION:用户每次只能申请elemSize大小的内存，但是每次申请的新block大小是num* elemSize大小的内存
            // 不论新申请的block还是已存在的满足要求的block都会被放到表头。这样每次都是从表头分配内存。
            if (size != 0 && size != x->elemSize) 
               HError(5173,"New: MHEAP req for %u size elem from heap %s size %u",
               size , x->name , x->elemSize);
             noSpace = x->totUsed == x->totAlloc; 
             if (noSpace || (q = GetElem(x->heap , x->elemSize , x->type)) == NULL)
             {	 
                 // 有空间的情况下，搜索存在至少一个空闲element的block，每次也只能分配一个element。
                 // BlockReorder遍历所有block 如果存在满足要求的block，移动到最前面。
                 if (!noSpace)
                     BlockReorder(&(x->heap), 1); 
                 // MHEAP没有空间，或者分配失败
                 if (noSpace || (q = GetElem(x->heap, x->elemSize, x->type)) == NULL)
                 {
                     // curElem记录当前最大block分配element个数，num为根据增长因子growf自适应增长后的大小，但同时被						 //maxElem约束
                     num = (size_t) ((double)x->curElem * (x->growf + 1.0) + 0.5);
                     if (num > x->maxElem)
                        num = x->maxElem;
                     // 分配新block
                     newp = AllocBlock(x->elemSize, num, x->type); 
                     // x->totAlloc和 num都是element的个数;
                     x->totAlloc += num;
                     x->curElem = num;
                     // 头插法放入表头，即新分配的block永远为第一个block
                     newp->next = x->heap;
                     x->heap = newp;
                     if ((q=GetElem(x->heap, x->elemSize, x->type)) == NULL)
                        HError(5191,"New: null elem but just made block in heap %s", x->name);
                    }
               }
               // 虽然可能分配的block很大，但是分配给用户的elem个数 = 1
               x->totUsed++;
               if (trace&T_MHP)
                   printf("HMem: %s[M] %u bytes at %p allocated\n", x->name, size, q);
             return q;
         case CHEAP:
             // 在每次申请内存时多分配一个sizeof(size_t)大小的空间：chdr，用于记录分配内存的大小。
             chdr = MRound(sizeof(size_t));
             q = malloc(size+chdr); //直接使用malloc分配
             if (q==NULL)
                 HError(5105,"New: memory exhausted");
             x->totUsed += size;
             x->totAlloc += size+chdr;
             ip = (size_t *)q;
             *ip = size;
             if (trace&T_CHP)
                 printf("HMem: %s[C] %u+%u bytes at %p allocated\n", x->name, chdr,size, q);
             return (Ptr)((ByteP)q+chdr);
          case MSTAK:
             // 用户可以申请任意大小的内存，但elementSize被限制为1bytes
             if (x->protectStk)
                size += sizeof(Ptr);
             size = MRound(size); 
            //  由于MSTACK的性质，导致每次只能从表头分配内存或者释放内存。不再有查找空余内存的动作(BlockReorder)
             if ((q = GetElem(x->heap, size, x->type)) == NULL)
			 {
                 // 每次分配bytes大小的新block
                 bytes = (size_t)((double)x->curElem * (x->growf + 1.0) + 0.5);
                 if (bytes > x->maxElem)
                     bytes = x->maxElem;
                 x->curElem = bytes;
                 // 由于bytes大小有突破x->maxElem的可能性，所以可以重新分配
                 if (bytes < size)
					 bytes = size;
                 bytes = MRound(bytes);
                 newp = AllocBlock(1, bytes, x->type);
                 x->totAlloc += bytes;
                 // 新block位置和MHEAP操作一致
                 newp->next = x->heap;
                 x->heap = newp;
                 if ((q=GetElem(x->heap, size, x->type)) == NULL)
                    HError(5191,"New: null elem but just made block in heap %s",x->name);
              }
              x->totUsed += size;
              if (trace&T_STK)
                 printf("HMem: %s[S] %u bytes at %p allocated\n", x->name, size, q);
              if (x->protectStk)
              {
                  pp = (Ptr *)((long)q + size - sizeof(Ptr));
                  *pp = q;
              }
              return q;
            }
            return NULL;

}

static void *GetElem(BlockP p, size_t elemSize, HeapType type)
{
    int i,index;
    if (p == NULL)
        return NULL;
    switch (type)
    {
	case MHEAP:
        // MHEAP由于每次只能分配一个element，所以会维护一个table:p->used，用于查找下一个空闲elem索引。
        if (p->numFree == 0)
            return NULL;
        index = p->firstFree; //第一个空闲elem index，直接分配给用户
        p->used[p->firstFree/8] |= 1<<(p->firstFree&7); //table对应索引位置flag置1
        p->numFree--;
        // 查找下一个空闲元素索引，为下一次分配elem做准备。当没有空闲元素时p->firstFree指向最后一个elem的下一个index。
        if (p->numFree > 0)
        {
            for (i=p->firstFree+1; i<p->numElem;i++)
            {
                if ((p->used[i/8] & (1 <<(i&7))) == 0)
                {
                     p->firstFree = i;
                      break;
                 }
             }
         }
         else
            p->firstFree = p->numElem;            
	     return (void *)((ByteP)p->data+index*elemSize); //返回分配的数据区指针
     case MSTAK:
         // 栈顶的block不满足要求直接返回。比较简单，因为
        if (p->numFree < elemSize) 
            return NULL;
        index = p->firstFree;
        p->firstFree += elemSize;
        p->numFree = p->numFree - elemSize;
        return (void *)((ByteP)p->data + index); //返回分配的数据区指针
     default:
        HError(5190,"GetElem: bad type %d", type);
     }
     return NULL;

}

void Dispose(MemHeap *x, void *p) //从内存堆x中释放p
{
    BlockP head , cur , prev;
    Boolean found = FALSE;
    ByteP bp;
    size_t size,chdr;
    size_t num,index, *ip;
    Ptr *pp;
    if (x->totUsed == 0)
    HError(5105 , "Dispose: heap %s is empty" , x->name);
    switch(x->type)
    {
        case MHEAP:
            // 支持链表中任意block的删除操作
            head = x->heap;
            cur=head;
            prev=NULL;
            size = x->elemSize;
            while (cur != NULL && !found)
            {
                num = cur->numElem;
                // 判断指针在该位置
                found = cur->data <= p &&(((void*)((ByteP)cur->data+(num-1)*size)) >= p);
                if (!found)
                {
                    prev=cur;
                    cur=cur->next;
                 }
             }
             if (cur == NULL)
                 HError(5175,"Dispose: Item to free in MHEAP %s not found",x->name);
            index = ((size_t)p-(size_t)cur->data)/size;
            cur->used[index/8] &= ~(1 <<(index&7));
            if (index < cur->firstFree)
                cur->firstFree = index;
            cur->numFree++;
            x->totUsed--;
            // 如果该block没有elem被使用，则释放
            if (cur->numFree == cur->numElem)
            {
                if (cur != head)
                    prev->next = cur->next;
                else
                    head = cur->next;
                x->heap = head;
                x->totAlloc -= cur->numElem;
                free(cur->data);
                free(cur->used);
                free(cur);
            }
            if (trace&T_MHP)
                printf("HMem: %s[M] %u bytes at %p de-allocated\n", x->name, size, p);
			return;
            
        case MSTAK:
            // 由于MSTACK遵从LIFO，因此要想释放掉p所在的block，需要将之前的block全部释放才能释放处于栈顶的p所在的block
            cur = x->heap;
            if (x->protectStk)
            {
                if (cur->firstFree > 0 ) 
                    pp = (Ptr *)((size_t)cur->data+cur->firstFree-sizeof(Ptr));
                else
                {
                    if (cur->next == NULL)
                        HError(5175,"Dispose: empty stack");
                    pp = (Ptr *)((size_t)cur->next->data+cur->next->firstFree-sizeof(Ptr));
                }
                if (*pp != p)
                    HError(-5175,"Dispose: violation of stack discipline in %s [%p != %p]",
                           x->name, *pp, p);
            }
            while (cur != NULL && !found)
            {
                num = cur->numElem;
                found = cur->data <= p &&
                    (((void*)((ByteP)cur->data+num)) > p);
                if (!found)
                {
                    x->heap = cur->next;
                    x->totAlloc -= cur->numElem;
                    x->totUsed -= cur->firstFree;//fristFree体现了使用量
                    free(cur->data);
                    free(cur);
                    cur = x->heap;
                    if (trace&T_STK)
                        printf("HMem: deleleting block in %s[S]\n", x->name);
                }
            }
            if (!found)
                HError(5175,"Dispose: Item to free in MSTAK %s not found", x->name);
            // CAUTION:block内同样遵循stack准则，会将p之后不属于p指针指向的内存空间一块释放掉。
            size = ((ByteP)cur->data + cur->firstFree) - (ByteP)p; //分配数据区的实际大小
            if (size < 0)
                HError( 5175 , "Dispose: item to free in MSTAK %s is above stack top",
                       x->name);
            cur->firstFree -= size;
            cur->numFree += size;
            x->totUsed -= size;
            if (trace&T_STK)
                printf("HMem: %s[S] %u bytes at %p de-allocated\n", x->name, size, p);
		return;
    case CHEAP:
        // 只需要注意释放内存时释放储存分配空间大小的chdr空间即可。
        chdr = MRound(sizeof(size_t));
        bp = (ByteP)p-chdr;
        ip = (size_t *)bp;
        x->totAlloc -= (*ip + chdr);
        x->totUsed -= *ip;
        free(bp);
        if (trace&T_CHP)
            printf("HMem: %s[C] %u+%u bytes at %p de-allocated\n",
                   x->name, chdr, *ip, bp);
        return;
   }

}