void InterruptHandler(int interrupt, PCBPtr pcbRequest)
{
	switch (interrupt)
	{
	//if i/o request
	case 1:
		aCPU->runningPCB->state = 2;
		int number = rand() % 2;
		if((aCPU->IO1->owner == NULL) && (number == 1) ||
		   (aCPU->IO1->owner == NULL && aCPU->IO2->owner != NULL)) {
			printf("\nP%d moved to I/O1 device", aCPU->runningPCB->pid);
			aCPU->IO1->owner = aCPU->runningPCB;
		}
		else if((aCPU->IO2->owner == NULL) && (number == 0) ||
		   (aCPU->IO2->owner == NULL && aCPU->IO1->owner != NULL)) {
			printf("\nP%d moved to I/O2 device", aCPU->runningPCB->pid);
			aCPU->IO2->owner = aCPU->runningPCB;
		}
		else {
			printf("\nP%d moved to IO Queue", aCPU->runningPCB->pid);
			enqueue(aCPU->IoQueue, aCPU->runningPCB);
		}
		aCPU->runningPCB = dequeue(ReadyQPtr);
		aCPU->runningPCB->state = 0;
		printf("\nP%d selected from ready queue", aCPU->runningPCB->pid);
	break;
	//if keyboard request
	case 2:
		if(aCPU->Keyboard->keyboardFree == 1) {
			aCPU->runningPCB->state = 3;
			enqueue(aCPU->Keyboard->Blocked, aCPU->runningPCB);
			KBHASPCB = 1;
			printf("\nP%d was moved to the Keyboard's blocked queue", aCPU->runningPCB->pid);
		} else {
			aCPU->Keyboard->keyboardFree = 1;
			printf("\nP%d is now the Keyboard device's owner", aCPU->runningPCB->pid);
			aCPU->Keyboard->owner = aCPU->runningPCB;
			aCPU->runningPCB->state = 3;
		}
		aCPU->runningPCB = dequeue(ReadyQPtr);
		aCPU->runningPCB->state = 0;
		printf("\nP%d selected from ready queue", aCPU->runningPCB->pid);
	break;
	//if i/o 1 complete
	case 3:
		IO1INT = 0;
		printf("\nP%d's I/O interrupt complete", pcbRequest->pid);
		printf("\nP%d moved from I/O1 to ready queue", pcbRequest->pid);
		pcbRequest->state = 1;
		enqueue(ReadyQPtr, pcbRequest);

		if(aCPU->IoQueue->count != 0 && aCPU->IoQueue->first != aCPU->IoQueue->last ) {
			PCBPtr pcbPtr = dequeue(aCPU->IoQueue);
			printf("\nP%d moved from IO Queue, now owner of I/O1", pcbPtr->pid);
			aCPU->IO1->owner = pcbPtr;
			aCPU->IO1->IOAvailable = 1;
		} else {
			aCPU->IO1->IOAvailable = 0;
			aCPU->IO1->owner = NULL;
		}
	break;
	//if i/o 2 complete
	case 4:
		IO2INT = 0;
		printf("\nP%d's I/O interrupt complete", pcbRequest->pid);
		printf("\nP%d moved from I/O2 to ready queue", pcbRequest->pid);
		pcbRequest->state = 1;
		enqueue(ReadyQPtr, pcbRequest);

		if(aCPU->IoQueue->count != 0 && aCPU->IoQueue->first != aCPU->IoQueue->last) {
			PCBPtr pcbPtr = dequeue(aCPU->IoQueue);
			printf("\nP%d moved from IO Queue, now owner of I/O2", pcbPtr->pid);
			aCPU->IO2->owner = pcbPtr;
			aCPU->IO2->IOAvailable = 1;
		} else {
			aCPU->IO2->owner = NULL;
			aCPU->IO2->IOAvailable = 0;
		}
	break;
	//if keyboard complete
	case 5:
		KBINT = 0;
		enqueue(ReadyQPtr, pcbRequest);
		if(aCPU->Keyboard->Blocked->count != 0) {
			aCPU->Keyboard->owner = dequeue(aCPU->Keyboard->Blocked);
			aCPU->Keyboard->keyboardFree = 1;
			printf("\nKeyboard owner given to P%d", aCPU->Keyboard->owner->pid);
		} else {
			aCPU->Keyboard->owner = NULL;
			aCPU->Keyboard->keyboardFree = 0;
			KBHASPCB = 0;
		}
	break;
	//if  producer or consumer request for mutex
	case 6:
		//printf("\nMutex request made by P%d", aCPU->runningPCB->pid);

		//if (pthread_mutex_trylock(&(mutex[pcbRequest->sharedMemInd])) == 0) {
		//if (MutexMem[aCPU->runningPCB->sharedMemInd]->mutexLocked == 0) {
		//	printf("\nM%d is now locked by P%d", aCPU->runningPCB->sharedMemInd, aCPU->runningPCB->pid);
//.........这里部分代码省略.........

 // yield::EventHandler
 void handle(YO_NEW_REF Event& event) {
   enqueue(event);
 }

int kfork(char *filename)
{
  PROC *p;
  int  i, child;
  u16 word;
  u16  segment;

  /*** get a PROC for child process: ***/
  if ( (p = get_proc(&freeList)) == 0){
       printf("no more proc\n");
       return(-1);
  }

  /* initialize the new proc and its stack */
  p->status = READY;
  p->ppid = running->pid;
  p->parent = running;
  p->priority  = 1;                 // all of the same priority 1

  /******* write C code to to do THIS YOURSELF ********************
     Initialize p's kstack AS IF it had called tswitch() 
     from the entry address of body():

   HI   -1  -2    -3  -4   -5   -6   -7   -8    -9                LOW
      -------------------------------------------------------------
      |body| ax | bx | cx | dx | bp | si | di |flag|
      ------------------------------------------------------------
                                                ^
                                    PROC.ksp ---|

  ******************************************************************/

  // fill in resume address
  p->kstack[SSIZE-1] = (int)body;

  // save stack TOP address in PROC
  p->ksp = &(p->kstack[SSIZE - 9]);


  enqueue(&readyQueue, p);
 
  // make Umode image by loading /bin/u1 into segment
  segment = (p->pid + 1)*0x2000;
  load(filename, segment);

  /*************** WRITE C CODE TO DO THESE ******************
     Initialize new proc's ustak AS IF it had done INT 80
     from virtual address 0:

    HI  -1  -2  -3  -4  -5  -6  -7  -8  -9 -10 -11 -12
       flag uCS uPC uax ubx ucx udx ubp usi udi ues uds
     0x0200 seg  0   0   0   0   0   0   0   0  seg seg
                                                     ^
    PROC.uss = segment;           PROC.usp ----------|
 
  ***********************************************************/

	for (i = 1; i < 13; ++i)
	{
		switch(i) 
		{
			case 1:   word = 0x0200;  break;  // uFlag
			case 2:
			case 11:
			case 12:  word = segment; break;  // uCS, uES, uDS
			default:  word = 0;       break;  // pretty much everything else
		}

		put_word(word, segment, 0x2000-i*2);  // stack starts at highest end of segment
	}
	
    p->uss = segment;
    p->usp = 0x2000 - 24; // usp is byte address, x2

  printf("Proc%d forked a child %d segment=%x\n", running->pid,p->pid,segment);
  return(p->pid);
}

// test
int main() {
  struct node* queue = new_queue();
  queue = enqueue(queue, 1);
  queue = enqueue(queue, 2);
  print_list(queue);
}

void task::exec_internal()
{
    task_state READY_STATE = TASK_STATE_READY;
    task_state RUNNING_STATE = TASK_STATE_RUNNING;

    if (_state.compare_exchange_strong(READY_STATE, TASK_STATE_RUNNING))
    {
        task* parent_task = nullptr;
        if (tls_task_info.magic == 0xdeadbeef)
        {
            parent_task = tls_task_info.current_task;
        }
        else
        {
            set_current_worker(nullptr);
        }
        
        tls_task_info.current_task = this;

        _spec->on_task_begin.execute(this);

        exec();
        
        if (_state.compare_exchange_strong(RUNNING_STATE, TASK_STATE_FINISHED))
        {
            _spec->on_task_end.execute(this);

            // signal_waiters(); [
            // inline for performance
            void* evt = _wait_event.load();
            if (evt != nullptr)
            {
                auto nevt = (utils::notify_event*)evt;
                nevt->notify();
            }
            // ]
        }

        // for timer
        else
        {
            if (!_wait_for_cancel)
            {
                _spec->on_task_end.execute(this);
                enqueue();
            }   
            else
            {
                _state.compare_exchange_strong(READY_STATE, TASK_STATE_CANCELLED);
                _spec->on_task_end.execute(this);

                // signal_waiters(); [
                // inline for performance
                void* evt = _wait_event.load();
                if (evt != nullptr)
                {
                    auto nevt = (utils::notify_event*)evt;
                    nevt->notify();
                }
                // ]
            }
        }
        
        tls_task_info.current_task = parent_task;
    }

    if (!_spec->allow_inline && !_is_null)
    {
        service::lock_checker::check_dangling_lock();
    }
}

void* handle_client(void* args) 
{ 	
	int quit;
	client_t* newClient;
	int n;
	
	char *buffer1;
	char *buffer;
	char *newLineMessage;
	
	
	buffer=malloc(sizeof(char)*MAXMSG);/*store message coming from client*/
	
	
	
	quit=0;
	
	
	n=0;
	while(!quit){
	
	newClient=(client_t*)args;
	
	/*received data from client*/
	
	
	
	
	/*if message is bigger than the MAXMSG have to read more than ones because tcp it store and only sent when it read again.*/
	n=recvfrom(newClient->sd,buffer,MAXMSG,0,(struct sockaddr *)&(newClient->cliaddr),&(newClient->clilen));
	
	if (n == 0||n==-1) {
		/*n==0 connection is closed or n==-1 something wrong with client connection close the connection and put index -1 in client array I wont free that passion in array.I suppose it just wastage  of time.*/
		clients[newClient->index]->index=-1;
		close(newClient->sd);
		
		quit=1;
		
    		printf("Connection closed.\n");
    		
		
  	}
  	else{
		buffer[strlen(buffer)]='\0';
		newLineMessage=malloc(sizeof(char)*1000);/*message which is read line by line if it is big message and send line by line*/
		newLineMessage=strtok(buffer,"\n");
		sem_wait(&space);
		while (newLineMessage != NULL){
				/*read by line by  line and store in queue atthe same time put some headers about who send this message */
				buffer1=malloc(sizeof(char)*1000);/*message to be store in queue */
				strcpy(buffer1,newLineMessage);
				newLineMessage[0]='\0';
				strcat(buffer1,"\n");
				buffer1[strlen(buffer1)]='\0';
				
				
				/*put lock here to avoid race condition because If same time two thread(client) are accessed queue is going to be a big problem. */
				sem_wait(&enter);
				enqueue(buffer1);
				sem_post(&enter);
				newLineMessage= strtok(NULL,"\n");
				
  		}

		
		
		sem_post(&signalB);
	
	}
	}

	return NULL;	 
}

void OutPacketBuffer::enqueueWord(u_int32_t word) {
  u_int32_t nWord = htonl(word);
  enqueue((unsigned char*)&nWord, 4);
}

void OutPacketBuffer::useOverflowData() {
  enqueue(&fBuf[fPacketStart + fOverflowDataOffset], fOverflowDataSize);
  fCurOffset -= fOverflowDataSize; // undoes increment performed by "enqueue"
  resetOverflowData();
}

void stackPush(struct node **top,int x){
	enqueue(top,x); //push value to queue
	count++; //get no of elements added to queue
		
}

void housekeep() {
    usb_task(); 	// service periodic usb functions
    while (usb_cdc_kbhit() && (nqueue(&rxque0) < HIBUF)) {
	enqueue(&rxque0, usb_cdc_getc());
    }
}

int AllocateInputBuffer(FrameBufferManager* fbm, VencAllocateBufferParam *buffer_param)
{
	int result = 0;
	int i= 0;

	if(!fbm)
	{
		return -1;
	}

	fbm->ABM_inputbuffer.buffer_num = buffer_param->nBufferNum;	
	fbm->ABM_inputbuffer.allocate_buffer = (VencInputBufferInfo*) \
												calloc(sizeof(VencInputBufferInfo),
												buffer_param->nBufferNum);

	if(!fbm->ABM_inputbuffer.allocate_buffer)
	{
		loge("allocate_buffer error");
		return -1;
	}

	fbm->size_y = buffer_param->nSizeY;
	fbm->size_c = buffer_param->nSizeC;

	memset(fbm->ABM_inputbuffer.allocate_buffer, 0, sizeof(VencInputBufferInfo)*buffer_param->nBufferNum);

	for(i=0; i<(int)buffer_param->nBufferNum; i++) {
		fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.nID  = i;
		fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY = \
								(unsigned char *)EncAdapterMemPalloc(fbm->size_y);
		if(!fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY)
		{
			loge("ABM_inputbuffer Y alloc error");
			break;
		}
		
		fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrPhyY = \
			(unsigned char *)EncAdapterMemGetPhysicAddressCpu(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY);

		EncAdapterMemFlushCache(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY, fbm->size_y);

		if(fbm->size_c > 0)
		{
			fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC = \
						  (unsigned char *)EncAdapterMemPalloc((int)fbm->size_c);
			if(!fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC)
			{
				loge("ABM_inputbuffer C alloc error");
				break;
			}
			
			fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrPhyC = \
				(unsigned char *)EncAdapterMemGetPhysicAddressCpu(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC);
			EncAdapterMemFlushCache(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC, fbm->size_c);
		}
	}

	if(i < (int)buffer_param->nBufferNum) 
	{
		for(i=0; i<(int)buffer_param->nBufferNum; i++) 
		{
			if(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY)
			{
			    EncAdapterMemPfree(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirY);
			}

			if(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC)
			{
			    EncAdapterMemPfree(fbm->ABM_inputbuffer.allocate_buffer[i].inputbuffer.pAddrVirC);
			}
		}

		free(fbm->ABM_inputbuffer.allocate_buffer);
		fbm->ABM_inputbuffer.allocate_buffer = NULL;
		return -1;
	}

	// all allocate buffer enquene
	for(i=0; i<(int)buffer_param->nBufferNum; i++) 
	{
		enqueue(&fbm->ABM_inputbuffer.allocate_queue,&fbm->ABM_inputbuffer.allocate_buffer[i]);
	}

	pthread_mutex_init(&fbm->ABM_inputbuffer.mutex, NULL);

	return 0;
}

int main(void) {
  char buf[BUFSIZE];
  char canvas[N][N];
  int i,j;
  elemtype point,pos;
  struct queue que;
  initqueue(&que);
  
  for (i = 0; i < N; i++) {
    fgets(buf, BUFSIZE, stdin);
    for (j = 0; j < N && (buf[j] != '\n' && buf[j] != '\0'); j++)
      canvas[i][j] = buf[j];
    while (j < N) canvas[i][j++] = ' ';
  }

  point.x=point.y=N/2;
  canvas[point.y][point.x]=C;
  enqueue(&que,point);

  while(!queueempty(&que)){
    point=dequeue(&que);
    if(point.y!=0){
      if(canvas[point.y-1][point.x]==' '){
	pos.x=point.x;
	pos.y=point.y-1;
	enqueue(&que,pos);
	canvas[pos.y][pos.x]=C;
      }
    }
    if(point.x!=0){
      if(canvas[point.y][point.x-1]==' '){
	pos.x=point.x-1;
	pos.y=point.y;
	enqueue(&que,pos);
	canvas[pos.y][pos.x]=C;
      }
    }
    if(point.y!=N-1){
      if(canvas[point.y+1][point.x]==' '){
	pos.x=point.x;
	pos.y=point.y+1;
	enqueue(&que,pos);
	canvas[pos.y][pos.x]=C;
      }
    }
    if(point.x!=N-1){
      if(canvas[point.y][point.x+1]==' '){
	pos.x=point.x+1;
	pos.y=point.y;
	enqueue(&que,pos);
	canvas[pos.y][pos.x]=C;
      }
    }
  }

  for(i=0;i<N;i++){
    for(j=0;j<N;j++)printf("%c",canvas[i][j]);
    printf("\n");
  }
  return 0;
}

//.........这里部分代码省略.........
				if (condVar[m]->pcbQueue->count > 0)
				{
					printf("\nCV%d - ", m);
					printQueue(condVar[m]->pcbQueue);
				}
			}
		}
		//Keyboard
		//printf();
		printf("\n-------------------------");
		
		if(interruptOccurred == 0)
		{
			if(aCPU->runningPCB->curr_count > WAIT_TIME)
			{
				runForCount = WAIT_TIME;
			}
		} 
		else
		{
			runForCount = aCPU->runningPCB->curr_count;
		}
		runForCount = rand() % 7;
		
		while(runForCount > 0)
		{
			runForCount--;
			aCPU->runningPCB->curr_count++;
			if (aCPU->runningPCB->curr_count == WAIT_TIME) TIMERINT = 1;
			interruptOccurred = (IO1INT || IO2INT || KBINT || TIMERINT);

			if (interruptOccurred)
			{
				if(TIMERINT)
				{
					InterruptHandler( 7, aCPU->runningPCB);
					runForCount = 0;
				}
				if(IO1INT) InterruptHandler( 3, aCPU->IO1->owner);
				if(IO2INT) InterruptHandler( 4, aCPU->IO2->owner);
				if(KBINT) InterruptHandler( 5, aCPU->Keyboard->owner);
			}
			int processType = aCPU->runningPCB->process->proc_type;
			if ((processType == 0) && (runForCount != 0))
			{
				if (runForCount == 1)
				{
					TIMERINT = 1;
				}
			}
			else if ((processType == 1) && (runForCount != 0))
			{
				int i;
				for(i = 0; i < aCPU->runningPCB->process->no_requests; i++)
				{
					if ( (rand() % 10) == (rand() % 10) )
					{
						aCPU->runningPCB->state = 2;
						aCPU->runningPCB->curr_count = runForCount;
						runForCount = 0;
						InterruptHandler( 1, aCPU->runningPCB);
					}
					else if ( runForCount == 1 )
					{
						TIMERINT = 1;
					}
				}
			}
			else if ((processType == 2) && (runForCount != 0))
			{
				InterruptHandler( 2, aCPU->runningPCB);
				runForCount = 0;
			}
			else if ((processType == 3) || (processType == 4) && (runForCount != 0))
			{
				if(processType == 3)
				{
					pthread_create(&aCPU->producer_thread[aCPU->runningPCB->sharedMemInd], NULL, incCount, (void *) aCPU->runningPCB);
				}
				else if (processType == 4)
				{
					pthread_create(&aCPU->consumer_thread[aCPU->runningPCB->sharedMemInd], NULL, resetCount, (void *) aCPU->runningPCB);
				}
				aCPU->runningPCB->state = 1;
				printf("\nP%d returned to ready queue", aCPU->runningPCB->pid);
				enqueue(ReadyQPtr, aCPU->runningPCB);
				aCPU->runningPCB = dequeue(ReadyQPtr);
				printf("\nP%d selected from ready queue", aCPU->runningPCB->pid);
				runForCount = 0;
			}
			aCPU->count--;
			if (aCPU->count == 0)
			{
			cpuRunning = 0;
			KBDevDestructor(aCPU->Keyboard);
			pthread_exit(NULL);
			}
		}
	}
}

int main()
{
    int i,j,V,E;

    FILE* fp=fopen("graph.txt","r"); //for sample graph at http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

    printf("Enter no. of vertices and edges : ");
    fscanf(fp,"%d%d",&V,&E);
    //scanf("%d%d",&V,&E);
    printf("V=%d, E=%d\n",V,E);

    //int from[20];
    //int to[20];

    int a,b,c;

    int adj[MAX][MAX];



     for(i=0;i<=V;i++)
     {
        for(j=0;j<=V;j++)
        {
            adj[i][j]=-1;
        }
     }

    for(i=1;i<=E;i++)
    {
        fscanf(fp,"%d%d%d",&a,&b,&c);//alphabetical, undirected edges (source, destination, weight)
        //scanf("%d%d%d",&a,&b,&c);
        adj[a][b]=c;
        adj[b][a]=c;
        //printf("%d %d %d\n",a,b,c);
    }

    //starting node=0



   /* for(i=0;i<=V;i++)
    {
        for(j=0;j<=V;j++)
        {
            printf("%d ",adj[i][j]);
        }
        printf("\n");
    } */

    int distance[MAX];
    int visited[MAX]={0};
    for(i=1;i<=V;i++)
    {
        distance[i]=999999;//infinity
    }
    distance[0]=0;
    int count=0;

    Q.front=-1;
    Q.rear=-1;

    int k=0;
    enqueue(k);


    while(count<=V)
    {
        k=dequeue();
        for(i=0;i<V;i++)
        {
            if(adj[k][i]>=0 && visited[i]==0)
            {
                //printf("dk=%d,di+adj[k][i]=%d\n",distance[k],distance[i]+adj[k][i]);
                distance[i]=min(distance[i],distance[k]+adj[k][i]);
                enqueue(i);
            }
        }
        visited[k]=1;
        count++;

    }

    for(i=0;i<V;i++)
        printf("%d %d\n",i,distance[i]);

    return 0;
}

/* Compute the shift for each trie node, as well as the delta
   table and next cache for the given keyword set. */
const char *
kwsprep (kwset_t kws)
{
  register struct kwset *kwset;
  register int i;
  register struct trie *curr;
  register char const *trans;
  unsigned char delta[NCHAR];

  kwset = (struct kwset *) kws;

  /* Initial values for the delta table; will be changed later.  The
     delta entry for a given character is the smallest depth of any
     node at which an outgoing edge is labeled by that character. */
  memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);

  /* Check if we can use the simple boyer-moore algorithm, instead
     of the hairy commentz-walter algorithm. */
  if (kwset->words == 1 && kwset->trans == NULL)
    {
      char c;

      /* Looking for just one string.  Extract it from the trie. */
      kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
      if (!kwset->target)
	return "memory exhausted";
      for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
	{
	  kwset->target[i] = curr->links->label;
	  curr = curr->links->trie;
	}
      /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
      for (i = 0; i < kwset->mind; ++i)
	delta[U(kwset->target[i])] = kwset->mind - (i + 1);
      /* Find the minimal delta2 shift that we might make after
	 a backwards match has failed. */
      c = kwset->target[kwset->mind - 1];
      for (i = kwset->mind - 2; i >= 0; --i)
	if (kwset->target[i] == c)
	  break;
      kwset->mind2 = kwset->mind - (i + 1);
    }
  else
    {
      register struct trie *fail;
      struct trie *last, *next[NCHAR];

      /* Traverse the nodes of the trie in level order, simultaneously
	 computing the delta table, failure function, and shift function. */
      for (curr = last = kwset->trie; curr; curr = curr->next)
	{
	  /* Enqueue the immediate descendents in the level order queue. */
	  enqueue(curr->links, &last);

	  curr->shift = kwset->mind;
	  curr->maxshift = kwset->mind;

	  /* Update the delta table for the descendents of this node. */
	  treedelta(curr->links, curr->depth, delta);

	  /* Compute the failure function for the descendants of this node. */
	  treefails(curr->links, curr->fail, kwset->trie);

	  /* Update the shifts at each node in the current node's chain
	     of fails back to the root. */
	  for (fail = curr->fail; fail; fail = fail->fail)
	    {
	      /* If the current node has some outgoing edge that the fail
		 doesn't, then the shift at the fail should be no larger
		 than the difference of their depths. */
	      if (!hasevery(fail->links, curr->links))
		if (curr->depth - fail->depth < fail->shift)
		  fail->shift = curr->depth - fail->depth;

	      /* If the current node is accepting then the shift at the
		 fail and its descendents should be no larger than the
		 difference of their depths. */
	      if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
		fail->maxshift = curr->depth - fail->depth;
	    }
	}

      /* Traverse the trie in level order again, fixing up all nodes whose
	 shift exceeds their inherited maxshift. */
      for (curr = kwset->trie->next; curr; curr = curr->next)
	{
	  if (curr->maxshift > curr->parent->maxshift)
	    curr->maxshift = curr->parent->maxshift;
	  if (curr->shift > curr->maxshift)
	    curr->shift = curr->maxshift;
	}

      /* Create a vector, indexed by character code, of the outgoing links
	 from the root node. */
      for (i = 0; i < NCHAR; ++i)
	next[i] = NULL;
      treenext(kwset->trie->links, next);

//.........这里部分代码省略.........

void compress()
{
	Hashtable *ht = createHashtable();
	linkedList *charBits = newLinkedList();
    FILE *file = fopen("file.txt", "r");
    FILE *backp = fopen("backp.txt","w");
    FILE *backp2 = fopen("backp2.txt","w");
    PriorityQueue * queue = createPriorityQueue();
    int characters[256],i,count=0,j,count2=0;
    unsigned char currentChar;
    memset(characters,0,sizeof(characters));

    if (file == NULL)
    {
        printf ("ERROR 404: FILE NOT FOUND\n");
        exit(0);
    }
    else
    {
        do
        {
            currentChar = fgetc(file);
            if(currentChar == UNSIGNED_EOF)
            {
                break;
            }
            characters[currentChar]++;
            count2++;
        }
        while(currentChar != UNSIGNED_EOF);
    }
    for(i=0; i < UNSIGNED_EOF; i++)
    {
        if(characters[i]!=0)
        {
            count++;
            enqueue(queue,i,characters[i],NULL);
        }
    }
    for(j = count ; j>1 ; j--)
    {
        dequeue(queue);
    }
	generateBits(ht, charBits, returnBT(queue));
	freeBT(returnBT(queue));
	rewind(file);
	do
    {
        currentChar = fgetc(file);
        if(currentChar == UNSIGNED_EOF)
        {
            break;
        }
        fprintf(backp,"%s",get(ht,currentChar));
    }
    while(currentChar != UNSIGNED_EOF);

    fprintf(backp2,"%d\n",count); // SALVA QUANTAS LINHAS DE HASH TERÁ NO ARQUIVO

    for(i=0; i < UNSIGNED_EOF; i++)
    {
        if(characters[i]!=0)
        {
            fprintf(backp2,"%c %s\n",i,get(ht,i)); //SALVA QUAL CARACTERE E O SEU CODIGO ASCII REDUZIDO NA HASH
        }
    }
    fprintf(backp2,"%d\n",count2); // SALVA A QUANTIDADE DE CHARS QUE EXISTIRÃO
    fclose(backp);
    writeCompressedData(backp2);
	fclose(backp2);
    fclose(file);
    rename("backp2.txt","compressed.txt");
    remove("backp.txt");
}

void LLObjectMediaDataClient::fetchMedia(LLMediaDataClientObject *object)
{
	// Create a get request and put it in the queue.
	enqueue(new RequestGet(object, this));
}

/*
 * Opens a file and processes it.  Each file is processed line-by-line
 * passing the lines to procline().
 */
int
procfile(const char *fn)
{
	struct file *f;
	struct stat sb;
	struct str ln;
	mode_t s;
	int c, t;

	mcount = mlimit;

	if (strcmp(fn, "-") == 0) {
		fn = label != NULL ? label : getstr(1);
		f = grep_open(NULL);
	} else {
		if (!stat(fn, &sb)) {
			/* Check if we need to process the file */
			s = sb.st_mode & S_IFMT;
			if (s == S_IFDIR && dirbehave == DIR_SKIP)
				return (0);
			if ((s == S_IFIFO || s == S_IFCHR || s == S_IFBLK
				|| s == S_IFSOCK) && devbehave == DEV_SKIP)
					return (0);
		}
		f = grep_open(fn);
	}
	if (f == NULL) {
		file_err = true;
		if (!sflag)
			warn("%s", fn);
		return (0);
	}

	ln.file = grep_malloc(strlen(fn) + 1);
	strcpy(ln.file, fn);
	ln.line_no = 0;
	ln.len = 0;
	linesqueued = 0;
	tail = 0;
	ln.off = -1;

	for (c = 0;  c == 0 || !(lflag || qflag); ) {
		ln.off += ln.len + 1;
		if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL || ln.len == 0) {
			if (ln.line_no == 0 && matchall)
				exit(0);
			else
				break;
		}
		if (ln.len > 0 && ln.dat[ln.len - 1] == '\n')
			--ln.len;
		ln.line_no++;

		/* Return if we need to skip a binary file */
		if (f->binary && binbehave == BINFILE_SKIP) {
			grep_close(f);
			free(ln.file);
			free(f);
			return (0);
		}
		/* Process the file line-by-line */
		if ((t = procline(&ln, f->binary)) == 0 && Bflag > 0) {
			enqueue(&ln);
			linesqueued++;
		}
		c += t;
		if (mflag && mcount <= 0)
			break;
	}
	if (Bflag > 0)
		clearqueue();
	grep_close(f);

	if (cflag) {
		if (!hflag)
			printf("%s:", ln.file);
		printf("%u\n", c);
	}
	if (lflag && !qflag && c != 0)
		printf("%s%c", fn, nullflag ? 0 : '\n');
	if (Lflag && !qflag && c == 0)
		printf("%s%c", fn, nullflag ? 0 : '\n');
	if (c && !cflag && !lflag && !Lflag &&
	    binbehave == BINFILE_BIN && f->binary && !qflag)
		printf(getstr(8), fn);

	free(ln.file);
	free(f);
	return (c);
}

// Fill the staging area with a minimal chunk of input ranges.
int mergestream::prime()
{
	if (dbg & 4)
		printf("#entering mergestream::prime()\n");
	if (!empty())
		return 1;
	int brkok = 1;			// is it OK to break after the last
					// VBOX that was added to the stage?
	int needheight = -1;		// minimum acceptable height of the
					// chunk being constructed on stage
	// If the range at the head of any queue is breaking,
	// deal with it first.
	if (squeue.more() && squeue.current()->breaking())
		enqueue(squeue.dequeue());
	else if (bfqueue.more() && (bfqueue.current()->breaking() ||
		(bfqueue.serialno() < squeue.serialno())))
		enqueue(bfqueue.dequeue());
	else if (ufqueue.more() && (ufqueue.current()->breaking() ||
		(ufqueue.serialno() < squeue.serialno())))
		enqueue(ufqueue.dequeue());
	else while (squeue.more()) {
		// Fill the stage with enough ranges to be a valid chunk.
		range *r = squeue.dequeue();
		if (r->isvbox()) {	// VBOX
			if (dbg & 16)
				printf("#VBOX: !empty: %d; brkok: %d; vsince: %d\n",
					!empty(), brkok, currpage->vsince);
			if (!empty()	// there's something there
				&& brkok
					// it's OK to break here
				&& currpage->vsince >= 2
					// enough stream has gone onto this page
				&& rawht() >= needheight
					// current need has been satisfied
				) {
					// the stage already contains enough
					// ranges, so this one can wait
				r->enqueue();
				break;
			} else {
				if (r->rawht() > 0) {
					++currpage->vsince;
					brkok = r->brkafter();
				}
				enqueue(r);
			}
		} else if (r->isnested() || r->issp()) {	// US, SP
			if (!empty() && rawht() >= needheight) {
					// enough already, wait
				r->enqueue();
				break;
			}
			currpage->vsince = 0;
			enqueue(r);
			if (height() >= needheight)
				break;
		} else if (r->isneed()) {	// NE
			if (!empty() && rawht() >= needheight) {
					// not currently working on an unsatisfied NEed 
				r->enqueue();
				break;
			}
					// deal with overlapping NEeds
			needheight = rawht() + max(needheight - rawht(), r->needht());
			enqueue(r);
		} else if (r->forceflush() == NO) {
			enqueue(r);
		} else if (r->forceflush() == YES) {
			currpage->vsince = 0;
			if (!empty()) {
					// ready or not, r must wait
				r->enqueue();
				break;
			}
			enqueue(r);
			break;
		} else
			ERROR "unexpected  %s[%s] in prime(), line %d\n",
				r->type_name(), r->headstr(), r->lineno() FATAL;
	}
	return more();			// 0 if nothing was staged
}

int scheduler(){
	if (running->status == READY)
		enqueue(&readyQueue, running);
	//enqueue(running, &readyQueue);
	running = dequeue(&readyQueue);
}