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