mpdm_h.c

   1 /*
   2
   3     MPDM - Minimum Profit Data Manager
   4     Copyright (C) 2003/2010 Angel Ortega <angel@triptico.com>
   5
   6     mpdm_h.c - Hash 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 /** code **/
  36
  37 /* prototype for the one-time wrapper hash function */
  38 static int switch_hash_func(const wchar_t *, int);
  39
  40 /* pointer to the hashing function */
  41 static int (*mpdm_hash_func) (const wchar_t *, int) = switch_hash_func;
  42
  43 static int standard_hash_func(const wchar_t * string, int mod)
  44 /* computes a hashing function on string */
  45 {
  46     int c;
  47
  48     for (c = 0; *string != L'\0'; string++)
  49         c ^= (int) *string;
  50
  51     return c % mod;
  52 }
  53
  54
  55 static int null_hash_func(const wchar_t * string, int mod)
  56 {
  57     return *string % mod;
  58 }
  59
  60 static int switch_hash_func(const wchar_t * string, int mod)
  61 /* one-time wrapper for hash method autodetection */
  62 {
  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;
  67     else
  68         mpdm_hash_func = standard_hash_func;
  69
  70     /* and fall back to it */
  71     return mpdm_hash_func(string, mod);
  72 }
  73
  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)))
  76
  77 /* interface */
  78
  79 /**
  80  * mpdm_hsize - Returns the number of pairs of a hash.
  81  * @h: the hash
  82  *
  83  * Returns the number of key-value pairs of a hash.
  84  * [Hashes]
  85  */
  86 int mpdm_hsize(const mpdm_t h)
  87 {
  88     int n;
  89     int ret = 0;
  90
  91     mpdm_ref(h);
  92
  93     for (n = 0; n < mpdm_size(h); n++) {
  94         mpdm_t b = mpdm_aget(h, n);
  95         ret += mpdm_size(b);
  96     }
  97
  98     mpdm_unref(h);
  99
 100     return ret / 2;
 101 }
 102
 103
 104 /**
 105  * mpdm_hget - Gets a value from a hash.
 106  * @h: the hash
 107  * @k: the key
 108  *
 109  * Gets the value from the hash @h having @k as key, or
 110  * NULL if the key does not exist.
 111  * [Hashes]
 112  */
 113 mpdm_t mpdm_hget(const mpdm_t h, const mpdm_t k)
 114 {
 115     mpdm_t b;
 116     mpdm_t v = NULL;
 117     int n = 0;
 118
 119     mpdm_ref(h);
 120     mpdm_ref(k);
 121
 122     if (mpdm_size(h)) {
 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);
 126
 127         if (n >= 0)
 128             v = mpdm_aget(b, n + 1);
 129     }
 130
 131     mpdm_unref(k);
 132     mpdm_unref(h);
 133
 134     return v;
 135 }
 136
 137
 138 /**
 139  * mpdm_hget_s - Gets the value from a hash (string version).
 140  * @h: the hash
 141  * @k: the key
 142  *
 143  * Gets the value from the hash @h having @k as key, or
 144  * NULL if the key does not exist.
 145  * [Hashes]
 146  */
 147 mpdm_t mpdm_hget_s(const mpdm_t h, const wchar_t * k)
 148 {
 149     return mpdm_hget(h, MPDM_AS(k));
 150 }
 151
 152
 153 /**
 154  * mpdm_exists - Tests if a key exists.
 155  * @h: the hash
 156  * @k: the key
 157  *
 158  * Returns 1 if @k is defined in @h, or 0 othersize.
 159  * [Hashes]
 160  */
 161 int mpdm_exists(const mpdm_t h, const mpdm_t k)
 162 {
 163     mpdm_t b;
 164     int ret = 0;
 165
 166     mpdm_ref(h);
 167     mpdm_ref(k);
 168
 169     if (mpdm_size(h)) {
 170         /* if hash is not empty... */
 171         if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 172             /* if bucket exists, binary-seek it */
 173             if (mpdm_bseek(b, k, 2, NULL) >= 0)
 174                 ret = 1;
 175         }
 176     }
 177
 178     mpdm_unref(k);
 179     mpdm_unref(h);
 180
 181     return ret;
 182 }
 183
 184
 185 /**
 186  * mpdm_hset - Sets a value in a hash.
 187  * @h: the hash
 188  * @k: the key
 189  * @v: the value
 190  *
 191  * Sets the value @v to the key @k in the hash @h. Returns
 192  * the new value (versions prior to 1.0.10 returned the old
 193  * value).
 194  * [Hashes]
 195  */
 196 mpdm_t mpdm_hset(mpdm_t h, mpdm_t k, mpdm_t v)
 197 {
 198     mpdm_t b, r;
 199     int n;
 200
 201     mpdm_ref(h);
 202     mpdm_ref(k);
 203     mpdm_ref(v);
 204
 205     /* if hash is empty, create an optimal number of buckets */
 206     if (mpdm_size(h) == 0)
 207         mpdm_expand(h, 0, mpdm->hash_buckets);
 208
 209     n = HASH_BUCKET(h, k);
 210
 211     if ((b = mpdm_aget(h, n)) != NULL) {
 212         int pos;
 213
 214         /* bucket exists; try to find the key there */
 215         n = mpdm_bseek(b, k, 2, &pos);
 216
 217         if (n < 0) {
 218             /* the pair does not exist: create it */
 219             n = pos;
 220             mpdm_expand(b, n, 2);
 221
 222             mpdm_aset(b, k, n);
 223         }
 224     }
 225     else {
 226         /* the bucket does not exist; create it */
 227         b = MPDM_A(2);
 228
 229         /* put the bucket into the hash */
 230         mpdm_aset(h, b, n);
 231
 232         /* offset 0 */
 233         n = 0;
 234
 235         /* insert the key */
 236         mpdm_aset(b, k, n);
 237     }
 238
 239     r = mpdm_aset(b, v, n + 1);
 240
 241     mpdm_unref(v);
 242     mpdm_unref(k);
 243     mpdm_unref(h);
 244
 245     return r;
 246 }
 247
 248
 249 /**
 250  * mpdm_hset_s - Sets a value in a hash (string version).
 251  * @h: the hash
 252  * @k: the key
 253  * @v: the value
 254  *
 255  * Sets the value @v to the key @k in the hash @h. Returns
 256  * the new value (versions prior to 1.0.10 returned the old
 257  * value).
 258  * [Hashes]
 259  */
 260 mpdm_t mpdm_hset_s(mpdm_t h, const wchar_t * k, mpdm_t v)
 261 {
 262     return mpdm_hset(h, MPDM_S(k), v);
 263 }
 264
 265
 266 /**
 267  * mpdm_hdel - Deletes a key from a hash.
 268  * @h: the hash
 269  * @k: the key
 270  *
 271  * Deletes the key @k from the hash @h. Returns NULL
 272  * (versions prior to 1.0.10 returned the deleted value).
 273  * [Hashes]
 274  */
 275 mpdm_t mpdm_hdel(mpdm_t h, const mpdm_t k)
 276 {
 277     mpdm_t b;
 278     int n;
 279
 280     mpdm_ref(h);
 281     mpdm_ref(k);
 282
 283     if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 284         /* bucket exists */
 285         if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0) {
 286             /* collapse the bucket */
 287             mpdm_collapse(b, n, 2);
 288         }
 289     }
 290
 291     mpdm_unref(k);
 292     mpdm_unref(h);
 293
 294     return NULL;
 295 }
 296
 297
 298 /**
 299  * mpdm_keys - Returns the keys of a hash.
 300  * @h: the hash
 301  *
 302  * Returns an array containing all the keys of the @h hash.
 303  * [Hashes]
 304  * [Arrays]
 305  */
 306 mpdm_t mpdm_keys(const mpdm_t h)
 307 {
 308     int n, c;
 309     mpdm_t a, k;
 310
 311     mpdm_ref(h);
 312
 313     /* create an array with the same number of elements */
 314     a = MPDM_A(mpdm_hsize(h));
 315
 316     mpdm_ref(a);
 317
 318     c = n = 0;
 319     while (mpdm_iterator(h, &c, &k, NULL))
 320         mpdm_aset(a, k, n++);
 321
 322     mpdm_unrefnd(a);
 323
 324     mpdm_unref(h);
 325
 326     return a;
 327 }
 328
 329
 330 /**
 331  * mpdm_iterator - Iterates through the content of a hash or array.
 332  * @h: the hash (or array)
 333  * @context: A pointer to an opaque context
 334  * @v1: a pointer to a value
 335  * @v2: another pointer to a value
 336  *
 337  * Iterates through the content of a hash, filling the @v1 and @v2
 338  * pointers with key-value pairs on each call until the hash is
 339  * exhausted. If @h is an array, only the @v1 pointer is filled.
 340  * @v1 and @v2 pointers can be NULL.
 341  *
 342  * The @context pointer to integer is opaque and should be
 343  * initialized to zero on the first call.
 344  *
 345  * Returns 0 if no more data is left in @h.
 346  * [Hashes]
 347  * [Arrays]
 348  */
 349 int mpdm_iterator(mpdm_t h, int *context, mpdm_t * v1, mpdm_t * v2)
 350 {
 351     int ret = 0;
 352     mpdm_t w1, w2;
 353
 354     mpdm_ref(h);
 355
 356     if (v1 == NULL)
 357         v1 = &w1;
 358
 359     if (v2 == NULL)
 360         v2 = &w2;
 361
 362     if (MPDM_IS_HASH(h)) {
 363         int bi, ei;
 364
 365         if (mpdm_size(h)) {
 366             /* get bucket and element index */
 367             bi = (*context) % mpdm_size(h);
 368             ei = (*context) / mpdm_size(h);
 369
 370             while (ret == 0 && bi < mpdm_size(h)) {
 371                 mpdm_t b;
 372
 373                 /* if bucket is empty or there is no more elements in it, pick next */
 374                 if ((b = mpdm_aget(h, bi)) == NULL || ei >= mpdm_size(b)) {
 375                     ei = 0;
 376                     bi++;
 377                     continue;
 378                 }
 379
 380                 /* get pair */
 381                 *v1 = mpdm_aget(b, ei++);
 382                 *v2 = mpdm_aget(b, ei++);
 383
 384                 /* update context */
 385                 *context = (ei * mpdm_size(h)) + bi;
 386                 ret = 1;
 387             }
 388         }
 389     }
 390     else
 391     if (MPDM_IS_ARRAY(h)) {
 392         if (*context < mpdm_size(h)) {
 393             *v1 = mpdm_aget(h, (*context)++);
 394             ret = 1;
 395         }
 396     }
 397
 398     mpdm_unref(h);
 399
 400     return ret;
 401 }
 402
 403
 404 static mpdm_t mpdm_sym(mpdm_t r, mpdm_t k, mpdm_t v, int o, int s)
 405 {
 406     int n;
 407     mpdm_t p, w;
 408
 409     if (r == NULL)
 410         r = mpdm_root();
 411
 412     mpdm_ref(r);
 413     mpdm_ref(k);
 414     mpdm_ref(v);
 415
 416     /* splits the path, if needed */
 417     if (k->flags & MPDM_MULTIPLE)
 418         p = mpdm_ref(k);
 419     else
 420         p = mpdm_ref(mpdm_split_s(k, L"."));
 421
 422     w = r;
 423
 424     for (n = 0; n < mpdm_size(p) - o; n++) {
 425
 426         /* is executable? run it and take its output */
 427         while (MPDM_IS_EXEC(w))
 428             w = mpdm_exec(w, NULL, NULL);
 429
 430         if (MPDM_IS_HASH(w))
 431             w = mpdm_hget(w, mpdm_aget(p, n));
 432         else
 433         if (MPDM_IS_ARRAY(w)) {
 434             int i = mpdm_ival(mpdm_aget(p, n));
 435             w = mpdm_aget(w, i);
 436         }
 437         else {
 438             mpdm_unref(mpdm_ref(w));
 439             w = NULL;
 440         }
 441
 442         if (w == NULL)
 443             break;
 444     }
 445
 446     /* if want to set, do it */
 447     if (s && w != NULL) {
 448         /* resolve executable values again */
 449         while (MPDM_IS_EXEC(w))
 450             w = mpdm_exec(w, NULL, NULL);
 451
 452         if (w) {
 453             if (w->flags & MPDM_HASH)
 454                 w = mpdm_hset(w, mpdm_aget(p, n), v);
 455             else {
 456                 int i = mpdm_ival(mpdm_aget(p, n));
 457                 w = mpdm_aset(w, v, i);
 458             }
 459         }
 460     }
 461
 462     mpdm_unref(p);
 463     mpdm_unref(v);
 464     mpdm_unref(k);
 465     mpdm_unref(r);
 466
 467     return w;
 468 }
 469
 470
 471 mpdm_t mpdm_sget(mpdm_t r, mpdm_t k)
 472 {
 473     return mpdm_sym(r, k, NULL, 0, 0);
 474 }
 475
 476
 477 mpdm_t mpdm_sget_i(mpdm_t r, mpdm_t k, int i)
 478 {
 479     return mpdm_sym(r, k, NULL, i, 0);
 480 }
 481
 482
 483 mpdm_t mpdm_sset(mpdm_t r, mpdm_t k, mpdm_t v)
 484 {
 485     return mpdm_sym(r, k, v, 1, 1);
 486 }