mpdm_a.c

   1 /*
   2
   3     MPDM - Minimum Profit Data Manager
   4     Copyright (C) 2003/2010 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 /** data **/
  37
  38 /* sorting callback code */
  39 static mpdm_t sort_cb = NULL;
  40
  41
  42 /** code **/
  43
  44 mpdm_t mpdm_new_a(int flags, int size)
  45 /* creates a new array value */
  46 {
  47     mpdm_t v;
  48
  49     /* creates and expands */
  50     if ((v = mpdm_new(flags | MPDM_MULTIPLE | MPDM_FREE, NULL, 0)) != NULL)
  51         mpdm_expand(v, 0, size);
  52
  53     return v;
  54 }
  55
  56
  57 static int wrap_offset(const mpdm_t a, int offset)
  58 /* manages negative offsets */
  59 {
  60     if (offset < 0)
  61         offset = mpdm_size(a) + offset;
  62
  63     return offset;
  64 }
  65
  66
  67 mpdm_t mpdm_aclone(const mpdm_t v)
  68 /* clones a multiple value */
  69 {
  70     mpdm_t w;
  71     int n;
  72
  73     mpdm_ref(v);
  74
  75     /* creates a similar value */
  76     w = mpdm_new_a(v->flags, v->size);
  77
  78     mpdm_ref(w);
  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     mpdm_unrefnd(w);
  85
  86     mpdm_unref(v);
  87
  88     return w;
  89 }
  90
  91
  92 /* interface */
  93
  94 /**
  95  * mpdm_expand - Expands an array.
  96  * @a: the array
  97  * @offset: insertion offset
  98  * @num: number of elements to insert
  99  *
 100  * Expands an array value, inserting @num elements (initialized
 101  * to NULL) at the specified @offset.
 102  * [Arrays]
 103  */
 104 mpdm_t mpdm_expand(mpdm_t a, int offset, int num)
 105 {
 106     int n;
 107     mpdm_t *p;
 108
 109     /* sanity checks */
 110     if (num > 0) {
 111         /* add size */
 112         a->size += num;
 113
 114         /* expand */
 115         p = (mpdm_t *) realloc((mpdm_t *) a->data,
 116                                a->size * sizeof(mpdm_t));
 117
 118         /* moves up from top of the array */
 119         for (n = a->size - 1; n >= offset + num; n--)
 120             p[n] = p[n - num];
 121
 122         /* fills the new space with blanks */
 123         for (; n >= offset; n--)
 124             p[n] = NULL;
 125
 126         a->data = p;
 127     }
 128
 129     return a;
 130 }
 131
 132
 133 /**
 134  * mpdm_collapse - Collapses an array.
 135  * @a: the array
 136  * @offset: deletion offset
 137  * @num: number of elements to collapse
 138  *
 139  * Collapses an array value, deleting @num elements at
 140  * the specified @offset.
 141  * [Arrays]
 142  */
 143 mpdm_t mpdm_collapse(mpdm_t a, int offset, int num)
 144 {
 145     int n;
 146     mpdm_t *p;
 147
 148     if (num > 0) {
 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         a->data = realloc(p, a->size * sizeof(mpdm_t));
 168     }
 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 new element (versions prior to 1.0.10 returned the
 182  * old element).
 183  * [Arrays]
 184  */
 185 mpdm_t mpdm_aset(mpdm_t a, mpdm_t e, int offset)
 186 {
 187     mpdm_t *p;
 188
 189     mpdm_ref(a);
 190     mpdm_ref(e);
 191
 192     offset = wrap_offset(a, offset);
 193
 194     if (offset >= 0) {
 195         /* if the array is shorter than offset, expand to make room for it */
 196         if (offset >= mpdm_size(a))
 197             mpdm_expand(a, mpdm_size(a), offset - mpdm_size(a) + 1);
 198
 199         p = (mpdm_t *) a->data;
 200
 201         /* assigns and references */
 202         mpdm_ref(e);
 203         mpdm_unref(p[offset]);
 204         p[offset] = e;
 205     }
 206
 207     mpdm_unref(e);
 208     mpdm_unref(a);
 209
 210     return e;
 211 }
 212
 213
 214 /**
 215  * mpdm_aget - Gets an element of an array.
 216  * @a: the array
 217  * @offset: the subscript of the element
 218  *
 219  * Returns the element at @offset of the array @a.
 220  * [Arrays]
 221  */
 222 mpdm_t mpdm_aget(const mpdm_t a, int offset)
 223 {
 224     mpdm_t r;
 225     mpdm_t *p;
 226
 227     offset = wrap_offset(a, offset);
 228
 229     /* boundary checks */
 230     if (offset >= 0 && offset < mpdm_size(a)) {
 231         p = (mpdm_t *) a->data;
 232         r = p[offset];
 233     }
 234     else
 235         r = NULL;
 236
 237     return r;
 238 }
 239
 240
 241 /**
 242  * mpdm_ins - Insert an element in an array.
 243  * @a: the array
 244  * @e: the element to be inserted
 245  * @offset: subscript where the element is going to be inserted
 246  *
 247  * Inserts the @e value in the @a array at @offset.
 248  * Further elements are pushed up, so the array increases its size
 249  * by one. Returns the inserted element.
 250  * [Arrays]
 251  */
 252 mpdm_t mpdm_ins(mpdm_t a, mpdm_t e, int offset)
 253 {
 254     mpdm_ref(a);
 255     mpdm_ref(e);
 256
 257     offset = wrap_offset(a, offset);
 258
 259     /* open room and set value */
 260     mpdm_expand(a, offset, 1);
 261     mpdm_aset(a, e, offset);
 262
 263     mpdm_unref(e);
 264     mpdm_unref(a);
 265
 266     return e;
 267 }
 268
 269
 270 /**
 271  * mpdm_adel - Deletes an element of an array.
 272  * @a: the array
 273  * @offset: subscript of the element to be deleted
 274  *
 275  * Deletes the element at @offset of the @a array. The array
 276  * is shrinked by one. If @offset is negative, is counted from
 277  * the end of the array (so a value of -1 means delete the
 278  * last element of the array).
 279  *
 280  * Always returns NULL (version prior to 1.0.10 used to return
 281  * the deleted element).
 282  * [Arrays]
 283  */
 284 mpdm_t mpdm_adel(mpdm_t a, int offset)
 285 {
 286     mpdm_ref(a);
 287
 288     if (mpdm_size(a))
 289         mpdm_collapse(a, wrap_offset(a, offset), 1);
 290
 291     mpdm_unref(a);
 292
 293     return NULL;
 294 }
 295
 296
 297 /**
 298  * mpdm_shift - Extracts the first element of an array.
 299  * @a: the array
 300  *
 301  * Extracts the first element of the array. The array
 302  * is shrinked by one.
 303  *
 304  * Returns the element.
 305  * [Arrays]
 306  */
 307 mpdm_t mpdm_shift(mpdm_t a)
 308 {
 309     mpdm_t r;
 310
 311     mpdm_ref(a);
 312
 313     r = mpdm_ref(mpdm_aget(a, 0));
 314     mpdm_adel(a, 0);
 315     mpdm_unrefnd(r);
 316
 317     mpdm_unref(a);
 318
 319     return r;
 320 }
 321
 322
 323 /**
 324  * mpdm_push - Pushes a value into an array.
 325  * @a: the array
 326  * @e: the value
 327  *
 328  * Pushes a value into an array (i.e. inserts at the end).
 329  * [Arrays]
 330  */
 331 mpdm_t mpdm_push(mpdm_t a, mpdm_t e)
 332 {
 333     mpdm_t r;
 334
 335     mpdm_ref(a);
 336
 337     /* inserts at the end */
 338     r = mpdm_ins(a, e, mpdm_size(a));
 339
 340     mpdm_unref(a);
 341
 342     return r;
 343 }
 344
 345
 346 /**
 347  * mpdm_pop - Pops a value from an array.
 348  * @a: the array
 349  *
 350  * Pops a value from the array (i.e. deletes from the end
 351  * and returns it).
 352  * [Arrays]
 353  */
 354 mpdm_t mpdm_pop(mpdm_t a)
 355 {
 356     mpdm_t r;
 357
 358     mpdm_ref(a);
 359
 360     r = mpdm_ref(mpdm_aget(a, -1));
 361     mpdm_adel(a, -1);
 362     r = mpdm_unrefnd(r);
 363
 364     mpdm_unref(a);
 365
 366     return r;
 367 }
 368
 369
 370 /**
 371  * mpdm_queue - Implements a queue in an array.
 372  * @a: the array
 373  * @e: the element to be pushed
 374  * @size: maximum size of array
 375  *
 376  * Pushes the @e element into the @a array. If the array already has
 377  * @size elements, the first (oldest) element is deleted from the
 378  * queue and returned.
 379  *
 380  * Returns the deleted element, or NULL if the array doesn't have
 381  * @size elements yet.
 382  * [Arrays]
 383  */
 384 mpdm_t mpdm_queue(mpdm_t a, mpdm_t e, int size)
 385 {
 386     mpdm_t v = NULL;
 387
 388     mpdm_ref(a);
 389     mpdm_ref(e);
 390
 391     /* zero size is nonsense */
 392     if (size) {
 393         /* loop until a has the desired size */
 394         while (mpdm_size(a) > size)
 395             mpdm_adel(a, 0);
 396
 397         if (mpdm_size(a) == size)
 398             v = mpdm_shift(a);
 399
 400         mpdm_push(a, e);
 401     }
 402
 403     mpdm_unref(e);
 404     mpdm_unref(a);
 405
 406     return v;
 407 }
 408
 409
 410 /**
 411  * mpdm_seek - Seeks a value in an array (sequential).
 412  * @a: the array
 413  * @k: the key
 414  * @step: number of elements to step
 415  *
 416  * Seeks sequentially the value @k in the @a array in
 417  * increments of @step. A complete search should use a step of 1.
 418  * Returns the offset of the element if found, or -1 otherwise.
 419  * [Arrays]
 420  */
 421 int mpdm_seek(const mpdm_t a, const mpdm_t k, int step)
 422 {
 423     int n, o;
 424
 425     mpdm_ref(a);
 426     mpdm_ref(k);
 427
 428     /* avoid stupid steps */
 429     if (step <= 0)
 430         step = 1;
 431
 432     o = -1;
 433
 434     for (n = 0; o == -1 && n < mpdm_size(a); n += step) {
 435         int r;
 436
 437         mpdm_t v = mpdm_aget(a, n);
 438
 439         r = mpdm_cmp(v, k);
 440
 441         if (r == 0)
 442             o = n;
 443     }
 444
 445     mpdm_unref(k);
 446     mpdm_unref(a);
 447
 448     return o;
 449 }
 450
 451
 452 /**
 453  * mpdm_seek_s - Seeks a value in an array (sequential, string version).
 454  * @a: the array
 455  * @k: the key
 456  * @step: number of elements to step
 457  *
 458  * Seeks sequentially the value @k in the @a array in
 459  * increments of @step. A complete search should use a step of 1.
 460  * Returns the offset of the element if found, or -1 otherwise.
 461  * [Arrays]
 462  */
 463 int mpdm_seek_s(const mpdm_t a, const wchar_t * k, int step)
 464 {
 465     return mpdm_seek(a, MPDM_AS(k), step);
 466 }
 467
 468
 469 /**
 470  * mpdm_bseek - Seeks a value in an array (binary).
 471  * @a: the ordered array
 472  * @k: the key
 473  * @step: number of elements to step
 474  * @pos: the position where the element should be, if it's not found
 475  *
 476  * Seeks the value @k in the @a array in increments of @step.
 477  * The array should be sorted to work correctly. A complete search
 478  * should use a step of 1.
 479  *
 480  * If the element is found, returns the offset of the element
 481  * as a positive number; otherwise, -1 is returned and the position
 482  * where the element should be is stored in @pos. You can set @pos
 483  * to NULL if you don't mind.
 484  * [Arrays]
 485  */
 486 int mpdm_bseek(const mpdm_t a, const mpdm_t k, int step, int *pos)
 487 {
 488     int b, t, n, c, o;
 489
 490     mpdm_ref(a);
 491     mpdm_ref(k);
 492
 493     /* avoid stupid steps */
 494     if (step <= 0)
 495         step = 1;
 496
 497     b = 0;
 498     t = (mpdm_size(a) - 1) / step;
 499
 500     o = -1;
 501
 502     while (o == -1 && t >= b) {
 503         mpdm_t v;
 504
 505         n = (b + t) / 2;
 506         if ((v = mpdm_aget(a, n * step)) == NULL)
 507             break;
 508
 509         c = mpdm_cmp(v, k);
 510
 511         if (c == 0)
 512             o = n * step;
 513         else
 514         if (c > 0)
 515             t = n - 1;
 516         else
 517             b = n + 1;
 518     }
 519
 520     if (pos != NULL)
 521         *pos = b * step;
 522
 523     mpdm_unref(k);
 524     mpdm_unref(a);
 525
 526     return o;
 527 }
 528
 529
 530 /**
 531  * mpdm_bseek_s - Seeks a value in an array (binary, string version).
 532  * @a: the ordered array
 533  * @k: the key
 534  * @step: number of elements to step
 535  * @pos: the position where the element should be, if it's not found
 536  *
 537  * Seeks the value @k in the @a array in increments of @step.
 538  * The array should be sorted to work correctly. A complete search
 539  * should use a step of 1.
 540  *
 541  * If the element is found, returns the offset of the element
 542  * as a positive number; otherwise, -1 is returned and the position
 543  * where the element should be is stored in @pos. You can set @pos
 544  * to NULL if you don't mind.
 545  * [Arrays]
 546  */
 547 int mpdm_bseek_s(const mpdm_t a, const wchar_t * k, int step, int *pos)
 548 {
 549     return mpdm_bseek(a, MPDM_AS(k), step, pos);
 550 }
 551
 552
 553 static int sort_cmp(const void *s1, const void *s2)
 554 /* qsort help function */
 555 {
 556     int ret = 0;
 557
 558     /* if callback is NULL, use basic value comparisons */
 559     if (sort_cb == NULL)
 560         ret = mpdm_cmp(*(mpdm_t *) s1, *(mpdm_t *) s2);
 561     else {
 562         /* executes the callback and converts to integer */
 563         ret = mpdm_ival(mpdm_exec_2(sort_cb,
 564                                     (mpdm_t) * ((mpdm_t *) s1),
 565                                     (mpdm_t) * ((mpdm_t *) s2), NULL)
 566             );
 567     }
 568
 569     return ret;
 570 }
 571
 572
 573 /**
 574  * mpdm_sort - Sorts an array.
 575  * @a: the array
 576  * @step: increment step
 577  *
 578  * Sorts the array. @step is the number of elements to group together.
 579  *
 580  * Returns the same array, sorted (versions prior to 1.0.10 returned
 581  * a new array).
 582  * [Arrays]
 583  */
 584 mpdm_t mpdm_sort(const mpdm_t a, int step)
 585 {
 586     return mpdm_sort_cb(a, step, NULL);
 587 }
 588
 589
 590 /**
 591  * mpdm_sort_cb - Sorts an array with a special sorting function.
 592  * @a: the array
 593  * @step: increment step
 594  * @asort_cb: sorting function
 595  *
 596  * Sorts the array. @step is the number of elements to group together.
 597  * For each pair of elements being sorted, the executable mpdm_t value
 598  * @sort_cb is called with an array containing the two elements as
 599  * argument. It must return a signed numerical mpdm_t value indicating
 600  * the sorting order.
 601  *
 602  * Returns the same array, sorted (versions prior to 1.0.10 returned
 603  * a new array).
 604  * [Arrays]
 605  */
 606 mpdm_t mpdm_sort_cb(mpdm_t a, int step, mpdm_t cb)
 607 {
 608     if (a != NULL) {
 609         sort_cb = cb;
 610
 611         mpdm_ref(a);
 612         mpdm_ref(sort_cb);
 613
 614         qsort((mpdm_t *) a->data, mpdm_size(a) / step,
 615               sizeof(mpdm_t) * step, sort_cmp);
 616
 617         /* unreferences */
 618         mpdm_unrefnd(sort_cb);
 619         mpdm_unrefnd(a);
 620
 621         sort_cb = NULL;
 622     }
 623
 624     return a;
 625 }
 626
 627
 628 /**
 629  * mpdm_split_s - Separates a string into an array of pieces (string version).
 630  * @v: the value to be separated
 631  * @s: the separator
 632  *
 633  * Separates the @v string value into an array of pieces, using @s
 634  * as a separator.
 635  *
 636  * If the separator is NULL, the string is splitted by characters.
 637  *
 638  * If the string does not contain the separator, an array holding
 639  * the complete string is returned.
 640  * [Arrays]
 641  * [Strings]
 642  */
 643 mpdm_t mpdm_split_s(const mpdm_t v, const wchar_t *s)
 644 {
 645     mpdm_t w = NULL;
 646     const wchar_t *ptr;
 647
 648     if (v != NULL) {
 649         mpdm_ref(v);
 650
 651         w = MPDM_A(0);
 652         mpdm_ref(w);
 653
 654         /* NULL separator? special case: split string in characters */
 655         if (s == NULL) {
 656             for (ptr = mpdm_string(v); ptr && *ptr != '\0'; ptr++)
 657                 mpdm_push(w, MPDM_NS(ptr, 1));
 658         }
 659         else {
 660             wchar_t *sptr;
 661             int ss;
 662
 663             ss = wcslen(s);
 664
 665             /* travels the string finding separators and creating new values */
 666             for (ptr = v->data;
 667                  *ptr != L'\0' && (sptr = wcsstr(ptr, s)) != NULL;
 668                  ptr = sptr + ss)
 669                 mpdm_push(w, MPDM_NS(ptr, sptr - ptr));
 670
 671             /* add last part */
 672             mpdm_push(w, MPDM_S(ptr));
 673         }
 674
 675         mpdm_unrefnd(w);
 676
 677         mpdm_unref(v);
 678     }
 679
 680     return w;
 681 }
 682
 683
 684 /**
 685  * mpdm_split - Separates a string into an array of pieces.
 686  * @v: the value to be separated
 687  * @s: the separator
 688  *
 689  * Separates the @v string value into an array of pieces, using @s
 690  * as a separator.
 691  *
 692  * If the separator is NULL, the string is splitted by characters.
 693  *
 694  * If the string does not contain the separator, an array holding
 695  * the complete string is returned.
 696  * [Arrays]
 697  * [Strings]
 698  */
 699 mpdm_t mpdm_split(const mpdm_t v, const mpdm_t s)
 700 {
 701     mpdm_t r;
 702     wchar_t *ss = NULL;
 703
 704     mpdm_ref(s);
 705
 706     if (s != NULL)
 707         ss = (wchar_t *) s->data;
 708
 709     r = mpdm_split_s(v, ss);
 710
 711     mpdm_unref(s);
 712
 713     return r;
 714 }
 715
 716
 717 /**
 718  * mpdm_join_s - Joins all elements of an array into one (string version).
 719  * @a: array to be joined
 720  * @s: joiner string
 721  *
 722  * Joins all elements from @a into one string, using @s as a glue.
 723  * [Arrays]
 724  * [Strings]
 725  */
 726 mpdm_t mpdm_join_s(const mpdm_t a, const wchar_t *s)
 727 {
 728     int n;
 729     wchar_t *ptr = NULL;
 730     int l = 0;
 731     int ss;
 732     mpdm_t r = NULL;
 733
 734     mpdm_ref(a);
 735
 736     if (MPDM_IS_ARRAY(a)) {
 737         /* adds the first string */
 738         ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, 0));
 739
 740         ss = s ? wcslen(s) : 0;
 741
 742         for (n = 1; n < mpdm_size(a); n++) {
 743             /* add separator */
 744             ptr = mpdm_pokewsn(ptr, &l, s, ss);
 745
 746             /* add element */
 747             ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, n));
 748         }
 749
 750         ptr = mpdm_poke(ptr, &l, L"", 1, sizeof(wchar_t));
 751         r = MPDM_ENS(ptr, l - 1);
 752     }
 753
 754     mpdm_unref(a);
 755
 756     return r;
 757 }
 758
 759
 760 /**
 761  * mpdm_join - Joins all elements of an array into one.
 762  * @a: array to be joined
 763  * @s: joiner string
 764  *
 765  * Joins all elements from @a into one string, using @s as a glue.
 766  * [Arrays]
 767  * [Strings]
 768  */
 769 mpdm_t mpdm_join(const mpdm_t a, const mpdm_t s)
 770 {
 771     mpdm_t r;
 772
 773     mpdm_ref(s);
 774     r = mpdm_join_s(a, s ? mpdm_string(s) : NULL);
 775     mpdm_unref(s);
 776
 777     return r;
 778 }