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, v;
 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, &v))
 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  *
 320  * The @context pointer to integer is opaque and should be
 321  * initialized to zero on the first call.
 322  *
 323  * Returns 0 if no more data is left in @h.
 324  * [Hashes]
 325  * [Arrays]
 326  */
 327 int mpdm_iterator(mpdm_t h, int *context, mpdm_t *v1, mpdm_t *v2)
 328 {
 329         if (MPDM_IS_HASH(h)) {
 330                 int bi, ei;
 331
 332                 if (!mpdm_size(h))
 333                         return 0;
 334
 335                 /* get bucket and element index */
 336                 bi = (*context) % mpdm_size(h);
 337                 ei = (*context) / mpdm_size(h);
 338
 339                 while (bi < mpdm_size(h)) {
 340                         mpdm_t b;
 341
 342                         /* if bucket is empty or there is no more elements in it, pick next */
 343                         if ((b = mpdm_aget(h, bi)) == NULL || ei >= mpdm_size(b)) {
 344                                 ei = 0;
 345                                 bi++;
 346                                 continue;
 347                         }
 348
 349                         /* get pair */
 350                         *v1 = mpdm_aget(b, ei++);
 351                         *v2 = mpdm_aget(b, ei++);
 352
 353                         /* update context */
 354                         *context = (ei * mpdm_size(h)) + bi;
 355                         return 1;
 356                 }
 357         }
 358         else
 359         if (MPDM_IS_ARRAY(h)) {
 360                 if (*context < mpdm_size(h)) {
 361                         *v1 = mpdm_aget(h, (*context)++);
 362                         return 1;
 363                 }
 364         }
 365
 366         return 0;
 367 }
 368
 369
 370 static mpdm_t mpdm_sym(mpdm_t r, mpdm_t k, mpdm_t v, int s)
 371 {
 372         int n;
 373         mpdm_t p;
 374
 375         if (r == NULL)
 376                 r = mpdm_root();
 377
 378         /* splits the path, if needed */
 379         if (k->flags & MPDM_MULTIPLE)
 380                 p = k;
 381         else
 382                 p = mpdm_split_s(L".", k);
 383
 384         for (n = 0; n < mpdm_size(p) - s; n++) {
 385
 386                 /* is executable? run it and take its output */
 387                 while (MPDM_IS_EXEC(r))
 388                         r = mpdm_exec(r, NULL);
 389
 390                 if (MPDM_IS_HASH(r))
 391                         r = mpdm_hget(r, mpdm_aget(p, n));
 392                 else
 393                 if (MPDM_IS_ARRAY(r)) {
 394                         int i = mpdm_ival(mpdm_aget(p, n));
 395                         r = mpdm_aget(r, i);
 396                 }
 397                 else
 398                         r = NULL;
 399
 400                 if (r == NULL)
 401                         break;
 402         }
 403
 404         /* if want to set, do it */
 405         if (s && r != NULL) {
 406                 /* resolve executable values again */
 407                 while (MPDM_IS_EXEC(r))
 408                         r = mpdm_exec(r, NULL);
 409
 410                 if (r->flags & MPDM_HASH)
 411                         r = mpdm_hset(r, mpdm_aget(p, n), v);
 412                 else {
 413                         int i = mpdm_ival(mpdm_aget(p, n));
 414                         r = mpdm_aset(r, v, i);
 415                 }
 416         }
 417
 418         return r;
 419 }
 420
 421
 422 mpdm_t mpdm_sget(mpdm_t r, mpdm_t k)
 423 {
 424         return mpdm_sym(r, k, NULL, 0);
 425 }
 426
 427
 428 mpdm_t mpdm_sset(mpdm_t r, mpdm_t k, mpdm_t v)
 429 {
 430         return mpdm_sym(r, k, v, 1);
 431 }