trunk/src/queue.c

/***************************************
 $Header: /home/amb/CVS/routino/src/queue.c,v 1.1 2009-07-23 17:34:59 amb Exp $

 Queue data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <sys/types.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"

/*+ The size of the increment for the Queue data structure. +*/
#define QUEUE_INCREMENT   10240


/*+ A queue of results. +*/
typedef struct _Queue
{
 uint32_t  alloced;             /*+ The amount of space allocated for results in the array. +*/
 uint32_t  number;              /*+ The number of occupied results in the array. +*/

 Result  **xqueue;              /*+ An array of pointers to parts of the results structure. +*/
}
 Queue;

/*+ The queue of nodes. +*/
static Queue queue={0,0,NULL};


/*++++++++++++++++++++++++++++++++++++++
  Insert an item into the queue in the right order.

  Result *result The result to insert into the queue.
  ++++++++++++++++++++++++++++++++++++++*/

void InsertInQueue(Result *result)
{
 int start=0;
 int end=queue.number-1;
 int mid;
 int insert=-1;

 /* Check that the array is allocated. */

 if(!queue.xqueue)
   {
    queue.alloced=QUEUE_INCREMENT;
    queue.number=0;
    queue.xqueue=(Result**)malloc(queue.alloced*sizeof(Result*));
   }

 /* Check that the arrays have enough space. */

 if(queue.number==queue.alloced)
   {
    queue.alloced+=QUEUE_INCREMENT;
    queue.xqueue=(Result**)realloc((void*)queue.xqueue,queue.alloced*sizeof(Result*));
   }

 /* Binary search - search key may not match, new insertion point required
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since there may not be an exact match we must set end=mid
  *  # <- mid    |  or start=mid because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually end=start+1 and the insertion point is before
  *  # <- end    |  end (since it cannot be before the initial start or end).
  */

 if(queue.number==0)                                 /* There is nothing in the queue */
    insert=0;
 else if(result->sortby>queue.xqueue[start]->sortby) /* Check key is not before start */
    insert=start;
 else if(result->sortby<queue.xqueue[end]->sortby)   /* Check key is not after end */
    insert=end+1;
 else if(queue.number==2)                            /* Must be between them */
    insert=1;
 else
   {
    do
      {
       mid=(start+end)/2;                                /* Choose mid point */

       if(queue.xqueue[mid]->sortby>result->sortby)      /* Mid point is too low */
          start=mid;
       else if(queue.xqueue[mid]->sortby<result->sortby) /* Mid point is too high */
          end=mid;
       else                                              /* Mid point is correct */
         {
          if(queue.xqueue[mid]==result)
             return;

          insert=mid;
          break;
         }
      }
    while((end-start)>1);

    if(insert==-1)
       insert=end;
   }

 /* Shuffle the array up */

 if(insert!=queue.number)
    memmove(&queue.xqueue[insert+1],&queue.xqueue[insert],(queue.number-insert)*sizeof(Result*));

 /* Insert the new entry */

 queue.xqueue[insert]=result;

 queue.number++;
}


/*++++++++++++++++++++++++++++++++++++++
  Pop an item from the end of the queue.

  Result *PopFromQueue Returns the top item.

  Results *results The set of results that the queue is processing.
  ++++++++++++++++++++++++++++++++++++++*/

Result *PopFromQueue()
{
 if(queue.number)
    return(queue.xqueue[--queue.number]);
 else
    return(NULL);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/queue.c,v 1.1 2009-07-23 17:34:59 amb Exp $
3
4	Queue data type functions.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008,2009 Andrew M. Bishop
9
10	This program is free software: you can redistribute it and/or modify
11	it under the terms of the GNU Affero General Public License as published by
12	the Free Software Foundation, either version 3 of the License, or
13	(at your option) any later version.
14
15	This program is distributed in the hope that it will be useful,
16	but WITHOUT ANY WARRANTY; without even the implied warranty of
17	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18	GNU Affero General Public License for more details.
19
20	You should have received a copy of the GNU Affero General Public License
21	along with this program. If not, see <http://www.gnu.org/licenses/>.
22	***************************************/
23
24
25	#include <sys/types.h>
26	#include <string.h>
27	#include <stdlib.h>
28
29	#include "results.h"
30
31	/+ The size of the increment for the Queue data structure. +/
32	#define QUEUE_INCREMENT 10240
33
34
35	/+ A queue of results. +/
36	typedef struct _Queue
37	{
38	uint32_t alloced; /+ The amount of space allocated for results in the array. +/
39	uint32_t number; /+ The number of occupied results in the array. +/
40
41	Result *xqueue; /+ An array of pointers to parts of the results structure. +*/
42	}
43	Queue;
44
45	/+ The queue of nodes. +/
46	static Queue queue={0,0,NULL};
47
48
49	/*++++++++++++++++++++++++++++++++++++++
50	Insert an item into the queue in the right order.
51
52	Result *result The result to insert into the queue.
53	++++++++++++++++++++++++++++++++++++++*/
54
55	void InsertInQueue(Result *result)
56	{
57	int start=0;
58	int end=queue.number-1;
59	int mid;
60	int insert=-1;
61
62	/* Check that the array is allocated. */
63
64	if(!queue.xqueue)
65	{
66	queue.alloced=QUEUE_INCREMENT;
67	queue.number=0;
68	queue.xqueue=(Result*)malloc(queue.allocedsizeof(Result*));
69	}
70
71	/* Check that the arrays have enough space. */
72
73	if(queue.number==queue.alloced)
74	{
75	queue.alloced+=QUEUE_INCREMENT;
76	queue.xqueue=(Result*)realloc((void)queue.xqueue,queue.allocedsizeof(Result));
77	}
78
79	/* Binary search - search key may not match, new insertion point required
80	*
81	* # <- start \| Check mid and move start or end if it doesn't match
82	* # \|
83	* # \| Since there may not be an exact match we must set end=mid
84	* # <- mid \| or start=mid because we know that mid doesn't match.
85	* # \|
86	* # \| Eventually end=start+1 and the insertion point is before
87	* # <- end \| end (since it cannot be before the initial start or end).
88	*/
89
90	if(queue.number==0) /* There is nothing in the queue */
91	insert=0;
92	else if(result->sortby>queue.xqueue[start]->sortby) /* Check key is not before start */
93	insert=start;
94	else if(result->sortby<queue.xqueue[end]->sortby) /* Check key is not after end */
95	insert=end+1;
96	else if(queue.number==2) /* Must be between them */
97	insert=1;
98	else
99	{
100	do
101	{
102	mid=(start+end)/2; /* Choose mid point */
103
104	if(queue.xqueue[mid]->sortby>result->sortby) /* Mid point is too low */
105	start=mid;
106	else if(queue.xqueue[mid]->sortby<result->sortby) /* Mid point is too high */
107	end=mid;
108	else /* Mid point is correct */
109	{
110	if(queue.xqueue[mid]==result)
111	return;
112
113	insert=mid;
114	break;
115	}
116	}
117	while((end-start)>1);
118
119	if(insert==-1)
120	insert=end;
121	}
122
123	/* Shuffle the array up */
124
125	if(insert!=queue.number)
126	memmove(&queue.xqueue[insert+1],&queue.xqueue[insert],(queue.number-insert)sizeof(Result));
127
128	/* Insert the new entry */
129
130	queue.xqueue[insert]=result;
131
132	queue.number++;
133	}
134
135
136	/*++++++++++++++++++++++++++++++++++++++
137	Pop an item from the end of the queue.
138
139	Result *PopFromQueue Returns the top item.
140
141	Results *results The set of results that the queue is processing.
142	++++++++++++++++++++++++++++++++++++++*/
143
144	Result *PopFromQueue()
145	{
146	if(queue.number)
147	return(queue.xqueue[--queue.number]);
148	else
149	return(NULL);
150	}