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