3 MPDM - Minimum Profit Data Manager
4 Copyright (C) 2003/2010 Angel Ortega <angel@triptico.com>
6 mpdm_a.c - Array management
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.
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.
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.
22 http://www.triptico.com
38 /* sorting callback code */
39 static mpdm_t sort_cb
= NULL
;
44 mpdm_t
mpdm_new_a(int flags
, int size
)
45 /* creates a new array value */
49 /* creates and expands */
50 if ((v
= mpdm_new(flags
| MPDM_MULTIPLE
, NULL
, 0)) != NULL
)
51 mpdm_expand(v
, 0, size
);
57 static int wrap_offset(const mpdm_t a
, int offset
)
58 /* manages negative offsets */
61 offset
= mpdm_size(a
) + offset
;
67 mpdm_t
mpdm_aclone(const mpdm_t v
)
68 /* clones a multiple value */
75 /* creates a similar value */
76 w
= mpdm_new_a(v
->flags
, v
->size
);
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
);
91 * mpdm_expand - Expands an array.
93 * @offset: insertion offset
94 * @num: number of elements to insert
96 * Expands an array value, inserting @num elements (initialized
97 * to NULL) at the specified @offset.
100 mpdm_t
mpdm_expand(mpdm_t a
, int offset
, int num
)
111 p
= (mpdm_t
*) realloc((mpdm_t
*)a
->data
, a
->size
* sizeof(mpdm_t
));
113 /* moves up from top of the array */
114 for (n
= a
->size
- 1; n
>= offset
+ num
; n
--)
117 /* fills the new space with blanks */
118 for (; n
>= offset
; n
--)
129 * mpdm_collapse - Collapses an array.
131 * @offset: deletion offset
132 * @num: number of elements to collapse
134 * Collapses an array value, deleting @num elements at
135 * the specified @offset.
138 mpdm_t
mpdm_collapse(mpdm_t a
, int offset
, int num
)
144 /* don't try to delete beyond the limit */
145 if (offset
+ num
> a
->size
)
146 num
= a
->size
- offset
;
148 p
= (mpdm_t
*) a
->data
;
150 /* unrefs the about-to-be-deleted elements */
151 for (n
= offset
; n
< offset
+ num
; n
++)
154 /* array is now shorter */
157 /* moves down the elements */
158 for (n
= offset
; n
< a
->size
; n
++)
161 /* finally shrinks the memory block */
162 a
->data
= realloc(p
, a
->size
* sizeof(mpdm_t
));
170 * mpdm_aset - Sets the value of an array's element.
172 * @e: the element to be assigned
173 * @offset: the subscript of the element
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
180 mpdm_t
mpdm_aset(mpdm_t a
, mpdm_t e
, int offset
)
184 offset
= wrap_offset(a
, offset
);
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);
191 p
= (mpdm_t
*) a
->data
;
193 /* assigns and references */
195 mpdm_unref(p
[offset
]);
204 * mpdm_aget - Gets an element of an array.
206 * @offset: the subscript of the element
208 * Returns the element at @offset of the array @a.
211 mpdm_t
mpdm_aget(const mpdm_t a
, int offset
)
216 offset
= wrap_offset(a
, offset
);
218 /* boundary checks */
219 if (offset
>= 0 && offset
< mpdm_size(a
)) {
220 p
= (mpdm_t
*) a
->data
;
231 * mpdm_ins - Insert an element in an array.
233 * @e: the element to be inserted
234 * @offset: subscript where the element is going to be inserted
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.
241 mpdm_t
mpdm_ins(mpdm_t a
, mpdm_t e
, int offset
)
243 offset
= wrap_offset(a
, offset
);
245 /* open room and set value */
246 if (mpdm_expand(a
, offset
, 1))
247 mpdm_aset(a
, e
, offset
);
254 * mpdm_adel - Deletes an element of an array.
256 * @offset: subscript of the element to be deleted
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).
263 * Always returns NULL (version prior to 1.0.10 used to return
264 * the deleted element).
267 mpdm_t
mpdm_adel(mpdm_t a
, int offset
)
270 mpdm_collapse(a
, wrap_offset(a
, offset
), 1);
277 * mpdm_shift - Extracts the first element of an array.
280 * Extracts the first element of the array. The array
281 * is shrinked by one.
283 * Returns the element.
286 mpdm_t
mpdm_shift(mpdm_t a
)
288 mpdm_t v
= mpdm_ref(mpdm_aget(a
, 0));
292 return mpdm_unrefnd(v
);
297 * mpdm_push - Pushes a value into an array.
301 * Pushes a value into an array (i.e. inserts at the end).
304 mpdm_t
mpdm_push(mpdm_t a
, mpdm_t e
)
306 /* inserts at the end */
307 return mpdm_ins(a
, e
, mpdm_size(a
));
312 * mpdm_pop - Pops a value from an array.
315 * Pops a value from the array (i.e. deletes from the end
319 mpdm_t
mpdm_pop(mpdm_t a
)
321 mpdm_t v
= mpdm_ref(mpdm_aget(a
, -1));
325 return mpdm_unrefnd(v
);
330 * mpdm_queue - Implements a queue in an array.
332 * @e: the element to be pushed
333 * @size: maximum size of array
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.
339 * Returns the deleted element, or NULL if the array doesn't have
340 * @size elements yet.
343 mpdm_t
mpdm_queue(mpdm_t a
, mpdm_t e
, int size
)
347 /* zero size is nonsense */
349 /* loop until a has the desired size */
350 while (mpdm_size(a
) > size
)
353 if (mpdm_size(a
) == size
)
363 static int seek(const mpdm_t a
, const mpdm_t k
, const wchar_t *ks
, int step
)
367 /* avoid stupid steps */
373 for (n
= 0; o
== -1 && n
< mpdm_size(a
); n
+= step
) {
376 mpdm_t v
= mpdm_aget(a
, n
);
378 r
= ks
? mpdm_cmp_s(v
, ks
) : mpdm_cmp(v
, k
);
389 * mpdm_seek - Seeks a value in an array (sequential).
392 * @step: number of elements to step
394 * Seeks sequentially the value @k in the @a array in
395 * increments of @step. A complete search should use a step of 1.
396 * Returns the offset of the element if found, or -1 otherwise.
399 int mpdm_seek(const mpdm_t a
, const mpdm_t k
, int step
)
401 return seek(a
, k
, NULL
, step
);
406 * mpdm_seek_s - Seeks a value in an array (sequential, string version).
409 * @step: number of elements to step
411 * Seeks sequentially the value @k in the @a array in
412 * increments of @step. A complete search should use a step of 1.
413 * Returns the offset of the element if found, or -1 otherwise.
416 int mpdm_seek_s(const mpdm_t a
, const wchar_t *k
, int step
)
418 return seek(a
, NULL
, k
, step
);
422 static int bseek(const mpdm_t a
, const mpdm_t k
, const wchar_t *ks
, int step
, int *pos
)
426 /* avoid stupid steps */
431 t
= (mpdm_size(a
) - 1) / step
;
435 while (o
== -1 && t
>= b
) {
439 if ((v
= mpdm_aget(a
, n
* step
)) == NULL
)
442 c
= ks
? mpdm_cmp_s(v
, ks
) : mpdm_cmp(v
, k
);
461 * mpdm_bseek - Seeks a value in an array (binary).
462 * @a: the ordered array
464 * @step: number of elements to step
465 * @pos: the position where the element should be, if it's not found
467 * Seeks the value @k in the @a array in increments of @step.
468 * The array should be sorted to work correctly. A complete search
469 * should use a step of 1.
471 * If the element is found, returns the offset of the element
472 * as a positive number; otherwise, -1 is returned and the position
473 * where the element should be is stored in @pos. You can set @pos
474 * to NULL if you don't mind.
477 int mpdm_bseek(const mpdm_t a
, const mpdm_t k
, int step
, int *pos
)
479 return bseek(a
, k
, NULL
, step
, pos
);
484 * mpdm_bseek_s - Seeks a value in an array (binary, string version).
485 * @a: the ordered array
487 * @step: number of elements to step
488 * @pos: the position where the element should be, if it's not found
490 * Seeks the value @k in the @a array in increments of @step.
491 * The array should be sorted to work correctly. A complete search
492 * should use a step of 1.
494 * If the element is found, returns the offset of the element
495 * as a positive number; otherwise, -1 is returned and the position
496 * where the element should be is stored in @pos. You can set @pos
497 * to NULL if you don't mind.
500 int mpdm_bseek_s(const mpdm_t a
, const wchar_t *k
, int step
, int *pos
)
502 return bseek(a
, NULL
, k
, step
, pos
);
506 static int sort_cmp(const void *s1
, const void *s2
)
507 /* qsort help function */
511 /* if callback is NULL, use basic value comparisons */
513 ret
= mpdm_cmp(*(mpdm_t
*) s1
, *(mpdm_t
*) s2
);
515 /* executes the callback and converts to integer */
516 ret
= mpdm_ival(mpdm_exec_2(sort_cb
,
517 (mpdm_t
) * ((mpdm_t
*) s1
),
518 (mpdm_t
) * ((mpdm_t
*) s2
))
527 * mpdm_sort - Sorts an array.
529 * @step: increment step
531 * Sorts the array. @step is the number of elements to group together.
533 * Returns the same array, sorted (versions prior to 1.0.10 returned
537 mpdm_t
mpdm_sort(const mpdm_t a
, int step
)
539 return mpdm_sort_cb(a
, step
, NULL
);
544 * mpdm_sort_cb - Sorts an array with a special sorting function.
546 * @step: increment step
547 * @asort_cb: sorting function
549 * Sorts the array. @step is the number of elements to group together.
550 * For each pair of elements being sorted, the executable mpdm_t value
551 * @sort_cb is called with an array containing the two elements as
552 * argument. It must return a signed numerical mpdm_t value indicating
555 * Returns the same array, sorted (versions prior to 1.0.10 returned
559 mpdm_t
mpdm_sort_cb(mpdm_t a
, int step
, mpdm_t cb
)
564 /* references the array and the code, as the latter
565 can include anything (including sweeping) */
569 qsort((mpdm_t
*)a
->data
, mpdm_size(a
) / step
, sizeof(mpdm_t
) * step
, sort_cmp
);
572 mpdm_unrefnd(sort_cb
);
583 * mpdm_split_s - Separates a string into an array of pieces (string version).
585 * @v: the value to be separated
587 * Separates the @v string value into an array of pieces, using @s
590 * If the separator is NULL, the string is splitted by characters.
592 * If the string does not contain the separator, an array holding
593 * the complete string is returned.
597 mpdm_t
mpdm_split_s(const wchar_t *s
, const mpdm_t v
)
607 /* NULL separator? special case: split string in characters */
609 for (ptr
= mpdm_string(v
); ptr
&& *ptr
!= '\0'; ptr
++)
610 mpdm_push(w
, MPDM_NS(ptr
, 1));
618 /* travels the string finding separators and creating new values */
620 *ptr
!= L
'\0' && (sptr
= wcsstr(ptr
, s
)) != NULL
;
622 mpdm_push(w
, MPDM_NS(ptr
, sptr
- ptr
));
625 mpdm_push(w
, MPDM_S(ptr
));
636 * mpdm_split - Separates a string into an array of pieces.
638 * @v: the value to be separated
640 * Separates the @v string value into an array of pieces, using @s
643 * If the separator is NULL, the string is splitted by characters.
645 * If the string does not contain the separator, an array holding
646 * the complete string is returned.
650 mpdm_t
mpdm_split(const mpdm_t s
, const mpdm_t v
)
658 ss
= (wchar_t *)s
->data
;
660 r
= mpdm_split_s(ss
, v
);
669 * mpdm_join_s - Joins all elements of an array into one (string version).
671 * @a: array to be joined
673 * Joins all elements from @a into one string, using @s as a glue.
677 mpdm_t
mpdm_join_s(const wchar_t *s
, const mpdm_t a
)
687 if (MPDM_IS_ARRAY(a
)) {
688 /* adds the first string */
689 ptr
= mpdm_pokev(ptr
, &l
, mpdm_aget(a
, 0));
691 ss
= s
? wcslen(s
) : 0;
693 for (n
= 1; n
< mpdm_size(a
); n
++) {
695 ptr
= mpdm_pokewsn(ptr
, &l
, s
, ss
);
698 ptr
= mpdm_pokev(ptr
, &l
, mpdm_aget(a
, n
));
701 ptr
= mpdm_poke(ptr
, &l
, L
"", 1, sizeof(wchar_t));
702 r
= MPDM_ENS(ptr
, l
- 1);
712 * mpdm_join - Joins all elements of an array into one.
714 * @a: array to be joined
716 * Joins all elements from @a into one string, using @s as a glue.
720 mpdm_t
mpdm_join(const mpdm_t s
, const mpdm_t a
)
725 r
= mpdm_join_s(s
? mpdm_string(s
) : NULL
, a
);