trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.2 2009-01-17 17:49:58 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"


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

  Results *NewResultsList Returns the results list.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(void)
{
 Results *results;
#if NBINS_RESULTS
 int i;
#endif

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

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

#if NBINS_RESULTS
 for(i=0;i<NBINS_RESULTS;i++)
   {
    results->numbin[i]=0;

    results->offsets[i]=(uint32_t*)malloc(results->alloced*sizeof(uint32_t));
   }

 results->results=(Result*)malloc(results->alloced*NBINS_RESULTS*sizeof(Result));
#else
 results->offsets=(uint32_t*)malloc(results->alloced*sizeof(uint32_t));

 results->data=(Result*)malloc(results->alloced*sizeof(Result));
#endif

 return(results);
}


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

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

void FreeResultsList(Results *results)
{
#if NBINS_RESULTS
 int i;
#endif

#if NBINS_RESULTS
 for(i=0;i<NBINS_RESULTS;i++)
    free(results->offsets[i]);
#else
 free(results->offsets);
#endif

 free(results->results);

 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.

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

Result *InsertResult(Results *results,node_t node)
{
#ifdef NBINS_RESULTS
 int bin=node%NBINS_RESULTS;
 int start=0;
 int end=results->numbin[bin]-1;
 uint32_t *offsetsp=results->offsets[bin];
 int i;
#else
 int start=0;
 int end=results->number-1;
 uint32_t *offsetsp=results->offsets;
#endif
 int mid;
 int insert=-1;

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

#ifdef NBINS_RESULTS
 if(results->numbin[bin]==results->alloced)
   {
    results->alloced+=INCREMENT_RESULTS;

    for(i=0;i<NBINS_RESULTS;i++)
       results->offsets[i]=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t));

    offsetsp=results->offsets[bin];

    results->results=(Result*)realloc((void*)results->results,results->alloced*NBINS_RESULTS*sizeof(Result));
   }
#else
 if(results->number==results->alloced)
   {
    results->alloced+=INCREMENT_RESULTS;

    results->offsets=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t));

    offsetsp=results->offsets;

    results->results=(Result*)realloc((void*)results->results,results->alloced*sizeof(Result));
   }
#endif

 /* Binary search - search key may not match, if not then 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(end<start)                                         /* There are no results */
    insert=start;
 else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
    insert=start;
 else if(node>results->results[offsetsp[end]].node)   /* Check key is not after end */
    insert=end+1;
 else
   {
    do
      {
       mid=(start+end)/2;                                  /* Choose mid point */

       if(results->results[offsetsp[mid]].node<node)      /* Mid point is too low */
          start=mid;
       else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
          end=mid;
       else
          assert(0);
      }
    while((end-start)>1);

    insert=end;
   }

 /* Shuffle the array up */

#ifdef NBINS_RESULTS
 if(insert!=results->numbin[bin])
    memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t));
#else
 if(insert!=results->number)
    memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t));
#endif

 /* Insert the new entry */

 offsetsp[insert]=results->number;

 results->number++;

#ifdef NBINS_RESULTS
 results->numbin[bin]++;
#endif

 return(&results->results[offsetsp[insert]]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result, ordered by node.

  Result *insert_result Returns the result that has been found.

  Results *results The results structure to search.

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

Result *FindResult(Results *results,node_t node)
{
#ifdef NBINS_RESULTS
 int bin=node%NBINS_RESULTS;
 int start=0;
 int end=results->numbin[bin]-1;
 uint32_t *offsetsp=results->offsets[bin];
#else
 int start=0;
 int end=results->number-1;
 uint32_t *offsetsp=results->offsets;
#endif
 int mid;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                                         /* There are no results */
    return(NULL);
 else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
    return(NULL);
 else if(node>results->results[offsetsp[end]].node)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                                  /* Choose mid point */

       if(results->results[offsetsp[mid]].node<node)      /* Mid point is too low */
          start=mid+1;
       else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
          end=mid-1;
       else                                                /* Mid point is correct */
          return(&results->results[offsetsp[mid]]);
      }
    while((end-start)>1);

    if(results->results[offsetsp[start]].node==node)      /* Start is correct */
       return(&results->results[offsetsp[start]]);

    if(results->results[offsetsp[end]].node==node)        /* End is correct */
       return(&results->results[offsetsp[end]]);
   }

 return(NULL);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/results.c,v 1.2 2009-01-17 17:49:58 amb Exp $
3
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	/*++++++++++++++++++++++++++++++++++++++
23	Allocate a new results list.
24
25	Results *NewResultsList Returns the results list.
26	++++++++++++++++++++++++++++++++++++++*/
27
28	Results *NewResultsList(void)
29	{
30	Results *results;
31	#if NBINS_RESULTS
32	int i;
33	#endif
34
35	results=(Results*)malloc(sizeof(Results));
36
37	results->alloced=INCREMENT_RESULTS;
38	results->number=0;
39
40	#if NBINS_RESULTS
41	for(i=0;i<NBINS_RESULTS;i++)
42	{
43	results->numbin[i]=0;
44
45	results->offsets[i]=(uint32_t)malloc(results->allocedsizeof(uint32_t));
46	}
47
48	results->results=(Result)malloc(results->allocedNBINS_RESULTS*sizeof(Result));
49	#else
50	results->offsets=(uint32_t)malloc(results->allocedsizeof(uint32_t));
51
52	results->data=(Result)malloc(results->allocedsizeof(Result));
53	#endif
54
55	return(results);
56	}
57
58
59	/*++++++++++++++++++++++++++++++++++++++
60	Allocate a new results list.
61
62	Results *results The results list to be destroyed.
63	++++++++++++++++++++++++++++++++++++++*/
64
65	void FreeResultsList(Results *results)
66	{
67	#if NBINS_RESULTS
68	int i;
69	#endif
70
71	#if NBINS_RESULTS
72	for(i=0;i<NBINS_RESULTS;i++)
73	free(results->offsets[i]);
74	#else
75	free(results->offsets);
76	#endif
77
78	free(results->results);
79
80	free(results);
81	}
82
83
84	/*++++++++++++++++++++++++++++++++++++++
85	Insert a new result into the results data structure in the right order.
86
87	Result *insert_result Returns the result that has been inserted.
88
89	Results *results The results structure to insert into.
90
91	node_t node The node that is to be inserted into the results.
92	++++++++++++++++++++++++++++++++++++++*/
93
94	Result InsertResult(Results results,node_t node)
95	{
96	#ifdef NBINS_RESULTS
97	int bin=node%NBINS_RESULTS;
98	int start=0;
99	int end=results->numbin[bin]-1;
100	uint32_t *offsetsp=results->offsets[bin];
101	int i;
102	#else
103	int start=0;
104	int end=results->number-1;
105	uint32_t *offsetsp=results->offsets;
106	#endif
107	int mid;
108	int insert=-1;
109
110	/* Check that the arrays have enough space. */
111
112	#ifdef NBINS_RESULTS
113	if(results->numbin[bin]==results->alloced)
114	{
115	results->alloced+=INCREMENT_RESULTS;
116
117	for(i=0;i<NBINS_RESULTS;i++)
118	results->offsets[i]=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
119
120	offsetsp=results->offsets[bin];
121
122	results->results=(Result)realloc((void)results->results,results->allocedNBINS_RESULTSsizeof(Result));
123	}
124	#else
125	if(results->number==results->alloced)
126	{
127	results->alloced+=INCREMENT_RESULTS;
128
129	results->offsets=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
130
131	offsetsp=results->offsets;
132
133	results->results=(Result)realloc((void)results->results,results->alloced*sizeof(Result));
134	}
135	#endif
136
137	/* Binary search - search key may not match, if not then insertion point required
138	*
139	* # <- start \| Check mid and move start or end if it doesn't match
140	* # \|
141	* # \| Since there may not be an exact match we must set end=mid
142	* # <- mid \| or start=mid because we know that mid doesn't match.
143	* # \|
144	* # \| Eventually end=start+1 and the insertion point is before
145	* # <- end \| end (since it cannot be before the initial start or end).
146	*/
147
148	if(end<start) /* There are no results */
149	insert=start;
150	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
151	insert=start;
152	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
153	insert=end+1;
154	else
155	{
156	do
157	{
158	mid=(start+end)/2; /* Choose mid point */
159
160	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
161	start=mid;
162	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
163	end=mid;
164	else
165	assert(0);
166	}
167	while((end-start)>1);
168
169	insert=end;
170	}
171
172	/* Shuffle the array up */
173
174	#ifdef NBINS_RESULTS
175	if(insert!=results->numbin[bin])
176	memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t));
177	#else
178	if(insert!=results->number)
179	memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t));
180	#endif
181
182	/* Insert the new entry */
183
184	offsetsp[insert]=results->number;
185
186	results->number++;
187
188	#ifdef NBINS_RESULTS
189	results->numbin[bin]++;
190	#endif
191
192	return(&results->results[offsetsp[insert]]);
193	}
194
195
196	/*++++++++++++++++++++++++++++++++++++++
197	Find a result, ordered by node.
198
199	Result *insert_result Returns the result that has been found.
200
201	Results *results The results structure to search.
202
203	node_t node The node that is to be found.
204	++++++++++++++++++++++++++++++++++++++*/
205
206	Result FindResult(Results results,node_t node)
207	{
208	#ifdef NBINS_RESULTS
209	int bin=node%NBINS_RESULTS;
210	int start=0;
211	int end=results->numbin[bin]-1;
212	uint32_t *offsetsp=results->offsets[bin];
213	#else
214	int start=0;
215	int end=results->number-1;
216	uint32_t *offsetsp=results->offsets;
217	#endif
218	int mid;
219
220	/* Binary search - search key exact match only is required.
221	*
222	* # <- start \| Check mid and move start or end if it doesn't match
223	* # \|
224	* # \| Since an exact match is wanted we can set end=mid-1
225	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
226	* # \|
227	* # \| Eventually either end=start or end=start+1 and one of
228	* # <- end \| start or end is the wanted one.
229	*/
230
231	if(end<start) /* There are no results */
232	return(NULL);
233	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
234	return(NULL);
235	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
236	return(NULL);
237	else
238	{
239	do
240	{
241	mid=(start+end)/2; /* Choose mid point */
242
243	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
244	start=mid+1;
245	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
246	end=mid-1;
247	else /* Mid point is correct */
248	return(&results->results[offsetsp[mid]]);
249	}
250	while((end-start)>1);
251
252	if(results->results[offsetsp[start]].node==node) /* Start is correct */
253	return(&results->results[offsetsp[start]]);
254
255	if(results->results[offsetsp[end]].node==node) /* End is correct */
256	return(&results->results[offsetsp[end]]);
257	}
258
259	return(NULL);
260	}