src/search.c

   1 /*
   2  *  This library is free software; you can redistribute it and/or
   3  *  modify it under the terms of the GNU Lesser General Public
   4  *  License as published by the Free Software Foundation; either
   5  *  version 2 of the License, or (at your option) any later version.
   6  *
   7  *  This library is distributed in the hope that it will be useful,
   8  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  10  *  Lesser General Public License for more details.
  11  *
  12  *  You should have received a copy of the GNU General Public License
  13  *  along with this program; if not, write to the Free Software
  14  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  15  *
  16  *  Copyright (C) 2008 Liam Girdwood
  17  */
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <errno.h>
  22
  23 #include <libastrodb/search.h>
  24 #include <libastrodb/object.h>
  25 #include <libastrodb/adbstdio.h>
  26
  27 #define MAX_PARAMS      128
  28 #define PARAM_OPER      0
  29 #define PARAM_COMP      1
  30 #define OP_OP   1
  31 #define OP_COMP 2
  32
  33 /* comparators (type)_(oper)_comp */
  34 static int int_lt_comp(void *data, void *value)
  35 {
  36         return *(int *) data < *(int *) value;
  37 }
  38 static int int_gt_comp(void *data, void *value)
  39 {
  40         return *(int *) data > *(int *) value;
  41 }
  42 static int int_eq_comp(void *data, void *value)
  43 {
  44         return *(int *) data == *(int *) value;
  45 }
  46 static int int_ne_comp(void *data, void *value)
  47 {
  48         return *(int *) data != *(int *) value;
  49 }
  50 static int float_lt_comp(void *data, void *value)
  51 {
  52         return *(float *) data < *(float *) value;
  53 }
  54 static int float_gt_comp(void *data, void *value)
  55 {
  56         return *(float *) data > *(float *) value;
  57 }
  58 static int float_eq_comp(void *data, void *value)
  59 {
  60         return *(float *) data == *(float *) value;
  61 }
  62 static int float_ne_comp(void *data, void *value)
  63 {
  64         return *(float *) data != *(float *) value;
  65 }
  66 static int double_lt_comp(void *data, void *value)
  67 {
  68         return *(double *) data < *(double *) value;
  69 }
  70 static int double_gt_comp(void *data, void *value)
  71 {
  72         return *(double *) data > *(double *) value;
  73 }
  74 static int double_eq_comp(void *data, void *value)
  75 {
  76         return *(double *) data == *(double *) value;
  77 }
  78 static int double_ne_comp(void *data, void *value)
  79 {
  80         return *(double *) data != *(double *) value;
  81 }
  82 static int string_lt_comp(void *data, void *value)
  83 {
  84         return (strcmp(data, value) > 0);
  85 }
  86 static int string_gt_comp(void *data, void *value)
  87 {
  88         return (strcmp(data, value) < 0);
  89 }
  90 static int string_eq_comp(void *data, void *value)
  91 {
  92         return !strcmp(data, value);
  93 }
  94 static int string_ne_comp(void *data, void *value)
  95 {
  96         return strcmp(data, value);
  97 }
  98 static int string_eq_wildcard_comp(void *data, void *value)
  99 {
 100         int i = 0;
 101         char *ptr = value;
 102
 103         while (*ptr != '*') {
 104                 i++;
 105                 ptr++;
 106         }
 107
 108         return !strncmp(data, value, i);
 109 }
 110
 111 /* comparator list operators */
 112 static int comp_AND(void *object, struct astrodb_slist *slist)
 113 {
 114         if (slist->tail)
 115                 return ((struct search_node *) slist->data)->comp(object +
 116                                 ((struct search_node *) slist->data)->offset,
 117                                 ((struct search_node *) slist->data)->value)
 118                                 && comp_AND(object, slist->tail);
 119         return ((struct search_node *) slist->data)->comp(object +
 120                 ((struct search_node *) slist->data)->offset,
 121                 ((struct search_node *) slist->data)->value);
 122 }
 123
 124 static int comp_OR(void *object, struct astrodb_slist *slist)
 125 {
 126         if (slist->tail)
 127                 return ((struct search_node *) slist->data)->comp(object +
 128                         ((struct search_node *) slist->data)->offset,
 129                         ((struct search_node *) slist->data)->value)
 130                         || comp_OR(object, slist->tail);
 131         return ((struct search_node *) slist->data)->comp(object +
 132                         ((struct search_node *) slist->data)->offset,
 133                         ((struct search_node *) slist->data)->value);
 134 }
 135
 136 /*  node list operators, operate on list of struct search_branch's */
 137 static int node_AND_comp(void *object, struct astrodb_slist * slist)
 138 {
 139         struct search_node *node = (struct search_node *) slist->data;
 140
 141         if (slist->tail)
 142                 return node->comp(object + node->offset, node->value) &&
 143                         node_AND_comp(object, slist->tail);
 144         return node->comp(object + node->offset, node->value);
 145 }
 146
 147 static int node_OR_comp(void *object, struct astrodb_slist * slist)
 148 {
 149         struct search_node *node = (struct search_node *) slist->data;
 150
 151         if (slist->tail)
 152                 return node->comp(object + node->offset, node->value) ||
 153                         node_OR_comp(object, slist->tail);
 154         return node->comp(object + node->offset, node->value);
 155 }
 156
 157 /*  node list operators, operate on list of struct search_branch's */
 158 static int node_AND_oper(void *object, struct astrodb_slist *slist)
 159 {
 160         struct search_branch *node = (struct search_branch *) slist->data;
 161
 162         if (slist->tail)
 163                 return node->oper(object, node->slist) &&
 164                         node_AND_oper(object, slist->tail);
 165         return node->oper(object, node->slist);
 166 }
 167
 168 static int node_OR_oper(void *object, struct astrodb_slist * slist)
 169 {
 170         struct search_branch *node = (struct search_branch *) slist->data;
 171
 172         if (slist->tail)
 173                 return node->oper(object, node->slist) ||
 174                         node_OR_oper(object, slist->tail);
 175         return node->oper(object, node->slist);
 176 }
 177
 178
 179 static comp_ get_comparator(enum astrodb_comparator comp, astrodb_ctype ctype)
 180 {
 181         switch (ctype) {
 182         case CT_INT:
 183                 switch (comp) {
 184                 case ADB_COMP_LT:
 185                         return int_lt_comp;
 186                 case ADB_COMP_GT:
 187                         return int_gt_comp;
 188                 case ADB_COMP_EQ:
 189                         return int_eq_comp;
 190                 case ADB_COMP_NE:
 191                         return int_ne_comp;
 192                 }
 193                 break;
 194         case CT_FLOAT:
 195                 switch (comp) {
 196                 case ADB_COMP_LT:
 197                         return float_lt_comp;
 198                 case ADB_COMP_GT:
 199                         return float_gt_comp;
 200                 case ADB_COMP_EQ:
 201                         return float_eq_comp;
 202                 case ADB_COMP_NE:
 203                         return float_ne_comp;
 204                 }
 205                 break;
 206         case CT_DOUBLE:
 207                 switch (comp) {
 208                 case ADB_COMP_LT:
 209                         return double_lt_comp;
 210                 case ADB_COMP_GT:
 211                         return double_gt_comp;
 212                 case ADB_COMP_EQ:
 213                         return double_eq_comp;
 214                 case ADB_COMP_NE:
 215                         return double_ne_comp;
 216                 }
 217                 break;
 218         case CT_STRING:
 219                 switch (comp) {
 220                 case ADB_COMP_LT:
 221                         return string_lt_comp;
 222                 case ADB_COMP_GT:
 223                         return string_gt_comp;
 224                 case ADB_COMP_EQ:
 225                         return string_eq_comp;
 226                 case ADB_COMP_NE:
 227                         return string_ne_comp;
 228                 }
 229                 break;
 230         case CT_DOUBLE_DMS_DEGS:
 231         case CT_DOUBLE_DMS_MINS:
 232         case CT_DOUBLE_DMS_SECS:
 233         case CT_DOUBLE_HMS_HRS:
 234         case CT_DOUBLE_HMS_MINS:
 235         case CT_DOUBLE_HMS_SECS:
 236         case CT_SIGN:
 237         case CT_NULL:
 238         case CT_DOUBLE_MPC:
 239                 return NULL;
 240         }
 241         return NULL;
 242 }
 243
 244 /*! \fn astrodb_search* astrodb_search_create(astrodb_table *table)
 245  * \param table dataset
 246  * \returns astrodb_search object on success or NULL on failure
 247  *
 248  * Creates an new search object
 249  */
 250 struct astrodb_search *astrodb_search_create(struct astrodb_table *table)
 251 {
 252         struct astrodb_search *srch =
 253                 (struct astrodb_search *)
 254                         calloc(1, sizeof(struct astrodb_search));
 255         if (srch == NULL)
 256                 return NULL;
 257
 258         srch->table = table;
 259         return srch;
 260 }
 261
 262 static void free_orphans(void *data, void *user)
 263 {
 264         struct astrodb_slist *slist = data;
 265
 266         while (slist) {
 267                 struct astrodb_slist *tmp = slist;
 268                 slist = slist->tail;
 269                 free(tmp);
 270         }
 271 }
 272
 273 /*! \fn void astrodb_search_free(astrodb_search* search);
 274  * \param search Search
 275  *
 276  * Free's a search and it resources
 277  */
 278 void astrodb_search_free(struct astrodb_search *search)
 279 {
 280         astrodb_slist_foreach_free(search->free_list, NULL, NULL);
 281         astrodb_slist_foreach_free(search->free_slist, free_orphans, NULL);
 282         free(search);
 283 }
 284
 285 /*! \fn int astrodb_search_add_operator(astrodb_search* search, astrodb_operator op);
 286  * \param search Search
 287  * \param op Operator
 288  * \returns 0 on success
 289  *
 290  * Add a node operation in RPN to the search
 291  */
 292 int astrodb_search_add_operator(struct astrodb_search * search,
 293                                 enum astrodb_operator op)
 294 {
 295         struct search_branch *branch;
 296
 297         branch = calloc(1, sizeof(struct search_branch));
 298         if (branch == NULL)
 299                 return -ENOMEM;
 300
 301         /* cannnot have lone operator */
 302         if (search->root == NULL &&
 303                 search->oper_orphans == NULL &&
 304                 search->comp_orphans == NULL) {
 305                 free(branch);
 306                 return -EINVAL;
 307         }
 308
 309         /* we either have a parent of a comp or op
 310          * or a sibling of an op
 311          *
 312          * comparator parent = comp_orphans != NULL, oper_orphans = NULL
 313          * operator parent = comp_orphans = NULL, oper_orphans != NULL
 314          */
 315
 316         if (search->comp_orphans != NULL) {
 317                 /* comparator parent */
 318                 switch (op) {
 319                 case ADB_OP_AND:
 320                         branch->oper = node_AND_comp;
 321                         break;
 322                 case ADB_OP_OR:
 323                         branch->oper = node_OR_comp;
 324                         break;
 325                 }
 326                 branch->type = OP_COMP;
 327                 branch->slist = search->comp_orphans;
 328                 search->free_slist =
 329                         astrodb_slist_prepend(search->free_slist,
 330                                                 search->comp_orphans);
 331                 search->comp_orphans = NULL;
 332         } else {
 333                 /* operator parent */
 334                 switch (op) {
 335                 case ADB_OP_AND:
 336                         branch->oper = node_AND_oper;
 337                         break;
 338                 case ADB_OP_OR:
 339                         branch->oper = node_OR_oper;
 340                         break;
 341                 }
 342                 branch->slist = search->oper_orphans;
 343                 branch->type = OP_OP;
 344                 search->free_slist =
 345                         astrodb_slist_prepend(search->free_slist,
 346                                                 search->oper_orphans);
 347                 search->oper_orphans = NULL;
 348         }
 349
 350         /* we are an orphan ourselves */
 351         search->oper_orphans =
 352                 astrodb_slist_prepend(search->oper_orphans, branch);
 353         search->free_list = astrodb_slist_prepend(search->free_list, branch);
 354         search->start_oper = branch;
 355         search->num_search_nodes++;
 356
 357         return 0;
 358 }
 359
 360 /*! \fn int astrodb_search_add_comparator(astrodb_search* search, char* field, astrodb_comparator comp, char* value);
 361  * \param search Search
 362  * \param field Field name
 363  * \param comp Comparator
 364  * \param value Compare value
 365  *
 366  * Add a comparator in RPN to the search
 367  */
 368 int astrodb_search_add_comparator(struct astrodb_search *search, char *field,
 369                                 enum astrodb_comparator comp, char *value)
 370 {
 371         astrodb_ctype ctype;
 372         struct search_node *node;
 373         comp_ srch_comp;
 374
 375         ctype = astrodb_table_get_column_type(search->table, field);
 376         srch_comp = get_comparator(comp, ctype);
 377         if (srch_comp == NULL) {
 378                 astrodb_error("failed to object_slist comparator %d for Ctype %d\n",
 379                         comp, ctype);
 380                 return -EINVAL;
 381         }
 382         if (strstr(value, "*"))
 383                 srch_comp = string_eq_wildcard_comp;
 384
 385         node = calloc(1, sizeof(struct search_node));
 386         if (node == NULL)
 387                 return -ENOMEM;
 388
 389         node->offset = astrodb_table_get_column_offset(search->table, field);
 390         node->comp = srch_comp;
 391
 392         switch (ctype) {
 393         case CT_SIGN:
 394         case CT_NULL:
 395         case CT_STRING:
 396         case CT_DOUBLE_MPC:
 397                 node->value = strdup(value);
 398                 break;
 399         case CT_INT:
 400                 node->value = calloc(1, sizeof(int));
 401                 *((int *) node->value) = strtol(value, NULL, 10);
 402                 break;
 403         case CT_FLOAT:
 404                 node->value = calloc(1, sizeof(float));
 405                 *((float *) node->value) = strtod(value, NULL);
 406                 break;
 407         case CT_DOUBLE:
 408         case CT_DOUBLE_DMS_DEGS:
 409         case CT_DOUBLE_DMS_MINS:
 410         case CT_DOUBLE_DMS_SECS:
 411         case CT_DOUBLE_HMS_HRS:
 412         case CT_DOUBLE_HMS_MINS:
 413         case CT_DOUBLE_HMS_SECS:
 414                 node->value = calloc(1, sizeof(double));
 415                 *((double *) node->value) = strtod(value, NULL);
 416                 break;
 417         }
 418         search->comp_orphans =
 419                 astrodb_slist_prepend(search->comp_orphans, node);
 420         search->free_list = astrodb_slist_prepend(search->free_list, node);
 421         search->free_list =
 422                 astrodb_slist_prepend(search->free_list, node->value);
 423         search->num_search_nodes++;
 424         search->start_oper = NULL;
 425
 426         return 0;
 427 }
 428
 429 /*! \fn int astrodb_search_add_custom_comparator(astrodb_search* search, astrodb_custom_comparator comp)
 430  * \param search Search
 431  * \param comp Custom comparator function
 432  * \returns 0 on success
 433  *
 434  * Add a custom search comparator. It should return 1 for a match and 0 for a
 435  * search miss.
 436  */
 437 int astrodb_search_add_custom_comparator(struct astrodb_search *search,
 438                                         astrodb_custom_comparator comp)
 439 {
 440         return -EINVAL;
 441 }
 442
 443 /*! \fn int astrodb_search_get_results(astrodb_search* search, astrodb_progress progress, astrodb_slist **result, unsigned int src)
 444  * \param search Search
 445  * \param progress Progress callback
 446  * \param result Search results
 447  * \param src Object source
 448  *
 449  * Get search results.
 450  */
 451 int astrodb_search_get_results(struct astrodb_search *search,
 452                                 struct astrodb_slist **result,
 453                                 unsigned int src)
 454 {
 455         struct astrodb_slist *object_slist = NULL, *object_slist_;
 456         struct astrodb_slist *res = NULL;
 457         *result = NULL;
 458
 459         if (search->oper_orphans) {
 460                 search->root = search->oper_orphans;
 461                 search->free_slist =
 462                         astrodb_slist_prepend(search->free_slist,
 463                                                         search->oper_orphans);
 464                 search->oper_orphans = NULL;
 465         } else if (search->comp_orphans) {
 466                 astrodb_error("unbalanced search - comp orphans exist\n");
 467                 return -EINVAL;
 468         }
 469
 470         if (search->start_oper == NULL) {
 471                 astrodb_error("unbalanced search - no start oper\n");
 472                 return -EINVAL;
 473         }
 474
 475         /* operator is root */
 476         astrodb_table_get_objects(search->table, &object_slist, src);
 477         object_slist_ = object_slist;
 478         while (object_slist_) {
 479                 struct astrodb_slist *object = object_slist_->data;
 480                 struct astrodb_slist *slist =
 481                         ((struct search_branch *) search->root->data)->slist;
 482
 483                 while (object) {
 484                         if (search->start_oper->oper(object->data, slist)) {
 485                                 search->hits++;
 486                                 res = astrodb_slist_prepend(res, object->data);
 487                         }
 488                         search->tests++;
 489                         object = object->tail;
 490                 }
 491                 object_slist_ = object_slist_->tail;
 492         }
 493
 494
 495         astrodb_table_put_objects(object_slist);
 496         *result = astrodb_slist_prepend(*result, res);
 497         return 0;
 498 }
 499
 500 /*! \fn void astrodb_search_put_results (astrodb_slist *results)
 501  * \param results
 502  *
 503  * Frees search results
 504  */
 505 void astrodb_search_put_results(struct astrodb_slist *results)
 506 {
 507         struct astrodb_slist *slist;
 508
 509         if (results == NULL)
 510                 return;
 511
 512         slist = results->data;
 513
 514         while (slist) {
 515                 struct astrodb_slist *tmp = slist;
 516                 slist = slist->tail;
 517                 free(tmp);
 518         }
 519         free(results);
 520 }
 521
 522 /*! \fn int astrodb_search_get_hits(astrodb_search* search);
 523  * \param search Search
 524  * \returns Hits
 525  *
 526  * Get the number of search hits.
 527  */
 528 int astrodb_search_get_hits(struct astrodb_search *search)
 529 {
 530         return search->hits;
 531 }
 532
 533
 534 /*! \fn int astrodb_search_get_tests(astrodb_search* search);
 535  * \param search Search
 536  * \returns Tests
 537  *
 538  * Get the number of search tests
 539  */
 540 int astrodb_search_get_tests(struct astrodb_search *search)
 541 {
 542         return search->tests;
 543 }