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 int 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         return 0;
 272 }
 273
 274 /*! \fn void astrodb_search_free(astrodb_search* search);
 275  * \param search Search
 276  *
 277  * Free's a search and it resources
 278  */
 279 void astrodb_search_free(struct astrodb_search *search)
 280 {
 281         astrodb_slist_foreach_free(search->free_list, NULL, NULL);
 282         astrodb_slist_foreach_free(search->free_slist, free_orphans, NULL);
 283         free(search);
 284 }
 285
 286 /*! \fn int astrodb_search_add_operator(astrodb_search* search, astrodb_operator op);
 287  * \param search Search
 288  * \param op Operator
 289  * \returns 0 on success
 290  *
 291  * Add a node operation in RPN to the search
 292  */
 293 int astrodb_search_add_operator(struct astrodb_search * search,
 294                                 enum astrodb_operator op)
 295 {
 296         struct search_branch *branch;
 297
 298         branch = calloc(1, sizeof(struct search_branch));
 299         if (branch == NULL)
 300                 return -ENOMEM;
 301
 302         /* cannnot have lone operator */
 303         if (search->root == NULL &&
 304                 search->oper_orphans == NULL &&
 305                 search->comp_orphans == NULL) {
 306                 free(branch);
 307                 return -EINVAL;
 308         }
 309
 310         /* we either have a parent of a comp or op
 311          * or a sibling of an op
 312          *
 313          * comparator parent = comp_orphans != NULL, oper_orphans = NULL
 314          * operator parent = comp_orphans = NULL, oper_orphans != NULL
 315          */
 316
 317         if (search->comp_orphans != NULL) {
 318                 /* comparator parent */
 319                 switch (op) {
 320                 case ADB_OP_AND:
 321                         branch->oper = node_AND_comp;
 322                         break;
 323                 case ADB_OP_OR:
 324                         branch->oper = node_OR_comp;
 325                         break;
 326                 }
 327                 branch->type = OP_COMP;
 328                 branch->slist = search->comp_orphans;
 329                 search->free_slist =
 330                         astrodb_slist_prepend(search->free_slist,
 331                                                 search->comp_orphans);
 332                 search->comp_orphans = NULL;
 333         } else {
 334                 /* operator parent */
 335                 switch (op) {
 336                 case ADB_OP_AND:
 337                         branch->oper = node_AND_oper;
 338                         break;
 339                 case ADB_OP_OR:
 340                         branch->oper = node_OR_oper;
 341                         break;
 342                 }
 343                 branch->slist = search->oper_orphans;
 344                 branch->type = OP_OP;
 345                 search->free_slist =
 346                         astrodb_slist_prepend(search->free_slist,
 347                                                 search->oper_orphans);
 348                 search->oper_orphans = NULL;
 349         }
 350
 351         /* we are an orphan ourselves */
 352         search->oper_orphans =
 353                 astrodb_slist_prepend(search->oper_orphans, branch);
 354         search->free_list = astrodb_slist_prepend(search->free_list, branch);
 355         search->start_oper = branch;
 356         search->num_search_nodes++;
 357
 358         return 0;
 359 }
 360
 361 /*! \fn int astrodb_search_add_comparator(astrodb_search* search, char* field, astrodb_comparator comp, char* value);
 362  * \param search Search
 363  * \param field Field name
 364  * \param comp Comparator
 365  * \param value Compare value
 366  *
 367  * Add a comparator in RPN to the search
 368  */
 369 int astrodb_search_add_comparator(struct astrodb_search *search, char *field,
 370                                 enum astrodb_comparator comp, char *value)
 371 {
 372         astrodb_ctype ctype;
 373         struct search_node *node;
 374         comp_ srch_comp;
 375
 376         ctype = astrodb_table_get_column_type(search->table, field);
 377         srch_comp = get_comparator(comp, ctype);
 378         if (srch_comp == NULL) {
 379                 astrodb_error("failed to object_slist comparator %d for Ctype %d\n",
 380                         comp, ctype);
 381                 return -EINVAL;
 382         }
 383         if (strstr(value, "*"))
 384                 srch_comp = string_eq_wildcard_comp;
 385
 386         node = calloc(1, sizeof(struct search_node));
 387         if (node == NULL)
 388                 return -ENOMEM;
 389
 390         node->offset = astrodb_table_get_column_offset(search->table, field);
 391         node->comp = srch_comp;
 392
 393         switch (ctype) {
 394         case CT_SIGN:
 395         case CT_NULL:
 396         case CT_STRING:
 397         case CT_DOUBLE_MPC:
 398                 node->value = strdup(value);
 399                 break;
 400         case CT_INT:
 401                 node->value = calloc(1, sizeof(int));
 402                 *((int *) node->value) = strtol(value, NULL, 10);
 403                 break;
 404         case CT_FLOAT:
 405                 node->value = calloc(1, sizeof(float));
 406                 *((float *) node->value) = strtod(value, NULL);
 407                 break;
 408         case CT_DOUBLE:
 409         case CT_DOUBLE_DMS_DEGS:
 410         case CT_DOUBLE_DMS_MINS:
 411         case CT_DOUBLE_DMS_SECS:
 412         case CT_DOUBLE_HMS_HRS:
 413         case CT_DOUBLE_HMS_MINS:
 414         case CT_DOUBLE_HMS_SECS:
 415                 node->value = calloc(1, sizeof(double));
 416                 *((double *) node->value) = strtod(value, NULL);
 417                 break;
 418         }
 419         search->comp_orphans =
 420                 astrodb_slist_prepend(search->comp_orphans, node);
 421         search->free_list = astrodb_slist_prepend(search->free_list, node);
 422         search->free_list =
 423                 astrodb_slist_prepend(search->free_list, node->value);
 424         search->num_search_nodes++;
 425         search->start_oper = NULL;
 426
 427         return 0;
 428 }
 429
 430 /*! \fn int astrodb_search_add_custom_comparator(astrodb_search* search, astrodb_custom_comparator comp)
 431  * \param search Search
 432  * \param comp Custom comparator function
 433  * \returns 0 on success
 434  *
 435  * Add a custom search comparator. It should return 1 for a match and 0 for a
 436  * search miss.
 437  */
 438 int astrodb_search_add_custom_comparator(struct astrodb_search *search,
 439                                         astrodb_custom_comparator comp)
 440 {
 441         return -EINVAL;
 442 }
 443
 444 /*! \fn int astrodb_search_get_results(astrodb_search* search, astrodb_progress progress, astrodb_slist **result, unsigned int src)
 445  * \param search Search
 446  * \param progress Progress callback
 447  * \param result Search results
 448  * \param src Object source
 449  *
 450  * Get search results.
 451  */
 452 int astrodb_search_get_results(struct astrodb_search *search,
 453                                 struct astrodb_slist **result,
 454                                 unsigned int src)
 455 {
 456         struct astrodb_slist *object_slist = NULL, *object_slist_;
 457         struct astrodb_slist *res = NULL;
 458         *result = NULL;
 459
 460         if (search->oper_orphans) {
 461                 search->root = search->oper_orphans;
 462                 search->free_slist =
 463                         astrodb_slist_prepend(search->free_slist,
 464                                                         search->oper_orphans);
 465                 search->oper_orphans = NULL;
 466         } else if (search->comp_orphans) {
 467                 astrodb_error("unbalanced search - comp orphans exist\n");
 468                 return -EINVAL;
 469         }
 470
 471         if (search->start_oper == NULL) {
 472                 astrodb_error("unbalanced search - no start oper\n");
 473                 return -EINVAL;
 474         }
 475
 476         /* operator is root */
 477         astrodb_table_get_objects(search->table, &object_slist, src);
 478         object_slist_ = object_slist;
 479         while (object_slist_) {
 480                 struct astrodb_slist *object = object_slist_->data;
 481                 struct astrodb_slist *slist =
 482                         ((struct search_branch *) search->root->data)->slist;
 483
 484                 while (object) {
 485                         if (search->start_oper->oper(object->data, slist)) {
 486                                 search->hits++;
 487                                 res = astrodb_slist_prepend(res, object->data);
 488                         }
 489                         search->tests++;
 490                         object = object->tail;
 491                 }
 492                 object_slist_ = object_slist_->tail;
 493         }
 494
 495
 496         astrodb_table_put_objects(object_slist);
 497         *result = astrodb_slist_prepend(*result, res);
 498         return 0;
 499 }
 500
 501 /*! \fn void astrodb_search_put_results (astrodb_slist *results)
 502  * \param results
 503  *
 504  * Frees search results
 505  */
 506 void astrodb_search_put_results(struct astrodb_slist *results)
 507 {
 508         struct astrodb_slist *slist;
 509
 510         if (results == NULL)
 511                 return;
 512
 513         slist = results->data;
 514
 515         while (slist) {
 516                 struct astrodb_slist *tmp = slist;
 517                 slist = slist->tail;
 518                 free(tmp);
 519         }
 520         free(results);
 521 }
 522
 523 /*! \fn int astrodb_search_get_hits(astrodb_search* search);
 524  * \param search Search
 525  * \returns Hits
 526  *
 527  * Get the number of search hits.
 528  */
 529 int astrodb_search_get_hits(struct astrodb_search *search)
 530 {
 531         return search->hits;
 532 }
 533
 534
 535 /*! \fn int astrodb_search_get_tests(astrodb_search* search);
 536  * \param search Search
 537  * \returns Tests
 538  *
 539  * Get the number of search tests
 540  */
 541 int astrodb_search_get_tests(struct astrodb_search *search)
 542 {
 543         return search->tests;
 544 }