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         for (n = 0; n < mpdm_size(h); n++) {
  92                 mpdm_t b = mpdm_aget(h, n);
  93                 ret += mpdm_size(b);
  94         }
  95
  96         return ret / 2;
  97 }
  98
  99
 100 static mpdm_t hget(const mpdm_t h, const mpdm_t k, const wchar_t *ks)
 101 {
 102         mpdm_t b;
 103         mpdm_t v = NULL;
 104         int n = 0;
 105
 106         if (mpdm_size(h)) {
 107                 /* if hash is not empty... */
 108                 if (ks) {
 109                         if ((b = mpdm_aget(h, HASH_BUCKET_S(h, ks))) != NULL)
 110                                 n = mpdm_bseek_s(b, ks, 2, NULL);
 111                 }
 112                 else {
 113                         if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL)
 114                                 n = mpdm_bseek(b, k, 2, NULL);
 115                 }
 116
 117                 if (n >= 0)
 118                         v = mpdm_aget(b, n + 1);
 119         }
 120
 121         return v;
 122 }
 123
 124
 125 /**
 126  * mpdm_hget - Gets a value from a hash.
 127  * @h: the hash
 128  * @k: the key
 129  *
 130  * Gets the value from the hash @h having @k as key, or
 131  * NULL if the key does not exist.
 132  * [Hashes]
 133  */
 134 mpdm_t mpdm_hget(const mpdm_t h, const mpdm_t k)
 135 {
 136         return hget(h, k, NULL);
 137 }
 138
 139
 140 /**
 141  * mpdm_hget_s - Gets the value from a hash (string version).
 142  * @h: the hash
 143  * @k: the key
 144  *
 145  * Gets the value from the hash @h having @k as key, or
 146  * NULL if the key does not exist.
 147  * [Hashes]
 148  */
 149 mpdm_t mpdm_hget_s(const mpdm_t h, const wchar_t *k)
 150 {
 151         return hget(h, NULL, k);
 152 }
 153
 154
 155 /**
 156  * mpdm_exists - Tests if a key exists.
 157  * @h: the hash
 158  * @k: the key
 159  *
 160  * Returns 1 if @k is defined in @h, or 0 othersize.
 161  * [Hashes]
 162  */
 163 int mpdm_exists(const mpdm_t h, const mpdm_t k)
 164 {
 165         mpdm_t b;
 166         int n;
 167         int ret = 0;
 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 ((n = mpdm_bseek(b, k, 2, NULL)) >= 0)
 174                                 ret = 1;
 175                 }
 176         }
 177
 178         return ret;
 179 }
 180
 181
 182 static mpdm_t hset(mpdm_t h, mpdm_t k, const wchar_t *ks, mpdm_t v)
 183 {
 184         mpdm_t b;
 185         int n;
 186
 187         /* if hash is empty, create an optimal number of buckets */
 188         if (mpdm_size(h) == 0)
 189                 mpdm_expand(h, 0, mpdm->hash_buckets);
 190
 191         n = ks ? HASH_BUCKET_S(h, ks) : HASH_BUCKET(h, k);
 192
 193         if ((b = mpdm_aget(h, n)) != NULL) {
 194                 int pos;
 195
 196                 /* bucket exists; try to find the key there */
 197                 n = ks ? mpdm_bseek_s(b, ks, 2, &pos) : mpdm_bseek(b, k, 2, &pos);
 198
 199                 if (n < 0) {
 200                         /* the pair does not exist: create it */
 201                         n = pos;
 202                         mpdm_expand(b, n, 2);
 203
 204                         mpdm_aset(b, ks ? MPDM_S(ks) : k, n);
 205                 }
 206         }
 207         else {
 208                 /* the bucket does not exist; create it */
 209                 b = MPDM_A(2);
 210
 211                 /* put the bucket into the hash */
 212                 mpdm_aset(h, b, n);
 213
 214                 /* offset 0 */
 215                 n = 0;
 216
 217                 /* insert the key */
 218                 mpdm_aset(b, ks ? MPDM_S(ks) : k, n);
 219         }
 220
 221         return mpdm_aset(b, v, n + 1);
 222 }
 223
 224
 225 /**
 226  * mpdm_hset - Sets a value in a hash.
 227  * @h: the hash
 228  * @k: the key
 229  * @v: the value
 230  *
 231  * Sets the value @v to the key @k in the hash @h. Returns
 232  * the new value (versions prior to 1.0.10 returned the old
 233  * value).
 234  * [Hashes]
 235  */
 236 mpdm_t mpdm_hset(mpdm_t h, mpdm_t k, mpdm_t v)
 237 {
 238         return hset(h, k, NULL, v);
 239 }
 240
 241
 242 /**
 243  * mpdm_hset_s - Sets a value in a hash (string version).
 244  * @h: the hash
 245  * @k: the key
 246  * @v: the value
 247  *
 248  * Sets the value @v to the key @k in the hash @h. Returns
 249  * the new value (versions prior to 1.0.10 returned the old
 250  * value).
 251  * [Hashes]
 252  */
 253 mpdm_t mpdm_hset_s(mpdm_t h, const wchar_t *k, mpdm_t v)
 254 {
 255         return hset(h, NULL, k, v);
 256 }
 257
 258
 259 /**
 260  * mpdm_hdel - Deletes a key from a hash.
 261  * @h: the hash
 262  * @k: the key
 263  *
 264  * Deletes the key @k from the hash @h. Returns NULL
 265  * (versions prior to 1.0.10 returned the deleted value).
 266  * [Hashes]
 267  */
 268 mpdm_t mpdm_hdel(mpdm_t h, const mpdm_t k)
 269 {
 270         mpdm_t b;
 271         int n;
 272
 273         if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 274                 /* bucket exists */
 275                 if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0) {
 276                         /* collapse the bucket */
 277                         mpdm_collapse(b, n, 2);
 278                 }
 279         }
 280
 281         return NULL;
 282 }
 283
 284
 285 /**
 286  * mpdm_keys - Returns the keys of a hash.
 287  * @h: the hash
 288  *
 289  * Returns an array containing all the keys of the @h hash.
 290  * [Hashes]
 291  * [Arrays]
 292  */
 293 mpdm_t mpdm_keys(const mpdm_t h)
 294 {
 295         int n, c;
 296         mpdm_t a, k;
 297
 298         /* create an array with the same number of elements */
 299         a = MPDM_A(mpdm_hsize(h));
 300
 301         c = n = 0;
 302         while (mpdm_iterator(h, &c, &k, NULL))
 303                 mpdm_aset(a, k, n++);
 304
 305         return a;
 306 }
 307
 308
 309 /**
 310  * mpdm_interator - Iterates through the content of a hash or array.
 311  * @h: the hash (or array)
 312  * @context: A pointer to an opaque context
 313  * @v1: a pointer to a value
 314  * @v2: another pointer to a value
 315  *
 316  * Iterates through the content of a hash, filling the @v1 and @v2
 317  * pointers with key-value pairs on each call until the hash is
 318  * exhausted. If @h is an array, only the @v1 pointer is filled.
 319  * @v1 and @v2 pointers can be NULL.
 320  *
 321  * The @context pointer to integer is opaque and should be
 322  * initialized to zero on the first call.
 323  *
 324  * Returns 0 if no more data is left in @h.
 325  * [Hashes]
 326  * [Arrays]
 327  */
 328 int mpdm_iterator(mpdm_t h, int *context, mpdm_t *v1, mpdm_t *v2)
 329 {
 330         mpdm_t w1, w2;
 331
 332         if (v1 == NULL)
 333                 v1 = &w1;
 334
 335         if (v2 == NULL)
 336                 v2 = &w2;
 337
 338         if (MPDM_IS_HASH(h)) {
 339                 int bi, ei;
 340
 341                 if (!mpdm_size(h))
 342                         return 0;
 343
 344                 /* get bucket and element index */
 345                 bi = (*context) % mpdm_size(h);
 346                 ei = (*context) / mpdm_size(h);
 347
 348                 while (bi < mpdm_size(h)) {
 349                         mpdm_t b;
 350
 351                         /* if bucket is empty or there is no more elements in it, pick next */
 352                         if ((b = mpdm_aget(h, bi)) == NULL || ei >= mpdm_size(b)) {
 353                                 ei = 0;
 354                                 bi++;
 355                                 continue;
 356                         }
 357
 358                         /* get pair */
 359                         *v1 = mpdm_aget(b, ei++);
 360                         *v2 = mpdm_aget(b, ei++);
 361
 362                         /* update context */
 363                         *context = (ei * mpdm_size(h)) + bi;
 364                         return 1;
 365                 }
 366         }
 367         else
 368         if (MPDM_IS_ARRAY(h)) {
 369                 if (*context < mpdm_size(h)) {
 370                         *v1 = mpdm_aget(h, (*context)++);
 371                         return 1;
 372                 }
 373         }
 374
 375         return 0;
 376 }
 377
 378
 379 static mpdm_t mpdm_sym(mpdm_t r, mpdm_t k, mpdm_t v, int s)
 380 {
 381         int n;
 382         mpdm_t p;
 383     mpdm_t w = NULL;
 384
 385         if (r == NULL)
 386                 r = mpdm_root();
 387
 388         /* splits the path, if needed */
 389         if (k->flags & MPDM_MULTIPLE)
 390                 p = k;
 391         else
 392                 w = p = mpdm_split_s(L".", k);
 393
 394         for (n = 0; n < mpdm_size(p) - s; n++) {
 395
 396                 /* is executable? run it and take its output */
 397                 while (MPDM_IS_EXEC(r)) {
 398             mpdm_t t = mpdm_ref(r);
 399                         r = mpdm_exec(t, NULL);
 400             mpdm_unref(t);
 401         }
 402
 403                 if (MPDM_IS_HASH(r))
 404                         r = mpdm_hget(r, mpdm_aget(p, n));
 405                 else
 406                 if (MPDM_IS_ARRAY(r)) {
 407                         int i = mpdm_ival(mpdm_aget(p, n));
 408                         r = mpdm_aget(r, i);
 409                 }
 410                 else
 411                         r = NULL;
 412
 413                 if (r == NULL)
 414                         break;
 415         }
 416
 417         /* if want to set, do it */
 418         if (s && r != NULL) {
 419                 /* resolve executable values again */
 420                 while (MPDM_IS_EXEC(r)) {
 421             mpdm_t t = mpdm_ref(r);
 422                         r = mpdm_exec(t, NULL);
 423             mpdm_unref(t);
 424         }
 425
 426                 if (r->flags & MPDM_HASH)
 427                         r = mpdm_hset(r, mpdm_aget(p, n), v);
 428                 else {
 429                         int i = mpdm_ival(mpdm_aget(p, n));
 430                         r = mpdm_aset(r, v, i);
 431                 }
 432         }
 433
 434     mpdm_unref(w);
 435
 436         return r;
 437 }
 438
 439
 440 mpdm_t mpdm_sget(mpdm_t r, mpdm_t k)
 441 {
 442         return mpdm_sym(r, k, NULL, 0);
 443 }
 444
 445
 446 mpdm_t mpdm_sset(mpdm_t r, mpdm_t k, mpdm_t v)
 447 {
 448         return mpdm_sym(r, k, v, 1);
 449 }