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