hstore_support.c

   1 #include "postgres.h"
   2 #include "utils/builtins.h"
   3
   4 #include "hstore.h"
   5
   6 /****************************************************************************
   7  *                         Compare Functions                                *
   8  ****************************************************************************/
   9 int
  10 compareHStoreStringValue(const void *a, const void *b, void *arg)
  11 {
  12         const HStoreValue  *va = a;
  13         const HStoreValue  *vb = b;
  14         int                                     res;
  15
  16         Assert(va->type == hsvString);
  17         Assert(vb->type == hsvString);
  18
  19         if (va->string.len == vb->string.len)
  20         {
  21                 res = memcmp(va->string.val, vb->string.val, va->string.len);
  22                 if (res == 0 && arg)
  23                         *(bool*)arg = true;
  24         }
  25         else
  26         {
  27                 res = (va->string.len > vb->string.len) ? 1 : -1;
  28         }
  29
  30         return res;
  31 }
  32
  33 int
  34 compareHStorePair(const void *a, const void *b, void *arg)
  35 {
  36         const   HStorePair *pa = a;
  37         const   HStorePair *pb = b;
  38         int     res;
  39
  40         res = compareHStoreStringValue(&pa->key, &pb->key, arg);
  41
  42         /*
  43          * guarantee keeping order of equal pair. Unique algorithm will
  44          * prefer first element as value
  45          */
  46
  47         if (res == 0)
  48                 res = (pa->order > pb->order) ? -1 : 1;
  49
  50         return res;
  51 }
  52
  53 int
  54 compareHStoreValue(HStoreValue *a, HStoreValue *b)
  55 {
  56         if (a->type == b->type)
  57         {
  58                 switch(a->type)
  59                 {
  60                         case hsvNull:
  61                                 return 0;
  62                         case hsvString:
  63                                 return compareHStoreStringValue(a, b, NULL);
  64                         case hsvBool:
  65                                 if (a->boolean == b->boolean)
  66                                         return 0;
  67                                 return (a->boolean > b->boolean) ? 1 : -1;
  68                         case hsvNumeric:
  69                                 return DatumGetInt32(DirectFunctionCall2(numeric_cmp,
  70                                                                                                                  PointerGetDatum(a->numeric),
  71                                                                                                                  PointerGetDatum(b->numeric)));
  72                         case hsvArray:
  73                                 if (a->array.nelems == b->array.nelems)
  74                                 {
  75                                         int i, r;
  76
  77                                         for(i=0; i<a->array.nelems; i++)
  78                                                 if ((r = compareHStoreValue(a->array.elems + i,
  79                                                                                                         b->array.elems + i)) != 0)
  80                                                         return r;
  81
  82                                         return 0;
  83                                 }
  84
  85                                 return (a->array.nelems > b->array.nelems) ? 1 : -1;
  86                         case hsvHash:
  87                                 if (a->hash.npairs == b->hash.npairs)
  88                                 {
  89                                         int i, r;
  90
  91                                         for(i=0; i<a->hash.npairs; i++)
  92                                         {
  93                                                 if ((r = compareHStoreStringValue(&a->hash.pairs[i].key,
  94                                                                                                                   &b->hash.pairs[i].key,
  95                                                                                                                   NULL)) != 0)
  96                                                         return r;
  97                                                 if ((r = compareHStoreValue(&a->hash.pairs[i].value,
  98                                                                                                         &b->hash.pairs[i].value)) != 0)
  99                                                         return r;
 100                                         }
 101
 102                                         return 0;
 103                                 }
 104
 105                                 return (a->hash.npairs > b->hash.npairs) ? 1 : -1;
 106                         case hsvBinary:
 107                                 return compareHStoreBinaryValue(a->binary.data, b->binary.data);
 108                         default:
 109                                 elog(PANIC, "unknown HStoreValue->type: %d", a->type);
 110                 }
 111         }
 112
 113         return (a->type > b->type) ? 1 : -1;
 114 }
 115
 116 int
 117 compareHStoreBinaryValue(char *a, char *b)
 118 {
 119         HStoreIterator  *it1, *it2;
 120         int                             res = 0;
 121
 122         it1 = HStoreIteratorInit(a);
 123         it2 = HStoreIteratorInit(b);
 124
 125         while(res == 0)
 126         {
 127                 HStoreValue             v1, v2;
 128                 int                             r1, r2;
 129
 130                 r1 = HStoreIteratorGet(&it1, &v1, false);
 131                 r2 = HStoreIteratorGet(&it2, &v2, false);
 132
 133                 if (r1 == r2)
 134                 {
 135                         if (r1 == 0)
 136                                 break; /* equal */
 137
 138                         if (v1.type == v2.type)
 139                         {
 140                                 switch(v1.type)
 141                                 {
 142                                         case hsvString:
 143                                                 res = compareHStoreStringValue(&v1, &v2, NULL);
 144                                                 break;
 145                                         case hsvBool:
 146                                                 if (v1.boolean == v2.boolean)
 147                                                         res = 0;
 148                                                 else
 149                                                         res = (v1.boolean > v2.boolean) ? 1 : -1;
 150                                                 break;
 151                                         case hsvNumeric:
 152                                                 res = DatumGetInt32(DirectFunctionCall2(numeric_cmp,
 153                                                                                                 PointerGetDatum(v1.numeric),
 154                                                                                                 PointerGetDatum(v2.numeric)));
 155                                                 break;
 156                                         case hsvArray:
 157                                                 if (v1.array.nelems != v2.array.nelems)
 158                                                         res = (v1.array.nelems > v2.array.nelems) ? 1 : -1;
 159                                                 break;
 160                                         case hsvHash:
 161                                                 if (v1.hash.npairs != v2.hash.npairs)
 162                                                         res = (v1.hash.npairs > v2.hash.npairs) ? 1 : -1;
 163                                                 break;
 164                                         default:
 165                                                 break;
 166                                 }
 167                         }
 168                         else
 169                         {
 170                                 res = (v1.type > v2.type) ?  1 : -1; /* dummy order */
 171                         }
 172                 }
 173                 else
 174                 {
 175                         res = (r1 > r2) ? 1 : -1; /* dummy order */
 176                 }
 177         }
 178
 179         return res;
 180 }
 181
 182 /*
 183  * Sort and unique pairs in hash-like HStoreValue
 184  */
 185 void
 186 uniqueHStoreValue(HStoreValue *v)
 187 {
 188         bool    hasNonUniq = false;
 189
 190         Assert(v->type == hsvHash);
 191
 192         if (v->hash.npairs > 1)
 193                 qsort_arg(v->hash.pairs, v->hash.npairs, sizeof(*v->hash.pairs),
 194                                   compareHStorePair, &hasNonUniq);
 195
 196         if (hasNonUniq)
 197         {
 198                 HStorePair  *ptr = v->hash.pairs + 1,
 199                                         *res = v->hash.pairs;
 200
 201                 while(ptr - v->hash.pairs < v->hash.npairs)
 202                 {
 203                         if (ptr->key.string.len == res->key.string.len &&
 204                                 memcmp(ptr->key.string.val, res->key.string.val,
 205                                            ptr->key.string.len) == 0)
 206                         {
 207                                 v->size -= ptr->key.size + ptr->value.size;
 208                         }
 209                         else
 210                         {
 211                                 res++;
 212                                 if (ptr != res)
 213                                         memcpy(res, ptr, sizeof(*res));
 214                         }
 215                         ptr++;
 216                 }
 217
 218                 v->hash.npairs = res + 1 - v->hash.pairs;
 219         }
 220 }
 221
 222
 223 /****************************************************************************
 224  *                         find string key in hash or array                 *
 225  ****************************************************************************/
 226 HStoreValue*
 227 findUncompressedHStoreValueByValue(char *buffer, uint32 flags, uint32 *lowbound, HStoreValue *key)
 228 {
 229         uint32                          header = *(uint32*)buffer;
 230         static HStoreValue      r;
 231
 232         Assert((header & (HS_FLAG_ARRAY | HS_FLAG_HSTORE)) !=
 233                    (HS_FLAG_ARRAY | HS_FLAG_HSTORE));
 234
 235         if (flags & HS_FLAG_ARRAY & header)
 236         {
 237                 HEntry  *array = (HEntry*)(buffer + sizeof(header));
 238                 char    *data = (char*)(array + (header & HS_COUNT_MASK));
 239                 int     i;
 240
 241                 for(i=(lowbound) ? *lowbound : 0; i<(header & HS_COUNT_MASK); i++) {
 242                         HEntry  *e = array + i;
 243
 244                         if (HSE_ISNULL(*e) && key->type == hsvNull)
 245                         {
 246                                 r.type = hsvNull;
 247                                 if (lowbound)
 248                                         *lowbound = i;
 249                                 r.size = sizeof(HEntry);
 250
 251                                 return &r;
 252                         }
 253                         else if (HSE_ISSTRING(*e) && key->type == hsvString )
 254                         {
 255                                 if (key->string.len == HSE_LEN(*e) &&
 256                                         memcmp(key->string.val, data + HSE_OFF(*e),
 257                                                    key->string.len) == 0)
 258                                 {
 259                                         r.type = hsvString;
 260                                         r.string.val = data + HSE_OFF(*e);
 261                                         r.string.len = key->string.len;
 262                                         r.size = sizeof(HEntry) + r.string.len;
 263                                         if (lowbound)
 264                                                 *lowbound = i;
 265
 266                                         return &r;
 267                                 }
 268                         }
 269                         else if (HSE_ISBOOL(*e) && key->type == hsvBool)
 270                         {
 271                                 if ((HSE_ISBOOL_TRUE(*e) && key->boolean == true) ||
 272                                         (HSE_ISBOOL_FALSE(*e) && key->boolean == false))
 273                                 {
 274                                         r = *key;
 275                                         r.size = sizeof(HEntry);
 276                                         if (lowbound)
 277                                                 *lowbound = i;
 278
 279                                         return &r;
 280                                 }
 281                         }
 282                         else if (HSE_ISNUMERIC(*e) && key->type == hsvNumeric)
 283                         {
 284                                 if (DatumGetBool(DirectFunctionCall2(numeric_eq,
 285                                                                 PointerGetDatum(data + INTALIGN(HSE_OFF(*e))),
 286                                                                 PointerGetDatum(key->numeric))) == true)
 287                                 {
 288                                         r.type = hsvNumeric;
 289                                         r.numeric = (Numeric)(data + INTALIGN(HSE_OFF(*e)));
 290                                         if (lowbound)
 291                                                 *lowbound = i;
 292
 293                                         return &r;
 294                                 }
 295                         }
 296                 }
 297         }
 298         else if (flags & HS_FLAG_HSTORE & header)
 299         {
 300                 HEntry  *array = (HEntry*)(buffer + sizeof(header));
 301                 char    *data = (char*)(array + (header & HS_COUNT_MASK) * 2);
 302                 uint32  stopLow = lowbound ? *lowbound : 0,
 303                                 stopHigh = (header & HS_COUNT_MASK),
 304                                 stopMiddle;
 305
 306                 if (key->type != hsvString)
 307                         return NULL;
 308
 309                 while (stopLow < stopHigh)
 310                 {
 311                         int             difference;
 312                         HEntry  *e;
 313
 314                         stopMiddle = stopLow + (stopHigh - stopLow) / 2;
 315
 316                         e = array + stopMiddle * 2;
 317
 318                         if (key->string.len == HSE_LEN(*e))
 319                                 difference = memcmp(data + HSE_OFF(*e), key->string.val,
 320                                                                         key->string.len);
 321                         else
 322                                 difference = (HSE_LEN(*e) > key->string.len) ? 1 : -1;
 323
 324                         if (difference == 0)
 325                         {
 326                                 HEntry  *v = e + 1;
 327
 328                                 if (lowbound)
 329                                         *lowbound = stopMiddle + 1;
 330
 331                                 if (HSE_ISSTRING(*v))
 332                                 {
 333                                         r.type = hsvString;
 334                                         r.string.val = data + HSE_OFF(*v);
 335                                         r.string.len = HSE_LEN(*v);
 336                                         r.size = sizeof(HEntry) + r.string.len;
 337                                 }
 338                                 else if (HSE_ISBOOL(*v))
 339                                 {
 340                                         r.type = hsvBool;
 341                                         r.boolean = (HSE_ISBOOL_TRUE(*v)) ? true : false;
 342                                         r.size = sizeof(HEntry);
 343                                 }
 344                                 else if (HSE_ISNUMERIC(*v))
 345                                 {
 346                                         r.type = hsvNumeric;
 347                                         r.numeric = (Numeric)(data + INTALIGN(HSE_OFF(*v)));
 348                                         r.size = 2*sizeof(HEntry) + VARSIZE_ANY(r.numeric);
 349                                 }
 350                                 else if (HSE_ISNULL(*v))
 351                                 {
 352                                         r.type = hsvNull;
 353                                         r.size = sizeof(HEntry);
 354                                 }
 355                                 else
 356                                 {
 357                                         r.type = hsvBinary;
 358                                         r.binary.data = data + INTALIGN(HSE_OFF(*v));
 359                                         r.binary.len = HSE_LEN(*v) -
 360                                                                         (INTALIGN(HSE_OFF(*v)) - HSE_OFF(*v));
 361                                         r.size = 2*sizeof(HEntry) + r.binary.len;
 362                                 }
 363
 364                                 return &r;
 365                         }
 366                         else if (difference < 0)
 367                         {
 368                                 stopLow = stopMiddle + 1;
 369                         }
 370                         else
 371                         {
 372                                 stopHigh = stopMiddle;
 373                         }
 374                 }
 375
 376                 if (lowbound)
 377                         *lowbound = stopLow;
 378         }
 379
 380         return NULL;
 381 }
 382
 383 HStoreValue*
 384 findUncompressedHStoreValue(char *buffer, uint32 flags, uint32 *lowbound,
 385                                                         char *key, uint32 keylen)
 386 {
 387         HStoreValue     v;
 388
 389         if (key == NULL)
 390         {
 391                 v.type = hsvNull;
 392         }
 393         else
 394         {
 395                 v.type = hsvString;
 396                 v.string.val = key;
 397                 v.string.len = keylen;
 398         }
 399
 400         return findUncompressedHStoreValueByValue(buffer, flags, lowbound, &v);
 401 }
 402
 403 HStoreValue*
 404 getHStoreValue(char *buffer, uint32 flags, int32 i)
 405 {
 406         uint32                          header = *(uint32*)buffer;
 407         static HStoreValue      r;
 408         HEntry                          *array, *e;
 409         char                            *data;
 410
 411         Assert((header & (HS_FLAG_ARRAY | HS_FLAG_HSTORE)) !=
 412                    (HS_FLAG_ARRAY | HS_FLAG_HSTORE));
 413
 414         if (i >= 0)
 415         {
 416                 if (i >= (header & HS_COUNT_MASK))
 417                         return NULL;
 418         }
 419         else
 420         {
 421                 if (-i > (header & HS_COUNT_MASK))
 422                         return NULL;
 423
 424                 i = (header & HS_COUNT_MASK) + i;
 425         }
 426
 427         array = (HEntry*)(buffer + sizeof(header));
 428
 429         if (flags & HS_FLAG_ARRAY & header)
 430         {
 431                 e = array + i;
 432                 data = (char*)(array + (header & HS_COUNT_MASK));
 433         }
 434         else if (flags & HS_FLAG_HSTORE & header)
 435         {
 436                 e = array + i * 2 + 1;
 437                 data = (char*)(array + (header & HS_COUNT_MASK) * 2);
 438         }
 439         else
 440         {
 441                 return NULL;
 442         }
 443
 444         if (HSE_ISSTRING(*e))
 445         {
 446                 r.type = hsvString;
 447                 r.string.val = data + HSE_OFF(*e);
 448                 r.string.len = HSE_LEN(*e);
 449                 r.size = sizeof(HEntry) + r.string.len;
 450         }
 451         else if (HSE_ISBOOL(*e))
 452         {
 453                 r.type = hsvBool;
 454                 r.boolean = (HSE_ISBOOL_TRUE(*e)) ? true : false;
 455                 r.size = sizeof(HEntry);
 456         }
 457         else if (HSE_ISNUMERIC(*e))
 458         {
 459                 r.type = hsvNumeric;
 460                 r.numeric = (Numeric)(data + INTALIGN(HSE_OFF(*e)));
 461                 r.size = 2*sizeof(HEntry) + VARSIZE_ANY(r.numeric);
 462         }
 463         else if (HSE_ISNULL(*e))
 464         {
 465                 r.type = hsvNull;
 466                 r.size = sizeof(HEntry);
 467         }
 468         else
 469         {
 470                 r.type = hsvBinary;
 471                 r.binary.data = data + INTALIGN(HSE_OFF(*e));
 472                 r.binary.len = HSE_LEN(*e) - (INTALIGN(HSE_OFF(*e)) - HSE_OFF(*e));
 473                 r.size = r.binary.len + 2*sizeof(HEntry);
 474         }
 475
 476         return &r;
 477 }
 478
 479 /****************************************************************************
 480  *                         Walk on tree representation of hstore            *
 481  ****************************************************************************/
 482 static void
 483 walkUncompressedHStoreDo(HStoreValue *v, walk_hstore_cb cb, void *cb_arg,
 484                                                  uint32 level)
 485 {
 486         int i;
 487
 488         switch(v->type)
 489         {
 490                 case hsvArray:
 491                         cb(cb_arg, v, WHS_BEGIN_ARRAY, level);
 492                         for(i=0; i<v->array.nelems; i++)
 493                         {
 494                                 if (v->array.elems[i].type == hsvNull ||
 495                                         v->array.elems[i].type == hsvString ||
 496                                         v->array.elems[i].type == hsvBool ||
 497                                         v->array.elems[i].type == hsvNumeric ||
 498                                         v->array.elems[i].type == hsvBinary)
 499                                         cb(cb_arg, v->array.elems + i, WHS_ELEM, level);
 500                                 else
 501                                         walkUncompressedHStoreDo(v->array.elems + i, cb, cb_arg,
 502                                                                                          level + 1);
 503                         }
 504                         cb(cb_arg, v, WHS_END_ARRAY, level);
 505                         break;
 506                 case hsvHash:
 507                         cb(cb_arg, v, WHS_BEGIN_HASH, level);
 508
 509                         for(i=0; i<v->hash.npairs; i++)
 510                         {
 511                                 cb(cb_arg, &v->hash.pairs[i].key, WHS_KEY, level);
 512
 513                                 if (v->hash.pairs[i].value.type == hsvNull ||
 514                                         v->hash.pairs[i].value.type == hsvString ||
 515                                         v->hash.pairs[i].value.type == hsvBool ||
 516                                         v->hash.pairs[i].value.type == hsvNumeric ||
 517                                         v->hash.pairs[i].value.type == hsvBinary)
 518                                         cb(cb_arg, &v->hash.pairs[i].value, WHS_VALUE, level);
 519                                 else
 520                                         walkUncompressedHStoreDo(&v->hash.pairs[i].value, cb, cb_arg, level + 1);
 521                         }
 522
 523                         cb(cb_arg, v, WHS_END_HASH, level);
 524                         break;
 525                 default:
 526                         elog(PANIC, "impossible HStoreValue->type: %d", v->type);
 527         }
 528 }
 529
 530 void
 531 walkUncompressedHStore(HStoreValue *v, walk_hstore_cb cb, void *cb_arg)
 532 {
 533         if (v)
 534                 walkUncompressedHStoreDo(v, cb, cb_arg, 0);
 535 }
 536
 537 /****************************************************************************
 538  *                         Iteration over binary hstore                     *
 539  ****************************************************************************/
 540 static void
 541 parseBuffer(HStoreIterator *it, char *buffer)
 542 {
 543         uint32  header = *(uint32*)buffer;
 544
 545         it->type = header & (HS_FLAG_ARRAY | HS_FLAG_HSTORE);
 546         it->nelems = header & HS_COUNT_MASK;
 547         it->buffer = buffer;
 548
 549
 550         buffer += sizeof(uint32);
 551         it->array = (HEntry*)buffer;
 552
 553         it->state = hsi_start;
 554
 555         switch(it->type)
 556         {
 557                 case HS_FLAG_ARRAY:
 558                         it->data = buffer + it->nelems * sizeof(HEntry);
 559                         it->isScalar = (header & HS_FLAG_SCALAR) ? true : false;
 560                         Assert(it->isScalar == false || it->nelems == 1);
 561                         break;
 562                 case HS_FLAG_HSTORE:
 563                         it->data = buffer + it->nelems * sizeof(HEntry) * 2;
 564                         break;
 565                 default:
 566                         elog(PANIC, "impossible type: %08x", it->type);
 567         }
 568 }
 569
 570 HStoreIterator*
 571 HStoreIteratorInit(char *buffer)
 572 {
 573         HStoreIterator  *it = palloc(sizeof(*it));
 574
 575         parseBuffer(it, buffer);
 576         it->next = NULL;
 577
 578         return it;
 579 }
 580
 581 static bool
 582 formAnswer(HStoreIterator **it, HStoreValue *v, HEntry *e, bool skipNested)
 583 {
 584         if (HSE_ISSTRING(*e))
 585         {
 586                 v->type = hsvString;
 587                 v->string.val = (*it)->data + HSE_OFF(*e);
 588                 v->string.len = HSE_LEN(*e);
 589                 v->size = sizeof(HEntry) + v->string.len;
 590
 591                 return false;
 592         }
 593         else if (HSE_ISBOOL(*e))
 594         {
 595                 v->type = hsvBool;
 596                 v->boolean = (HSE_ISBOOL_TRUE(*e)) ? true : false;
 597                 v->size = sizeof(HEntry);
 598
 599                 return false;
 600         }
 601         else if (HSE_ISNUMERIC(*e))
 602         {
 603                 v->type = hsvNumeric;
 604                 v->numeric = (Numeric)((*it)->data + INTALIGN(HSE_OFF(*e)));
 605                 v->size = 2*sizeof(HEntry) + VARSIZE_ANY(v->numeric);
 606
 607                 return false;
 608         }
 609         else if (HSE_ISNULL(*e))
 610         {
 611                 v->type = hsvNull;
 612                 v->size = sizeof(HEntry);
 613
 614                 return false;
 615         }
 616         else if (skipNested)
 617         {
 618                 v->type = hsvBinary;
 619                 v->binary.data = (*it)->data + INTALIGN(HSE_OFF(*e));
 620                 v->binary.len = HSE_LEN(*e) - (INTALIGN(HSE_OFF(*e)) - HSE_OFF(*e));
 621                 v->size = v->binary.len + 2*sizeof(HEntry);
 622
 623                 return false;
 624         }
 625         else
 626         {
 627                 HStoreIterator *nit = palloc(sizeof(*nit));
 628
 629                 parseBuffer(nit, (*it)->data + INTALIGN(HSE_OFF(*e)));
 630                 nit->next = *it;
 631                 *it = nit;
 632
 633                 return true;
 634         }
 635 }
 636
 637 static HStoreIterator*
 638 up(HStoreIterator *it)
 639 {
 640         HStoreIterator *v = it->next;
 641
 642         pfree(it);
 643
 644         return v;
 645 }
 646
 647 int
 648 HStoreIteratorGet(HStoreIterator **it, HStoreValue *v, bool skipNested)
 649 {
 650         int res;
 651
 652         if (*it == NULL)
 653                 return 0;
 654
 655         /*
 656          * Encode all possible states by one integer. That's possible
 657          * because enum members of HStoreIterator->state uses different bits
 658          * than HS_FLAG_ARRAY/HS_FLAG_HSTORE. See definition of HStoreIterator
 659          */
 660
 661         switch((*it)->type | (*it)->state)
 662         {
 663                 case HS_FLAG_ARRAY | hsi_start:
 664                         (*it)->state = hsi_elem;
 665                         (*it)->i = 0;
 666                         v->type = hsvArray;
 667                         v->array.nelems = (*it)->nelems;
 668                         res = WHS_BEGIN_ARRAY;
 669                         v->array.scalar = (*it)->isScalar;
 670                         break;
 671                 case HS_FLAG_ARRAY | hsi_elem:
 672                         if ((*it)->i >= (*it)->nelems)
 673                         {
 674                                 *it = up(*it);
 675                                 res = WHS_END_ARRAY;
 676                         }
 677                         else if (formAnswer(it, v, &(*it)->array[ (*it)->i++ ], skipNested))
 678                         {
 679                                 res = HStoreIteratorGet(it, v, skipNested);
 680                         }
 681                         else
 682                         {
 683                                 res = WHS_ELEM;
 684                         }
 685                         break;
 686                 case HS_FLAG_HSTORE | hsi_start:
 687                         (*it)->state = hsi_key;
 688                         (*it)->i = 0;
 689                         v->type = hsvHash;
 690                         v->hash.npairs = (*it)->nelems;
 691                         res = WHS_BEGIN_HASH;
 692                         break;
 693                 case HS_FLAG_HSTORE | hsi_key:
 694                         if ((*it)->i >= (*it)->nelems)
 695                         {
 696                                 *it = up(*it);
 697                                 res = WHS_END_HASH;
 698                         }
 699                         else
 700                         {
 701                                 formAnswer(it, v, &(*it)->array[ (*it)->i * 2 ], false);
 702                                 (*it)->state = hsi_value;
 703                                 res = WHS_KEY;
 704                         }
 705                         break;
 706                 case HS_FLAG_HSTORE | hsi_value:
 707                         (*it)->state = hsi_key;
 708                         if (formAnswer(it, v, &(*it)->array[ ((*it)->i++) * 2 + 1],
 709                                                    skipNested))
 710                                 res = HStoreIteratorGet(it, v, skipNested);
 711                         else
 712                                 res = WHS_VALUE;
 713                         break;
 714                 default:
 715                         elog(PANIC,"unknown state %08x", (*it)->type & (*it)->state);
 716         }
 717
 718         return res;
 719 }
 720
 721 /****************************************************************************
 722  *        Transformation from tree to binary representation of hstore       *
 723  ****************************************************************************/
 724 typedef struct CompressState
 725 {
 726         char    *begin;
 727         char    *ptr;
 728
 729         struct {
 730                 uint32  i;
 731                 uint32  *header;
 732                 HEntry  *array;
 733                 char    *begin;
 734         } *levelstate, *lptr, *pptr;
 735
 736         uint32  maxlevel;
 737
 738 } CompressState;
 739
 740 #define curLevelState   state->lptr
 741 #define prevLevelState  state->pptr
 742
 743 static void
 744 putHEntryString(CompressState *state, HStoreValue* value,
 745                                 uint32 level, uint32 i)
 746 {
 747         curLevelState = state->levelstate + level;
 748
 749         if (i == 0)
 750                 curLevelState->array[0].entry = HENTRY_ISFIRST;
 751         else
 752                 curLevelState->array[i].entry = 0;
 753
 754         switch(value->type)
 755         {
 756                 case hsvNull:
 757                         curLevelState->array[i].entry |= HENTRY_ISNULL;
 758
 759                         if (i>0)
 760                                 curLevelState->array[i].entry |=
 761                                         curLevelState->array[i - 1].entry & HENTRY_POSMASK;
 762                         break;
 763                 case hsvString:
 764                         memcpy(state->ptr, value->string.val, value->string.len);
 765                         state->ptr += value->string.len;
 766
 767                         if (i == 0)
 768                                 curLevelState->array[i].entry |= value->string.len;
 769                         else
 770                                 curLevelState->array[i].entry |=
 771                                         (curLevelState->array[i - 1].entry & HENTRY_POSMASK) +
 772                                         value->string.len;
 773                         break;
 774                 case hsvBool:
 775                         curLevelState->array[i].entry |=
 776                                 (value->boolean) ? HENTRY_ISTRUE : HENTRY_ISFALSE;
 777
 778                         if (i>0)
 779                                 curLevelState->array[i].entry |=
 780                                         curLevelState->array[i - 1].entry & HENTRY_POSMASK;
 781                         break;
 782                 case hsvNumeric:
 783                         {
 784                                 int addlen = INTALIGN(state->ptr - state->begin) -
 785                                                                 (state->ptr - state->begin);
 786                                 int     numlen = VARSIZE_ANY(value->numeric);
 787
 788                                 switch(addlen)
 789                                 {
 790                                         case 3:
 791                                                 *state->ptr = '\0'; state->ptr++;
 792                                         case 2:
 793                                                 *state->ptr = '\0'; state->ptr++;
 794                                         case 1:
 795                                                 *state->ptr = '\0'; state->ptr++;
 796                                         case 0:
 797                                         default:
 798                                                 break;
 799                                 }
 800
 801                                 memcpy(state->ptr, value->numeric, numlen);
 802                                 state->ptr += numlen;
 803
 804                                 curLevelState->array[i].entry |= HENTRY_ISNUMERIC;
 805                                 if (i == 0)
 806                                         curLevelState->array[i].entry |= addlen + numlen;
 807                                 else
 808                                         curLevelState->array[i].entry |=
 809                                                 (curLevelState->array[i - 1].entry & HENTRY_POSMASK) +
 810                                                 addlen + numlen;
 811                                 break;
 812                         }
 813                 case hsvBinary:
 814                         {
 815                                 int addlen = INTALIGN(state->ptr - state->begin) -
 816                                                                 (state->ptr - state->begin);
 817
 818                                 switch(addlen)
 819                                 {
 820                                         case 3:
 821                                                 *state->ptr = '\0'; state->ptr++;
 822                                         case 2:
 823                                                 *state->ptr = '\0'; state->ptr++;
 824                                         case 1:
 825                                                 *state->ptr = '\0'; state->ptr++;
 826                                         case 0:
 827                                         default:
 828                                                 break;
 829                                 }
 830
 831                                 memcpy(state->ptr, value->binary.data, value->binary.len);
 832                                 state->ptr += value->binary.len;
 833
 834                                 curLevelState->array[i].entry |= HENTRY_ISNEST;
 835
 836                                 if (i == 0)
 837                                         curLevelState->array[i].entry |= addlen + value->binary.len;
 838                                 else
 839                                         curLevelState->array[i].entry |=
 840                                                 (curLevelState->array[i - 1].entry & HENTRY_POSMASK) +
 841                                                 addlen + value->binary.len;
 842                         }
 843                         break;
 844                 default:
 845                         elog(PANIC,"Unsupported HStoreValue type: %d", value->type);
 846         }
 847 }
 848
 849 static void
 850 compressCallback(void *arg, HStoreValue* value, uint32 flags, uint32 level)
 851 {
 852         CompressState   *state = arg;
 853
 854         if (level == state->maxlevel) {
 855                 state->maxlevel *= 2;
 856                 state->levelstate = repalloc(state->levelstate,
 857                                                                  sizeof(*state->levelstate) * state->maxlevel);
 858         }
 859
 860         curLevelState = state->levelstate + level;
 861
 862         if (flags & (WHS_BEGIN_ARRAY | WHS_BEGIN_HASH))
 863         {
 864                 Assert(((flags & WHS_BEGIN_ARRAY) && value->type == hsvArray) ||
 865                            ((flags & WHS_BEGIN_HASH) && value->type == hsvHash));
 866
 867                 curLevelState->begin = state->ptr;
 868
 869                 switch(INTALIGN(state->ptr - state->begin) -
 870                                                 (state->ptr - state->begin))
 871                 {
 872                         case 3:
 873                                 *state->ptr = '\0'; state->ptr++;
 874                         case 2:
 875                                 *state->ptr = '\0'; state->ptr++;
 876                         case 1:
 877                                 *state->ptr = '\0'; state->ptr++;
 878                         case 0:
 879                         default:
 880                                 break;
 881                 }
 882
 883                 curLevelState->header = (uint32*)state->ptr;
 884                 state->ptr += sizeof(*curLevelState->header);
 885
 886                 curLevelState->array = (HEntry*)state->ptr;
 887                 curLevelState->i = 0;
 888
 889                 if (value->type == hsvArray)
 890                 {
 891                         *curLevelState->header = value->array.nelems | HS_FLAG_ARRAY ;
 892                         state->ptr += sizeof(HEntry) * value->array.nelems;
 893
 894                         if (value->array.scalar)
 895                         {
 896                                 Assert(value->array.nelems == 1);
 897                                 Assert(level == 0);
 898                                 *curLevelState->header |= HS_FLAG_SCALAR;
 899                         }
 900                 }
 901                 else
 902                 {
 903                         *curLevelState->header = value->hash.npairs | HS_FLAG_HSTORE ;
 904                         state->ptr += sizeof(HEntry) * value->hash.npairs * 2;
 905                 }
 906
 907                 if (level == 0)
 908                         *curLevelState->header |= HS_FLAG_NEWVERSION;
 909         }
 910         else if (flags & WHS_ELEM)
 911         {
 912                 putHEntryString(state, value, level, curLevelState->i);
 913                 curLevelState->i++;
 914         }
 915         else if (flags & WHS_KEY)
 916         {
 917                 Assert(value->type == hsvString);
 918
 919                 putHEntryString(state, value, level, curLevelState->i * 2);
 920         }
 921         else if (flags & WHS_VALUE)
 922         {
 923                 putHEntryString(state, value, level, curLevelState->i * 2 + 1);
 924                 curLevelState->i++;
 925         }
 926         else if (flags & (WHS_END_ARRAY | WHS_END_HASH))
 927         {
 928                 uint32  len, i;
 929
 930                 Assert(((flags & WHS_END_ARRAY) && value->type == hsvArray) ||
 931                            ((flags & WHS_END_HASH) && value->type == hsvHash));
 932                 if (level == 0)
 933                         return;
 934
 935                 len = state->ptr - (char*)curLevelState->begin;
 936
 937                 prevLevelState = curLevelState - 1;
 938
 939                 if (*prevLevelState->header & HS_FLAG_ARRAY) {
 940                         i = prevLevelState->i;
 941
 942                         prevLevelState->array[i].entry = HENTRY_ISNEST;
 943
 944                         if (i == 0)
 945                                 prevLevelState->array[0].entry |= HENTRY_ISFIRST | len;
 946                         else
 947                                 prevLevelState->array[i].entry |=
 948                                         (prevLevelState->array[i - 1].entry & HENTRY_POSMASK) + len;
 949                 }
 950                 else if (*prevLevelState->header & HS_FLAG_HSTORE)
 951                 {
 952                         i = 2 * prevLevelState->i + 1; /* VALUE, not a KEY */
 953
 954                         prevLevelState->array[i].entry = HENTRY_ISNEST;
 955
 956                         prevLevelState->array[i].entry |=
 957                                 (prevLevelState->array[i - 1].entry & HENTRY_POSMASK) + len;
 958                 }
 959                 else
 960                 {
 961                         elog(PANIC, "Wrong parent");
 962                 }
 963
 964                 Assert(state->ptr - curLevelState->begin <= value->size);
 965                 prevLevelState->i++;
 966         }
 967         else
 968         {
 969                 elog(PANIC, "Wrong flags");
 970         }
 971 }
 972
 973 uint32
 974 compressHStore(HStoreValue *v, char *buffer) {
 975         uint32                  l = 0;
 976         CompressState   state;
 977
 978         state.begin = state.ptr = buffer;
 979         state.maxlevel = 8;
 980         state.levelstate = palloc(sizeof(*state.levelstate) * state.maxlevel);
 981
 982         walkUncompressedHStore(v, compressCallback, &state);
 983
 984         l = state.ptr - buffer;
 985         Assert(l <= v->size);
 986
 987         return l;
 988 }
 989
 990 /****************************************************************************
 991  *                  Iteration-like forming hstore                           *
 992  *       Note: it believ by default in already sorted keys in hash,         *
 993  *     although with r == WHS_END_HASH and v == NULL  it will sort itself   *
 994  ****************************************************************************/
 995 static ToHStoreState*
 996 pushState(ToHStoreState **state)
 997 {
 998         ToHStoreState   *ns = palloc(sizeof(*ns));
 999
1000         ns->next = *state;
1001         return ns;
1002 }
1003
1004 static void
1005 appendArray(ToHStoreState *state, HStoreValue *v)
1006 {
1007         HStoreValue     *a = &state->v;
1008
1009         Assert(a->type == hsvArray);
1010
1011         if (a->array.nelems >= state->size)
1012         {
1013                 state->size *= 2;
1014                 a->array.elems = repalloc(a->array.elems,
1015                                                                    sizeof(*a->array.elems) * state->size);
1016         }
1017
1018         a->array.elems[a->array.nelems ++] = *v;
1019
1020         a->size += v->size;
1021 }
1022
1023 static void
1024 appendKey(ToHStoreState *state, HStoreValue *v)
1025 {
1026         HStoreValue     *h = &state->v;
1027
1028         Assert(h->type == hsvHash);
1029
1030         if (h->hash.npairs >= state->size)
1031         {
1032                 state->size *= 2;
1033                 h->hash.pairs = repalloc(h->hash.pairs,
1034                                                                         sizeof(*h->hash.pairs) * state->size);
1035         }
1036
1037         h->hash.pairs[h->hash.npairs].key = *v;
1038         h->hash.pairs[h->hash.npairs].order = h->hash.npairs;
1039
1040         h->size += v->size;
1041 }
1042
1043 static void
1044 appendValue(ToHStoreState *state, HStoreValue *v)
1045 {
1046
1047         HStoreValue     *h = &state->v;
1048
1049         Assert(h->type == hsvHash);
1050
1051         h->hash.pairs[h->hash.npairs++].value = *v;
1052
1053         h->size += v->size;
1054 }
1055
1056
1057 HStoreValue*
1058 pushHStoreValue(ToHStoreState **state, int r /* WHS_* */, HStoreValue *v) {
1059         HStoreValue     *h = NULL;
1060
1061         switch(r)
1062         {
1063                 case WHS_BEGIN_ARRAY:
1064                         *state = pushState(state);
1065                         h = &(*state)->v;
1066                         (*state)->v.type = hsvArray;
1067                         (*state)->v.size = 3*sizeof(HEntry);
1068                         (*state)->v.array.nelems = 0;
1069                         (*state)->v.array.scalar = (v && v->array.scalar) ? true : false;
1070                         (*state)->size = (v && v->type == hsvArray && v->array.nelems > 0)
1071                                                                 ? v->array.nelems : 4;
1072                         (*state)->v.array.elems = palloc(sizeof(*(*state)->v.array.elems) *
1073                                                                                                         (*state)->size);
1074                         break;
1075                 case WHS_BEGIN_HASH:
1076                         *state = pushState(state);
1077                         h = &(*state)->v;
1078                         (*state)->v.type = hsvHash;
1079                         (*state)->v.size = 3*sizeof(HEntry);
1080                         (*state)->v.hash.npairs = 0;
1081                         (*state)->size = (v && v->type == hsvHash && v->hash.npairs > 0)
1082                                                                 ? v->hash.npairs : 4;
1083                         (*state)->v.hash.pairs = palloc(sizeof(*(*state)->v.hash.pairs) *
1084                                                                                                         (*state)->size);
1085                         break;
1086                 case WHS_ELEM:
1087                         Assert(v->type == hsvNull || v->type == hsvString ||
1088                                    v->type == hsvBool || v->type == hsvNumeric ||
1089                                    v->type == hsvBinary);
1090                         appendArray(*state, v);
1091                         break;
1092                 case WHS_KEY:
1093                         Assert(v->type == hsvString);
1094                         appendKey(*state, v);
1095                         break;
1096                 case WHS_VALUE:
1097                         Assert(v->type == hsvNull || v->type == hsvString ||
1098                                    v->type == hsvBool || v->type == hsvNumeric ||
1099                                    v->type == hsvBinary);
1100                         appendValue(*state, v);
1101                         break;
1102                 case WHS_END_HASH:
1103                         h = &(*state)->v;
1104                         if (v == NULL)
1105                                 uniqueHStoreValue(h);
1106                 case WHS_END_ARRAY:
1107                         h = &(*state)->v;
1108                         *state = (*state)->next;
1109                         if (*state)
1110                         {
1111                                 switch((*state)->v.type)
1112                                 {
1113                                         case hsvArray:
1114                                                 appendArray(*state, h);
1115                                                 break;
1116                                         case hsvHash:
1117                                                 appendValue(*state, h);
1118                                                 break;
1119                                         default:
1120                                                 elog(PANIC, "wrong parent type: %d", (*state)->v.type);
1121                                 }
1122                         }
1123                         break;
1124                 default:
1125                         elog(PANIC, "wrong type: %08x", r);
1126         }
1127
1128         return h;
1129 }
1130