void Synchrone_Init(uint8_t mac)
{
	uint8_t i;

	etat.state = WAIT_SCAN;			//first time ;initialisation
	etat.ID_Network = NO_NETWORK;		//no network at first
	etat.MAC = mac;
	etat.HOST = IS_NOT_CREATER ;
 	etat.synchrone = 0;			 

	etat.ID_Beacon = 0;
	etat.Dst = 0;
	etat.Counter = 0;
	etat.Surveille_Cnt = 0; 			 
	etat.Surveille_Cnt_Old = 0;

	InitQueue(&etat.FIFO_Send);
	InitQueue(&etat.FIFO_Recieve);

	Init_voisin(&etat);
	Init_route_table(&etat);		//reset the table of route

	for(i = 0; i<N_SLOT-2; i++){
		etat.check_old[i] = etat.check[i] = 0;
	}
}

ProcessManager* InitProcessManager( ){
	allocSpace = &procHeap;
	
	// Set mem location for procman and offset current location for further use
	ProcessManager* retval = falloc( sizeof(ProcessManager) );
	
	// Initialize the process manager with appropriate values;
	// size represents the number of priorities
	retval->readyCount = 0;
	retval->memBlockCount = 0;
	retval->msgBlockCount = 0;
	retval->size = PROC_NUMPRIORITIES;
	retval->nextPid = 1;
	retval->nullProc = NULL;
    retval->interruptProc = NULL;	
	retval->currentProc = NULL;

	
	// Allocate space for queues (4 levels each) and update current location pointer
	
	retval->ready = falloc( PROC_NUMPRIORITIES * sizeof(Queue) );
	retval->memBlock = falloc( PROC_NUMPRIORITIES * sizeof(Queue) );
	
	int i;
	
	// For each queue allocated, initialize queues
	for(i = 0; i < PROC_NUMPRIORITIES; i++ ){
		InitQueue( &(retval->ready[i]) );
		InitQueue( &(retval->memBlock[i]) );		
	}
	
	return retval;
}

/**
  Reset the input device and optionally run diagnostics

  There are 2 types of reset for USB keyboard.
  For non-exhaustive reset, only keyboard buffer is cleared.
  For exhaustive reset, in addition to clearance of keyboard buffer, the hardware status
  is also re-initialized.

  @param  This                 Protocol instance pointer.
  @param  ExtendedVerification Driver may perform diagnostics on reset.

  @retval EFI_SUCCESS          The device was reset.
  @retval EFI_DEVICE_ERROR     The device is not functioning properly and could not be reset.

**/
EFI_STATUS
EFIAPI
USBKeyboardReset (
  IN  EFI_SIMPLE_TEXT_INPUT_PROTOCOL   *This,
  IN  BOOLEAN                          ExtendedVerification
  )
{
  EFI_STATUS          Status;
  USB_KB_DEV          *UsbKeyboardDevice;

  UsbKeyboardDevice = USB_KB_DEV_FROM_THIS (This);

  REPORT_STATUS_CODE_WITH_DEVICE_PATH (
    EFI_PROGRESS_CODE,
    (EFI_PERIPHERAL_KEYBOARD | EFI_P_PC_RESET),
    UsbKeyboardDevice->DevicePath
    );

  //
  // Non-exhaustive reset:
  // only reset private data structures.
  //
  if (!ExtendedVerification) {
    REPORT_STATUS_CODE_WITH_DEVICE_PATH (
      EFI_PROGRESS_CODE,
      (EFI_PERIPHERAL_KEYBOARD | EFI_P_KEYBOARD_PC_CLEAR_BUFFER),
      UsbKeyboardDevice->DevicePath
      );
    //
    // Clear the key buffer of this USB keyboard
    //
    InitQueue (&UsbKeyboardDevice->UsbKeyQueue, sizeof (USB_KEY));
    InitQueue (&UsbKeyboardDevice->EfiKeyQueue, sizeof (EFI_KEY_DATA));
    InitQueue (&UsbKeyboardDevice->EfiKeyQueueForNotify, sizeof (EFI_KEY_DATA));

    return EFI_SUCCESS;
  }

  //
  // Exhaustive reset
  //
  Status = InitUSBKeyboard (UsbKeyboardDevice);
  if (EFI_ERROR (Status)) {
    return EFI_DEVICE_ERROR;
  }

  return EFI_SUCCESS;
}

void BFSTraverse(MGraph G)
{
    int i,j;
    Queue Q;
    for(i=0; i<G.numVertexes; i++)
        visited[i]=FALSE;
    InitQueue(&Q);
    for(i=0; i<G.numVertexes; ++i)
    {
        if(!visited[i])
        {
            visited[i]=TRUE;
            printf("%c ",G.vexs[i]);
            EnQueue(&Q,i);
            while(!QueueEmpty(Q))
            {
                DeQueue(&Q,&i);
                for(j=0; j<G.numVertexes; j++)
                {
                    if(G.arc[i][j]==1 && !visited[j])
                    {
                        visited[j]=TRUE;
                        printf("%c ",G.vexs[j]);
                        EnQueue(&Q,j);
                    }
                }
            }
        }
    }
}

/**
 * 广度优先搜索for图
 * @param {Graph}
 * @param {int} 
 */
void BFS2 (Graph G, int pos) {
  int i = 0, temp;

  Queue Q;
  InitQueue(&Q);

  for (i = 0; i < G -> vexnum; i++) {  //清零
    IsRead[i] = 0;
  }

  if(IsRead[pos] == 0) {
    IsRead[pos] = 1;
    printf("遍历顶点:%c\n",G->vertex[pos]);
  }

  EnterQueue(Q, pos);

  // 当队列不为空
  while (!isEmpty(Q)) {
    OutQueue(Q, &temp);
    for(i = 0; i< G->vexnum; i ++) {
      if(G->Arc[temp][i] != INFINITY && IsRead[i] == 0){
        IsRead[i] = 1;
        printf("遍历顶点:%c\n",G->vertex[i]);
        EnterQueue(Q,i);
      }
    }
  }

  free(Q);
}

 Status CreateBiTree(BiPTree *T)
 { /* 按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中定义）， */
   /* 构造三叉链表表示的二叉树T */
   LinkQueue q;
   QElemType a;
   Create(T); /* 构造二叉树(缺双亲指针) */
   if(*T) /* 非空树 */
   {
     (*T)->parent=NULL; /* 根结点的双亲为＂空＂ */
     InitQueue(&q); /* 初始化队列 */
     EnQueue(&q,*T); /* 根指针入队 */
     while(!QueueEmpty(q)) /* 队不空 */
     {
       DeQueue(&q,&a); /* 出队,队列元素赋给a */
       if(a->lchild) /* 有左孩子 */
       {
         a->lchild->parent=a; /* 给左孩子的双亲指针赋值 */
         EnQueue(&q,a->lchild); /* 左孩子入队 */
       }
       if(a->rchild) /* 有右孩子 */
       {
	 a->rchild->parent=a; /* 给右孩子的双亲指针赋值 */
         EnQueue(&q,a->rchild); /* 右孩子入队 */
       }
     }
   }
   return OK;
 }

 TElemType Parent(BiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
   LinkQueue q;
   QElemType a;
   if(T) /* 非空树 */
   {
     InitQueue(&q); /* 初始化队列 */
     EnQueue(&q,T); /* 树根入队 */
     while(!QueueEmpty(q)) /* 队不空 */
     {
       DeQueue(&q,&a); /* 出队,队列元素赋给a */
       if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)
       /* 找到e(是其左或右孩子) */
         return a->data; /* 返回e的双亲的值 */
       else /* 没找到e,则入队其左右孩子指针(如果非空) */
       {
         if(a->lchild)
           EnQueue(&q,a->lchild);
         if(a->rchild)
           EnQueue(&q,a->rchild);
       }
     }
   }
   return Nil; /* 树空或没找到e */
 }

void main(char** args) {
	TCB_t* threads[READER + WRITER];
	puts("initializing semaphores and threads");
	srand(time(NULL));
	mutex = malloc(sizeof(SEM_t));
	rsem = malloc(sizeof(SEM_t));
	wsem = malloc(sizeof(SEM_t));
	InitSem(mutex, 1);
	InitSem(rsem, 0);
	InitSem(wsem, 0);
	InitQueue(&runQ);
	int i = 0, j = 0, h = 0;
	while (i < READER + WRITER) {	
		int r = rand() % 2;
		if (j < READER && r == 0) {
			puts("Adding reader");
			start_thread(threads[i], reader);
			i++; j++;
		}
		if (h < WRITER && r == 1) {
			puts("Adding writer");
			start_thread(threads[i], writer);
			i++; h++;
		}
	}
	puts("runQ content:");
	printQueue(runQ);
	puts("\nstarting threads\n");
	run();
}

 static void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { // 层序遍历孩子－兄弟二叉链表结构的树T
   CSTree p;
   LinkQueue q;
   InitQueue(q);
   if(T)
   {
     Visit(Value(T)); // 先访问根结点
     EnQueue(q,T); // 入队根结点的指针
     while(!QueueEmpty(q)) // 队不空
     {
       DeQueue(q,p); // 出队一个结点的指针
       if(p->firstchild) // 有长子
       {
         p=p->firstchild;
         Visit(Value(p)); // 访问长子结点
         EnQueue(q,p); // 入队长子结点的指针
         while(p->nextsibling) // 有下一个兄弟
         {
           p=p->nextsibling;
           Visit(Value(p)); // 访问下一个兄弟
           EnQueue(q,p); // 入队兄弟结点的指针
         }
       }
     }
   }
 }

void bfs(Edge **C, int nNodes, int sink, int *sequenceList)
{
    int *colour;
    Item u, v, *p;
    Item i = 0; 
    int k = 0;
    p = (Item *)malloc(sizeof(Item));
    colour = (int *)calloc(nNodes, sizeof(int));
    colour[sink] = GRAY;
    Queue *queue = InitQueue();
    EnQueue(queue, sink);
    do {
        while (!IsEmpty(queue)) {
            DeQueue(queue, p);
            sequenceList[k++] = v = *p;
            for (u = 0; u < nNodes; u++) {
                if (colour[u] == WHITE && C[u][v].eContent > 0) {
                    EnQueue(queue, u);
                    colour[u] = GRAY;
                }
            }
            colour[v] = BLACK;
        }
        if (colour[i] == WHITE) {
            EnQueue(queue, i);
            colour[i] = GRAY;
        }
    } while(i++ < nNodes);

    free(p);
    free(colour);
    DestroyQueue(queue);
}

int main() {
	SeQueue Q;
	int data = 3, value;

	//0. Init
	InitQueue(Q);
	PrintQueue(Q);

	//1. Enter Queue
	printf("\n");
	PrintQueue(Q);
	printf("EnQueue = %d\n", data);
	EnQueue(Q, data);
	PrintQueue(Q);

	//2. DeQueue
	printf("\n");
	PrintQueue(Q);
	value = Front(Q);
	DeQueue(Q);
	printf("DeQueue value = %d\n", value);
	PrintQueue(Q);

	//3. Clear
	printf("\n");
	PrintQueue(Q);
	printf("Clear Queue\n");
	ClearQueue(Q);
	PrintQueue(Q);

	return 0;
}

int main()
{
	LinkQueue Q;
	if(InitQueue(&Q))
	{
		QElemType e;

		printf("initialize successful");
		if(IsEmpty(Q))
		{
			printf("queue is IsEmpty\n");
		}

		for (int i=0;i<10;i++)
		{
			EnQueue(&Q,i);
		}

		GetHead(Q,&e);
		printf("The head element is %d\n",e );
		printf("The length of the queue is %d\n",GetLength(Q));

		DeQueue(&Q,&e);

		printf("delete element is %d\n",e);

		TraverseQueue(Q,*visit);
		if (DestroyQueue(&Q))
		{
			printf("DestroyQueue successful\n");
		}
	}
	return 0;
}

 TElemType Parent(BiTree T,TElemType e)
 { // 初始条件: 二叉树T存在,e是T中某个结点
   // 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂
   LinkQueue q;
   QElemType a;
   if(T) // 非空树
   {
     InitQueue(q); // 初始化队列
     EnQueue(q,T); // 树根入队
     while(!QueueEmpty(q)) // 队不空
     {
       DeQueue(q,a); // 出队,队列元素赋给a
       if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e) // 找到e(是其左或右孩子)
         return a->data; // 返回e的双亲的值
       else // 没找到e,则入队其左右孩子指针(如果非空)
       {
         if(a->lchild)
           EnQueue(q,a->lchild);
         if(a->rchild)
           EnQueue(q,a->rchild);
       }
     }
   }
   return Nil; // 树空或没找到e
 }

 void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { /* 层序遍历孩子－兄弟二叉链表结构的树T */
   CSTree p;
   LinkQueue q;
   InitQueue(&q);
   if(T)
   {
     Visit(Value(T)); /* 先访问根结点 */
     EnQueue(&q,T); /* 入队根结点的指针 */
     while(!QueueEmpty(q)) /* 队不空 */
     {
       DeQueue(&q,&p); /* 出队一个结点的指针 */
       if(p->firstchild) /* 有长子 */
       {
         p=p->firstchild;
         Visit(Value(p)); /* 访问长子结点 */
         EnQueue(&q,p); /* 入队长子结点的指针 */
         while(p->nextsibling) /* 有下一个兄弟 */
         {
           p=p->nextsibling;
           Visit(Value(p)); /* 访问下一个兄弟 */
           EnQueue(&q,p); /* 入队兄弟结点的指针 */
         }
       }
     }
   }
 }

 TElemType Parent(CSTree T,TElemType cur_e)
 { /* 初始条件: 树T存在,cur_e是T中某个结点 */
   /* 操作结果: 若cur_e是T的非根结点,则返回它的双亲,否则函数值为＂空＂ */
   CSTree p,t;
   LinkQueue q;
   InitQueue(&q);
   if(T) /* 树非空 */
   {
     if(Value(T)==cur_e) /* 根结点值为cur_e */
       return Nil;
     EnQueue(&q,T); /* 根结点入队 */
     while(!QueueEmpty(q))
     {
       DeQueue(&q,&p);
       if(p->firstchild) /* p有长子 */
       {
         if(p->firstchild->data==cur_e) /* 长子为cur_e */
           return Value(p); /* 返回双亲 */
         t=p; /* 双亲指针赋给t */
         p=p->firstchild; /* p指向长子 */
         EnQueue(&q,p); /* 入队长子 */
         while(p->nextsibling) /* 有下一个兄弟 */
         {
           p=p->nextsibling; /* p指向下一个兄弟 */
	   if(Value(p)==cur_e) /* 下一个兄弟为cur_e */
	     return Value(t); /* 返回双亲 */
	   EnQueue(&q,p); /* 入队下一个兄弟 */
	 }
       }
     }
   }
   return Nil; /* 树空或没找到cur_e */
 }

extern  void    InitCG( void )
/****************************/
{
    InOptimizer = 0;
    InsId = 0;
    CurrProc = NULL;
    CurrBlock = NULL;
    BlockList = NULL;
    HeadBlock = NULL;
    BlockByBlock = FALSE;
    abortCG = FALSE;
    InitFP();/* must be before InitRegTbl */
    InitRegTbl();
    ScoreInit();
    InitQueue();
    InitMakeAddr();
    RegTreeInit();
    InitIns();
    InitConflict();
    InitRT();
    InitNames();
    ObjInit();
    ClassPointer = TypeClass( TypePtr );
    InitSegment();
}

 static TElemType Parent(CSTree T,TElemType cur_e)
 { // 初始条件: 树T存在,cur_e是T中某个结点
   // 操作结果: 若cur_e是T的非根结点,则返回它的双亲,否则函数值为＂空＂
   CSTree p,t;
   LinkQueue q;
   InitQueue(q);
   if(T) // 树非空
   {
     if(Value(T)==cur_e) // 根结点值为cur_e
       return Nil;
     EnQueue(q,T); // 根结点入队
     while(!QueueEmpty(q))
     {
       DeQueue(q,p);
       if(p->firstchild) // p有长子
       {
         if(p->firstchild->data==cur_e) // 长子为cur_e
           return Value(p); // 返回双亲
         t=p; // 双亲指针赋给t
         p=p->firstchild; // p指向长子
         EnQueue(q,p); // 入队长子
         while(p->nextsibling) // 有下一个兄弟
         {
           p=p->nextsibling; // p指向下一个兄弟
	   if(Value(p)==cur_e) // 下一个兄弟为cur_e
             return Value(t); // 返回双亲
           EnQueue(q,p); // 入队下一个兄弟
         }
       }
     }
   }
   return Nil; // 树空或没找到cur_e
 }

TElemType Parent(CSTree T, TElemType cur_e)
{
	CSTree p, t;
	LinkQueue q;

	InitQueue(q);
	if (T) {
		if (Value(T) == cur_e)
			return Nil;
		EnQueue(q, T);
		while (!QueueEmpty(q)) {
			DeQueue(q, p);
			if (p->firstchild) {
				if (p->firstchild->data == cur_e)
					return Value(p);
				t = p;
				p = p->firstchild;
				EnQueue(q, p);
				while (p->nextsibling) {
					p = p->nextsibling;
					if (Value(p) == cur_e)
						return Value(t);
					EnQueue(q, p);
				}
			}
		}
	}
	return Nil;
}

//把出现过的字符编码表经过压缩写进文件
short CodeToFile(FILE *fp,char **hc,short n,SeqQueue *Q,MyType *length)
{
    int i;
    char *p;
    MyType j,bits;
    short count=0;

    for(i = 0;i < n;i++)// 将n个叶子压缩并写入文件
    {
        for(p = hc[i]; '\0' != *p; p++)
            In_seqQueue( Q,*p );

        while(Q->length > 8)
        {
            bits = GetBits(Q);//出队8个元素
            fputc(bits,fp);
            count++;
        }
    }

    *length = Q->length;
    i = 8 - *length;
    bits = GetBits(Q);//取8个如果队不空
    for(j = 0;j < i;j++)
        bits = bits << 1;
    fputc(bits,fp);
    count++;

    InitQueue(Q);
    return count;
}

void LevelOrderTraverse(CSTree T, void (*Visit)(TElemType))
{
	CSTree p;
	LinkQueue q;

	InitQueue(q);
	if (T) {
		Visit(Value(T));
		EnQueue(q, T);
		while (!QueueEmpty(q)) {
			DeQueue(q, p);
			if (p->firstchild) {
				p = p->firstchild;
				Visit(Value(p));
				EnQueue(q, p);
				while (p->nextsibling) {
					p = p->nextsibling;
					Visit(Value(p));
					EnQueue(q, p);
				}
			}
		}
	}
	printf("\n");
}