mpdm_a.c

   1 /*
   2
   3     MPDM - Minimum Profit Data Manager
   4     Copyright (C) 2003/2007 Angel Ortega <angel@triptico.com>
   5
   6     mpdm_a.c - Array management
   7
   8     This program is free software; you can redistribute it and/or
   9     modify it under the terms of the GNU General Public License
  10     as published by the Free Software Foundation; either version 2
  11     of the License, or (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License
  19     along with this program; if not, write to the Free Software
  20     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  21
  22     http://www.triptico.com
  23
  24 */
  25
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <wchar.h>
  32
  33 #include "mpdm.h"
  34
  35
  36 /*******************
  37         Data
  38 ********************/
  39
  40 /* sorting callback code */
  41 static mpdm_t sort_cb = NULL;
  42
  43
  44 /*******************
  45         Code
  46 ********************/
  47
  48 mpdm_t mpdm_new_a(int flags, int size)
  49 /* creates a new array value */
  50 {
  51         mpdm_t v;
  52
  53         /* creates and expands */
  54         if ((v = mpdm_new(flags | MPDM_MULTIPLE, NULL, 0)) != NULL)
  55                 mpdm_expand(v, 0, size);
  56
  57         return v;
  58 }
  59
  60
  61 static int wrap_offset(mpdm_t a, int offset)
  62 /* manages negative offsets */
  63 {
  64         if (offset < 0)
  65                 offset = mpdm_size(a) + offset;
  66
  67         return offset;
  68 }
  69
  70
  71 mpdm_t mpdm_aclone(mpdm_t v)
  72 /* clones a multiple value */
  73 {
  74         mpdm_t w;
  75         int n;
  76
  77         /* creates a similar value */
  78         w = mpdm_new_a(v->flags, v->size);
  79
  80         /* fills each element with duplicates of the original */
  81         for (n = 0; n < w->size; n++)
  82                 mpdm_aset(w, mpdm_clone(mpdm_aget(v, n)), n);
  83
  84         return w;
  85 }
  86
  87
  88 /* interface */
  89
  90 /**
  91  * mpdm_expand - Expands an array.
  92  * @a: the array
  93  * @offset: insertion offset
  94  * @num: number of elements to insert
  95  *
  96  * Expands an array value, inserting @num elements (initialized
  97  * to NULL) at the specified @offset.
  98  * [Arrays]
  99  */
 100 mpdm_t mpdm_expand(mpdm_t a, int offset, int num)
 101 {
 102         int n;
 103         mpdm_t *p;
 104
 105         /* sanity checks */
 106         if (num <= 0)
 107                 return a;
 108
 109         /* add size */
 110         a->size += num;
 111
 112         /* expand, or fail */
 113         if ((p = (mpdm_t *) realloc(a->data, a->size * sizeof(mpdm_t))) == NULL)
 114                 return NULL;
 115
 116         /* moves up from top of the array */
 117         for (n = a->size - 1; n >= offset + num; n--)
 118                 p[n] = p[n - num];
 119
 120         /* fills the new space with blanks */
 121         for (; n >= offset; n--)
 122                 p[n] = NULL;
 123
 124         a->data = p;
 125
 126         return a;
 127 }
 128
 129
 130 /**
 131  * mpdm_collapse - Collapses an array.
 132  * @a: the array
 133  * @offset: deletion offset
 134  * @num: number of elements to collapse
 135  *
 136  * Collapses an array value, deleting @num elements at
 137  * the specified @offset.
 138  * [Arrays]
 139  */
 140 mpdm_t mpdm_collapse(mpdm_t a, int offset, int num)
 141 {
 142         int n;
 143         mpdm_t *p;
 144
 145         /* sanity checks */
 146         if (num <= 0)
 147                 return a;
 148
 149         /* don't try to delete beyond the limit */
 150         if (offset + num > a->size)
 151                 num = a->size - offset;
 152
 153         p = (mpdm_t *) a->data;
 154
 155         /* unrefs the about-to-be-deleted elements */
 156         for (n = offset; n < offset + num; n++)
 157                 mpdm_unref(p[n]);
 158
 159         /* array is now shorter */
 160         a->size -= num;
 161
 162         /* moves down the elements */
 163         for (n = offset; n < a->size; n++)
 164                 p[n] = p[n + num];
 165
 166         /* finally shrinks the memory block */
 167         if ((a->data = realloc(p, a->size * sizeof(mpdm_t))) == NULL)
 168                 return NULL;
 169
 170         return a;
 171 }
 172
 173
 174 /**
 175  * mpdm_aset - Sets the value of an array's element.
 176  * @a: the array
 177  * @e: the element to be assigned
 178  * @offset: the subscript of the element
 179  *
 180  * Sets the element of the array @a at @offset to be the @e value.
 181  * Returns the previous element.
 182  * [Arrays]
 183  */
 184 mpdm_t mpdm_aset(mpdm_t a, mpdm_t e, int offset)
 185 {
 186         mpdm_t v;
 187         mpdm_t *p;
 188
 189         offset = wrap_offset(a, offset);
 190
 191         /* boundary checks */
 192         if (offset < 0)
 193                 return NULL;
 194
 195         /* if the array is shorter than offset, expand to make room for it */
 196         if (offset >= mpdm_size(a))
 197                 if (mpdm_expand(a, mpdm_size(a), offset - mpdm_size(a) + 1) == NULL)
 198                         return NULL;
 199
 200         p = (mpdm_t *) a->data;
 201
 202         /* assigns and references */
 203         v = mpdm_unref(p[offset]);
 204         p[offset] = mpdm_ref(e);
 205
 206         return v;
 207 }
 208
 209
 210 /**
 211  * mpdm_aget - Gets an element of an array.
 212  * @a: the array
 213  * @offset: the subscript of the element
 214  *
 215  * Returns the element at @offset of the array @a.
 216  * [Arrays]
 217  */
 218 mpdm_t mpdm_aget(mpdm_t a, int offset)
 219 {
 220         mpdm_t *p;
 221
 222         offset = wrap_offset(a, offset);
 223
 224         /* boundary checks */
 225         if (offset < 0 || offset >= mpdm_size(a))
 226                 return NULL;
 227
 228         p = (mpdm_t *) a->data;
 229
 230         return p[offset];
 231 }
 232
 233
 234 /**
 235  * mpdm_ins - Insert an element in an array.
 236  * @a: the array
 237  * @e: the element to be inserted
 238  * @offset: subscript where the element is going to be inserted
 239  *
 240  * Inserts the @e value in the @a array at @offset.
 241  * Further elements are pushed up, so the array increases its size
 242  * by one. Returns the inserted element.
 243  * [Arrays]
 244  */
 245 mpdm_t mpdm_ins(mpdm_t a, mpdm_t e, int offset)
 246 {
 247         offset = wrap_offset(a, offset);
 248
 249         /* open room and set value */
 250         if (mpdm_expand(a, offset, 1))
 251                 mpdm_aset(a, e, offset);
 252
 253         return e;
 254 }
 255
 256
 257 /**
 258  * mpdm_adel - Deletes an element of an array.
 259  * @a: the array
 260  * @offset: subscript of the element to be deleted
 261  *
 262  * Deletes the element at @offset of the @a array. The array
 263  * is shrinked by one. If @offset is negative, is counted from
 264  * the end of the array (so a value of -1 means delete the
 265  * last element of the array).
 266  *
 267  * Returns the deleted element.
 268  * [Arrays]
 269  */
 270 mpdm_t mpdm_adel(mpdm_t a, int offset)
 271 {
 272         mpdm_t v;
 273
 274         if (a == NULL || mpdm_size(a) == 0)
 275                 return NULL;
 276
 277         offset = wrap_offset(a, offset);
 278
 279         /* gets current value */
 280         v = mpdm_aget(a, offset);
 281
 282         /* shrinks the array */
 283         mpdm_collapse(a, offset, 1);
 284
 285         return v;
 286 }
 287
 288
 289 /**
 290  * mpdm_shift - Extracts the first element of an array.
 291  * @a: the array
 292  *
 293  * Extracts the first element of the array. The array
 294  * is shrinked by one.
 295  *
 296  * Returns the deleted element.
 297  * [Arrays]
 298  */
 299 mpdm_t mpdm_shift(mpdm_t a)
 300 {
 301         return mpdm_adel(a, 0);
 302 }
 303
 304
 305 /**
 306  * mpdm_push - Pushes a value into an array.
 307  * @a: the array
 308  * @e: the value
 309  *
 310  * Pushes a value into an array (i.e. inserts at the end).
 311  * [Arrays]
 312  */
 313 mpdm_t mpdm_push(mpdm_t a, mpdm_t e)
 314 {
 315         /* inserts at the end */
 316         return mpdm_ins(a, e, mpdm_size(a));
 317 }
 318
 319
 320 /**
 321  * mpdm_pop - Pops a value from an array.
 322  * @a: the array
 323  *
 324  * Pops a value from the array (i.e. deletes from the end
 325  * and returns it).
 326  * [Arrays]
 327  */
 328 mpdm_t mpdm_pop(mpdm_t a)
 329 {
 330         /* deletes from the end */
 331         return mpdm_adel(a, -1);
 332 }
 333
 334
 335 /**
 336  * mpdm_queue - Implements a queue in an array.
 337  * @a: the array
 338  * @e: the element to be pushed
 339  * @size: maximum size of array
 340  *
 341  * Pushes the @e element into the @a array. If the array already has
 342  * @size elements, the first (oldest) element is deleted from the
 343  * queue and returned.
 344  *
 345  * Returns the deleted element, or NULL if the array doesn't have
 346  * @size elements yet.
 347  * [Arrays]
 348  */
 349 mpdm_t mpdm_queue(mpdm_t a, mpdm_t e, int size)
 350 {
 351         mpdm_t v = NULL;
 352
 353         /* zero size is nonsense */
 354         if (size == 0)
 355                 return NULL;
 356
 357         /* loop until a has the desired size */
 358         while (mpdm_size(a) > size - 1)
 359                 v = mpdm_shift(a);
 360
 361         mpdm_push(a, e);
 362         return v;
 363 }
 364
 365
 366 /**
 367  * mpdm_seek - Seeks a value in an array (sequential).
 368  * @a: the array
 369  * @k: the key
 370  * @step: number of elements to step
 371  *
 372  * Seeks sequentially the value @k in the @a array in
 373  * increments of @step. A complete search should use a step of 1.
 374  * Returns the offset of the element if found, or -1 otherwise.
 375  * [Arrays]
 376  */
 377 int mpdm_seek(mpdm_t a, mpdm_t k, int step)
 378 {
 379         int n;
 380
 381         /* avoid stupid steps */
 382         if (step <= 0)
 383                 step = 1;
 384
 385         for (n = 0; n < mpdm_size(a); n += step) {
 386                 mpdm_t v = mpdm_aget(a, n);
 387
 388                 if (mpdm_cmp(v, k) == 0)
 389                         return n;
 390         }
 391
 392         return -1;
 393 }
 394
 395
 396 /**
 397  * mpdm_seek_s - Seeks a value in an array (sequential, string version).
 398  * @a: the array
 399  * @k: the key
 400  * @step: number of elements to step
 401  *
 402  * Seeks sequentially the value @k in the @a array in
 403  * increments of @step. A complete search should use a step of 1.
 404  * Returns the offset of the element if found, or -1 otherwise.
 405  * [Arrays]
 406  */
 407 int mpdm_seek_s(mpdm_t a, wchar_t * k, int step)
 408 {
 409         return mpdm_seek(a, MPDM_LS(k), step);
 410 }
 411
 412
 413 /**
 414  * mpdm_bseek - Seeks a value in an array (binary).
 415  * @a: the ordered array
 416  * @k: the key
 417  * @step: number of elements to step
 418  * @pos: the position where the element should be, if it's not found
 419  *
 420  * Seeks the value @k in the @a array in increments of @step.
 421  * The array should be sorted to work correctly. A complete search
 422  * should use a step of 1.
 423  *
 424  * If the element is found, returns the offset of the element
 425  * as a positive number; otherwise, -1 is returned and the position
 426  * where the element should be is stored in @pos. You can set @pos
 427  * to NULL if you don't mind.
 428  * [Arrays]
 429  */
 430 int mpdm_bseek(mpdm_t a, mpdm_t k, int step, int *pos)
 431 {
 432         int b, t, n, c;
 433
 434         /* avoid stupid steps */
 435         if (step <= 0)
 436                 step = 1;
 437
 438         b = 0;
 439         t = (mpdm_size(a) - 1) / step;
 440
 441         while (t >= b) {
 442                 mpdm_t v;
 443
 444                 n = (b + t) / 2;
 445                 if ((v = mpdm_aget(a, n * step)) == NULL)
 446                         break;
 447
 448                 c = mpdm_cmp(k, v);
 449
 450                 if (c == 0)
 451                         return n * step;
 452                 else
 453                 if (c < 0)
 454                         t = n - 1;
 455                 else
 456                         b = n + 1;
 457         }
 458
 459         if (pos != NULL)
 460                 *pos = b * step;
 461         return -1;
 462 }
 463
 464
 465 /**
 466  * mpdm_bseek_s - Seeks a value in an array (binary, string version).
 467  * @a: the ordered array
 468  * @k: the key
 469  * @step: number of elements to step
 470  * @pos: the position where the element should be, if it's not found
 471  *
 472  * Seeks the value @k in the @a array in increments of @step.
 473  * The array should be sorted to work correctly. A complete search
 474  * should use a step of 1.
 475  *
 476  * If the element is found, returns the offset of the element
 477  * as a positive number; otherwise, -1 is returned and the position
 478  * where the element should be is stored in @pos. You can set @pos
 479  * to NULL if you don't mind.
 480  * [Arrays]
 481  */
 482 int mpdm_bseek_s(mpdm_t a, wchar_t * k, int step, int *pos)
 483 {
 484         return mpdm_bseek(a, MPDM_LS(k), step, pos);
 485 }
 486
 487
 488 static int sort_cmp(const void *s1, const void *s2)
 489 /* qsort help function */
 490 {
 491         int ret = 0;
 492
 493         /* if callback is NULL, use basic value comparisons */
 494         if (sort_cb == NULL)
 495                 ret = mpdm_cmp(*(mpdm_t *) s1, *(mpdm_t *) s2);
 496         else {
 497                 /* executes the callback and converts to integer */
 498                 ret = mpdm_ival(mpdm_exec_2(sort_cb,
 499                                             (mpdm_t) * ((mpdm_t *) s1),
 500                                             (mpdm_t) * ((mpdm_t *) s2)));
 501         }
 502
 503         return ret;
 504 }
 505
 506
 507 /**
 508  * mpdm_sort - Sorts an array.
 509  * @a: the array
 510  * @step: increment step
 511  *
 512  * Sorts the array. @step is the number of elements to group together.
 513  *
 514  * Returns the sorted array (the original one is left untouched).
 515  * [Arrays]
 516  */
 517 mpdm_t mpdm_sort(mpdm_t a, int step)
 518 {
 519         return mpdm_sort_cb(a, step, NULL);
 520 }
 521
 522
 523 /**
 524  * mpdm_sort_cb - Sorts an array with a special sorting function.
 525  * @a: the array
 526  * @step: increment step
 527  * @asort_cb: sorting function
 528  *
 529  * Sorts the array. @step is the number of elements to group together.
 530  * For each pair of elements being sorted, the executable mpdm_t value
 531  * @sort_cb is called with an array containing the two elements as
 532  * argument. It must return a signed numerical mpdm_t value indicating
 533  * the sorting order.
 534  *
 535  * Returns the sorted array (the original one is left untouched).
 536  * [Arrays]
 537  */
 538 mpdm_t mpdm_sort_cb(mpdm_t a, int step, mpdm_t cb)
 539 {
 540         if (a == NULL)
 541                 return NULL;
 542
 543         /* creates a copy to be sorted */
 544         a = mpdm_clone(a);
 545
 546         sort_cb = cb;
 547
 548         /* references the array and the code, as the latter
 549            can include anything (including sweeping) */
 550         mpdm_ref(a);
 551         mpdm_ref(sort_cb);
 552
 553         qsort(a->data, mpdm_size(a) / step, sizeof(mpdm_t) * step, sort_cmp);
 554
 555         /* unreferences */
 556         mpdm_unref(sort_cb);
 557         mpdm_unref(a);
 558
 559         sort_cb = NULL;
 560
 561         return a;
 562 }
 563
 564
 565 /**
 566  * mpdm_split - Separates a string into an array of pieces.
 567  * @s: the separator
 568  * @v: the value to be separated
 569  *
 570  * Separates the @v string value into an array of pieces, using @s
 571  * as a separator.
 572  *
 573  * If the separator is NULL, the string is splitted by characters.
 574  *
 575  * If the string does not contain the separator, an array holding
 576  * the complete string is returned.
 577  * [Arrays]
 578  * [Strings]
 579  */
 580 mpdm_t mpdm_split(mpdm_t s, mpdm_t v)
 581 {
 582         mpdm_t w;
 583         wchar_t *ptr;
 584         wchar_t *sptr;
 585
 586         /* nothing to split? */
 587         if (v == NULL)
 588                 return NULL;
 589
 590         w = MPDM_A(0);
 591
 592         /* NULL separator? special case: split string in characters */
 593         if (s == NULL) {
 594                 for (ptr = mpdm_string(v); ptr && *ptr != '\0'; ptr++)
 595                         mpdm_push(w, MPDM_NS(ptr, 1));
 596
 597                 return w;
 598         }
 599
 600         /* travels the string finding separators and creating new values */
 601         for (ptr = v->data;
 602              *ptr != L'\0' && (sptr = wcsstr(ptr, s->data)) != NULL;
 603              ptr = sptr + mpdm_size(s))
 604                 mpdm_push(w, MPDM_NS(ptr, sptr - ptr));
 605
 606         /* add last part */
 607         mpdm_push(w, MPDM_S(ptr));
 608
 609         return w;
 610 }
 611
 612
 613 /**
 614  * mpdm_join - Joins all elements of an array into one.
 615  * @s: joiner string
 616  * @a: array to be joined
 617  *
 618  * Joins all elements from @a into one string, using @s as a glue.
 619  * [Arrays]
 620  * [Strings]
 621  */
 622 mpdm_t mpdm_join(mpdm_t s, mpdm_t a)
 623 {
 624         int n;
 625         wchar_t *ptr = NULL;
 626         int l = 0;
 627
 628         /* adds the first string */
 629         ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, 0));
 630
 631         for (n = 1; n < mpdm_size(a); n++) {
 632                 /* add separator */
 633                 ptr = mpdm_pokev(ptr, &l, s);
 634
 635                 /* add element */
 636                 ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, n));
 637         }
 638
 639         if (ptr == NULL)
 640                 return NULL;
 641
 642         ptr = mpdm_poke(ptr, &l, L"", 1, sizeof(wchar_t));
 643         return MPDM_ENS(ptr, l - 1);
 644 }