3 MPDM - Minimum Profit Data Manager
4 Copyright (C) 2003/2010 Angel Ortega <angel@triptico.com>
6 mpdm_h.c - Hash 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
37 /* prototype for the one-time wrapper hash function */
38 static int switch_hash_func(const wchar_t *, int);
40 /* pointer to the hashing function */
41 static int (*mpdm_hash_func
) (const wchar_t *, int) = switch_hash_func
;
43 static int standard_hash_func(const wchar_t * string
, int mod
)
44 /* computes a hashing function on string */
48 for (c
= 0; *string
!= L
'\0'; string
++)
55 static int null_hash_func(const wchar_t * string
, int mod
)
60 static int switch_hash_func(const wchar_t * string
, int mod
)
61 /* one-time wrapper for hash method autodetection */
63 /* commute the real hashing function on
64 having the MPDM_NULL_HASH environment variable set */
65 if (getenv("MPDM_NULL_HASH") != NULL
)
66 mpdm_hash_func
= null_hash_func
;
68 mpdm_hash_func
= standard_hash_func
;
70 /* and fall back to it */
71 return mpdm_hash_func(string
, mod
);
74 #define HASH_BUCKET_S(h, k) mpdm_hash_func(k, mpdm_size(h))
75 #define HASH_BUCKET(h, k) (mpdm_hash_func(mpdm_string(k), mpdm_size(h)))
80 * mpdm_hsize - Returns the number of pairs of a hash.
83 * Returns the number of key-value pairs of a hash.
86 int mpdm_hsize(const mpdm_t h
)
93 for (n
= 0; n
< mpdm_size(h
); n
++) {
94 mpdm_t b
= mpdm_aget(h
, n
);
105 * mpdm_hget - Gets a value from a hash.
109 * Gets the value from the hash @h having @k as key, or
110 * NULL if the key does not exist.
113 mpdm_t
mpdm_hget(const mpdm_t h
, const mpdm_t k
)
123 /* if hash is not empty... */
124 if ((b
= mpdm_aget(h
, HASH_BUCKET(h
, k
))) != NULL
)
125 n
= mpdm_bseek(b
, k
, 2, NULL
);
128 v
= mpdm_aget(b
, n
+ 1);
139 * mpdm_hget_s - Gets the value from a hash (string version).
143 * Gets the value from the hash @h having @k as key, or
144 * NULL if the key does not exist.
147 mpdm_t
mpdm_hget_s(const mpdm_t h
, const wchar_t * k
)
149 return mpdm_hget(h
, MPDM_S(k
));
154 * mpdm_exists - Tests if a key exists.
158 * Returns 1 if @k is defined in @h, or 0 othersize.
161 int mpdm_exists(const mpdm_t h
, const mpdm_t k
)
171 /* if hash is not empty... */
172 if ((b
= mpdm_aget(h
, HASH_BUCKET(h
, k
))) != NULL
) {
173 /* if bucket exists, binary-seek it */
174 if ((n
= mpdm_bseek(b
, k
, 2, NULL
)) >= 0)
187 * mpdm_hset - Sets a value in a hash.
192 * Sets the value @v to the key @k in the hash @h. Returns
193 * the new value (versions prior to 1.0.10 returned the old
197 mpdm_t
mpdm_hset(mpdm_t h
, mpdm_t k
, mpdm_t v
)
206 /* if hash is empty, create an optimal number of buckets */
207 if (mpdm_size(h
) == 0)
208 mpdm_expand(h
, 0, mpdm
->hash_buckets
);
210 n
= HASH_BUCKET(h
, k
);
212 if ((b
= mpdm_aget(h
, n
)) != NULL
) {
215 /* bucket exists; try to find the key there */
216 n
= mpdm_bseek(b
, k
, 2, &pos
);
219 /* the pair does not exist: create it */
221 mpdm_expand(b
, n
, 2);
227 /* the bucket does not exist; create it */
230 /* put the bucket into the hash */
240 r
= mpdm_aset(b
, v
, n
+ 1);
251 * mpdm_hset_s - Sets a value in a hash (string version).
256 * Sets the value @v to the key @k in the hash @h. Returns
257 * the new value (versions prior to 1.0.10 returned the old
261 mpdm_t
mpdm_hset_s(mpdm_t h
, const wchar_t * k
, mpdm_t v
)
263 return mpdm_hset(h
, MPDM_S(k
), v
);
268 * mpdm_hdel - Deletes a key from a hash.
272 * Deletes the key @k from the hash @h. Returns NULL
273 * (versions prior to 1.0.10 returned the deleted value).
276 mpdm_t
mpdm_hdel(mpdm_t h
, const mpdm_t k
)
284 if ((b
= mpdm_aget(h
, HASH_BUCKET(h
, k
))) != NULL
) {
286 if ((n
= mpdm_bseek(b
, k
, 2, NULL
)) >= 0) {
287 /* collapse the bucket */
288 mpdm_collapse(b
, n
, 2);
300 * mpdm_keys - Returns the keys of a hash.
303 * Returns an array containing all the keys of the @h hash.
307 mpdm_t
mpdm_keys(const mpdm_t h
)
314 /* create an array with the same number of elements */
315 a
= MPDM_A(mpdm_hsize(h
));
320 while (mpdm_iterator(h
, &c
, &k
, NULL
))
321 mpdm_aset(a
, k
, n
++);
332 * mpdm_iterator - Iterates through the content of a hash or array.
333 * @h: the hash (or array)
334 * @context: A pointer to an opaque context
335 * @v1: a pointer to a value
336 * @v2: another pointer to a value
338 * Iterates through the content of a hash, filling the @v1 and @v2
339 * pointers with key-value pairs on each call until the hash is
340 * exhausted. If @h is an array, only the @v1 pointer is filled.
341 * @v1 and @v2 pointers can be NULL.
343 * The @context pointer to integer is opaque and should be
344 * initialized to zero on the first call.
346 * Returns 0 if no more data is left in @h.
350 int mpdm_iterator(mpdm_t h
, int *context
, mpdm_t
* v1
, mpdm_t
* v2
)
363 if (MPDM_IS_HASH(h
)) {
367 /* get bucket and element index */
368 bi
= (*context
) % mpdm_size(h
);
369 ei
= (*context
) / mpdm_size(h
);
371 while (ret
== 0 && bi
< mpdm_size(h
)) {
374 /* if bucket is empty or there is no more elements in it, pick next */
375 if ((b
= mpdm_aget(h
, bi
)) == NULL
|| ei
>= mpdm_size(b
)) {
382 *v1
= mpdm_aget(b
, ei
++);
383 *v2
= mpdm_aget(b
, ei
++);
386 *context
= (ei
* mpdm_size(h
)) + bi
;
392 if (MPDM_IS_ARRAY(h
)) {
393 if (*context
< mpdm_size(h
)) {
394 *v1
= mpdm_aget(h
, (*context
)++);
405 static mpdm_t
mpdm_sym(mpdm_t r
, mpdm_t k
, mpdm_t v
, int o
, int s
)
417 /* splits the path, if needed */
418 if (k
->flags
& MPDM_MULTIPLE
)
421 p
= mpdm_ref(mpdm_split_s(k
, L
"."));
425 for (n
= 0; n
< mpdm_size(p
) - o
; n
++) {
427 /* is executable? run it and take its output */
428 while (MPDM_IS_EXEC(w
))
429 w
= mpdm_exec(w
, NULL
, NULL
);
432 w
= mpdm_hget(w
, mpdm_aget(p
, n
));
434 if (MPDM_IS_ARRAY(w
)) {
435 int i
= mpdm_ival(mpdm_aget(p
, n
));
439 mpdm_unref(mpdm_ref(w
));
447 /* if want to set, do it */
448 if (s
&& w
!= NULL
) {
449 /* resolve executable values again */
450 while (MPDM_IS_EXEC(w
))
451 w
= mpdm_exec(w
, NULL
, NULL
);
453 if (w
->flags
& MPDM_HASH
)
454 w
= mpdm_hset(w
, mpdm_aget(p
, n
), v
);
456 int i
= mpdm_ival(mpdm_aget(p
, n
));
457 w
= mpdm_aset(w
, v
, i
);
470 mpdm_t
mpdm_sget(mpdm_t r
, mpdm_t k
)
472 return mpdm_sym(r
, k
, NULL
, 0, 0);
476 mpdm_t
mpdm_sget_i(mpdm_t r
, mpdm_t k
, int i
)
478 return mpdm_sym(r
, k
, NULL
, i
, 0);
482 mpdm_t
mpdm_sset(mpdm_t r
, mpdm_t k
, mpdm_t v
)
484 return mpdm_sym(r
, k
, v
, 1, 1);