oggz_vector.c 8.75 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
#include "oggz_macros.h"

typedef int (*OggzFunc) (void * data);
typedef int (*OggzFindFunc) (void * data, long serialno);
typedef int (*OggzCmpFunc) (void * a, void * b, void * user_data);

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
59 60

/*
conrad's avatar
conrad committed
61 62 63
 * 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
64 65 66 67 68 69 70
 *
 * 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
71
 * to unset the comparison function, call oggz_vector_set_cmp (NULL,NULL)
andre's avatar
andre committed
72 73 74
 */

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

  vector = oggz_malloc (sizeof (OggzVector));

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

  return vector;
}

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

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

conrad's avatar
conrad committed
103 104 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
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
138 139 140 141 142 143 144
void *
oggz_vector_find (OggzVector * vector, OggzFindFunc func, long serialno)
{
  void * data;
  int i;

  for (i = 0; i < vector->nr_elements; i++) {
conrad's avatar
conrad committed
145
    data = vector->data[i].p;
andre's avatar
andre committed
146 147 148 149 150 151 152 153 154 155 156 157 158
    if (func (data, serialno))
      return data;
  }

  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
159
    func (vector->data[i].p);
andre's avatar
andre committed
160 161 162 163 164 165
  }

  return 0;
}

static void
conrad's avatar
conrad committed
166
_array_swap (oggz_data_t v[], int i, int j)
andre's avatar
andre committed
167 168 169
{
  void * t;

conrad's avatar
conrad committed
170 171 172
  t = v[i].p;
  v[i].p = v[j].p;
  v[j].p = t;
andre's avatar
andre committed
173 174 175
}

/**
conrad's avatar
conrad committed
176
 * Helper function for oggz_vector_insert (). Sorts the vector by
andre's avatar
andre committed
177 178 179 180 181 182 183 184 185 186 187 188 189 190
 * 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
191
    if (vector->compare (vector->data[i-1].p, vector->data[i].p,
andre's avatar
andre committed
192 193 194 195 196 197 198 199 200 201
			 vector->compare_user_data) > 0) {
      _array_swap (vector->data, i, i-1);
    } else {
      break;
    }
  }

  return;
}

conrad's avatar
conrad committed
202 203
static OggzVector *
oggz_vector_grow (OggzVector * vector)
andre's avatar
andre committed
204 205 206 207 208 209 210 211 212 213 214 215 216 217
{
  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 =
218
      oggz_realloc (vector->data, (size_t)new_max_elements * sizeof (oggz_data_t));
andre's avatar
andre committed
219 220 221

    if (new_elements == NULL) {
      vector->nr_elements--;
222
      vector->data = NULL;
andre's avatar
andre committed
223 224 225 226 227 228 229
      return NULL;
    }

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

conrad's avatar
conrad committed
230 231 232 233 234 235 236 237 238 239
  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
240 241 242 243

  oggz_vector_tail_insertion_sort (vector);

  return data;
conrad's avatar
conrad committed
244 245 246 247 248 249 250 251 252 253 254 255

}

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
256 257 258 259 260 261
}

static void
oggz_vector_qsort (OggzVector * vector, int left, int right)
{
  int i, last;
conrad's avatar
conrad committed
262
  oggz_data_t * v = vector->data;
andre's avatar
andre committed
263 264 265 266 267 268

  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
269
    if (vector->compare (v[i].p, v[left].p, vector->compare_user_data) < 0)
andre's avatar
andre committed
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
      _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
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311

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 =
312 313
        oggz_realloc (vector->data,
        (size_t)new_max_elements * sizeof (oggz_data_t));
conrad's avatar
conrad committed
314

315 316 317 318 319 320
      if (new_elements == NULL)
      {
        vector->data = NULL;
        return NULL;
      }

conrad's avatar
conrad committed
321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
      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
357 358 359 360
void *
oggz_vector_pop (OggzVector * vector)
{
  void * data;
conrad's avatar
conrad committed
361
#if 0
andre's avatar
andre committed
362 363
  void * new_elements;
  int new_max_elements;
conrad's avatar
conrad committed
364
#endif
andre's avatar
andre committed
365 366 367

  if (!vector || vector->data == NULL) return NULL;

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

conrad's avatar
conrad committed
370
#if 0
andre's avatar
andre committed
371 372 373 374 375 376 377 378 379 380 381 382
  vector->nr_elements--;

  if (vector->nr_elements == 0) {
    oggz_vector_clear (vector);
  } else {
#if 0
    memmove (vector->data, &vector->data[1],
	     vector->nr_elements * sizeof (void *));
#else
    {
      int i;
      for (i = 0; i < vector->nr_elements; i++) {
conrad's avatar
conrad committed
383
	vector->data[i].p = vector->data[i+1].p;
andre's avatar
andre committed
384 385 386 387 388 389 390
      }
    }
#endif
    if (vector->nr_elements < vector->max_elements/2) {
      new_max_elements = vector->max_elements/2;

      new_elements =
391 392
        oggz_realloc (vector->data,
        (size_t)new_max_elements * sizeof (oggz_data_t));
andre's avatar
andre committed
393 394

      if (new_elements != NULL) {
395 396
        vector->max_elements = new_max_elements;
        vector->data = new_elements;
andre's avatar
andre committed
397 398 399 400
      }
    }

  }
conrad's avatar
conrad committed
401 402 403 404 405
#else

  oggz_vector_remove_nth (vector, 0);

#endif
andre's avatar
andre committed
406 407 408 409

  return data;

}