int main()
{
	struct SqList L;
	InitList(&L);
	printf("ListEmpty(L) = %d\n", ListEmpty(L));
	printSqList(L);
	
	int e;
	int index = 7;
	GetElem(L, index, &e);
	printf("the %d th number is e : %d\n", index, e);
	printf("Find %d at index %d\n", e, Locate(L, e));


	int insertNum = 100;
	ListInsert(&L, index, 100);
	printf("Insert %d at index %d  into SqList\n", insertNum, index);
	printSqList(L);

	ListDelete(&L, index, &e); 
	printf("Delete %d at index %d from SqlList\n", e, index);
	printSqList(L);
	
	printf("ListLength(L) = %d\n", ListLength(L));

    ClearList(&L);
	printf("ListEmpty(L) = %d\n", ListEmpty(L));
	printSqList(L);

	return 0;
}

/*------------------------------------------------------------------------
------------------------- Execute the photoflo ---------------------------
------------------------------------------------------------------------*/
static Bool execute(floDefPtr flo, peTexPtr importer)
{
  bandMsk ready;
  peTexPtr  pet;
  peDefPtr  ped;
  pedLstPtr lst = ListEmpty(&flo->optDAG) ? &flo->defDAG : &flo->optDAG;
  CARD32    sched_count = SCHED_BAIL_OUT;
  CARD32    strip_count = flo->floTex->putCnt;

  if(importer) {
    /* Put the ImportClient element at the head of the ready-list */
    InsertMember(importer,&flo->floTex->schedHead);
    importer->scheduled = importer->receptor[IMPORT].ready;
  }
  do {
    /* execute elements from the head of the ready-list until it's empty
     *    (calls to schedule from the data manager may prepend
     *     additional elements to the ready-list)
     */
    while(!ListEmpty(&flo->floTex->schedHead)) {
      pet = flo->floTex->schedHead.flink;
      
      if(Activate(flo,pet->peDef,pet) && (ready = runnable(flo,pet))) {
	pet->scheduled = ready;	/* remember which bands keep us alive */
      } else {
	/* element is no longer runnable, remove it and check for errors
	 */
	RemoveMember(pet,pet);
	pet->scheduled = 0;
	if(ferrCode(flo))
	  return(flo->flags.active = FALSE);
      }
      if(strip_count != flo->floTex->putCnt) {
	sched_count = SCHED_BAIL_OUT;
	strip_count = flo->floTex->putCnt;
      } else if( !--sched_count)
	ImplementationError(flo,pet->peDef, return(FALSE));
    }
    /* Load all the elements onto the ready-list that can keep producing
     * output without requiring any additional input (e.g. ImportResource
     * elements).
     */
    for(ped = lst->flink; !ListEnd(ped,lst); ped = ped->flink)
      if(ped->peTex->emitting && !ped->peTex->admissionCnt)
	InsertMember(ped->peTex,&flo->floTex->schedHead);
    /*
     *  keep on trucking if there's nothing expected from the client
     */
  } while(!flo->floTex->imports && !ListEmpty(&flo->floTex->schedHead));
  
  /* if we still have stuff to do, count another round, otherwise shut it down
   */
  if(flo->floTex->imports || flo->floTex->exports)
    ++flo->floTex->exitCnt;
  else
    ddShutdown(flo);

  return(flo->flags.active);
}                               /* end execute */

void TrapTtyRecieve(UserContext *user_context) {
    TracePrintf(TRACE_LEVEL_FUNCTION_INFO, ">>> TrapTtyRecieve(%p)\n", user_context);
    int tty_id = user_context->code;
    
    // Find the proper terminal struct
    Tty term = ttys[tty_id];
    if (ListEmpty(term.waiting_to_receive)) { 
        // no waiting procs, so create line buffer and
        // add to list
        LineBuffer *lb = calloc(1, sizeof(LineBuffer));
        lb->buffer = calloc(TERMINAL_MAX_LINE, sizeof(char));
        lb->length = TtyReceive(tty_id, lb->buffer, TERMINAL_MAX_LINE);
        ListEnqueue(term.line_buffers, lb, 0);
    } else { 
        // at least one proc waiting
        // create heap in kernel to use
        char *input = calloc(TERMINAL_MAX_LINE, sizeof(char));
        char *input_ptr = input; // point how far into the buffer we've read
        int input_length = TtyReceive(tty_id, input, TERMINAL_MAX_LINE);
        int input_remaining = input_length;

        // Continue so long as procs are waiting and there is unconsumed input
        while (!ListEmpty(term.waiting_to_receive) && input_remaining > 0) {
            PCB *waiting_proc = (PCB *) ListDequeue(term.waiting_to_receive);
            assert(waiting_proc->tty_receive_buffer);

            // put proc back into ready queue
            ListAppend(ready_queue, waiting_proc, waiting_proc->pid);

            if (input_remaining <= waiting_proc->tty_receive_len) {
                // Consuming all the input
                memcpy(waiting_proc->tty_receive_buffer, input_ptr, input_remaining);
                waiting_proc->tty_receive_len = input_remaining;
                input_remaining = 0;
            } else {
                // Only consuming some of the input
                memcpy(waiting_proc->tty_receive_buffer, input_ptr, waiting_proc->tty_receive_len);
                input_remaining -= waiting_proc->tty_receive_len;
                input_ptr += waiting_proc->tty_receive_len;
            }
        }

        // Check if there is still input left after all the procs have been filled
        if (input_remaining > 0) {
            // Create new line buffer and store
            char *remaining_buff = calloc(input_remaining, sizeof(char));
            memcpy(remaining_buff, input_ptr, input_remaining);
            LineBuffer *lb = calloc(1, sizeof(LineBuffer));
            lb->buffer = remaining_buff;
            lb->length = input_remaining;
            ListEnqueue(term.line_buffers, lb, 0);
        }

        free(input);
    }
    TracePrintf(TRACE_LEVEL_FUNCTION_INFO, "<<< TrapTtyRecieve(%p)\n", user_context);
}

void TrapTtyTransmit(UserContext *user_context) {
    TracePrintf(TRACE_LEVEL_FUNCTION_INFO, ">>> TrapTtyTransmit(%p)\n", user_context);
    int tty_id = user_context->code;
    Tty term = ttys[tty_id];
    assert(!ListEmpty(term.waiting_to_transmit));

    // Get the currently transmitting proc (always at the front of the list)
    PCB *waiting_proc = (PCB *) ListPeak(term.waiting_to_transmit);
    if (waiting_proc->tty_transmit_len > TERMINAL_MAX_LINE) { 
        // not completely transmitted, so handle pointer stuff and leave in
        // front of the queue
        waiting_proc->tty_transmit_pointer += TERMINAL_MAX_LINE;
        waiting_proc->tty_transmit_len -= TERMINAL_MAX_LINE;

        // transmit min(MAX_LINE, len)
        if (TERMINAL_MAX_LINE > waiting_proc->tty_transmit_len) {
            TtyTransmit(tty_id, waiting_proc->tty_transmit_pointer,
                waiting_proc->tty_transmit_len);
        } else {
            TtyTransmit(tty_id, waiting_proc->tty_transmit_pointer,
                TERMINAL_MAX_LINE);
        }

        return;
    }

    // transmission complete
    // since done, take off transmitting list
    ListRemoveById(term.waiting_to_transmit, waiting_proc->pid);
    ListAppend(ready_queue, waiting_proc, waiting_proc->pid);
    free(waiting_proc->tty_transmit_buffer);

    if (ListEmpty(term.waiting_to_transmit)) {
        return; // no other procs waiting on this term
    }

    // Get the next proc waiting to submit
    PCB *next_to_transmit = (PCB *) ListPeak(term.waiting_to_transmit);
    // transmit min(MAX_LINE, len)
    if (TERMINAL_MAX_LINE > next_to_transmit->tty_transmit_len) {
        TtyTransmit(tty_id, next_to_transmit->tty_transmit_pointer,
            next_to_transmit->tty_transmit_len);
    } else {
        TtyTransmit(tty_id, next_to_transmit->tty_transmit_pointer,
            TERMINAL_MAX_LINE);
    }

    TracePrintf(TRACE_LEVEL_FUNCTION_INFO, "<<< TrapTtyTransmit(%p)\n", user_context);
}

void main()
{
	DLinkList *h;
	ElemType e;
	printf("(1)初始化循环双链表h\n");
	InitList(h);
	printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(h,1,'a');
	ListInsert(h,2,'b');
	ListInsert(h,3,'c');
	ListInsert(h,4,'d');
	ListInsert(h,5,'e');
	printf("(3)输出循环双链表h:");
	DispList(h);
	printf("(4)循环双链表h长度=%d\n",ListLength(h));
	printf("(5)循环双链表h为%s\n",(ListEmpty(h)?"空":"非空"));
	GetElem(h,3,e);
	printf("(6)循环双链表h的第3个元素=%c\n",e);
	printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
	printf("(8)在第4个元素位置上插入f元素\n");
	ListInsert(h,4,'f');
	printf("(9)输出循环双链表h:");
	DispList(h);
	printf("(10)删除h的第3个元素\n");
    	ListDelete(h,3,e);
	printf("(11)输出循环双链表h:");
	DispList(h);
	printf("(12)释放循环双链表h\n");
	DestroyList(h);
}

int main(void)
{
    /// create list
    SqList List;
    InitList(&List);
    /// insert element to list
    ListInsert(&List, 1, 1);
    ListInsert(&List, 2, 2);
    ListInsert(&List, 3, 3);
    ListInsert(&List, 4, 4);
    ListInsert(&List, 5, 5);
    /// locate element
    printf("element %d is in %d\n", 4, LocateElem(&List, 4));
    /// list length
    int length = ListLength(&List);
    printf("List length is %d\n", length);
    /// get list element
    int i, element;
    for (i = 1; i <= length; i++) {
        GetElem(&List, i, &element);
        printf("element in %d is %d\n", i, element);
    }
    /// delect element from list
    ListDelete(&List, 4, &element);
    printf("deleted element in %d is %d\n", 4, element);
    /// clear list
    ClearList(&List);
    printf("List empty is %d\n", ListEmpty(&List));
    return EXIT_SUCCESS;
}

Link *GetLast(LinkList linklist) {
	Link *t; 							//不根据linklist.tail直接获得，通过遍历链表得到最后一个
	if (ListEmpty(linklist) == true)
		return NULL;					//如果是空表，则没有最后一个，返回ERROR
	for (t = linklist.head; t->next; t = t->next); //一直走到头，返回该节点
	return t;
}

bool TestListInsertAfter(List *list)
{
    ListDeleteAll(list); // Already tested
    if (!ListEmpty(list)) {
        sprintf(error, "This test requires list to be empty");
        return false;
    }

    int i;
    int k = 5;
    for (i = length-k; i < length; i++)
        ListAppend(list, numbers[i]); // Already tested
    for (i = k - 1; i >= 0; i--)
        ListPrepend(list, numbers[i]); // Already tested

    ListItor itor = ListHead(list);
    for (i = 0; i < k-1; i++)
        itor = ListItorNext(itor);
    for (i = length - k - 1; i >= k; i--)
        if (!ListInsertAfter(itor, numbers[i])) {
            sprintf(error, "ListInsertAfter failed");
            return false;
        }
    if (!VerifyListConsistency(list)) {
        sprintf(error, "List is not consistent with numbers after ListInsertAfter");
        return false;
    }
    return true;
}

void Bank_simulation(int CloseTime){
	//银行业务模拟，统计一天内客户在银行的逗留时间
	//全局变量
	static Event en;//事件表
	static EvenList ev;//事件
	static LinkQueue q[5];//4个客户列队
	static QElemType customer;//客户记录
	static int TotalTime,CustomerNum;//累计逗留时间，客户数
	//变量结束
	EvenList p,e;
	OpenForDay(TotalTime,CustomerNum,en,ev,q);
	while(!ListEmpty(ev)){
		e=GetHead(ev);
		DelFirst(e,p);
		
		en=GetCurElem(p);

		if(en.NType==0)
			CustomerArrived(CloseTime,CustomerNum,en,ev,q);
		else CustomerDeparture(en,ev,q,customer,TotalTime);

		if(TotalTime>CloseTime)break;
	}
	printf("%0.2f\n",(float)TotalTime/CustomerNum);
}

int main(void)
{
	ElemType site[11] = { 'a', 'n', 'o', 't', 'h', 'e', 'r', 'h', 'o', 'm', 'e' };
	LinkList *Link, *LinkR;
	ElemType e;

	CreateListF(Link, site, 11);
	CreateListR(LinkR, site, 11);
	DispList(Link);
	DispList(LinkR);
	DestroyList(LinkR);
	if (ListEmpty(Link))
	{
		printf("List is empty\n");
	}
	else
	{
		printf("List isn't empty\n");
	}
	printf("ListLength: %d\n", ListLength(Link));
	GetElem(Link, ListLength(Link), e);
	ListInsert(Link, 2, e);
	DispList(Link);
	ListDelete(Link, 3, e);
	DispList(Link);
	printf("The location of 'o' is %d\n", LocateElem(Link, 'o'));
	DestroyList(Link);

	return 0;
}

////////////////////////////////////////////////////
// 功能: 等待DMA结束
// 输入: 
// 输出:
// 返回: 
// 说明: 
////////////////////////////////////////////////////
static void DacWaiteDmaEnd()
{
	int i,time;
	PRESAMPLE presample;

	if( ListEmpty(&DacList) )
		return;

	kdebug(mod_audio, PRINT_INFO, "DacWaiteDmaEnd start\n");
	presample = &DacDevice;
	time = 0;
	while(1)
	{

		for( i = 0 ; i < MAX_PCMBUFS ; i++ )
		{
			if( presample->BufFlag[i] != DAC_BUF_WRITE )
				break;
		}
		if( i == MAX_PCMBUFS )
			break;

		sTimerSleep(10,NULL);
		time++;
		if( time > 40 )
			break;
		if( GetDacChannel() != 1 )
			break;
	}

	kdebug(mod_audio, PRINT_INFO, "DacWaiteDmaEnd end\n");
	return;
}

////////////////////////////////////////////////////
// 功能: 结束某一任务的媒体播放，并锁定媒体播放任务
// 输入:
// 输出:
// 返回:
// 说明:
////////////////////////////////////////////////////
void MediaTerminateLock(HANDLE htask)
{
	PMEDIA_OBJECT obj;
	PLIST list;
	
	kMutexWait(hMediaMutex);
	list = &MediaObjList;
	if(!ListEmpty(list))
	{
		// 获取正在音频任务节点
		obj = ListEntry(ListFirst(list), MEDIA_OBJECT, Link);
		
		if(obj->hTask == htask)
		{
			// 结束当前正在录放的音频任务
			obj->Cb.MediaClose(obj->Media, 1);
			obj->Cb.MediaDestroy(obj->Media);
			
			ListRemove(&obj->Link);
			HandleDestroy(obj->Header.Handle, MEDIA_MAGIC);
			if(obj->MediaInfo)
				kfree(obj->MediaInfo);
			kfree(obj);
		}
	}
}

void main()
{
	SqList *L;
	ElemType e;
	printf("(1)初始化顺序表L\n");
	InitList(L);
	printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(L,1,'a');
	ListInsert(L,2,'b');
	ListInsert(L,3,'c');
	ListInsert(L,4,'d');
	ListInsert(L,5,'e');
	printf("(3)输出顺序表L:");
	DispList(L);
	printf("(4)顺序表L长度=%d\n",ListLength(L));
	printf("(5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));
	GetElem(L,3,e);
	printf("(6)顺序表L的第3个元素=%c\n",e);
	printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));
	printf("(8)在第4个元素位置上插入f元素\n");
	ListInsert(L,4,'f');
	printf("(9)输出顺序表L:");
	DispList(L);
	printf("(10)删除L的第3个元素\n");
    	ListDelete(L,3,e);
	printf("(11)输出顺序表L:");
	DispList(L);
	printf("(12)释放顺序表L\n");
	DestroyList(L);
}

// add only at the end. see there are approaches to find end; one is to use pnext and the other is
// to use count. 
bool AddList( List* list, EntryType entry )
{
  Node* pnode, *pend;

  if( (pnode = MakeNode(entry)) == NULL )
  {
    std::cout << "add: mem is full" << std::endl;
    return false;
  }

  if( ListEmpty( list ) )
  {
    list->header = pnode;
  }
  else
  {
#ifdef USE_PNEXT
    // search the end using pnext
    for( pend = list->header; pend->pnext; pend = pend->pnext )
      ;
#else
    // search the end using count
    pend = list->header;
    for( int current = 1; current < list->count; current++) // note that less than
      pend = pend->pnext;
#endif

    pend->pnext = pnode;
  }

  list->count++;

  return true;
}

/* Free the previous list of games.
 */
static void
GameListFree (List *gameList)
{
  while (!ListEmpty(gameList))
    {
	GameListDeleteGame((ListGame *) gameList->head);
    }
}

TEST(ListTest, checkEmpty) {
  List list;
  CreatList(&list);

  EXPECT_EQ( 1, ListEmpty(&list) );

  // to make fail
  // EXPECT_EQ( 0, ListEmpty(&list) );     // note: line #112 
}

int main()
{
    List list;
    InitList(&list);
    printf("创建线性表后线性表的当前长度:%d\n", list.length);  
    printf("ListTraverse:");
    
    //initialize
    int j;
    for(j = 0; j < 10; j++) {
        list.elem[j] = j;
        list.length++;  
    }
    printf("after sqlist inited: %d=====%d\n", list.listsize, list.length);

    //test DestoryList
    /*DestoryList(&list);
    printf("After Destory List %d=====%d\n", list.listsize, list.length);*/

    //test ListEmpty(List *list);
    printf("Is List Empty? %s\n", ListEmpty(&list) ? "true" : "false");

    //test GetElem(List *list, int i, ElemType *e)
    ElemType e1;
    if(GetElem(&list, 3, &e1) ) {
        printf("Get index 3 element from list: %d\n", e1);
    }
    
    /*for(j = 0; j < list.length; j++) {
        if(list.elem[j] == 3)
            printf("i found %d in list index %d\n", 3, j);
    }*/

    //test LocateElem
    ElemType e2 = 3;
    int position = LocateElem(&list, &e2);
    printf("%d\n", position);
    if (position >= 0)
        printf("I find e2 in list, it's index is %d\n", position);
    else 
        printf("Not Found!\n");
    
    //test ListInsert(List *list, int i, ElemType *e);
    ElemType e3 = 100;
    if(ListInsert(&list, 2, &e3)) {
        ListTraverse(&list);
    }

    //test BOOL ListDelete
    ElemType e4;
    if(ListDelete(&list, 2, &e4)) {
        printf("Delete index %d ElemType %d success\n", 1, e4);
    }
    ListTraverse(&list);

    return 0;
}

// 说明：获取下一个就就绪任务
// 返回：如果没有，返回NULL
static TASK* TaskNextReady(void)
{
    // 如果存在下一个就绪任务
    if (!ListEmpty(&list_ready_tasks) && 
        list_ready_tasks.next != &current_task->list_ready) {
        return LIST_ENTRY(list_ready_tasks.next, TASK, list_ready);
    }
    return NULL;
}

////////////////////////////////////////////////////
// 功能: 测试程序
// 输入: 
// 输出:
// 返回: 
// 说明: 
////////////////////////////////////////////////////
void DacClearPcmData()
{
	PRESAMPLE presample;

	//判断是否存在播放设备
	if( ListEmpty(&DacList) )
	{
		//kdebug(mod_audio, PRINT_WARNING, "dac list is null\n");
		return;
	}


	switch( fBeginDma )
	{
		case INIT_DMA_TRANS:	//初始化阶段，数据处于不确定状态，放静音
		case PAUSE_DMA_TRANS:	//暂停状态，放静音
		case STOP_DMA_TRANS:	//停止状态，放静音
			StartDmaPcmTrans(1,0);
			break;
		case END_DMA_TRANS:		//播放完成，停止触发新的DMA
			break;
		case RUNING_DMA_TRANS:
			//声音正常播放，DMA数据正常播放
			presample = &DacDevice;
			//		PrintfDacStatus(presample);
			switch(presample->BufFlag[presample->ReadBuf])
			{
				case DAC_BUF_WRITE:
					//当前读取BUF，没有数据，直接放静音
					StartDmaPcmTrans(1,0);
					break;
				case DAC_BUF_READ:
					//当前数据BUF，有数据，开始播放数据，同时把BUF属性定义成READING
					StartDmaPcmTrans(0,(unsigned int)presample->Buf[presample->ReadBuf]);
					presample->BufFlag[presample->ReadBuf] = DAC_BUF_READING;
					break;
				case DAC_BUF_READING:
					if( nMplayerDelay >= DAC_PCMBUF_SIZE )
						nMplayerDelay -= DAC_PCMBUF_SIZE;

					presample->BufFlag[presample->ReadBuf] = DAC_BUF_WRITE;
					if(++presample->ReadBuf == MAX_PCMBUFS )
						presample->ReadBuf = 0;

					if( presample->BufFlag[presample->ReadBuf] == DAC_BUF_READ )
					{
						StartDmaPcmTrans(0,(unsigned int)presample->Buf[presample->ReadBuf]);
						presample->BufFlag[presample->ReadBuf] = DAC_BUF_READING;
					}
					else
						StartDmaPcmTrans(1,0);
					break;
			}
			break;
	}
}

////////////////////////////////////////////////////
// 功能: 
// 输入: 
// 输出:
// 返回: 
// 说明: 
////////////////////////////////////////////////////
int DacClose(HANDLE hdac)
{
	PDAC_DEVICE dac;

	kMutexWait(hDacMutex);
	dac = (PDAC_DEVICE)hdac;
	kdebug(mod_audio, PRINT_INFO, "dac error data number = %d\n",nErrorData);
	if(dac)
	{
		ListRemove(&dac->Link);
		if(ListEmpty(&DacList))
		{
			//MillinsecoundDelay(20);

			SetMuteMode(0);

			//关闭功放
			SetPowerAmplifier(0);

			//MillinsecoundDelay(20);

			SetMoseCe(0);

			// 关闭耳机设备
			DacHeadphoneClose();		

			// 关闭DA设备
			DacDeviceClose();

			// 没有这个耳机会有爆破音.
			//MillinsecoundDelay(20);
		}

		DacDestorySamplerate(dac);	//释放resample数据
		DacDestoryWsola(hdac);		//释放wsola数据
#ifdef DAC_SAVE_PCM
		{
			HANDLE fp;
			fp = kfopen("d:\\pcm.bin","w+b");
			kfwrite(dac_buf,1,dac_offset,fp);
			kfclose(fp);

			fp = kfopen("d:\\source.bin","w+b");
			kfwrite(dac_source_buf,1,dac_source_offset,fp);
			kfclose(fp);
		}
#endif
		kfree(dac);
		kMutexRelease(hDacMutex);
		return 0;
	}
	nErrorData = 0;
	kMutexRelease(hDacMutex);
	return -1;
}