oggz_vector.c 8.83 KB
Newer Older
andre's avatar
andre committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/*
   Copyright (C) 2003 Commonwealth Scientific and Industrial Research
   Organisation (CSIRO) Australia

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

   - Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

   - Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

   - Neither the name of CSIRO Australia nor the names of its
   contributors may be used to endorse or promote products derived from
   this software without specific prior written permission.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
   PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE ORGANISATION OR
   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

33 34
#include "config.h"

andre's avatar
andre committed
35 36 37 38
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

conrad's avatar
conrad committed
39 40 41
#include "oggz_macros.h"

typedef int (*OggzFunc) (void * data);
shans's avatar
shans committed
42
typedef int (*OggzFunc1) (void * data, void * arg);
conrad's avatar
conrad committed
43
typedef int (*OggzFindFunc) (void * data, long serialno);
44
typedef int (*OggzCmpFunc) (const void * a, const void * b, void * user_data);
conrad's avatar
conrad committed
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

typedef struct _OggzVector OggzVector;

typedef union {
  void * p;
  long l;
} oggz_data_t;

struct _OggzVector {
  int max_elements;
  int nr_elements;
  oggz_data_t * data;
  OggzCmpFunc compare;
  void * compare_user_data;
};
andre's avatar
andre committed
60 61

/*
conrad's avatar
conrad committed
62 63 64
 * A vector of void * or long; iff it's a vector of void * objects, it
 * can be optionally sorted. (The sorting is used to implement the
 * packet queue; the vector of longs is used to implement OggzTable)
andre's avatar
andre committed
65 66 67 68 69 70 71
 *
 * if you set a comparison function (oggz_vector_set_cmp()), the vector
 * will be sorted and new elements will be inserted in sorted order.
 *
 * if you don't set a comparison function, new elements will be appended
 * at the tail
 *
conrad's avatar
conrad committed
72
 * to unset the comparison function, call oggz_vector_set_cmp (NULL,NULL)
andre's avatar
andre committed
73 74 75
 */

OggzVector *
conrad's avatar
conrad committed
76
oggz_vector_new (void)
andre's avatar
andre committed
77
{
conrad's avatar
conrad committed
78 79 80
  OggzVector * vector;

  vector = oggz_malloc (sizeof (OggzVector));
81
  if (vector == NULL) return NULL;
conrad's avatar
conrad committed
82

andre's avatar
andre committed
83 84 85 86
  vector->max_elements = 0;
  vector->nr_elements = 0;
  vector->data = NULL;
  vector->compare = NULL;
conrad's avatar
conrad committed
87
  vector->compare_user_data = NULL;
andre's avatar
andre committed
88 89 90 91

  return vector;
}

conrad's avatar
conrad committed
92
static void
andre's avatar
andre committed
93 94
oggz_vector_clear (OggzVector * vector)
{
conrad's avatar
conrad committed
95 96
  if (vector->data)
  {
97
    oggz_free (vector->data);
conrad's avatar
conrad committed
98 99
    vector->data = NULL;
  }
100

andre's avatar
andre committed
101 102 103 104
  vector->nr_elements = 0;
  vector->max_elements = 0;
}

conrad's avatar
conrad committed
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
void
oggz_vector_delete (OggzVector * vector)
{
  oggz_vector_clear (vector);
  oggz_free (vector);
}

int
oggz_vector_size (OggzVector * vector)
{
  if (vector == NULL) return 0;

  return vector->nr_elements;
}

void *
oggz_vector_nth_p (OggzVector * vector, int n)
{
  if (vector == NULL) return NULL;

  if (n >= vector->nr_elements) return NULL;

  return vector->data[n].p;
}

long
oggz_vector_nth_l (OggzVector * vector, int n)
{
  if (vector == NULL) return -1L;

  if (n >= vector->nr_elements) return -1L;

  return vector->data[n].l;
}

andre's avatar
andre committed
140
void *
141
oggz_vector_find_p (OggzVector * vector, const void * data)
andre's avatar
andre committed
142
{
143 144 145
  void * d;
  int i;

146
  if (vector->compare == NULL) return NULL;
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162

  for (i = 0; i < vector->nr_elements; i++) {
    d = vector->data[i].p;
    if (vector->compare (d, data, vector->compare_user_data))
      return d;
  }

  return NULL;
}

int
oggz_vector_find_index_p (OggzVector * vector, const void * data)
{
  void * d;
  int i;

163
  if (vector->compare == NULL) return -1;
164 165 166 167 168 169 170 171 172 173 174 175 176 177

  for (i = 0; i < vector->nr_elements; i++) {
    d = vector->data[i].p;
    if (vector->compare (d, data, vector->compare_user_data))
      return i;
  }

  return -1;
}

void *
oggz_vector_find_with (OggzVector * vector, OggzFindFunc func, long serialno)
{
  void * d;
andre's avatar
andre committed
178 179 180
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
181 182 183
    d = vector->data[i].p;
    if (func (d, serialno))
      return d;
andre's avatar
andre committed
184 185 186 187 188 189 190 191 192 193 194
  }

  return NULL;
}

int
oggz_vector_foreach (OggzVector * vector, OggzFunc func)
{
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
conrad's avatar
conrad committed
195
    func (vector->data[i].p);
andre's avatar
andre committed
196 197 198 199 200
  }

  return 0;
}

shans's avatar
shans committed
201 202 203 204 205 206 207 208 209 210 211 212
int
oggz_vector_foreach1 (OggzVector * vector, OggzFunc1 func, void *arg)
{
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
    func (vector->data[i].p, arg);
  }

  return 0;
}

andre's avatar
andre committed
213
static void
conrad's avatar
conrad committed
214
_array_swap (oggz_data_t v[], int i, int j)
andre's avatar
andre committed
215 216 217
{
  void * t;

conrad's avatar
conrad committed
218 219 220
  t = v[i].p;
  v[i].p = v[j].p;
  v[j].p = t;
andre's avatar
andre committed
221 222 223
}

/**
conrad's avatar
conrad committed
224
 * Helper function for oggz_vector_insert (). Sorts the vector by
andre's avatar
andre committed
225 226 227 228 229 230 231 232 233 234 235 236 237 238
 * insertion sort, assuming the tail element has just been added and the
 * rest of the vector is sorted.
 * \param vector An OggzVector
 * \pre The vector has just had a new element added to its tail
 * \pre All elements other than the tail element are already sorted.
 */
static void
oggz_vector_tail_insertion_sort (OggzVector * vector)
{
  int i;

  if (vector->compare == NULL) return;

  for (i = vector->nr_elements-1; i > 0; i--) {
conrad's avatar
conrad committed
239
    if (vector->compare (vector->data[i-1].p, vector->data[i].p,
andre's avatar
andre committed
240 241 242 243 244 245 246 247 248 249
			 vector->compare_user_data) > 0) {
      _array_swap (vector->data, i, i-1);
    } else {
      break;
    }
  }

  return;
}

conrad's avatar
conrad committed
250 251
static OggzVector *
oggz_vector_grow (OggzVector * vector)
andre's avatar
andre committed
252 253 254 255 256 257 258 259 260 261 262 263 264 265
{
  void * new_elements;
  int new_max_elements;

  vector->nr_elements++;

  if (vector->nr_elements > vector->max_elements) {
    if (vector->max_elements == 0) {
      new_max_elements = 1;
    } else {
      new_max_elements = vector->max_elements * 2;
    }

    new_elements =
266
      oggz_realloc (vector->data, (size_t)new_max_elements * sizeof (oggz_data_t));
andre's avatar
andre committed
267 268 269 270 271 272 273 274 275 276

    if (new_elements == NULL) {
      vector->nr_elements--;
      return NULL;
    }

    vector->max_elements = new_max_elements;
    vector->data = new_elements;
  }

conrad's avatar
conrad committed
277 278 279 280 281 282 283 284 285 286
  return vector;
}

void *
oggz_vector_insert_p (OggzVector * vector, void * data)
{
  if (oggz_vector_grow (vector) == NULL)
    return NULL;

  vector->data[vector->nr_elements-1].p = data;
andre's avatar
andre committed
287 288 289 290

  oggz_vector_tail_insertion_sort (vector);

  return data;
conrad's avatar
conrad committed
291 292 293 294 295 296 297 298 299 300 301 302

}

long
oggz_vector_insert_l (OggzVector * vector, long ldata)
{
  if (oggz_vector_grow (vector) == NULL)
    return -1;

  vector->data[vector->nr_elements-1].l = ldata;

  return ldata;
andre's avatar
andre committed
303 304 305 306 307 308
}

static void
oggz_vector_qsort (OggzVector * vector, int left, int right)
{
  int i, last;
conrad's avatar
conrad committed
309
  oggz_data_t * v = vector->data;
andre's avatar
andre committed
310 311 312 313 314 315

  if (left >= right) return;

  _array_swap (v, left, (left + right)/2);
  last = left;
  for (i = left+1; i <= right; i++) {
conrad's avatar
conrad committed
316
    if (vector->compare (v[i].p, v[left].p, vector->compare_user_data) < 0)
andre's avatar
andre committed
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
      _array_swap (v, ++last, i);
  }
  _array_swap (v, left, last);
  oggz_vector_qsort (vector, left, last-1);
  oggz_vector_qsort (vector, last+1, right);
}

int
oggz_vector_set_cmp (OggzVector * vector, OggzCmpFunc compare,
		     void * user_data)
{
  vector->compare = compare;
  vector->compare_user_data = user_data;

  if (compare) {
    oggz_vector_qsort (vector, 0, vector->nr_elements-1);
  }

  return 0;
}

conrad's avatar
conrad committed
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358

static void *
oggz_vector_remove_nth (OggzVector * vector, int n)
{
  int i;
  oggz_data_t * new_elements;
  int new_max_elements;

  vector->nr_elements--;

  if (vector->nr_elements == 0) {
    oggz_vector_clear (vector);
  } else {
    for (i = n; i < vector->nr_elements; i++) {
      vector->data[i] = vector->data[i+1];
    }

    if (vector->nr_elements < vector->max_elements/2) {
      new_max_elements = vector->max_elements/2;

      new_elements =
359 360
        oggz_realloc (vector->data,
        (size_t)new_max_elements * sizeof (oggz_data_t));
conrad's avatar
conrad committed
361

362
      if (new_elements == NULL) {
363 364 365
        vector->data = NULL;
        return NULL;
      }
conrad's avatar
conrad committed
366

conrad's avatar
conrad committed
367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
      vector->max_elements = new_max_elements;
      vector->data = new_elements;
    }
  }

  return vector;
}

OggzVector *
oggz_vector_remove_p (OggzVector * vector, void * data)
{
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
    if (vector->data[i].p == data) {
      return oggz_vector_remove_nth (vector, i);
    }
  }

  return vector;
}

OggzVector *
oggz_vector_remove_l (OggzVector * vector, long ldata)
{
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
    if (vector->data[i].l == ldata) {
      return oggz_vector_remove_nth (vector, i);
    }
  }

  return vector;
}

andre's avatar
andre committed
403 404 405 406 407
void *
oggz_vector_pop (OggzVector * vector)
{
  void * data;

408
  if (vector == NULL || vector->data == NULL) return NULL;
andre's avatar
andre committed
409

conrad's avatar
conrad committed
410
  data = vector->data[0].p;
andre's avatar
andre committed
411

conrad's avatar
conrad committed
412 413
  oggz_vector_remove_nth (vector, 0);

andre's avatar
andre committed
414 415 416
  return data;

}