trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.9 2009-02-10 19:49:26 amb Exp $

 Result data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


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