trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.10 2009-04-08 16:54:34 amb Exp $

 Result 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 <assert.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"


#define RESULTS_INCREMENT    16
#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};


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *NewResultsList Returns the results list.

  int nbins The number of bins in the results array.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(int nbins)
{
 Results *results;
 int i;

 results=(Results*)malloc(sizeof(Results));

 results->nbins=1;
 results->mask=~0;

 while(nbins>>=1)
   {
    results->mask<<=1;
    results->nbins<<=1;
   }

 results->mask=~results->mask;

 results->alloced=RESULTS_INCREMENT;
 results->number=0;

 results->count=(uint32_t*)malloc(results->nbins*sizeof(uint32_t));
 results->point=(Result***)malloc(results->nbins*sizeof(Result**));

 for(i=0;i<results->nbins;i++)
   {
    results->count[i]=0;

    results->point[i]=(Result**)malloc(results->alloced*sizeof(Result*));
   }

 results->data=(Result**)malloc(1*sizeof(Result*));
 results->data[0]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));

 return(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *results The results list to be destroyed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeResultsList(Results *results)
{
 int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
 int i;

 for(i=c;i>=0;i--)
    free(results->data[i]);

 free(results->data);

 for(i=0;i<results->nbins;i++)
    free(results->point[i]);

 free(results->point);

 free(results->count);

 free(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert a new result into the results data structure in the right order.

  Result *insert_result Returns the result that has been inserted.

  Results *results The results structure to insert into.

  index_t node The node that is to be inserted into the results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *InsertResult(Results *results,index_t node)
{
 int bin=node&results->mask;
 int i;

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

 if(results->count[bin]==results->alloced)
   {
    results->alloced+=RESULTS_INCREMENT;

    for(i=0;i<results->nbins;i++)
       results->point[i]=(Result**)realloc((void*)results->point[i],results->alloced*sizeof(Result*));
   }

 if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
   {
    int c=results->number/(results->nbins*RESULTS_INCREMENT);

    results->data=(Result**)realloc((void*)results->data,(c+1)*sizeof(Result*));
    results->data[c]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
   }

 /* Insert the new entry */

 results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbins*RESULTS_INCREMENT)][results->number%(results->nbins*RESULTS_INCREMENT)];

 results->number++;

 results->count[bin]++;

 return(results->point[bin][results->count[bin]-1]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result; search by node.

  Result *insert_result Returns the result that has been found.

  Results *results The results structure to search.

  index_t node The node that is to be found.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FindResult(Results *results,index_t node)
{
 int bin=node&results->mask;
 int i;

 for(i=results->count[bin]-1;i>=0;i--)
    if(results->point[bin][i]->node==node)
       return(results->point[bin][i]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *FirstResult Returns the first results from a set of results.

  Results *results The set of results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FirstResult(Results *results)
{
 return(&results->data[0][0]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *NextResult Returns the next result from a set of results.

  Results *results The set of results.

  Result *result The previous result.
  ++++++++++++++++++++++++++++++++++++++*/

Result *NextResult(Results *results,Result *result)
{
 int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
 int i,j=0;

 for(i=0;i<=c;i++)
   {
    j=(result-results->data[i]);

    if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
       break;
   }

 if(++j>=(results->nbins*RESULTS_INCREMENT))
   {i++;j=0;}

 if((i*(results->nbins*RESULTS_INCREMENT)+j)>=results->number)
    return(NULL);

 return(&results->data[i][j]);
}


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

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

void insert_in_queue(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 *pop_from_queue Returns the top item.

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

Result *pop_from_queue()
{
 if(queue.number)
    return(queue.xqueue[--queue.number]);
 else
    return(NULL);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/results.c,v 1.10 2009-04-08 16:54:34 amb Exp $
3
4	Result 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 <assert.h>
26	#include <string.h>
27	#include <stdlib.h>
28
29	#include "results.h"
30
31
32	#define RESULTS_INCREMENT 16
33	#define QUEUE_INCREMENT 10240
34
35
36	/+ A queue of results. +/
37	typedef struct _Queue
38	{
39	uint32_t alloced; /+ The amount of space allocated for results in the array. +/
40	uint32_t number; /+ The number of occupied results in the array. +/
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	Allocate a new results list.
51
52	Results *NewResultsList Returns the results list.
53
54	int nbins The number of bins in the results array.
55	++++++++++++++++++++++++++++++++++++++*/
56
57	Results *NewResultsList(int nbins)
58	{
59	Results *results;
60	int i;
61
62	results=(Results*)malloc(sizeof(Results));
63
64	results->nbins=1;
65	results->mask=~0;
66
67	while(nbins>>=1)
68	{
69	results->mask<<=1;
70	results->nbins<<=1;
71	}
72
73	results->mask=~results->mask;
74
75	results->alloced=RESULTS_INCREMENT;
76	results->number=0;
77
78	results->count=(uint32_t)malloc(results->nbinssizeof(uint32_t));
79	results->point=(Result**)malloc(results->nbinssizeof(Result**));
80
81	for(i=0;i<results->nbins;i++)
82	{
83	results->count[i]=0;
84
85	results->point[i]=(Result*)malloc(results->allocedsizeof(Result*));
86	}
87
88	results->data=(Result*)malloc(1sizeof(Result*));
89	results->data[0]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
90
91	return(results);
92	}
93
94
95	/*++++++++++++++++++++++++++++++++++++++
96	Allocate a new results list.
97
98	Results *results The results list to be destroyed.
99	++++++++++++++++++++++++++++++++++++++*/
100
101	void FreeResultsList(Results *results)
102	{
103	int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
104	int i;
105
106	for(i=c;i>=0;i--)
107	free(results->data[i]);
108
109	free(results->data);
110
111	for(i=0;i<results->nbins;i++)
112	free(results->point[i]);
113
114	free(results->point);
115
116	free(results->count);
117
118	free(results);
119	}
120
121
122	/*++++++++++++++++++++++++++++++++++++++
123	Insert a new result into the results data structure in the right order.
124
125	Result *insert_result Returns the result that has been inserted.
126
127	Results *results The results structure to insert into.
128
129	index_t node The node that is to be inserted into the results.
130	++++++++++++++++++++++++++++++++++++++*/
131
132	Result InsertResult(Results results,index_t node)
133	{
134	int bin=node&results->mask;
135	int i;
136
137	/* Check that the arrays have enough space. */
138
139	if(results->count[bin]==results->alloced)
140	{
141	results->alloced+=RESULTS_INCREMENT;
142
143	for(i=0;i<results->nbins;i++)
144	results->point[i]=(Result*)realloc((void)results->point[i],results->allocedsizeof(Result));
145	}
146
147	if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
148	{
149	int c=results->number/(results->nbins*RESULTS_INCREMENT);
150
151	results->data=(Result*)realloc((void)results->data,(c+1)sizeof(Result));
152	results->data[c]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
153	}
154
155	/* Insert the new entry */
156
157	results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbinsRESULTS_INCREMENT)][results->number%(results->nbinsRESULTS_INCREMENT)];
158
159	results->number++;
160
161	results->count[bin]++;
162
163	return(results->point[bin][results->count[bin]-1]);
164	}
165
166
167	/*++++++++++++++++++++++++++++++++++++++
168	Find a result; search by node.
169
170	Result *insert_result Returns the result that has been found.
171
172	Results *results The results structure to search.
173
174	index_t node The node that is to be found.
175	++++++++++++++++++++++++++++++++++++++*/
176
177	Result FindResult(Results results,index_t node)
178	{
179	int bin=node&results->mask;
180	int i;
181
182	for(i=results->count[bin]-1;i>=0;i--)
183	if(results->point[bin][i]->node==node)
184	return(results->point[bin][i]);
185
186	return(NULL);
187	}
188
189
190	/*++++++++++++++++++++++++++++++++++++++
191	Find a result from a set of results.
192
193	Result *FirstResult Returns the first results from a set of results.
194
195	Results *results The set of results.
196	++++++++++++++++++++++++++++++++++++++*/
197
198	Result FirstResult(Results results)
199	{
200	return(&results->data[0][0]);
201	}
202
203
204	/*++++++++++++++++++++++++++++++++++++++
205	Find a result from a set of results.
206
207	Result *NextResult Returns the next result from a set of results.
208
209	Results *results The set of results.
210
211	Result *result The previous result.
212	++++++++++++++++++++++++++++++++++++++*/
213
214	Result NextResult(Results results,Result *result)
215	{
216	int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
217	int i,j=0;
218
219	for(i=0;i<=c;i++)
220	{
221	j=(result-results->data[i]);
222
223	if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
224	break;
225	}
226
227	if(++j>=(results->nbins*RESULTS_INCREMENT))
228	{i++;j=0;}
229
230	if((i(results->nbinsRESULTS_INCREMENT)+j)>=results->number)
231	return(NULL);
232
233	return(&results->data[i][j]);
234	}
235
236
237	/*++++++++++++++++++++++++++++++++++++++
238	Insert an item into the queue in the right order.
239
240	Result *result The result to insert into the queue.
241	++++++++++++++++++++++++++++++++++++++*/
242
243	void insert_in_queue(Result *result)
244	{
245	int start=0;
246	int end=queue.number-1;
247	int mid;
248	int insert=-1;
249
250	/* Check that the array is allocated. */
251
252	if(!queue.xqueue)
253	{
254	queue.alloced=QUEUE_INCREMENT;
255	queue.number=0;
256	queue.xqueue=(Result*)malloc(queue.allocedsizeof(Result*));
257	}
258
259	/* Check that the arrays have enough space. */
260
261	if(queue.number==queue.alloced)
262	{
263	queue.alloced+=QUEUE_INCREMENT;
264	queue.xqueue=(Result*)realloc((void)queue.xqueue,queue.allocedsizeof(Result));
265	}
266
267	/* Binary search - search key may not match, new insertion point required
268	*
269	* # <- start \| Check mid and move start or end if it doesn't match
270	* # \|
271	* # \| Since there may not be an exact match we must set end=mid
272	* # <- mid \| or start=mid because we know that mid doesn't match.
273	* # \|
274	* # \| Eventually end=start+1 and the insertion point is before
275	* # <- end \| end (since it cannot be before the initial start or end).
276	*/
277
278	if(queue.number==0) /* There is nothing in the queue */
279	insert=0;
280	else if(result->sortby>queue.xqueue[start]->sortby) /* Check key is not before start */
281	insert=start;
282	else if(result->sortby<queue.xqueue[end]->sortby) /* Check key is not after end */
283	insert=end+1;
284	else if(queue.number==2) /* Must be between them */
285	insert=1;
286	else
287	{
288	do
289	{
290	mid=(start+end)/2; /* Choose mid point */
291
292	if(queue.xqueue[mid]->sortby>result->sortby) /* Mid point is too low */
293	start=mid;
294	else if(queue.xqueue[mid]->sortby<result->sortby) /* Mid point is too high */
295	end=mid;
296	else /* Mid point is correct */
297	{
298	if(queue.xqueue[mid]==result)
299	return;
300
301	insert=mid;
302	break;
303	}
304	}
305	while((end-start)>1);
306
307	if(insert==-1)
308	insert=end;
309	}
310
311	/* Shuffle the array up */
312
313	if(insert!=queue.number)
314	memmove(&queue.xqueue[insert+1],&queue.xqueue[insert],(queue.number-insert)sizeof(Result));
315
316	/* Insert the new entry */
317
318	queue.xqueue[insert]=result;
319
320	queue.number++;
321	}
322
323
324	/*++++++++++++++++++++++++++++++++++++++
325	Pop an item from the end of the queue.
326
327	Result *pop_from_queue Returns the top item.
328
329	Results *results The set of results that the queue is processing.
330	++++++++++++++++++++++++++++++++++++++*/
331
332	Result *pop_from_queue()
333	{
334	if(queue.number)
335	return(queue.xqueue[--queue.number]);
336	else
337	return(NULL);
338	}