1 /*
2
3 MPDM - Minimum Profit Data Manager
4 mpdm_o.c - Object management
5
6 ttcdt <dev@triptico.com> et al.
7
8 This software is released into the public domain.
9 NO WARRANTY. See file LICENSE for details.
10
11 */
12
13 #include "config.h"
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <wchar.h>
19
20 #include "mpdm.h"
21
22 /** code **/
23
24 /* default hash buckets (must be prime) */
25 int mpdm_hash_buckets = 31;
26
27 /* prototype for the one-time wrapper hash function */
28 static int switch_hash_func(const wchar_t *, int);
29
30 /* pointer to the hashing function */
31 static int (*mpdm_hash_func) (const wchar_t *, int) = switch_hash_func;
32
standard_hash_func(const wchar_t * string,int mod)33 static int standard_hash_func(const wchar_t *string, int mod)
34 /* computes a hashing function on string */
35 {
36 int c;
37
38 for (c = 0; *string != L'\0' && ! (c & 0x1000); string++)
39 c = (c << 1) ^ (int) *string;
40
41 return c % mod;
42 }
43
44
null_hash_func(const wchar_t * string,int mod)45 static int null_hash_func(const wchar_t *string, int mod)
46 {
47 return *string % mod;
48 }
49
switch_hash_func(const wchar_t * string,int mod)50 static int switch_hash_func(const wchar_t *string, int mod)
51 /* one-time wrapper for hash method autodetection */
52 {
53 /* commute the real hashing function on
54 having the MPDM_NULL_HASH environment variable set */
55 if (getenv("MPDM_NULL_HASH") != NULL)
56 mpdm_hash_func = null_hash_func;
57 else
58 mpdm_hash_func = standard_hash_func;
59
60 /* and fall back to it */
61 return mpdm_hash_func(string, mod);
62 }
63
64 #define HASH_BUCKET_S(h, k) mpdm_hash_func(k, mpdm_size(h))
65 #define HASH_BUCKET(h, k) mpdm_hash_func(mpdm_string(k), mpdm_size(h))
66
67 /* interface */
68
69
mpdm_new_o(void)70 mpdm_t mpdm_new_o(void)
71 /* creates a new object */
72 {
73 return mpdm_new(MPDM_TYPE_OBJECT, NULL, 0);
74 }
75
76
77 /**
78 * mpdm_get_wcs - Gets the value from an object by string index (string version).
79 * @o: the object
80 * @i: the index
81 *
82 * Returns the value from @o by index @i, or NULL if there is no
83 * value addressable by that index.
84 * [Objects]
85 */
mpdm_get_wcs(const mpdm_t o,const wchar_t * i)86 mpdm_t mpdm_get_wcs(const mpdm_t o, const wchar_t *i)
87 {
88 mpdm_t b;
89 mpdm_t v = NULL;
90 int n = 0;
91
92 if (mpdm_size(o)) {
93 /* if hash is not empty... */
94 if ((b = mpdm_get_i(o, HASH_BUCKET_S(o, i))) != NULL)
95 n = mpdm_bseek_wcs(b, i, 2, NULL);
96
97 if (n >= 0)
98 v = mpdm_get_i(b, n + 1);
99 }
100
101 return v;
102 }
103
104
105 /**
106 * mpdm_exists - Tests if there is a value available by index.
107 * @o: the object
108 * @i: the index
109 *
110 * Returns 1 if exists a value indexable by @i in @h, or 0 othersize.
111 * [Hashes]
112 */
mpdm_exists(const mpdm_t o,const mpdm_t i)113 int mpdm_exists(const mpdm_t o, const mpdm_t i)
114 {
115 mpdm_t b;
116 int ret = 0;
117
118 mpdm_ref(i);
119
120 if (mpdm_size(o)) {
121 if ((b = mpdm_get_i(o, HASH_BUCKET(o, i))) != NULL) {
122 /* if bucket exists, binary-seek it */
123 if (mpdm_bseek(b, i, 2, NULL) >= 0)
124 ret = 1;
125 }
126 }
127
128 mpdm_unref(i);
129
130 return ret;
131 }
132
133
134 /**
135 * mpdm_set_wcs - Sets a value in an object (string version).
136 * @o: the object
137 * @v: the value
138 * @i: the index
139 *
140 * Sets the value @v inside the object @o, accesible by index @i.
141 * Returns @v.
142 * [Objects]
143 */
mpdm_set_wcs(mpdm_t o,mpdm_t v,const wchar_t * i)144 mpdm_t mpdm_set_wcs(mpdm_t o, mpdm_t v, const wchar_t *i)
145 {
146 return mpdm_set(o, v, MPDM_S(i));
147 }
148
149
150 /* old hash compatibility layer */
151
152 /**
153 * mpdm_hsize - Returns the number of pairs of a hash.
154 * @h: the hash
155 *
156 * Returns the number of key-value pairs of a hash.
157 * [Hashes]
158 */
mpdm_hsize(const mpdm_t h)159 int mpdm_hsize(const mpdm_t h)
160 {
161 return mpdm_count(h);
162 }
163
164
165 /**
166 * mpdm_hget_s - Gets the value from a hash (string version).
167 * @h: the hash
168 * @k: the key
169 *
170 * Gets the value from the hash @h having @k as key, or
171 * NULL if the key does not exist.
172 * [Hashes]
173 */
mpdm_hget_s(const mpdm_t h,const wchar_t * k)174 mpdm_t mpdm_hget_s(const mpdm_t h, const wchar_t *k)
175 {
176 return mpdm_get_wcs(h, k);
177 }
178
179
180 /**
181 * mpdm_hget - Gets a value from a hash.
182 * @h: the hash
183 * @k: the key
184 *
185 * Gets the value from the hash @h having @k as key, or
186 * NULL if the key does not exist.
187 * [Hashes]
188 */
mpdm_hget(const mpdm_t h,const mpdm_t k)189 mpdm_t mpdm_hget(const mpdm_t h, const mpdm_t k)
190 {
191 return mpdm_get(h, k);
192 }
193
194
195 /**
196 * mpdm_hset - Sets a value in a hash.
197 * @h: the hash
198 * @k: the key
199 * @v: the value
200 *
201 * Sets the value @v to the key @k in the hash @h. Returns
202 * the new value (versions prior to 1.0.10 returned the old
203 * value).
204 * [Hashes]
205 */
mpdm_hset(mpdm_t h,mpdm_t k,mpdm_t v)206 mpdm_t mpdm_hset(mpdm_t h, mpdm_t k, mpdm_t v)
207 {
208 return mpdm_set(h, v, k);
209 }
210
211
212 /**
213 * mpdm_hset_s - Sets a value in a hash (string version).
214 * @h: the hash
215 * @k: the key
216 * @v: the value
217 *
218 * Sets the value @v to the key @k in the hash @h. Returns
219 * the new value (versions prior to 1.0.10 returned the old
220 * value).
221 * [Hashes]
222 */
mpdm_hset_s(mpdm_t h,const wchar_t * k,mpdm_t v)223 mpdm_t mpdm_hset_s(mpdm_t h, const wchar_t *k, mpdm_t v)
224 {
225 return mpdm_set_wcs(h, v, k);
226 }
227
228
229 /**
230 * mpdm_hdel - Deletes a key from a hash.
231 * @h: the hash
232 * @k: the key
233 *
234 * Deletes the key @k from the hash @h. Returns NULL
235 * (versions prior to 1.0.10 returned the deleted value).
236 * [Hashes]
237 */
mpdm_hdel(mpdm_t h,const mpdm_t k)238 mpdm_t mpdm_hdel(mpdm_t h, const mpdm_t k)
239 {
240 return mpdm_del(h, k);
241 }
242
243
244 /**
245 * mpdm_keys - Returns the keys of a hash.
246 * @h: the hash
247 *
248 * Returns an array containing all the keys of the @h hash.
249 * [Hashes]
250 * [Arrays]
251 */
mpdm_keys(const mpdm_t h)252 mpdm_t mpdm_keys(const mpdm_t h)
253 {
254 int c;
255 mpdm_t a, i;
256
257 printf("Warning: deprecated function mpdm_keys()\n");
258
259 mpdm_ref(h);
260
261 /* create an array with the same number of elements */
262 a = MPDM_A(0);
263
264 c = 0;
265 while (mpdm_iterator(h, &c, NULL, &i))
266 mpdm_push(a, i);
267
268 mpdm_unref(h);
269
270 return a;
271 }
272
273 /** data vc **/
274
vc_object_destroy(mpdm_t o)275 static mpdm_t vc_object_destroy(mpdm_t o)
276 {
277 struct mpdm_type_vc *vc = mpdm_type_vc_by_t(MPDM_TYPE_ARRAY);
278 return vc->destroy(o);
279 }
280
vc_object_count(const mpdm_t o)281 static int vc_object_count(const mpdm_t o)
282 {
283 int n;
284 int ret = 0;
285
286 for (n = 0; n < mpdm_size(o); n++) {
287 mpdm_t b = mpdm_get_i(o, n);
288 ret += mpdm_size(b);
289 }
290
291 return ret / 2;
292 }
293
vc_object_get_i(const mpdm_t o,int index)294 static mpdm_t vc_object_get_i(const mpdm_t o, int index)
295 {
296 struct mpdm_type_vc *vc = mpdm_type_vc_by_t(MPDM_TYPE_ARRAY);
297 return vc->get_i(o, index);
298 }
299
vc_object_get(const mpdm_t o,mpdm_t index)300 static mpdm_t vc_object_get(const mpdm_t o, mpdm_t index)
301 {
302 mpdm_t r;
303
304 mpdm_ref(index);
305 r = mpdm_get_wcs(o, mpdm_string(index));
306 mpdm_unref(index);
307
308 return r;
309 }
310
vc_object_del(mpdm_t o,mpdm_t index)311 static mpdm_t vc_object_del(mpdm_t o, mpdm_t index)
312 {
313 mpdm_t b;
314 int n;
315
316 mpdm_ref(index);
317
318 if (mpdm_size(o)) {
319 if ((b = mpdm_get_i(o, HASH_BUCKET(o, index))) != NULL) {
320 /* bucket exists */
321 if ((n = mpdm_bseek(b, index, 2, NULL)) >= 0) {
322 /* collapse the bucket */
323 mpdm_collapse(b, n, 2);
324 }
325 }
326 }
327
328 mpdm_unref(index);
329
330 return o;
331 }
332
vc_object_set_i(mpdm_t o,mpdm_t v,int index)333 static mpdm_t vc_object_set_i(mpdm_t o, mpdm_t v, int index)
334 {
335 return mpdm_type_vc_by_t(MPDM_TYPE_ARRAY)->set_i(o, v, index);
336 }
337
vc_object_set(mpdm_t o,mpdm_t v,mpdm_t index)338 static mpdm_t vc_object_set(mpdm_t o, mpdm_t v, mpdm_t index)
339 {
340 mpdm_t b, r;
341 int n;
342
343 mpdm_ref(index);
344 mpdm_ref(v);
345
346 /* if hash is empty, create an optimal number of buckets */
347 if (mpdm_size(o) == 0)
348 mpdm_expand(o, 0, mpdm_hash_buckets);
349
350 n = HASH_BUCKET(o, index);
351
352 if ((b = mpdm_get_i(o, n)) != NULL) {
353 int pos;
354
355 /* bucket exists; try to find the key there */
356 n = mpdm_bseek(b, index, 2, &pos);
357
358 if (n < 0) {
359 /* the pair does not exist: create it */
360 n = pos;
361 mpdm_expand(b, n, 2);
362
363 mpdm_set_i(b, index, n);
364 }
365 }
366 else {
367 /* the bucket does not exist; create it */
368 b = MPDM_A(2);
369
370 /* put the bucket into the hash */
371 mpdm_set_i(o, b, n);
372
373 /* offset 0 */
374 n = 0;
375
376 /* insert the key */
377 mpdm_set_i(b, index, n);
378 }
379
380 r = mpdm_set_i(b, v, n + 1);
381
382 mpdm_unref(v);
383 mpdm_unref(index);
384
385 return r;
386 }
387
388
vc_object_iterator(mpdm_t set,int * context,mpdm_t * v,mpdm_t * i)389 static int vc_object_iterator(mpdm_t set, int *context, mpdm_t *v, mpdm_t *i)
390 {
391 int ret = 0;
392
393 if (mpdm_size(set)) {
394 int bi, ei;
395
396 /* get bucket and element index */
397 bi = (*context) % mpdm_size(set);
398 ei = (*context) / mpdm_size(set);
399
400 while (ret == 0 && bi < mpdm_size(set)) {
401 mpdm_t b;
402
403 /* if bucket is empty or there are no more
404 elements in it, pick the next one */
405 if (!(b = mpdm_get_i(set, bi)) || ei >= mpdm_size(b)) {
406 ei = 0;
407 bi++;
408 }
409 else {
410 /* get pair */
411 if (v) *v = mpdm_get_i(b, ei + 1);
412 if (i) *i = mpdm_get_i(b, ei);
413
414 ei += 2;
415
416 /* update context */
417 *context = (ei * mpdm_size(set)) + bi;
418 ret = 1;
419 }
420 }
421 }
422
423 return ret;
424 }
425
426
427 struct mpdm_type_vc mpdm_vc_object = { /* VC */
428 L"object", /* name */
429 vc_object_destroy, /* destroy */
430 vc_default_is_true, /* is_true */
431 vc_object_count, /* count */
432 vc_object_get_i, /* get_i */
433 vc_object_get, /* get */
434 vc_default_string, /* string */
435 vc_default_del_i, /* del_i */
436 vc_object_del, /* del */
437 vc_object_set_i, /* set_i */
438 vc_object_set, /* set */
439 vc_default_exec, /* exec */
440 vc_object_iterator, /* iterator */
441 vc_default_map /* map */
442 };
443