contrib/btree_gist/btree_utils_var.c

   1 /*
   2  * contrib/btree_gist/btree_utils_var.c
   3  */
   4 #include "postgres.h"
   5
   6 #include <math.h>
   7 #include <limits.h>
   8 #include <float.h>
   9
  10 #include "btree_gist.h"
  11 #include "btree_utils_var.h"
  12 #include "utils/builtins.h"
  13 #include "utils/pg_locale.h"
  14 #include "utils/rel.h"
  15
  16 /* used for key sorting */
  17 typedef struct
  18 {
  19         int                     i;
  20         GBT_VARKEY *t;
  21 } Vsrt;
  22
  23 typedef struct
  24 {
  25         const gbtree_vinfo *tinfo;
  26         Oid                     collation;
  27         FmgrInfo   *flinfo;
  28 } gbt_vsrt_arg;
  29
  30
  31 PG_FUNCTION_INFO_V1(gbt_var_decompress);
  32 PG_FUNCTION_INFO_V1(gbt_var_fetch);
  33
  34
  35 Datum
  36 gbt_var_decompress(PG_FUNCTION_ARGS)
  37 {
  38         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  39         GBT_VARKEY *key = (GBT_VARKEY *) PG_DETOAST_DATUM(entry->key);
  40
  41         if (key != (GBT_VARKEY *) DatumGetPointer(entry->key))
  42         {
  43                 GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  44
  45                 gistentryinit(*retval, PointerGetDatum(key),
  46                                           entry->rel, entry->page,
  47                                           entry->offset, false);
  48
  49                 PG_RETURN_POINTER(retval);
  50         }
  51
  52         PG_RETURN_POINTER(entry);
  53 }
  54
  55 /* Returns a better readable representation of variable key ( sets pointer ) */
  56 GBT_VARKEY_R
  57 gbt_var_key_readable(const GBT_VARKEY *k)
  58 {
  59         GBT_VARKEY_R r;
  60
  61         r.lower = (bytea *) &(((char *) k)[VARHDRSZ]);
  62         if (VARSIZE(k) > (VARHDRSZ + (VARSIZE(r.lower))))
  63                 r.upper = (bytea *) &(((char *) k)[VARHDRSZ + INTALIGN(VARSIZE(r.lower))]);
  64         else
  65                 r.upper = r.lower;
  66         return r;
  67 }
  68
  69
  70 /*
  71  * Create a leaf-entry to store in the index, from a single Datum.
  72  */
  73 static GBT_VARKEY *
  74 gbt_var_key_from_datum(const struct varlena *u)
  75 {
  76         int32           lowersize = VARSIZE(u);
  77         GBT_VARKEY *r;
  78
  79         r = (GBT_VARKEY *) palloc(lowersize + VARHDRSZ);
  80         memcpy(VARDATA(r), u, lowersize);
  81         SET_VARSIZE(r, lowersize + VARHDRSZ);
  82
  83         return r;
  84 }
  85
  86 /*
  87  * Create an entry to store in the index, from lower and upper bound.
  88  */
  89 GBT_VARKEY *
  90 gbt_var_key_copy(const GBT_VARKEY_R *u)
  91 {
  92         int32           lowersize = VARSIZE(u->lower);
  93         int32           uppersize = VARSIZE(u->upper);
  94         GBT_VARKEY *r;
  95
  96         r = (GBT_VARKEY *) palloc0(INTALIGN(lowersize) + uppersize + VARHDRSZ);
  97         memcpy(VARDATA(r), u->lower, lowersize);
  98         memcpy(VARDATA(r) + INTALIGN(lowersize), u->upper, uppersize);
  99         SET_VARSIZE(r, INTALIGN(lowersize) + uppersize + VARHDRSZ);
 100
 101         return r;
 102 }
 103
 104
 105 static GBT_VARKEY *
 106 gbt_var_leaf2node(GBT_VARKEY *leaf, const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 107 {
 108         GBT_VARKEY *out = leaf;
 109
 110         if (tinfo->f_l2n)
 111                 out = tinfo->f_l2n(leaf, flinfo);
 112
 113         return out;
 114 }
 115
 116
 117 /*
 118  * returns the common prefix length of a node key
 119 */
 120 static int32
 121 gbt_var_node_cp_len(const GBT_VARKEY *node, const gbtree_vinfo *tinfo)
 122 {
 123         GBT_VARKEY_R r = gbt_var_key_readable(node);
 124         int32           i = 0;
 125         int32           l = 0;
 126         int32           t1len = VARSIZE(r.lower) - VARHDRSZ;
 127         int32           t2len = VARSIZE(r.upper) - VARHDRSZ;
 128         int32           ml = Min(t1len, t2len);
 129         char       *p1 = VARDATA(r.lower);
 130         char       *p2 = VARDATA(r.upper);
 131
 132         if (ml == 0)
 133                 return 0;
 134
 135         while (i < ml)
 136         {
 137                 if (tinfo->eml > 1 && l == 0)
 138                 {
 139                         if ((l = pg_mblen(p1)) != pg_mblen(p2))
 140                         {
 141                                 return i;
 142                         }
 143                 }
 144                 if (*p1 != *p2)
 145                 {
 146                         if (tinfo->eml > 1)
 147                         {
 148                                 return (i - l + 1);
 149                         }
 150                         else
 151                         {
 152                                 return i;
 153                         }
 154                 }
 155
 156                 p1++;
 157                 p2++;
 158                 l--;
 159                 i++;
 160         }
 161         return ml;                                      /* lower == upper */
 162 }
 163
 164
 165 /*
 166  * returns true, if query matches prefix ( common prefix )
 167  */
 168 static bool
 169 gbt_bytea_pf_match(const bytea *pf, const bytea *query, const gbtree_vinfo *tinfo)
 170 {
 171         bool            out = false;
 172         int32           qlen = VARSIZE(query) - VARHDRSZ;
 173         int32           nlen = VARSIZE(pf) - VARHDRSZ;
 174
 175         if (nlen <= qlen)
 176         {
 177                 char       *q = VARDATA(query);
 178                 char       *n = VARDATA(pf);
 179
 180                 out = (memcmp(q, n, nlen) == 0);
 181         }
 182
 183         return out;
 184 }
 185
 186
 187 /*
 188  * returns true, if query matches node using common prefix
 189  */
 190 static bool
 191 gbt_var_node_pf_match(const GBT_VARKEY_R *node, const bytea *query, const gbtree_vinfo *tinfo)
 192 {
 193         return (tinfo->trnc &&
 194                         (gbt_bytea_pf_match(node->lower, query, tinfo) ||
 195                          gbt_bytea_pf_match(node->upper, query, tinfo)));
 196 }
 197
 198
 199 /*
 200 *  truncates / compresses the node key
 201 *  cpf_length .. common prefix length
 202 */
 203 static GBT_VARKEY *
 204 gbt_var_node_truncate(const GBT_VARKEY *node, int32 cpf_length, const gbtree_vinfo *tinfo)
 205 {
 206         GBT_VARKEY *out = NULL;
 207         GBT_VARKEY_R r = gbt_var_key_readable(node);
 208         int32           len1 = VARSIZE(r.lower) - VARHDRSZ;
 209         int32           len2 = VARSIZE(r.upper) - VARHDRSZ;
 210         int32           si;
 211         char       *out2;
 212
 213         len1 = Min(len1, (cpf_length + 1));
 214         len2 = Min(len2, (cpf_length + 1));
 215
 216         si = 2 * VARHDRSZ + INTALIGN(len1 + VARHDRSZ) + len2;
 217         out = (GBT_VARKEY *) palloc0(si);
 218         SET_VARSIZE(out, si);
 219
 220         memcpy(VARDATA(out), r.lower, len1 + VARHDRSZ);
 221         SET_VARSIZE(VARDATA(out), len1 + VARHDRSZ);
 222
 223         out2 = VARDATA(out) + INTALIGN(len1 + VARHDRSZ);
 224         memcpy(out2, r.upper, len2 + VARHDRSZ);
 225         SET_VARSIZE(out2, len2 + VARHDRSZ);
 226
 227         return out;
 228 }
 229
 230
 231
 232 void
 233 gbt_var_bin_union(Datum *u, GBT_VARKEY *e, Oid collation,
 234                                   const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 235 {
 236         GBT_VARKEY_R eo = gbt_var_key_readable(e);
 237         GBT_VARKEY_R nr;
 238
 239         if (eo.lower == eo.upper)       /* leaf */
 240         {
 241                 GBT_VARKEY *tmp;
 242
 243                 tmp = gbt_var_leaf2node(e, tinfo, flinfo);
 244                 if (tmp != e)
 245                         eo = gbt_var_key_readable(tmp);
 246         }
 247
 248         if (DatumGetPointer(*u))
 249         {
 250                 GBT_VARKEY_R ro = gbt_var_key_readable((GBT_VARKEY *) DatumGetPointer(*u));
 251                 bool            update = false;
 252
 253                 nr.lower = ro.lower;
 254                 nr.upper = ro.upper;
 255
 256                 if (tinfo->f_cmp(ro.lower, eo.lower, collation, flinfo) > 0)
 257                 {
 258                         nr.lower = eo.lower;
 259                         update = true;
 260                 }
 261
 262                 if (tinfo->f_cmp(ro.upper, eo.upper, collation, flinfo) < 0)
 263                 {
 264                         nr.upper = eo.upper;
 265                         update = true;
 266                 }
 267
 268                 if (update)
 269                         *u = PointerGetDatum(gbt_var_key_copy(&nr));
 270         }
 271         else
 272         {
 273                 nr.lower = eo.lower;
 274                 nr.upper = eo.upper;
 275                 *u = PointerGetDatum(gbt_var_key_copy(&nr));
 276         }
 277 }
 278
 279
 280 GISTENTRY *
 281 gbt_var_compress(GISTENTRY *entry, const gbtree_vinfo *tinfo)
 282 {
 283         GISTENTRY  *retval;
 284
 285         if (entry->leafkey)
 286         {
 287                 struct varlena *leaf = PG_DETOAST_DATUM(entry->key);
 288                 GBT_VARKEY *r;
 289
 290                 r = gbt_var_key_from_datum(leaf);
 291
 292                 retval = palloc(sizeof(GISTENTRY));
 293                 gistentryinit(*retval, PointerGetDatum(r),
 294                                           entry->rel, entry->page,
 295                                           entry->offset, true);
 296         }
 297         else
 298                 retval = entry;
 299
 300         return retval;
 301 }
 302
 303
 304 Datum
 305 gbt_var_fetch(PG_FUNCTION_ARGS)
 306 {
 307         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 308         GBT_VARKEY *key = (GBT_VARKEY *) PG_DETOAST_DATUM(entry->key);
 309         GBT_VARKEY_R r = gbt_var_key_readable(key);
 310         GISTENTRY  *retval;
 311
 312         retval = palloc(sizeof(GISTENTRY));
 313         gistentryinit(*retval, PointerGetDatum(r.lower),
 314                                   entry->rel, entry->page,
 315                                   entry->offset, true);
 316
 317         PG_RETURN_POINTER(retval);
 318 }
 319
 320
 321 GBT_VARKEY *
 322 gbt_var_union(const GistEntryVector *entryvec, int32 *size, Oid collation,
 323                           const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 324 {
 325         int                     i = 0,
 326                                 numranges = entryvec->n;
 327         GBT_VARKEY *cur;
 328         Datum           out;
 329         GBT_VARKEY_R rk;
 330
 331         *size = sizeof(GBT_VARKEY);
 332
 333         cur = (GBT_VARKEY *) DatumGetPointer(entryvec->vector[0].key);
 334         rk = gbt_var_key_readable(cur);
 335         out = PointerGetDatum(gbt_var_key_copy(&rk));
 336
 337         for (i = 1; i < numranges; i++)
 338         {
 339                 cur = (GBT_VARKEY *) DatumGetPointer(entryvec->vector[i].key);
 340                 gbt_var_bin_union(&out, cur, collation, tinfo, flinfo);
 341         }
 342
 343
 344         /* Truncate (=compress) key */
 345         if (tinfo->trnc)
 346         {
 347                 int32           plen;
 348                 GBT_VARKEY *trc = NULL;
 349
 350                 plen = gbt_var_node_cp_len((GBT_VARKEY *) DatumGetPointer(out), tinfo);
 351                 trc = gbt_var_node_truncate((GBT_VARKEY *) DatumGetPointer(out), plen + 1, tinfo);
 352
 353                 out = PointerGetDatum(trc);
 354         }
 355
 356         return ((GBT_VARKEY *) DatumGetPointer(out));
 357 }
 358
 359
 360 bool
 361 gbt_var_same(Datum d1, Datum d2, Oid collation,
 362                          const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 363 {
 364         GBT_VARKEY *t1 = (GBT_VARKEY *) DatumGetPointer(d1);
 365         GBT_VARKEY *t2 = (GBT_VARKEY *) DatumGetPointer(d2);
 366         GBT_VARKEY_R r1,
 367                                 r2;
 368
 369         r1 = gbt_var_key_readable(t1);
 370         r2 = gbt_var_key_readable(t2);
 371
 372         return (tinfo->f_cmp(r1.lower, r2.lower, collation, flinfo) == 0 &&
 373                         tinfo->f_cmp(r1.upper, r2.upper, collation, flinfo) == 0);
 374 }
 375
 376
 377 float *
 378 gbt_var_penalty(float *res, const GISTENTRY *o, const GISTENTRY *n,
 379                                 Oid collation, const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 380 {
 381         GBT_VARKEY *orge = (GBT_VARKEY *) DatumGetPointer(o->key);
 382         GBT_VARKEY *newe = (GBT_VARKEY *) DatumGetPointer(n->key);
 383         GBT_VARKEY_R ok,
 384                                 nk;
 385
 386         *res = 0.0;
 387
 388         nk = gbt_var_key_readable(newe);
 389         if (nk.lower == nk.upper)       /* leaf */
 390         {
 391                 GBT_VARKEY *tmp;
 392
 393                 tmp = gbt_var_leaf2node(newe, tinfo, flinfo);
 394                 if (tmp != newe)
 395                         nk = gbt_var_key_readable(tmp);
 396         }
 397         ok = gbt_var_key_readable(orge);
 398
 399         if ((VARSIZE(ok.lower) - VARHDRSZ) == 0 && (VARSIZE(ok.upper) - VARHDRSZ) == 0)
 400                 *res = 0.0;
 401         else if (!((tinfo->f_cmp(nk.lower, ok.lower, collation, flinfo) >= 0 ||
 402                                 gbt_bytea_pf_match(ok.lower, nk.lower, tinfo)) &&
 403                            (tinfo->f_cmp(nk.upper, ok.upper, collation, flinfo) <= 0 ||
 404                                 gbt_bytea_pf_match(ok.upper, nk.upper, tinfo))))
 405         {
 406                 Datum           d = PointerGetDatum(0);
 407                 double          dres;
 408                 int32           ol,
 409                                         ul;
 410
 411                 gbt_var_bin_union(&d, orge, collation, tinfo, flinfo);
 412                 ol = gbt_var_node_cp_len((GBT_VARKEY *) DatumGetPointer(d), tinfo);
 413                 gbt_var_bin_union(&d, newe, collation, tinfo, flinfo);
 414                 ul = gbt_var_node_cp_len((GBT_VARKEY *) DatumGetPointer(d), tinfo);
 415
 416                 if (ul < ol)
 417                 {
 418                         dres = (ol - ul);       /* reduction of common prefix len */
 419                 }
 420                 else
 421                 {
 422                         GBT_VARKEY_R uk = gbt_var_key_readable((GBT_VARKEY *) DatumGetPointer(d));
 423                         unsigned char tmp[4];
 424
 425                         tmp[0] = (unsigned char) (((VARSIZE(ok.lower) - VARHDRSZ) <= ul) ? 0 : (VARDATA(ok.lower)[ul]));
 426                         tmp[1] = (unsigned char) (((VARSIZE(uk.lower) - VARHDRSZ) <= ul) ? 0 : (VARDATA(uk.lower)[ul]));
 427                         tmp[2] = (unsigned char) (((VARSIZE(ok.upper) - VARHDRSZ) <= ul) ? 0 : (VARDATA(ok.upper)[ul]));
 428                         tmp[3] = (unsigned char) (((VARSIZE(uk.upper) - VARHDRSZ) <= ul) ? 0 : (VARDATA(uk.upper)[ul]));
 429                         dres = Abs(tmp[0] - tmp[1]) + Abs(tmp[3] - tmp[2]);
 430                         dres /= 256.0;
 431                 }
 432
 433                 *res += FLT_MIN;
 434                 *res += (float) (dres / ((double) (ol + 1)));
 435                 *res *= (FLT_MAX / (o->rel->rd_att->natts + 1));
 436         }
 437
 438         return res;
 439 }
 440
 441
 442 static int
 443 gbt_vsrt_cmp(const void *a, const void *b, void *arg)
 444 {
 445         GBT_VARKEY_R ar = gbt_var_key_readable(((const Vsrt *) a)->t);
 446         GBT_VARKEY_R br = gbt_var_key_readable(((const Vsrt *) b)->t);
 447         const gbt_vsrt_arg *varg = (const gbt_vsrt_arg *) arg;
 448         int                     res;
 449
 450         res = varg->tinfo->f_cmp(ar.lower, br.lower, varg->collation, varg->flinfo);
 451         if (res == 0)
 452                 return varg->tinfo->f_cmp(ar.upper, br.upper, varg->collation, varg->flinfo);
 453
 454         return res;
 455 }
 456
 457 GIST_SPLITVEC *
 458 gbt_var_picksplit(const GistEntryVector *entryvec, GIST_SPLITVEC *v,
 459                                   Oid collation, const gbtree_vinfo *tinfo, FmgrInfo *flinfo)
 460 {
 461         OffsetNumber i,
 462                                 maxoff = entryvec->n - 1;
 463         Vsrt       *arr;
 464         int                     svcntr = 0,
 465                                 nbytes;
 466         char       *cur;
 467         GBT_VARKEY **sv = NULL;
 468         gbt_vsrt_arg varg;
 469
 470         arr = (Vsrt *) palloc((maxoff + 1) * sizeof(Vsrt));
 471         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 472         v->spl_left = (OffsetNumber *) palloc(nbytes);
 473         v->spl_right = (OffsetNumber *) palloc(nbytes);
 474         v->spl_ldatum = PointerGetDatum(0);
 475         v->spl_rdatum = PointerGetDatum(0);
 476         v->spl_nleft = 0;
 477         v->spl_nright = 0;
 478
 479         sv = palloc(sizeof(bytea *) * (maxoff + 1));
 480
 481         /* Sort entries */
 482
 483         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 484         {
 485                 GBT_VARKEY_R ro;
 486
 487                 cur = (char *) DatumGetPointer(entryvec->vector[i].key);
 488                 ro = gbt_var_key_readable((GBT_VARKEY *) cur);
 489                 if (ro.lower == ro.upper)       /* leaf */
 490                 {
 491                         sv[svcntr] = gbt_var_leaf2node((GBT_VARKEY *) cur, tinfo, flinfo);
 492                         arr[i].t = sv[svcntr];
 493                         if (sv[svcntr] != (GBT_VARKEY *) cur)
 494                                 svcntr++;
 495                 }
 496                 else
 497                         arr[i].t = (GBT_VARKEY *) cur;
 498                 arr[i].i = i;
 499         }
 500
 501         /* sort */
 502         varg.tinfo = tinfo;
 503         varg.collation = collation;
 504         varg.flinfo = flinfo;
 505         qsort_arg((void *) &arr[FirstOffsetNumber],
 506                           maxoff - FirstOffsetNumber + 1,
 507                           sizeof(Vsrt),
 508                           gbt_vsrt_cmp,
 509                           (void *) &varg);
 510
 511         /* We do simply create two parts */
 512
 513         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 514         {
 515                 if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
 516                 {
 517                         gbt_var_bin_union(&v->spl_ldatum, arr[i].t, collation, tinfo, flinfo);
 518                         v->spl_left[v->spl_nleft] = arr[i].i;
 519                         v->spl_nleft++;
 520                 }
 521                 else
 522                 {
 523                         gbt_var_bin_union(&v->spl_rdatum, arr[i].t, collation, tinfo, flinfo);
 524                         v->spl_right[v->spl_nright] = arr[i].i;
 525                         v->spl_nright++;
 526                 }
 527         }
 528
 529         /* Truncate (=compress) key */
 530         if (tinfo->trnc)
 531         {
 532                 int32           ll = gbt_var_node_cp_len((GBT_VARKEY *) DatumGetPointer(v->spl_ldatum), tinfo);
 533                 int32           lr = gbt_var_node_cp_len((GBT_VARKEY *) DatumGetPointer(v->spl_rdatum), tinfo);
 534                 GBT_VARKEY *dl;
 535                 GBT_VARKEY *dr;
 536
 537                 ll = Max(ll, lr);
 538                 ll++;
 539
 540                 dl = gbt_var_node_truncate((GBT_VARKEY *) DatumGetPointer(v->spl_ldatum), ll, tinfo);
 541                 dr = gbt_var_node_truncate((GBT_VARKEY *) DatumGetPointer(v->spl_rdatum), ll, tinfo);
 542                 v->spl_ldatum = PointerGetDatum(dl);
 543                 v->spl_rdatum = PointerGetDatum(dr);
 544         }
 545
 546         return v;
 547 }
 548
 549
 550 /*
 551  * The GiST consistent method
 552  */
 553 bool
 554 gbt_var_consistent(GBT_VARKEY_R *key,
 555                                    const void *query,
 556                                    StrategyNumber strategy,
 557                                    Oid collation,
 558                                    bool is_leaf,
 559                                    const gbtree_vinfo *tinfo,
 560                                    FmgrInfo *flinfo)
 561 {
 562         bool            retval = false;
 563
 564         switch (strategy)
 565         {
 566                 case BTLessEqualStrategyNumber:
 567                         if (is_leaf)
 568                                 retval = tinfo->f_ge(query, key->lower, collation, flinfo);
 569                         else
 570                                 retval = tinfo->f_cmp(query, key->lower, collation, flinfo) >= 0
 571                                         || gbt_var_node_pf_match(key, query, tinfo);
 572                         break;
 573                 case BTLessStrategyNumber:
 574                         if (is_leaf)
 575                                 retval = tinfo->f_gt(query, key->lower, collation, flinfo);
 576                         else
 577                                 retval = tinfo->f_cmp(query, key->lower, collation, flinfo) >= 0
 578                                         || gbt_var_node_pf_match(key, query, tinfo);
 579                         break;
 580                 case BTEqualStrategyNumber:
 581                         if (is_leaf)
 582                                 retval = tinfo->f_eq(query, key->lower, collation, flinfo);
 583                         else
 584                                 retval =
 585                                         (tinfo->f_cmp(key->lower, query, collation, flinfo) <= 0 &&
 586                                          tinfo->f_cmp(query, key->upper, collation, flinfo) <= 0) ||
 587                                         gbt_var_node_pf_match(key, query, tinfo);
 588                         break;
 589                 case BTGreaterStrategyNumber:
 590                         if (is_leaf)
 591                                 retval = tinfo->f_lt(query, key->upper, collation, flinfo);
 592                         else
 593                                 retval = tinfo->f_cmp(query, key->upper, collation, flinfo) <= 0
 594                                         || gbt_var_node_pf_match(key, query, tinfo);
 595                         break;
 596                 case BTGreaterEqualStrategyNumber:
 597                         if (is_leaf)
 598                                 retval = tinfo->f_le(query, key->upper, collation, flinfo);
 599                         else
 600                                 retval = tinfo->f_cmp(query, key->upper, collation, flinfo) <= 0
 601                                         || gbt_var_node_pf_match(key, query, tinfo);
 602                         break;
 603                 case BtreeGistNotEqualStrategyNumber:
 604                         retval = !(tinfo->f_eq(query, key->lower, collation, flinfo) &&
 605                                            tinfo->f_eq(query, key->upper, collation, flinfo));
 606                         break;
 607                 default:
 608                         retval = false;
 609         }
 610
 611         return retval;
 612 }