mpdm_h.c

   1 /*
   2
   3     MPDM - Minimum Profit Data Manager
   4     Copyright (C) 2003/2007 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 /*******************
  36         Code
  37 ********************/
  38
  39 /* prototype for the one-time wrapper hash function */
  40 static int switch_hash_func(const wchar_t *, int);
  41
  42 /* pointer to the hashing function */
  43 static int (*mpdm_hash_func) (const wchar_t *, int) = switch_hash_func;
  44
  45 static int standard_hash_func(const wchar_t * string, int mod)
  46 /* computes a hashing function on string */
  47 {
  48         int c;
  49
  50         for (c = 0; *string != L'\0'; string++)
  51                 c ^= (int) *string;
  52
  53         return c % mod;
  54 }
  55
  56
  57 static int null_hash_func(const wchar_t * string, int mod)
  58 {
  59         return *string % mod;
  60 }
  61
  62 static int switch_hash_func(const wchar_t * string, int mod)
  63 /* one-time wrapper for hash method autodetection */
  64 {
  65         /* commute the real hashing function on
  66            having the MPDM_NULL_HASH environment variable set */
  67         if (getenv("MPDM_NULL_HASH") != NULL)
  68                 mpdm_hash_func = null_hash_func;
  69         else
  70                 mpdm_hash_func = standard_hash_func;
  71
  72         /* and fall back to it */
  73         return mpdm_hash_func(string, mod);
  74 }
  75
  76 #define HASH_BUCKET(h, k) (mpdm_hash_func(mpdm_string(k), mpdm_size(h)))
  77
  78 /* interface */
  79
  80 /**
  81  * mpdm_hsize - Returns the number of pairs of a hash.
  82  * @h: the hash
  83  *
  84  * Returns the number of key-value pairs of a hash.
  85  * [Hashes]
  86  */
  87 int mpdm_hsize(const mpdm_t h)
  88 {
  89         int n;
  90         int ret = 0;
  91
  92         for (n = 0; n < mpdm_size(h); n++) {
  93                 mpdm_t b = mpdm_aget(h, n);
  94                 ret += mpdm_size(b);
  95         }
  96
  97         return ret / 2;
  98 }
  99
 100
 101 /**
 102  * mpdm_hget - Gets a value from a hash.
 103  * @h: the hash
 104  * @k: the key
 105  *
 106  * Gets the value from the hash @h having @k as key, or
 107  * NULL if the key does not exist.
 108  * [Hashes]
 109  */
 110 mpdm_t mpdm_hget(const mpdm_t h, const mpdm_t k)
 111 {
 112         mpdm_t b;
 113         mpdm_t v = NULL;
 114         int n;
 115
 116         if (mpdm_size(h)) {
 117                 /* if hash is not empty... */
 118                 if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 119                         /* if bucket exists, binary-seek it */
 120                         if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0)
 121                                 v = mpdm_aget(b, n + 1);
 122                 }
 123         }
 124
 125         return v;
 126 }
 127
 128
 129 /**
 130  * mpdm_hget_s - Gets the value from a hash (string version).
 131  * @h: the hash
 132  * @k: the key
 133  *
 134  * Gets the value from the hash @h having @k as key, or
 135  * NULL if the key does not exist.
 136  * [Hashes]
 137  */
 138 mpdm_t mpdm_hget_s(const mpdm_t h, const wchar_t * k)
 139 {
 140         return mpdm_hget(h, MPDM_LS(k));
 141 }
 142
 143
 144 /**
 145  * mpdm_exists - Tests if a key exists.
 146  * @h: the hash
 147  * @k: the key
 148  *
 149  * Returns 1 if @k is defined in @h, or 0 othersize.
 150  * [Hashes]
 151  */
 152 int mpdm_exists(const mpdm_t h, const mpdm_t k)
 153 {
 154         mpdm_t b;
 155         int n;
 156         int ret = 0;
 157
 158         if (mpdm_size(h)) {
 159                 /* if hash is not empty... */
 160                 if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 161                         /* if bucket exists, binary-seek it */
 162                         if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0)
 163                                 ret = 1;
 164                 }
 165         }
 166
 167         return ret;
 168 }
 169
 170
 171 /**
 172  * mpdm_hset - Sets a value in a hash.
 173  * @h: the hash
 174  * @k: the key
 175  * @v: the value
 176  *
 177  * Sets the value @v to the key @k in the hash @h. Returns
 178  * the previous value of the key, or NULL if the key was
 179  * previously undefined.
 180  * [Hashes]
 181  */
 182 mpdm_t mpdm_hset(mpdm_t h, mpdm_t k, 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 = 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                 if ((n = mpdm_bseek(b, k, 2, &pos)) < 0) {
 198                         /* the pair does not exist: create it */
 199                         n = pos;
 200                         mpdm_expand(b, n, 2);
 201                         mpdm_aset(b, k, n);
 202                 }
 203         }
 204         else {
 205                 /* the bucket does not exist; create it */
 206                 b = MPDM_A(2);
 207
 208                 /* put the bucket into the hash */
 209                 mpdm_aset(h, b, n);
 210
 211                 /* offset 0 */
 212                 n = 0;
 213
 214                 /* insert the key */
 215                 mpdm_aset(b, k, n);
 216         }
 217
 218         return mpdm_aset(b, v, n + 1);
 219 }
 220
 221
 222 /**
 223  * mpdm_hset_s - Sets a value in a hash (string version).
 224  * @h: the hash
 225  * @k: the key
 226  * @v: the value
 227  *
 228  * Sets the value @v to the key @k in the hash @h. Returns
 229  * the previous value of the key, or NULL if the key was
 230  * previously undefined.
 231  * [Hashes]
 232  */
 233 mpdm_t mpdm_hset_s(mpdm_t h, const wchar_t * k, mpdm_t v)
 234 {
 235         return mpdm_hset(h, MPDM_LS(k), v);
 236 }
 237
 238
 239 /**
 240  * mpdm_hdel - Deletes a key from a hash.
 241  * @h: the hash
 242  * @k: the key
 243  *
 244  * Deletes the key @k from the hash @h. Returns the previous
 245  * value, or NULL if the key was not defined.
 246  * [Hashes]
 247  */
 248 mpdm_t mpdm_hdel(mpdm_t h, const mpdm_t k)
 249 {
 250         mpdm_t v = NULL;
 251         mpdm_t b;
 252         int n;
 253
 254         if ((b = mpdm_aget(h, HASH_BUCKET(h, k))) != NULL) {
 255                 /* bucket exists */
 256                 if ((n = mpdm_bseek(b, k, 2, NULL)) >= 0) {
 257                         /* the pair exists: set key and value to NULL */
 258                         mpdm_aset(b, NULL, n);
 259                         v = mpdm_aset(b, NULL, n + 1);
 260
 261                         /* collapse the bucket */
 262                         mpdm_collapse(b, n, 2);
 263                 }
 264         }
 265
 266         return v;
 267 }
 268
 269
 270 /**
 271  * mpdm_keys - Returns the keys of a hash.
 272  * @h: the hash
 273  *
 274  * Returns an array containing all the keys of the @h hash.
 275  * [Hashes]
 276  * [Arrays]
 277  */
 278 mpdm_t mpdm_keys(const mpdm_t h)
 279 {
 280         int n, m, i;
 281         mpdm_t b;
 282         mpdm_t a;
 283
 284         /* create an array with the same number of elements */
 285         a = MPDM_A(mpdm_hsize(h));
 286
 287         /* sequentially fill with keys */
 288         for (n = i = 0; n < mpdm_size(h); n++) {
 289                 if ((b = mpdm_aget(h, n)) != NULL) {
 290                         for (m = 0; m < mpdm_size(b); m += 2)
 291                                 mpdm_aset(a, mpdm_aget(b, m), i++);
 292                 }
 293         }
 294
 295         return a;
 296 }
 297
 298
 299 static mpdm_t mpdm_sym(mpdm_t r, mpdm_t k, mpdm_t v, int s)
 300 {
 301         int n;
 302         mpdm_t p;
 303
 304         if (r == NULL)
 305                 r = mpdm_root();
 306
 307         /* splits the path, if needed */
 308         if (k->flags & MPDM_MULTIPLE)
 309                 p = k;
 310         else
 311                 p = mpdm_split(MPDM_LS(L"."), k);
 312
 313         for (n = 0; n < mpdm_size(p) - s; n++) {
 314
 315                 /* is executable? run it and take its output */
 316                 while (MPDM_IS_EXEC(r))
 317                         r = mpdm_exec(r, NULL);
 318
 319                 if (MPDM_IS_HASH(r))
 320                         r = mpdm_hget(r, mpdm_aget(p, n));
 321                 else
 322                 if (MPDM_IS_ARRAY(r)) {
 323                         int i = mpdm_ival(mpdm_aget(p, n));
 324                         r = mpdm_aget(r, i);
 325                 }
 326                 else
 327                         r = NULL;
 328
 329                 if (r == NULL)
 330                         break;
 331         }
 332
 333         /* if want to set, do it */
 334         if (s && r != NULL) {
 335                 if (r->flags & MPDM_HASH)
 336                         r = mpdm_hset(r, mpdm_aget(p, n), v);
 337                 else {
 338                         int i = mpdm_ival(mpdm_aget(p, n));
 339                         r = mpdm_aset(r, v, i);
 340                 }
 341         }
 342
 343         return r;
 344 }
 345
 346
 347 mpdm_t mpdm_sget(mpdm_t r, mpdm_t k)
 348 {
 349         return mpdm_sym(r, k, NULL, 0);
 350 }
 351
 352
 353 mpdm_t mpdm_sset(mpdm_t r, mpdm_t k, mpdm_t v)
 354 {
 355         return mpdm_sym(r, k, v, 1);
 356 }