lib/ldb/modules/sort.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce  2005-2008
   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 3 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, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb server side sort control module
  28  *
  29  *  Description: this module sorts the results of a search
  30  *
  31  *  Author: Simo Sorce
  32  */
  33
  34 #include "replace.h"
  35 #include "system/filesys.h"
  36 #include "system/time.h"
  37 #include "ldb_module.h"
  38
  39 struct opaque {
  40         struct ldb_context *ldb;
  41         const struct ldb_attrib_handler *h;
  42         const char *attribute;
  43         int reverse;
  44         int result;
  45 };
  46
  47 struct sort_context {
  48         struct ldb_module *module;
  49
  50         const char *attributeName;
  51         const char *orderingRule;
  52         int reverse;
  53
  54         struct ldb_request *req;
  55         struct ldb_message **msgs;
  56         char **referrals;
  57         unsigned int num_msgs;
  58         unsigned int num_refs;
  59         const char *extra_sort_key;
  60
  61         const struct ldb_schema_attribute *a;
  62         int sort_result;
  63 };
  64
  65 static int build_response(void *mem_ctx, struct ldb_control ***ctrls, int result, const char *desc)
  66 {
  67         struct ldb_control **controls;
  68         struct ldb_sort_resp_control *resp;
  69         unsigned int i;
  70
  71         if (*ctrls) {
  72                 controls = *ctrls;
  73                 for (i = 0; controls[i]; i++);
  74                 controls = talloc_realloc(mem_ctx, controls, struct ldb_control *, i + 2);
  75         } else {
  76                 i = 0;
  77                 controls = talloc_array(mem_ctx, struct ldb_control *, 2);
  78         }
  79         if (! controls )
  80                 return LDB_ERR_OPERATIONS_ERROR;
  81
  82         *ctrls = controls;
  83
  84         controls[i+1] = NULL;
  85         controls[i] = talloc(controls, struct ldb_control);
  86         if (! controls[i] )
  87                 return LDB_ERR_OPERATIONS_ERROR;
  88
  89         controls[i]->oid = LDB_CONTROL_SORT_RESP_OID;
  90         controls[i]->critical = 0;
  91
  92         resp = talloc(controls[i], struct ldb_sort_resp_control);
  93         if (! resp )
  94                 return LDB_ERR_OPERATIONS_ERROR;
  95
  96         resp->result = result;
  97         resp->attr_desc = talloc_strdup(resp, desc);
  98
  99         if (! resp->attr_desc )
 100                 return LDB_ERR_OPERATIONS_ERROR;
 101
 102         controls[i]->data = resp;
 103
 104         return LDB_SUCCESS;
 105 }
 106
 107 static int sort_compare(struct ldb_message **msg1, struct ldb_message **msg2, void *opaque)
 108 {
 109         struct sort_context *ac = talloc_get_type(opaque, struct sort_context);
 110         struct ldb_message_element *el1, *el2;
 111         struct ldb_context *ldb;
 112
 113         ldb = ldb_module_get_ctx(ac->module);
 114
 115         if (ac->sort_result != 0) {
 116                 /* an error occurred previously,
 117                  * let's exit the sorting by returning always 0 */
 118                 return 0;
 119         }
 120
 121         el1 = ldb_msg_find_element(*msg1, ac->attributeName);
 122         el2 = ldb_msg_find_element(*msg2, ac->attributeName);
 123
 124         if (!el1 && el2) {
 125                 return 1;
 126         }
 127         if (el1 && !el2) {
 128                 return -1;
 129         }
 130         if (!el1 && !el2) {
 131                 return 0;
 132         }
 133
 134         if (ac->reverse)
 135                 return ac->a->syntax->comparison_fn(ldb, ac, &el2->values[0], &el1->values[0]);
 136
 137         return ac->a->syntax->comparison_fn(ldb, ac, &el1->values[0], &el2->values[0]);
 138 }
 139
 140 static int server_sort_results(struct sort_context *ac)
 141 {
 142         struct ldb_context *ldb;
 143         struct ldb_reply *ares;
 144         unsigned int i;
 145         int ret;
 146
 147         ldb = ldb_module_get_ctx(ac->module);
 148
 149         ac->a = ldb_schema_attribute_by_name(ldb, ac->attributeName);
 150         ac->sort_result = 0;
 151
 152         LDB_TYPESAFE_QSORT(ac->msgs, ac->num_msgs, ac, sort_compare);
 153
 154         if (ac->sort_result != LDB_SUCCESS) {
 155                 return ac->sort_result;
 156         }
 157
 158         for (i = 0; i < ac->num_msgs; i++) {
 159                 ares = talloc_zero(ac, struct ldb_reply);
 160                 if (!ares) {
 161                         return LDB_ERR_OPERATIONS_ERROR;
 162                 }
 163
 164                 ares->type = LDB_REPLY_ENTRY;
 165                 ares->message = talloc_move(ares, &ac->msgs[i]);
 166                 if (ac->extra_sort_key) {
 167                         ldb_msg_remove_attr(ares->message, ac->extra_sort_key);
 168                 }
 169                 ret = ldb_module_send_entry(ac->req, ares->message, ares->controls);
 170                 if (ret != LDB_SUCCESS) {
 171                         return ret;
 172                 }
 173         }
 174
 175         for (i = 0; i < ac->num_refs; i++) {
 176                 ares = talloc_zero(ac, struct ldb_reply);
 177                 if (!ares) {
 178                         return LDB_ERR_OPERATIONS_ERROR;
 179                 }
 180
 181                 ares->type = LDB_REPLY_REFERRAL;
 182                 ares->referral = talloc_move(ares, &ac->referrals[i]);
 183
 184                 ret = ldb_module_send_referral(ac->req, ares->referral);
 185                 if (ret != LDB_SUCCESS) {
 186                         return ret;
 187                 }
 188         }
 189
 190         return LDB_SUCCESS;
 191 }
 192
 193 static int server_sort_search_callback(struct ldb_request *req, struct ldb_reply *ares)
 194 {
 195         struct sort_context *ac;
 196         struct ldb_context *ldb;
 197         int ret;
 198
 199         ac = talloc_get_type(req->context, struct sort_context);
 200         ldb = ldb_module_get_ctx(ac->module);
 201
 202         if (!ares) {
 203                 return ldb_module_done(ac->req, NULL, NULL,
 204                                         LDB_ERR_OPERATIONS_ERROR);
 205         }
 206         if (ares->error != LDB_SUCCESS) {
 207                 return ldb_module_done(ac->req, ares->controls,
 208                                         ares->response, ares->error);
 209         }
 210
 211         switch (ares->type) {
 212         case LDB_REPLY_ENTRY:
 213                 ac->msgs = talloc_realloc(ac, ac->msgs, struct ldb_message *, ac->num_msgs + 2);
 214                 if (! ac->msgs) {
 215                         talloc_free(ares);
 216                         ldb_oom(ldb);
 217                         return ldb_module_done(ac->req, NULL, NULL,
 218                                                 LDB_ERR_OPERATIONS_ERROR);
 219                 }
 220
 221                 ac->msgs[ac->num_msgs] = talloc_steal(ac->msgs, ares->message);
 222                 ac->num_msgs++;
 223                 ac->msgs[ac->num_msgs] = NULL;
 224
 225                 break;
 226
 227         case LDB_REPLY_REFERRAL:
 228                 ac->referrals = talloc_realloc(ac, ac->referrals, char *, ac->num_refs + 2);
 229                 if (! ac->referrals) {
 230                         talloc_free(ares);
 231                         ldb_oom(ldb);
 232                         return ldb_module_done(ac->req, NULL, NULL,
 233                                                 LDB_ERR_OPERATIONS_ERROR);
 234                 }
 235
 236                 ac->referrals[ac->num_refs] = talloc_steal(ac->referrals, ares->referral);
 237                 ac->num_refs++;
 238                 ac->referrals[ac->num_refs] = NULL;
 239
 240                 break;
 241
 242         case LDB_REPLY_DONE:
 243
 244                 ret = server_sort_results(ac);
 245                 return ldb_module_done(ac->req, ares->controls,
 246                                         ares->response, ret);
 247         }
 248
 249         talloc_free(ares);
 250         return LDB_SUCCESS;
 251 }
 252
 253 static int server_sort_search(struct ldb_module *module, struct ldb_request *req)
 254 {
 255         struct ldb_control *control;
 256         struct ldb_server_sort_control **sort_ctrls;
 257         struct ldb_control **saved_controls;
 258         struct ldb_request *down_req;
 259         struct sort_context *ac;
 260         struct ldb_context *ldb;
 261         int ret;
 262         const char * const *attrs;
 263         size_t n_attrs, i;
 264         const char *sort_attr;
 265
 266         ldb = ldb_module_get_ctx(module);
 267
 268         /* check if there's a server sort control */
 269         control = ldb_request_get_control(req, LDB_CONTROL_SERVER_SORT_OID);
 270         if (control == NULL) {
 271                 /* not found go on */
 272                 return ldb_next_request(module, req);
 273         }
 274
 275         ac = talloc_zero(req, struct sort_context);
 276         if (ac == NULL) {
 277                 ldb_oom(ldb);
 278                 return LDB_ERR_OPERATIONS_ERROR;
 279         }
 280
 281         ac->module = module;
 282         ac->req = req;
 283
 284         sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
 285         if (!sort_ctrls) {
 286                 return LDB_ERR_PROTOCOL_ERROR;
 287         }
 288
 289         /* FIXME: we do not support more than one attribute for sorting right now */
 290         /* FIXME: we need to check if the attribute type exist or return an error */
 291
 292         if (sort_ctrls[1] != NULL) {
 293                 if (control->critical) {
 294                         struct ldb_control **controls = NULL;
 295
 296                         /* callback immediately */
 297                         ret = build_response(req, &controls,
 298                                              LDB_ERR_UNWILLING_TO_PERFORM,
 299                                              "sort control is not complete yet");
 300                         if (ret != LDB_SUCCESS) {
 301                                 return ldb_module_done(req, NULL, NULL,
 302                                                     LDB_ERR_OPERATIONS_ERROR);
 303                         }
 304
 305                         return ldb_module_done(req, controls, NULL, ret);
 306                 } else {
 307                         /* just pass the call down and don't do any sorting */
 308                         return ldb_next_request(module, req);
 309                 }
 310         }
 311
 312         control->critical = 0;
 313
 314         /* We are asked to sort on an attribute, and if that attribute is not
 315            already in the search attributes we need to add it (and later
 316            remove it on the return journey).
 317         */
 318         sort_attr = sort_ctrls[0]->attributeName;
 319         if (req->op.search.attrs == NULL) {
 320                 /* This means all non-operational attributes, which means
 321                    there's nothing to add. */
 322                 attrs = NULL;
 323         } else {
 324                 n_attrs = 0;
 325                 while (req->op.search.attrs[n_attrs] != NULL) {
 326                         if (sort_attr &&
 327                             strcmp(req->op.search.attrs[n_attrs], sort_attr) == 0) {
 328                                 sort_attr = NULL;
 329                         }
 330                         n_attrs++;
 331                 }
 332
 333                 if (sort_attr == NULL) {
 334                         attrs = req->op.search.attrs;
 335                 } else {
 336                         const char **tmp = talloc_array(ac, const char *, n_attrs + 2);
 337
 338                         for (i = 0; i < n_attrs; i++) {
 339                                 tmp[i] = req->op.search.attrs[i];
 340                         }
 341                         ac->extra_sort_key = sort_attr;
 342                         tmp[n_attrs] = sort_attr;
 343                         tmp[n_attrs + 1] = NULL;
 344                         attrs = tmp;
 345                 }
 346         }
 347
 348         ac->attributeName = sort_ctrls[0]->attributeName;
 349         ac->orderingRule = sort_ctrls[0]->orderingRule;
 350         ac->reverse = sort_ctrls[0]->reverse;
 351
 352         ret = ldb_build_search_req_ex(&down_req, ldb, ac,
 353                                         req->op.search.base,
 354                                         req->op.search.scope,
 355                                         req->op.search.tree,
 356                                         attrs,
 357                                         req->controls,
 358                                         ac,
 359                                         server_sort_search_callback,
 360                                         req);
 361         if (ret != LDB_SUCCESS) {
 362                 return ret;
 363         }
 364
 365         /* save it locally and remove it from the list */
 366         /* we do not need to replace them later as we
 367          * are keeping the original req intact */
 368         if (!ldb_save_controls(control, down_req, &saved_controls)) {
 369                 return LDB_ERR_OPERATIONS_ERROR;
 370         }
 371
 372         return ldb_next_request(module, down_req);
 373 }
 374
 375 static int server_sort_init(struct ldb_module *module)
 376 {
 377         struct ldb_context *ldb;
 378         int ret;
 379
 380         ldb = ldb_module_get_ctx(module);
 381
 382         ret = ldb_mod_register_control(module, LDB_CONTROL_SERVER_SORT_OID);
 383         if (ret != LDB_SUCCESS) {
 384                 ldb_debug(ldb, LDB_DEBUG_WARNING,
 385                         "server_sort:"
 386                         "Unable to register control with rootdse!");
 387         }
 388
 389         return ldb_next_init(module);
 390 }
 391
 392 static const struct ldb_module_ops ldb_server_sort_module_ops = {
 393         .name              = "server_sort",
 394         .search            = server_sort_search,
 395         .init_context      = server_sort_init
 396 };
 397
 398 int ldb_server_sort_init(const char *version)
 399 {
 400         LDB_MODULE_CHECK_VERSION(version);
 401         return ldb_register_module(&ldb_server_sort_module_ops);
 402 }