git.cworth.org Git - rrsolve/blob - src/rrs_state_buf.c

   1 /* rrsolve - Simple RR solver and librr client.
   2  *
   3  * Copyright © 2003 Carl Worth
   4  *
   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.
  15  *
  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.
  23  *
  24  * Author: Carl Worth <carl@theworths.org>
  25  */
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include "rrsolve.h"
  31
  32 static int
  33 _rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state);
  34
  35 static void
  36 _rrs_state_buf_sort (rrs_state_buf_t *buf);
  37
  38 static rr_status_t
  39 _rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth);
  40
  41 static rr_status_t
  42 _rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size);
  43
  44 rrs_state_buf_t *
  45 rrs_state_buf_create (int initial_size)
  46 {
  47     rrs_state_buf_t *buf;
  48
  49     buf = malloc (sizeof (rrs_state_buf_t));
  50     if (buf == NULL)
  51         return NULL;
  52
  53     buf->state = NULL;
  54     buf->num_states = 0;
  55     buf->size = 0;
  56
  57     buf->sorted = 0;
  58
  59     _rrs_state_buf_grow_by (buf, initial_size);
  60
  61     return buf;
  62 }
  63
  64 void
  65 rrs_state_buf_destroy (rrs_state_buf_t *buf)
  66 {
  67     free (buf->state);
  68
  69     free (buf);
  70 }
  71
  72 static rr_status_t
  73 _rrs_state_buf_grow_by (rrs_state_buf_t *buf, int growth)
  74 {
  75     rrs_state_t *new_state;
  76
  77     buf->size += growth;
  78
  79     new_state = realloc (buf->state, buf->size * sizeof (rrs_state_t));
  80     if (new_state == NULL) {
  81         buf->size -= growth;
  82         return RR_STATUS_NO_MEMORY;
  83     }
  84
  85     buf->state = new_state;
  86
  87     return RR_STATUS_SUCCESS;
  88 }
  89
  90 static rr_status_t
  91 _rrs_state_buf_grow_to (rrs_state_buf_t *buf, int new_size)
  92 {
  93     if (new_size > buf->size)
  94         return _rrs_state_buf_grow_by (buf, new_size - buf->size);
  95
  96     return RR_STATUS_SUCCESS;
  97 }
  98
  99 #define RRS_STATE_BUF_MIN_GROWTH 10
 100
 101 #define MAX(a,b) ((a) > (b) ? (a) : (b))
 102
 103 rr_status_t
 104 rrs_state_buf_add (rrs_state_buf_t *buf, rrs_state_t state)
 105 {
 106     rr_status_t status;
 107
 108     if (buf->num_states >= buf->size) {
 109         status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
 110         if (status)
 111             return status;
 112     }
 113
 114     buf->state[buf->num_states++] = state;
 115
 116     buf->sorted = 0;
 117
 118     return RR_STATUS_SUCCESS;
 119 }
 120
 121 rr_status_t
 122 rrs_state_buf_add_sorted (rrs_state_buf_t *buf, rrs_state_t state)
 123 {
 124     int i;
 125     rr_status_t status;
 126
 127     i = _rrs_state_buf_search (buf, state);
 128
 129     if (i < buf->num_states && buf->state[i] == state)
 130         return RR_STATUS_OCCUPIED;
 131
 132     if (buf->num_states >= buf->size) {
 133         status = _rrs_state_buf_grow_by (buf, MAX (RRS_STATE_BUF_MIN_GROWTH, buf->size));
 134         if (status)
 135             return status;
 136     }
 137
 138     memmove (&buf->state[i+1], &buf->state[i],
 139              (buf->num_states - i) * sizeof (rrs_state_t));
 140     buf->state[i] = state;
 141     buf->num_states++;
 142
 143     return RR_STATUS_SUCCESS;
 144 }
 145
 146 rr_status_t
 147 rrs_state_buf_remove (rrs_state_buf_t *buf, rrs_state_t state)
 148 {
 149     int i;
 150
 151     i = _rrs_state_buf_search (buf, state);
 152
 153     if (buf->state[i] != state)
 154         return RR_STATUS_OCCUPIED;
 155
 156     buf->num_states--;
 157     memmove (&buf->state[i], &buf->state[i+1],
 158              (buf->num_states - i) * sizeof (rrs_state_t));
 159
 160     return RR_STATUS_SUCCESS;
 161 }
 162
 163 rr_status_t
 164 rrs_state_buf_append (rrs_state_buf_t *buf, rrs_state_buf_t *other)
 165 {
 166     rr_status_t status;
 167     int new_size;
 168
 169     if (other == NULL)
 170         return RR_STATUS_SUCCESS;
 171
 172     new_size = buf->num_states + other->num_states;
 173     status = _rrs_state_buf_grow_to (buf, new_size);
 174     if (status)
 175         return status;
 176
 177     memcpy (&buf->state[buf->num_states], other->state, other->num_states * sizeof (rrs_state_t));
 178     buf->num_states += other->num_states;
 179
 180     buf->sorted = 0;
 181
 182     return RR_STATUS_SUCCESS;
 183 }
 184
 185 static int
 186 _rrs_state_compare (const void *a, const void *b)
 187 {
 188     rrs_state_t a_state = *((rrs_state_t *) a);
 189     rrs_state_t b_state = *((rrs_state_t *) b);
 190
 191     if (a_state > b_state)
 192         return 1;
 193     else if (a_state < b_state)
 194         return -1;
 195     else
 196         return 0;
 197 }
 198
 199 static int
 200 _rrs_state_buf_search (rrs_state_buf_t *buf, rrs_state_t state)
 201 {
 202     int min, mid, max;
 203
 204     if (buf->sorted == 0)
 205         _rrs_state_buf_sort (buf);
 206
 207     if (buf->num_states == 0)
 208         return 0;
 209
 210     min = 0;
 211     max = buf->num_states - 1;
 212
 213     do {
 214         mid = min + (max - min) / 2;
 215
 216         if (state == buf->state[mid])
 217             return mid;
 218         else if (state > buf->state[mid])
 219             min = mid + 1;
 220         else
 221             max = mid;
 222     } while (min < max);
 223
 224     if (state > buf->state[max])
 225         return max + 1;
 226     else
 227         return min;
 228 }
 229
 230 static void
 231 _rrs_state_buf_sort (rrs_state_buf_t *buf)
 232 {
 233     qsort (buf->state, buf->num_states, sizeof (rrs_state_t), _rrs_state_compare);
 234     buf->sorted = 1;
 235 }
 236
 237 int
 238 rrs_state_buf_contains (rrs_state_buf_t *buf, rrs_state_t state)
 239 {
 240     int i;
 241
 242     i = _rrs_state_buf_search (buf, state);
 243
 244     if (i > buf->num_states - 1)
 245         return 0;
 246     else
 247         return buf->state[i] == state;
 248 }