1 /* rrsolve - Simple RR solver and librr client.
3 * Copyright © 2003 Carl Worth
5 * Permission to use, copy, modify, distribute, and sell this software
6 * and its documentation for any purpose is hereby granted without
7 * fee, provided that the above copyright notice appear in all copies
8 * and that both that copyright notice and this permission notice
9 * appear in supporting documentation, and that the name of Carl Worth
10 * not be used in advertising or publicity pertaining to distribution
11 * of the software without specific, written prior permission.
12 * Carl Worth makes no representations about the suitability of this
13 * software for any purpose. It is provided "as is" without express
14 * or implied warranty.
16 * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
18 * NO EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
20 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
21 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
22 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 * Author: Carl Worth <carl@theworths.org>
33 _rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state);
36 _rrs_state_buf_sort (rrs_state_buf_t *buf);
39 _rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth);
42 _rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size);
45 rrs_state_buf_create (int initial_size)
49 buf = malloc (sizeof (rrs_state_buf_t));
59 _rrs_state_buf_grow_by (buf, initial_size);
65 rrs_state_buf_destroy (rrs_state_buf_t *buf)
73 _rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth)
75 rrs_state_t *new_state;
79 new_state = realloc (buf->state, buf->size * sizeof (rrs_state_t));
80 if (new_state == NULL) {
82 return RR_STATUS_NO_MEMORY;
85 buf->state = new_state;
87 return RR_STATUS_SUCCESS;
91 _rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size)
93 if (new_size > buf->size)
94 return _rrs_state_buf_grow_by (buf, new_size - buf->size);
96 return RR_STATUS_SUCCESS;
99 #define RRS_STATE_BUF_MIN_GROWTH 10
101 #define MAX(a,b) ((a) > (b) ? (a) : (b))
104 rrs_state_buf_add (rrs_state_buf_t *buf, rrs_state_t state)
108 if (buf->num_states >= buf->size) {
109 status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
114 buf->state[buf->num_states++] = state;
118 return RR_STATUS_SUCCESS;
122 rrs_state_buf_add_sorted (rrs_state_buf_t *buf, rrs_state_t state)
127 i = _rrs_state_buf_search (buf, state);
129 if (i < buf->num_states && buf->state[i] == state)
130 return RR_STATUS_OCCUPIED;
132 if (buf->num_states >= buf->size) {
133 status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
138 memmove (&buf->state[i+1], &buf->state[i],
139 (buf->num_states - i) * sizeof (rrs_state_t));
140 buf->state[i] = state;
143 return RR_STATUS_SUCCESS;
147 rrs_state_buf_remove (rrs_state_buf_t *buf, rrs_state_t state)
151 i = _rrs_state_buf_search (buf, state);
153 if (buf->state[i] != state)
154 return RR_STATUS_OCCUPIED;
157 memmove (&buf->state[i], &buf->state[i+1],
158 (buf->num_states - i) * sizeof (rrs_state_t));
160 return RR_STATUS_SUCCESS;
164 rrs_state_buf_append (rrs_state_buf_t *buf, rrs_state_buf_t *other)
170 return RR_STATUS_SUCCESS;
172 new_size = buf->num_states + other->num_states;
173 status = _rrs_state_buf_grow_to (buf, new_size);
177 memcpy (&buf->state[buf->num_states], other->state, other->num_states * sizeof (rrs_state_t));
178 buf->num_states += other->num_states;
182 return RR_STATUS_SUCCESS;
186 _rrs_state_compare (const void *a, const void *b)
188 rrs_state_t a_state = *((rrs_state_t *) a);
189 rrs_state_t b_state = *((rrs_state_t *) b);
191 if (a_state > b_state)
193 else if (a_state < b_state)
200 _rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state)
204 if (buf->sorted == 0)
205 _rrs_state_buf_sort (buf);
207 if (buf->num_states == 0)
211 max = buf->num_states - 1;
214 mid = min + (max - min) / 2;
216 if (state == buf->state[mid])
218 else if (state > buf->state[mid])
224 if (state > buf->state[max])
231 _rrs_state_buf_sort (rrs_state_buf_t *buf)
233 qsort (buf->state, buf->num_states, sizeof (rrs_state_t), _rrs_state_compare);
238 rrs_state_buf_contains (rrs_state_buf_t *buf, rrs_state_t state)
242 i = _rrs_state_buf_search (buf, state);
244 if (i > buf->num_states - 1)
247 return buf->state[i] == state;