source/lib/ldb/ldb_tdb/ldb_index.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 2 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb tdb backend - indexing
  29  *
  30  *  Description: indexing routines for ldb tdb backend
  31  *
  32  *  Author: Andrew Tridgell
  33  */
  34
  35 #include "includes.h"
  36 #include "ldb/ldb_tdb/ldb_tdb.h"
  37 #include "ldb/include/ldb_parse.h"
  38
  39 struct dn_list {
  40         unsigned int count;
  41         char **dn;
  42 };
  43
  44 /*
  45   free a struct dn_list
  46 */
  47 static void dn_list_free(struct ldb_context *ldb, struct dn_list *list)
  48 {
  49         unsigned int i;
  50         for (i=0;i<list->count;i++) {
  51                 ldb_free(ldb, list->dn[i]);
  52         }
  53         ldb_free(ldb, list->dn);
  54 }
  55
  56 /*
  57   return the dn key to be used for an index
  58   caller frees
  59 */
  60 static char *ldb_dn_key(struct ldb_context *ldb,
  61                         const char *attr, const struct ldb_val *value)
  62 {
  63         char *ret = NULL;
  64
  65         if (ldb_should_b64_encode(value)) {
  66                 char *vstr = ldb_base64_encode(ldb, value->data, value->length);
  67                 if (!vstr) return NULL;
  68                 ldb_asprintf(ldb, &ret, "%s:%s::%s", LTDB_INDEX, attr, vstr);
  69                 ldb_free(ldb, vstr);
  70                 return ret;
  71         }
  72
  73         ldb_asprintf(ldb, &ret, "%s:%s:%s", LTDB_INDEX, attr, (char *)value->data);
  74         return ret;
  75 }
  76
  77 /*
  78   see if a attribute value is in the list of indexed attributes
  79 */
  80 static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
  81                             int *v_idx, const char *key)
  82 {
  83         unsigned int i, j;
  84         for (i=0;i<msg->num_elements;i++) {
  85                 if (ldb_attr_cmp(msg->elements[i].name, key) == 0) {
  86                         const struct ldb_message_element *el =
  87                                 &msg->elements[i];
  88                         for (j=0;j<el->num_values;j++) {
  89                                 if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
  90                                         if (v_idx) {
  91                                                 *v_idx = j;
  92                                         }
  93                                         return i;
  94                                 }
  95                         }
  96                 }
  97         }
  98         return -1;
  99 }
 100
 101 /* used in sorting dn lists */
 102 static int list_cmp(const char **s1, const char **s2)
 103 {
 104         return strcmp(*s1, *s2);
 105 }
 106
 107 /*
 108   return a list of dn's that might match a simple indexed search or
 109  */
 110 static int ltdb_index_dn_simple(struct ldb_context *ldb,
 111                                 struct ldb_parse_tree *tree,
 112                                 const struct ldb_message *index_list,
 113                                 struct dn_list *list)
 114 {
 115         char *dn = NULL;
 116         int ret;
 117         unsigned int i, j;
 118         struct ldb_message msg;
 119
 120         list->count = 0;
 121         list->dn = NULL;
 122
 123         /*
 124           if the value is a wildcard then we can't do a match via indexing
 125         */
 126         if (ltdb_has_wildcard(ldb, tree->u.simple.attr, &tree->u.simple.value)) {
 127                 return -1;
 128         }
 129
 130         /* if the attribute isn't in the list of indexed attributes then
 131            this node needs a full search */
 132         if (ldb_msg_find_idx(index_list, tree->u.simple.attr, NULL, LTDB_IDXATTR) == -1) {
 133                 return -1;
 134         }
 135
 136         /* the attribute is indexed. Pull the list of DNs that match the
 137            search criterion */
 138         dn = ldb_dn_key(ldb, tree->u.simple.attr, &tree->u.simple.value);
 139         if (!dn) return -1;
 140
 141         ret = ltdb_search_dn1(ldb, dn, &msg);
 142         ldb_free(ldb, dn);
 143         if (ret == 0 || ret == -1) {
 144                 return ret;
 145         }
 146
 147         for (i=0;i<msg.num_elements;i++) {
 148                 struct ldb_message_element *el;
 149
 150                 if (strcmp(msg.elements[i].name, LTDB_IDX) != 0) {
 151                         continue;
 152                 }
 153
 154                 el = &msg.elements[i];
 155
 156                 list->dn = ldb_malloc_array_p(ldb, char *, el->num_values);
 157                 if (!list->dn) {
 158                         break;
 159                 }
 160
 161                 for (j=0;j<el->num_values;j++) {
 162                         list->dn[list->count] =
 163                                 ldb_strdup(ldb, (char *)el->values[j].data);
 164                         if (!list->dn[list->count]) {
 165                                 dn_list_free(ldb, list);
 166                                 ltdb_search_dn1_free(ldb, &msg);
 167                                 return -1;
 168                         }
 169                         list->count++;
 170                 }
 171         }
 172
 173         ltdb_search_dn1_free(ldb, &msg);
 174
 175         qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) list_cmp);
 176
 177         return 1;
 178 }
 179
 180
 181 static int list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
 182
 183 /*
 184   return a list of dn's that might match a simple indexed search on
 185   the special objectclass attribute
 186  */
 187 static int ltdb_index_dn_objectclass(struct ldb_context *ldb,
 188                                      struct ldb_parse_tree *tree,
 189                                      const struct ldb_message *index_list,
 190                                      struct dn_list *list)
 191 {
 192         struct ltdb_private *ltdb = ldb->private_data;
 193         unsigned int i;
 194         int ret;
 195         const char *target = tree->u.simple.value.data;
 196
 197         list->count = 0;
 198         list->dn = NULL;
 199
 200         ret = ltdb_index_dn_simple(ldb, tree, index_list, list);
 201
 202         for (i=0;i<ltdb->cache.subclasses.num_elements;i++) {
 203                 struct ldb_message_element *el = &ltdb->cache.subclasses.elements[i];
 204                 if (ldb_attr_cmp(el->name, target) == 0) {
 205                         unsigned int j;
 206                         for (j=0;j<el->num_values;j++) {
 207                                 struct ldb_parse_tree tree2;
 208                                 struct dn_list list2;
 209                                 tree2.operation = LDB_OP_SIMPLE;
 210                                 tree2.u.simple.attr = ldb_strdup(ldb, LTDB_OBJECTCLASS);
 211                                 if (!tree2.u.simple.attr) {
 212                                         return -1;
 213                                 }
 214                                 tree2.u.simple.value = el->values[j];
 215                                 if (ltdb_index_dn_objectclass(ldb, &tree2,
 216                                                               index_list, &list2) == 1) {
 217                                         if (list->count == 0) {
 218                                                 *list = list2;
 219                                                 ret = 1;
 220                                         } else {
 221                                                 list_union(ldb, list, &list2);
 222                                                 dn_list_free(ldb, &list2);
 223                                         }
 224                                 }
 225                                 ldb_free(ldb, tree2.u.simple.attr);
 226                         }
 227                 }
 228         }
 229
 230         return ret;
 231 }
 232
 233 /*
 234   return a list of dn's that might match a leaf indexed search
 235  */
 236 static int ltdb_index_dn_leaf(struct ldb_context *ldb,
 237                               struct ldb_parse_tree *tree,
 238                               const struct ldb_message *index_list,
 239                               struct dn_list *list)
 240 {
 241         if (ldb_attr_cmp(tree->u.simple.attr, LTDB_OBJECTCLASS) == 0) {
 242                 return ltdb_index_dn_objectclass(ldb, tree, index_list, list);
 243         }
 244         return ltdb_index_dn_simple(ldb, tree, index_list, list);
 245 }
 246
 247
 248 /*
 249   list intersection
 250   list = list & list2
 251   relies on the lists being sorted
 252 */
 253 static int list_intersect(struct ldb_context *ldb,
 254                           struct dn_list *list, const struct dn_list *list2)
 255 {
 256         struct dn_list list3;
 257         unsigned int i;
 258
 259         if (list->count == 0 || list2->count == 0) {
 260                 /* 0 & X == 0 */
 261                 dn_list_free(ldb, list);
 262                 return 0;
 263         }
 264
 265         list3.dn = ldb_malloc_array_p(ldb, char *, list->count);
 266         if (!list3.dn) {
 267                 dn_list_free(ldb, list);
 268                 return -1;
 269         }
 270         list3.count = 0;
 271
 272         for (i=0;i<list->count;i++) {
 273                 if (list_find(list->dn[i], list2->dn, list2->count,
 274                               sizeof(char *), (comparison_fn_t)strcmp) != -1) {
 275                         list3.dn[list3.count] = list->dn[i];
 276                         list3.count++;
 277                 } else {
 278                         ldb_free(ldb, list->dn[i]);
 279                 }
 280         }
 281
 282         ldb_free(ldb, list->dn);
 283         list->dn = list3.dn;
 284         list->count = list3.count;
 285
 286         return 0;
 287 }
 288
 289
 290 /*
 291   list union
 292   list = list | list2
 293   relies on the lists being sorted
 294 */
 295 static int list_union(struct ldb_context *ldb,
 296                       struct dn_list *list, const struct dn_list *list2)
 297 {
 298         unsigned int i;
 299         char **d;
 300         unsigned int count = list->count;
 301
 302         if (list->count == 0 && list2->count == 0) {
 303                 /* 0 | 0 == 0 */
 304                 dn_list_free(ldb, list);
 305                 return 0;
 306         }
 307
 308         d = ldb_realloc_p(ldb, list->dn, char *, list->count + list2->count);
 309         if (!d) {
 310                 dn_list_free(ldb, list);
 311                 return -1;
 312         }
 313         list->dn = d;
 314
 315         for (i=0;i<list2->count;i++) {
 316                 if (list_find(list2->dn[i], list->dn, count,
 317                               sizeof(char *), (comparison_fn_t)strcmp) == -1) {
 318                         list->dn[list->count] = ldb_strdup(ldb, list2->dn[i]);
 319                         if (!list->dn[list->count]) {
 320                                 dn_list_free(ldb, list);
 321                                 return -1;
 322                         }
 323                         list->count++;
 324                 }
 325         }
 326
 327         if (list->count != count) {
 328                 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)list_cmp);
 329         }
 330
 331         return 0;
 332 }
 333
 334 static int ltdb_index_dn(struct ldb_context *ldb,
 335                          struct ldb_parse_tree *tree,
 336                          const struct ldb_message *index_list,
 337                          struct dn_list *list);
 338
 339
 340 /*
 341   OR two index results
 342  */
 343 static int ltdb_index_dn_or(struct ldb_context *ldb,
 344                             struct ldb_parse_tree *tree,
 345                             const struct ldb_message *index_list,
 346                             struct dn_list *list)
 347 {
 348         unsigned int i;
 349         int ret;
 350
 351         ret = -1;
 352         list->dn = NULL;
 353         list->count = 0;
 354
 355         for (i=0;i<tree->u.list.num_elements;i++) {
 356                 struct dn_list list2;
 357                 int v;
 358                 v = ltdb_index_dn(ldb, tree->u.list.elements[i], index_list, &list2);
 359
 360                 if (v == 0) {
 361                         /* 0 || X == X */
 362                         if (ret == -1) {
 363                                 ret = 0;
 364                         }
 365                         continue;
 366                 }
 367
 368                 if (v == -1) {
 369                         /* 1 || X == 1 */
 370                         dn_list_free(ldb, list);
 371                         return -1;
 372                 }
 373
 374                 if (ret == -1) {
 375                         ret = 1;
 376                         *list = list2;
 377                 } else {
 378                         if (list_union(ldb, list, &list2) == -1) {
 379                                 dn_list_free(ldb, &list2);
 380                                 return -1;
 381                         }
 382                         dn_list_free(ldb, &list2);
 383                 }
 384         }
 385
 386         if (list->count == 0) {
 387                 dn_list_free(ldb, list);
 388                 return 0;
 389         }
 390
 391         return ret;
 392 }
 393
 394
 395 /*
 396   NOT an index results
 397  */
 398 static int ltdb_index_dn_not(struct ldb_context *ldb,
 399                              struct ldb_parse_tree *tree,
 400                              const struct ldb_message *index_list,
 401                              struct dn_list *list)
 402 {
 403         /* the only way to do an indexed not would be if we could
 404            negate the not via another not or if we knew the total
 405            number of database elements so we could know that the
 406            existing expression covered the whole database.
 407
 408            instead, we just give up, and rely on a full index scan
 409            (unless an outer & manages to reduce the list)
 410         */
 411         return -1;
 412 }
 413
 414 /*
 415   AND two index results
 416  */
 417 static int ltdb_index_dn_and(struct ldb_context *ldb,
 418                              struct ldb_parse_tree *tree,
 419                              const struct ldb_message *index_list,
 420                              struct dn_list *list)
 421 {
 422         unsigned int i;
 423         int ret;
 424
 425         ret = -1;
 426         list->dn = NULL;
 427         list->count = 0;
 428
 429         for (i=0;i<tree->u.list.num_elements;i++) {
 430                 struct dn_list list2;
 431                 int v;
 432                 v = ltdb_index_dn(ldb, tree->u.list.elements[i], index_list, &list2);
 433
 434                 if (v == 0) {
 435                         /* 0 && X == 0 */
 436                         dn_list_free(ldb, list);
 437                         return 0;
 438                 }
 439
 440                 if (v == -1) {
 441                         continue;
 442                 }
 443
 444                 if (ret == -1) {
 445                         ret = 1;
 446                         *list = list2;
 447                 } else {
 448                         if (list_intersect(ldb, list, &list2) == -1) {
 449                                 dn_list_free(ldb, &list2);
 450                                 return -1;
 451                         }
 452                         dn_list_free(ldb, &list2);
 453                 }
 454
 455                 if (list->count == 0) {
 456                         if (list->dn) ldb_free(ldb, list->dn);
 457                         return 0;
 458                 }
 459         }
 460
 461         return ret;
 462 }
 463
 464 /*
 465   return a list of dn's that might match a indexed search or
 466   -1 if an error. return 0 for no matches, or 1 for matches
 467  */
 468 static int ltdb_index_dn(struct ldb_context *ldb,
 469                          struct ldb_parse_tree *tree,
 470                          const struct ldb_message *index_list,
 471                          struct dn_list *list)
 472 {
 473         int ret = -1;
 474
 475         switch (tree->operation) {
 476         case LDB_OP_SIMPLE:
 477                 ret = ltdb_index_dn_leaf(ldb, tree, index_list, list);
 478                 break;
 479
 480         case LDB_OP_AND:
 481                 ret = ltdb_index_dn_and(ldb, tree, index_list, list);
 482                 break;
 483
 484         case LDB_OP_OR:
 485                 ret = ltdb_index_dn_or(ldb, tree, index_list, list);
 486                 break;
 487
 488         case LDB_OP_NOT:
 489                 ret = ltdb_index_dn_not(ldb, tree, index_list, list);
 490                 break;
 491         }
 492
 493         return ret;
 494 }
 495
 496 /*
 497   filter a candidate dn_list from an indexed search into a set of results
 498   extracting just the given attributes
 499 */
 500 static int ldb_index_filter(struct ldb_context *ldb, struct ldb_parse_tree *tree,
 501                             const char *base,
 502                             enum ldb_scope scope,
 503                             const struct dn_list *dn_list,
 504                             const char * const attrs[], struct ldb_message ***res)
 505 {
 506         unsigned int count = 0, i;
 507
 508         for (i=0;i<dn_list->count;i++) {
 509                 struct ldb_message msg;
 510                 int ret;
 511                 ret = ltdb_search_dn1(ldb, dn_list->dn[i], &msg);
 512                 if (ret == 0) {
 513                         /* the record has disappeared? yes, this can happen */
 514                         continue;
 515                 }
 516
 517                 if (ret == -1) {
 518                         /* an internal error */
 519                         return -1;
 520                 }
 521
 522                 if (ldb_message_match(ldb, &msg, tree, base, scope) == 1) {
 523                         ret = ltdb_add_attr_results(ldb, &msg, attrs, &count, res);
 524                 }
 525                 ltdb_search_dn1_free(ldb, &msg);
 526                 if (ret != 0) {
 527                         return -1;
 528                 }
 529         }
 530
 531         return count;
 532 }
 533
 534 /*
 535   search the database with a LDAP-like expression using indexes
 536   returns -1 if an indexed search is not possible, in which
 537   case the caller should call ltdb_search_full()
 538 */
 539 int ltdb_search_indexed(struct ldb_context *ldb,
 540                         const char *base,
 541                         enum ldb_scope scope,
 542                         struct ldb_parse_tree *tree,
 543                         const char * const attrs[], struct ldb_message ***res)
 544 {
 545         struct ltdb_private *ltdb = ldb->private_data;
 546         struct dn_list dn_list;
 547         int ret;
 548
 549         if (ltdb->cache.indexlist.num_elements == 0) {
 550                 /* no index list? must do full search */
 551                 return -1;
 552         }
 553
 554         ret = ltdb_index_dn(ldb, tree, &ltdb->cache.indexlist, &dn_list);
 555
 556         if (ret == 1) {
 557                 /* we've got a candidate list - now filter by the full tree
 558                    and extract the needed attributes */
 559                 ret = ldb_index_filter(ldb, tree, base, scope, &dn_list,
 560                                        attrs, res);
 561                 dn_list_free(ldb, &dn_list);
 562         }
 563
 564         return ret;
 565 }
 566
 567 /*
 568   add a index element where this is the first indexed DN for this value
 569 */
 570 static int ltdb_index_add1_new(struct ldb_context *ldb,
 571                                struct ldb_message *msg,
 572                                struct ldb_message_element *el,
 573                                char *dn)
 574 {
 575         struct ldb_message_element *el2;
 576
 577         /* add another entry */
 578         el2 = ldb_realloc_p(ldb, msg->elements,
 579                             struct ldb_message_element, msg->num_elements+1);
 580         if (!el2) {
 581                 return -1;
 582         }
 583
 584         msg->elements = el2;
 585         msg->elements[msg->num_elements].name = ldb_strdup(ldb, LTDB_IDX);
 586         if (!msg->elements[msg->num_elements].name) {
 587                 return -1;
 588         }
 589         msg->elements[msg->num_elements].num_values = 0;
 590         msg->elements[msg->num_elements].values = ldb_malloc_p(ldb, struct ldb_val);
 591         if (!msg->elements[msg->num_elements].values) {
 592                 return -1;
 593         }
 594         msg->elements[msg->num_elements].values[0].length = strlen(dn);
 595         msg->elements[msg->num_elements].values[0].data = dn;
 596         msg->elements[msg->num_elements].num_values = 1;
 597         msg->num_elements++;
 598
 599         return 0;
 600 }
 601
 602
 603 /*
 604   add a index element where this is not the first indexed DN for this
 605   value
 606 */
 607 static int ltdb_index_add1_add(struct ldb_context *ldb,
 608                                struct ldb_message *msg,
 609                                struct ldb_message_element *el,
 610                                int idx,
 611                                char *dn)
 612 {
 613         struct ldb_val *v2;
 614         unsigned int i;
 615
 616         /* for multi-valued attributes we can end up with repeats */
 617         for (i=0;i<msg->elements[idx].num_values;i++) {
 618                 if (strcmp(dn, msg->elements[idx].values[i].data) == 0) {
 619                         return 0;
 620                 }
 621         }
 622
 623         v2 = ldb_realloc_p(ldb, msg->elements[idx].values,
 624                            struct ldb_val,
 625                            msg->elements[idx].num_values+1);
 626         if (!v2) {
 627                 return -1;
 628         }
 629         msg->elements[idx].values = v2;
 630
 631         msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
 632         msg->elements[idx].values[msg->elements[idx].num_values].data = dn;
 633         msg->elements[idx].num_values++;
 634
 635         return 0;
 636 }
 637
 638 /*
 639   add an index entry for one message element
 640 */
 641 static int ltdb_index_add1(struct ldb_context *ldb, char *dn,
 642                            struct ldb_message_element *el, int v_idx)
 643 {
 644         struct ldb_message msg;
 645         char *dn_key;
 646         int ret, added=0, added_dn=0;
 647         unsigned int i;
 648
 649         dn_key = ldb_dn_key(ldb, el->name, &el->values[v_idx]);
 650         if (!dn_key) {
 651                 return -1;
 652         }
 653
 654         ret = ltdb_search_dn1(ldb, dn_key, &msg);
 655         if (ret == -1) {
 656                 ldb_free(ldb, dn_key);
 657                 return -1;
 658         }
 659
 660         if (ret == 0) {
 661                 added_dn = 1;
 662                 msg.dn = ldb_strdup(ldb, dn_key);
 663                 if (!msg.dn) {
 664                         ldb_free(ldb, dn_key);
 665                         errno = ENOMEM;
 666                         return -1;
 667                 }
 668                 msg.num_elements = 0;
 669                 msg.elements = NULL;
 670                 msg.private_data = NULL;
 671         }
 672
 673         ldb_free(ldb, dn_key);
 674
 675         for (i=0;i<msg.num_elements;i++) {
 676                 if (strcmp(LTDB_IDX, msg.elements[i].name) == 0) {
 677                         break;
 678                 }
 679         }
 680
 681         if (i == msg.num_elements) {
 682                 added = 1;
 683                 ret = ltdb_index_add1_new(ldb, &msg, el, dn);
 684         } else {
 685                 ret = ltdb_index_add1_add(ldb, &msg, el, i, dn);
 686         }
 687
 688         if (ret == 0) {
 689                 ret = ltdb_store(ldb, &msg, TDB_REPLACE);
 690         }
 691
 692         if (added) {
 693                 ldb_free(ldb, msg.elements[i].name);
 694         }
 695         if (added_dn) {
 696                 ldb_free(ldb, msg.dn);
 697         }
 698
 699         ltdb_search_dn1_free(ldb, &msg);
 700
 701         return ret;
 702 }
 703
 704 /*
 705   add the index entries for a new record
 706   return -1 on failure
 707 */
 708 int ltdb_index_add(struct ldb_context *ldb, const struct ldb_message *msg)
 709 {
 710         struct ltdb_private *ltdb = ldb->private_data;
 711         int ret;
 712         unsigned int i, j;
 713
 714         if (ltdb->cache.indexlist.num_elements == 0) {
 715                 /* no indexed fields */
 716                 return 0;
 717         }
 718
 719         for (i=0;i<msg->num_elements;i++) {
 720                 ret = ldb_msg_find_idx(&ltdb->cache.indexlist, msg->elements[i].name,
 721                                        NULL, LTDB_IDXATTR);
 722                 if (ret == -1) {
 723                         continue;
 724                 }
 725                 for (j=0;j<msg->elements[i].num_values;j++) {
 726                         ret = ltdb_index_add1(ldb, msg->dn, &msg->elements[i], j);
 727                         if (ret == -1) {
 728                                 return -1;
 729                         }
 730                 }
 731         }
 732
 733         return 0;
 734 }
 735
 736
 737 /*
 738   delete an index entry for one message element
 739 */
 740 static int ltdb_index_del1(struct ldb_context *ldb, const char *dn,
 741                            struct ldb_message_element *el, int v_idx)
 742 {
 743         struct ldb_message msg;
 744         char *dn_key;
 745         int ret, i;
 746         unsigned int j;
 747
 748         dn_key = ldb_dn_key(ldb, el->name, &el->values[v_idx]);
 749         if (!dn_key) {
 750                 return -1;
 751         }
 752
 753         ret = ltdb_search_dn1(ldb, dn_key, &msg);
 754         if (ret == -1) {
 755                 ldb_free(ldb, dn_key);
 756                 return -1;
 757         }
 758
 759         if (ret == 0) {
 760                 /* it wasn't indexed. Did we have an earlier error? If we did then
 761                    its gone now */
 762                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ERROR: dn_key %s was not indexed\n", dn_key);
 763                 ldb_free(ldb, dn_key);
 764                 return 0;
 765         }
 766
 767         i = ldb_msg_find_idx(&msg, dn, &j, LTDB_IDX);
 768         if (i == -1) {
 769                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ERROR: dn %s not found in %s\n", dn, dn_key);
 770                 /* it ain't there. hmmm */
 771                 ltdb_search_dn1_free(ldb, &msg);
 772                 ldb_free(ldb, dn_key);
 773                 return 0;
 774         }
 775
 776         if (j != msg.elements[i].num_values - 1) {
 777                 memmove(&msg.elements[i].values[j],
 778                         &msg.elements[i].values[j+1],
 779                         (msg.elements[i].num_values-(j+1)) *
 780                         sizeof(msg.elements[i].values[0]));
 781         }
 782         msg.elements[i].num_values--;
 783
 784         if (msg.elements[i].num_values == 0) {
 785                 ret = ltdb_delete_noindex(ldb, dn_key);
 786         } else {
 787                 ret = ltdb_store(ldb, &msg, TDB_REPLACE);
 788         }
 789
 790         ltdb_search_dn1_free(ldb, &msg);
 791         ldb_free(ldb, dn_key);
 792
 793         return ret;
 794 }
 795
 796 /*
 797   delete the index entries for a record
 798   return -1 on failure
 799 */
 800 int ltdb_index_del(struct ldb_context *ldb, const struct ldb_message *msg)
 801 {
 802         struct ltdb_private *ltdb = ldb->private_data;
 803         int ret;
 804         unsigned int i, j;
 805
 806         /* find the list of indexed fields */
 807         if (ltdb->cache.indexlist.num_elements == 0) {
 808                 /* no indexed fields */
 809                 return 0;
 810         }
 811
 812         for (i=0;i<msg->num_elements;i++) {
 813                 ret = ldb_msg_find_idx(&ltdb->cache.indexlist, msg->elements[i].name,
 814                                        NULL, LTDB_IDXATTR);
 815                 if (ret == -1) {
 816                         continue;
 817                 }
 818                 for (j=0;j<msg->elements[i].num_values;j++) {
 819                         ret = ltdb_index_del1(ldb, msg->dn, &msg->elements[i], j);
 820                         if (ret == -1) {
 821                                 return -1;
 822                         }
 823                 }
 824         }
 825
 826         return 0;
 827 }
 828
 829
 830 /*
 831   traversal function that deletes all @INDEX records
 832 */
 833 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
 834 {
 835         const char *dn = "DN=" LTDB_INDEX ":";
 836         if (strncmp(key.dptr, dn, strlen(dn)) == 0) {
 837                 return tdb_delete(tdb, key);
 838         }
 839         return 0;
 840 }
 841
 842 /*
 843   traversal function that adds @INDEX records during a re index
 844 */
 845 static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
 846 {
 847         struct ldb_context *ldb = state;
 848         struct ldb_message msg;
 849         int ret;
 850
 851         if (strncmp(key.dptr, "DN=@", 4) == 0 ||
 852             strncmp(key.dptr, "DN=", 3) != 0) {
 853                 return 0;
 854         }
 855
 856         ret = ltdb_unpack_data(ldb, &data, &msg);
 857         if (ret != 0) {
 858                 return -1;
 859         }
 860
 861         if (!msg.dn) {
 862                 msg.dn = key.dptr+3;
 863         }
 864
 865         ret = ltdb_index_add(ldb, &msg);
 866
 867         ltdb_unpack_data_free(ldb, &msg);
 868
 869         return ret;
 870 }
 871
 872 /*
 873   force a complete reindex of the database
 874 */
 875 int ltdb_reindex(struct ldb_context *ldb)
 876 {
 877         struct ltdb_private *ltdb = ldb->private_data;
 878         int ret;
 879
 880         ltdb_cache_free(ldb);
 881
 882         if (ltdb_cache_load(ldb) != 0) {
 883                 return -1;
 884         }
 885
 886         /* first traverse the database deleting any @INDEX records */
 887         ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
 888         if (ret == -1) {
 889                 errno = EIO;
 890                 return -1;
 891         }
 892
 893         /* now traverse adding any indexes for normal LDB records */
 894         ret = tdb_traverse(ltdb->tdb, re_index, ldb);
 895         if (ret == -1) {
 896                 errno = EIO;
 897                 return -1;
 898         }
 899
 900         return 0;
 901 }