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_S(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 n;
 165     int ret = 0;
 166
 167     mpdm_ref(h);
 168     mpdm_ref(k);
 169
 170     if (mpdm_size(h)) {
 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)
 175                 ret = 1;
 176         }
 177     }
 178
 179     mpdm_unref(k);
 180     mpdm_unref(h);
 181
 182     return ret;
 183 }
 184
 185
 186 /**
 187  * mpdm_hset - Sets a value in a hash.
 188  * @h: the hash
 189  * @k: the key
 190  * @v: the value
 191  *
 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
 194  * value).
 195  * [Hashes]
 196  */
 197 mpdm_t mpdm_hset(mpdm_t h, mpdm_t k, mpdm_t v)
 198 {
 199     mpdm_t b, r;
 200     int n;
 201
 202     mpdm_ref(h);
 203     mpdm_ref(k);
 204     mpdm_ref(v);
 205
 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);
 209
 210     n = HASH_BUCKET(h, k);
 211
 212     if ((b = mpdm_aget(h, n)) != NULL) {
 213         int pos;
 214
 215         /* bucket exists; try to find the key there */
 216         n = mpdm_bseek(b, k, 2, &pos);
 217
 218         if (n < 0) {
 219             /* the pair does not exist: create it */
 220             n = pos;
 221             mpdm_expand(b, n, 2);
 222
 223             mpdm_aset(b, k, n);
 224         }
 225     }
 226     else {
 227         /* the bucket does not exist; create it */
 228         b = MPDM_A(2);
 229
 230         /* put the bucket into the hash */
 231         mpdm_aset(h, b, n);
 232
 233         /* offset 0 */
 234         n = 0;
 235
 236         /* insert the key */
 237         mpdm_aset(b, k, n);
 238     }
 239
 240     r = mpdm_aset(b, v, n + 1);
 241
 242     mpdm_unref(v);
 243     mpdm_unref(k);
 244     mpdm_unref(h);
 245
 246     return r;
 247 }
 248
 249
 250 /**
 251  * mpdm_hset_s - Sets a value in a hash (string version).
 252  * @h: the hash
 253  * @k: the key
 254  * @v: the value
 255  *
 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
 258  * value).
 259  * [Hashes]
 260  */
 261 mpdm_t mpdm_hset_s(mpdm_t h, const wchar_t * k, mpdm_t v)
 262 {
 263     return mpdm_hset(h, MPDM_S(k), v);
 264 }
 265
 266
 267 /**
 268  * mpdm_hdel - Deletes a key from a hash.
 269  * @h: the hash
 270  * @k: the key
 271  *
 272  * Deletes the key @k from the hash @h. Returns NULL
 273  * (versions prior to 1.0.10 returned the deleted value).
 274  * [Hashes]
 275  */
 276 mpdm_t mpdm_hdel(mpdm_t h, const mpdm_t k)
 277 {
 278     mpdm_t b;
 279     int n;
 280
 281     mpdm_ref(h);
 282     mpdm_ref(k);
 283
 284     if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 285         /* bucket exists */
 286         if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0) {
 287             /* collapse the bucket */
 288             mpdm_collapse(b, n, 2);
 289         }
 290     }
 291
 292     mpdm_unref(k);
 293     mpdm_unref(h);
 294
 295     return NULL;
 296 }
 297
 298
 299 /**
 300  * mpdm_keys - Returns the keys of a hash.
 301  * @h: the hash
 302  *
 303  * Returns an array containing all the keys of the @h hash.
 304  * [Hashes]
 305  * [Arrays]
 306  */
 307 mpdm_t mpdm_keys(const mpdm_t h)
 308 {
 309     int n, c;
 310     mpdm_t a, k;
 311
 312     mpdm_ref(h);
 313
 314     /* create an array with the same number of elements */
 315     a = MPDM_A(mpdm_hsize(h));
 316
 317     mpdm_ref(a);
 318
 319     c = n = 0;
 320     while (mpdm_iterator(h, &c, &k, NULL))
 321         mpdm_aset(a, k, n++);
 322
 323     mpdm_unrefnd(a);
 324
 325     mpdm_unref(h);
 326
 327     return a;
 328 }
 329
 330
 331 /**
 332  * mpdm_interator - 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
 337  *
 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.
 342  *
 343  * The @context pointer to integer is opaque and should be
 344  * initialized to zero on the first call.
 345  *
 346  * Returns 0 if no more data is left in @h.
 347  * [Hashes]
 348  * [Arrays]
 349  */
 350 int mpdm_iterator(mpdm_t h, int *context, mpdm_t * v1, mpdm_t * v2)
 351 {
 352     int ret = 0;
 353     mpdm_t w1, w2;
 354
 355     mpdm_ref(h);
 356
 357     if (v1 == NULL)
 358         v1 = &w1;
 359
 360     if (v2 == NULL)
 361         v2 = &w2;
 362
 363     if (MPDM_IS_HASH(h)) {
 364         int bi, ei;
 365
 366         if (mpdm_size(h)) {
 367             /* get bucket and element index */
 368             bi = (*context) % mpdm_size(h);
 369             ei = (*context) / mpdm_size(h);
 370
 371             while (ret == 0 && bi < mpdm_size(h)) {
 372                 mpdm_t b;
 373
 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)) {
 376                     ei = 0;
 377                     bi++;
 378                     continue;
 379                 }
 380
 381                 /* get pair */
 382                 *v1 = mpdm_aget(b, ei++);
 383                 *v2 = mpdm_aget(b, ei++);
 384
 385                 /* update context */
 386                 *context = (ei * mpdm_size(h)) + bi;
 387                 ret = 1;
 388             }
 389         }
 390     }
 391     else
 392     if (MPDM_IS_ARRAY(h)) {
 393         if (*context < mpdm_size(h)) {
 394             *v1 = mpdm_aget(h, (*context)++);
 395             ret = 1;
 396         }
 397     }
 398
 399     mpdm_unref(h);
 400
 401     return ret;
 402 }
 403
 404
 405 static mpdm_t mpdm_sym(mpdm_t r, mpdm_t k, mpdm_t v, int s)
 406 {
 407     int n;
 408     mpdm_t p, w;
 409
 410     if (r == NULL)
 411         r = mpdm_root();
 412
 413     mpdm_ref(r);
 414     mpdm_ref(k);
 415     mpdm_ref(v);
 416
 417     /* splits the path, if needed */
 418     if (k->flags & MPDM_MULTIPLE)
 419         p = mpdm_ref(k);
 420     else
 421         p = mpdm_ref(mpdm_split_s(L".", k));
 422
 423     w = r;
 424
 425     for (n = 0; n < mpdm_size(p) - s; n++) {
 426
 427         /* is executable? run it and take its output */
 428         while (MPDM_IS_EXEC(w))
 429             w = mpdm_exec(w, NULL, NULL);
 430
 431         if (MPDM_IS_HASH(w))
 432             w = mpdm_hget(w, mpdm_aget(p, n));
 433         else
 434         if (MPDM_IS_ARRAY(w)) {
 435             int i = mpdm_ival(mpdm_aget(p, n));
 436             w = mpdm_aget(w, i);
 437         }
 438         else {
 439             mpdm_unref(mpdm_ref(w));
 440             w = NULL;
 441         }
 442
 443         if (w == NULL)
 444             break;
 445     }
 446
 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);
 452
 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     mpdm_unref(p);
 462     mpdm_unref(v);
 463     mpdm_unref(k);
 464     mpdm_unref(r);
 465
 466     return w;
 467 }
 468
 469
 470 mpdm_t mpdm_sget(mpdm_t r, mpdm_t k)
 471 {
 472     return mpdm_sym(r, k, NULL, 0);
 473 }
 474
 475
 476 mpdm_t mpdm_sset(mpdm_t r, mpdm_t k, mpdm_t v)
 477 {
 478     return mpdm_sym(r, k, v, 1);
 479 }