bin/tests/rbt_test.c

   1 /*
   2  * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: rbt_test.c,v 1.48 2007/06/19 23:46:59 tbox Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stdlib.h>
  23
  24 #include <isc/commandline.h>
  25 #include <isc/mem.h>
  26 #include <isc/string.h>
  27 #include <isc/util.h>
  28
  29 #include <dns/rbt.h>
  30 #include <dns/fixedname.h>
  31 #include <dns/result.h>
  32
  33 char *progname;
  34 isc_mem_t *mctx;
  35
  36 #define DNSNAMELEN 255
  37
  38 static dns_name_t *
  39 create_name(char *s) {
  40         int length;
  41         isc_result_t result;
  42         isc_buffer_t source, target;
  43         static dns_name_t *name;
  44
  45         if (s == NULL || *s == '\0') {
  46                 printf("missing name argument\n");
  47                 return (NULL);
  48         }
  49
  50         length = strlen(s);
  51
  52         isc_buffer_init(&source, s, length);
  53         isc_buffer_add(&source, length);
  54
  55         /*
  56          * It isn't really necessary in this program to create individual
  57          * memory spaces for each name structure and its associated character
  58          * string.  It is done here to provide a relatively easy way to test
  59          * the callback from dns_rbt_deletename that is supposed to free the
  60          * data associated with a node.
  61          *
  62          * The buffer for the actual name will immediately follow the
  63          * name structure.
  64          */
  65         name = isc_mem_get(mctx, sizeof(*name) + DNSNAMELEN);
  66         if (name == NULL) {
  67                 printf("out of memory!\n");
  68                 return (NULL);
  69         }
  70
  71         dns_name_init(name, NULL);
  72         isc_buffer_init(&target, name + 1, DNSNAMELEN);
  73
  74         result = dns_name_fromtext(name, &source, dns_rootname,
  75                                    ISC_FALSE, &target);
  76
  77         if (result != ISC_R_SUCCESS) {
  78                 printf("dns_name_fromtext(%s) failed: %s\n",
  79                        s, dns_result_totext(result));
  80                 return (NULL);
  81         }
  82
  83         return (name);
  84 }
  85
  86 static void
  87 delete_name(void *data, void *arg) {
  88         dns_name_t *name;
  89
  90         UNUSED(arg);
  91         name = data;
  92         isc_mem_put(mctx, data, sizeof(dns_name_t) + DNSNAMELEN);
  93 }
  94
  95 static void
  96 print_name(dns_name_t *name) {
  97         isc_buffer_t target;
  98         char buffer[1024];
  99
 100         isc_buffer_init(&target, buffer, sizeof(buffer));
 101
 102         /*
 103          * ISC_FALSE means absolute names have the final dot added.
 104          */
 105         dns_name_totext(name, ISC_FALSE, &target);
 106
 107         printf("%.*s", (int)target.used, (char *)target.base);
 108 }
 109
 110 static void
 111 detail(dns_rbt_t *rbt, dns_name_t *name) {
 112         dns_name_t *foundname, *origin, *fullname;
 113         dns_fixedname_t fixedfoundname, fixedorigin, fixedfullname;
 114         dns_rbtnode_t *node1, *node2;
 115         dns_rbtnodechain_t chain;
 116         isc_result_t result;
 117         isc_boolean_t nodes_should_match = ISC_FALSE;
 118
 119         dns_rbtnodechain_init(&chain, mctx);
 120
 121         dns_fixedname_init(&fixedorigin);
 122         dns_fixedname_init(&fixedfullname);
 123         dns_fixedname_init(&fixedfoundname);
 124
 125         origin = dns_fixedname_name(&fixedorigin);
 126         fullname = dns_fixedname_name(&fixedfullname);
 127         foundname = dns_fixedname_name(&fixedfoundname);
 128
 129         node1 = node2 = NULL;
 130
 131         printf("checking chain information for ");
 132         print_name(name);
 133         printf("\n");
 134
 135         result = dns_rbt_findnode(rbt, name, foundname, &node1, &chain,
 136                                   DNS_RBTFIND_EMPTYDATA, NULL, NULL);
 137
 138         switch (result) {
 139         case ISC_R_SUCCESS:
 140                 printf("  found exact.");
 141                 nodes_should_match = ISC_TRUE;
 142                 break;
 143         case DNS_R_PARTIALMATCH:
 144                 printf("  found parent.");
 145                 break;
 146         case ISC_R_NOTFOUND:
 147                 printf("  name not found.");
 148                 break;
 149         default:
 150                 printf("  unexpected result: %s\n", dns_result_totext(result));
 151                 return;
 152         }
 153
 154         if (node1 != NULL && node1->data != NULL) {
 155                 printf("  data at node: ");
 156                 print_name(node1->data);
 157         } else
 158                 printf("  no data at node.");
 159
 160         if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH) {
 161                 printf("\n  name from dns_rbt_findnode: ");
 162                 print_name(foundname);
 163         }
 164
 165         result = dns_rbtnodechain_current(&chain, foundname, origin, &node2);
 166
 167         if (result == ISC_R_SUCCESS) {
 168                 printf("\n  name from dns_rbtnodechain_current: ");
 169
 170                 result = dns_name_concatenate(foundname, origin,
 171                                               fullname, NULL);
 172                 if (result == ISC_R_SUCCESS)
 173                         print_name(fullname);
 174                 else
 175                         printf("%s\n", dns_result_totext(result));
 176                 printf("\n      (foundname = ");
 177                 print_name(foundname);
 178                 printf(", origin = ");
 179                 print_name(origin);
 180                 printf(")\n");
 181                 if (nodes_should_match && node1 != node2)
 182                         printf("  nodes returned from each function "
 183                                "DO NOT match!\n");
 184
 185         } else
 186                 printf("\n  result from dns_rbtnodechain_current: %s\n",
 187                        dns_result_totext(result));
 188
 189         printf("  level_matches = %d, level_count = %d\n",
 190                chain.level_matches, chain.level_count);
 191 }
 192
 193 static void
 194 iterate(dns_rbt_t *rbt, isc_boolean_t forward) {
 195         dns_name_t foundname, *origin;
 196         dns_rbtnodechain_t chain;
 197         dns_fixedname_t fixedorigin;
 198         isc_result_t result;
 199         isc_result_t (*move)(dns_rbtnodechain_t *chain, dns_name_t *name,
 200                              dns_name_t *origin);
 201
 202         dns_rbtnodechain_init(&chain, mctx);
 203
 204         dns_name_init(&foundname, NULL);
 205         dns_fixedname_init(&fixedorigin);
 206         origin = dns_fixedname_name(&fixedorigin);
 207
 208         if (forward) {
 209                 printf("iterating forward\n" );
 210                 move = dns_rbtnodechain_next;
 211
 212                 result = dns_rbtnodechain_first(&chain, rbt, &foundname,
 213                                                 origin);
 214
 215         } else {
 216                 printf("iterating backward\n" );
 217                 move = dns_rbtnodechain_prev;
 218
 219                 result = dns_rbtnodechain_last(&chain, rbt, &foundname,
 220                                                origin);
 221         }
 222
 223         if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN)
 224                 printf("start not found!\n");
 225
 226         else {
 227                 for (;;) {
 228                         if (result == DNS_R_NEWORIGIN) {
 229                                 printf("  new origin: ");
 230                                 print_name(origin);
 231                                 printf("\n");
 232                         }
 233
 234                         if (result == ISC_R_SUCCESS ||
 235                             result == DNS_R_NEWORIGIN) {
 236                                 print_name(&foundname);
 237                                 printf("\n");
 238
 239                         } else {
 240                                 if (result != ISC_R_NOMORE)
 241                                        printf("UNEXEPCTED ITERATION ERROR: %s",
 242                                               dns_result_totext(result));
 243                                 break;
 244                         }
 245
 246                         result = move(&chain, &foundname, origin);
 247                 }
 248         }
 249 }
 250
 251
 252 #define CMDCHECK(s)     (strncasecmp(command, (s), length) == 0)
 253 #define PRINTERR(r)     if (r != ISC_R_SUCCESS) \
 254                                 printf("... %s\n", dns_result_totext(r));
 255
 256 int
 257 main(int argc, char **argv) {
 258         char *command, *arg, buffer[1024];
 259         const char *whitespace;
 260         dns_name_t *name, *foundname;
 261         dns_fixedname_t fixedname;
 262         dns_rbt_t *rbt = NULL;
 263         int length, ch;
 264         isc_boolean_t show_final_mem = ISC_FALSE;
 265         isc_result_t result;
 266         void *data;
 267
 268         progname = strrchr(*argv, '/');
 269         if (progname != NULL)
 270                 progname++;
 271         else
 272                 progname = *argv;
 273
 274         while ((ch = isc_commandline_parse(argc, argv, "m")) != -1) {
 275                 switch (ch) {
 276                 case 'm':
 277                         show_final_mem = ISC_TRUE;
 278                         break;
 279                 }
 280         }
 281
 282         argc -= isc_commandline_index;
 283         argv += isc_commandline_index;
 284
 285         if (argc > 1) {
 286                 printf("Usage: %s [-m]\n", progname);
 287                 exit(1);
 288         }
 289
 290         setbuf(stdout, NULL);
 291
 292         /*
 293          * So isc_mem_stats() can report any allocation leaks.
 294          */
 295         isc_mem_debugging = ISC_MEM_DEBUGRECORD;
 296
 297         result = isc_mem_create(0, 0, &mctx);
 298         if (result != ISC_R_SUCCESS) {
 299                 printf("isc_mem_create: %s: exiting\n",
 300                        dns_result_totext(result));
 301                 exit(1);
 302         }
 303
 304         result = dns_rbt_create(mctx, delete_name, NULL, &rbt);
 305         if (result != ISC_R_SUCCESS) {
 306                 printf("dns_rbt_create: %s: exiting\n",
 307                        dns_result_totext(result));
 308                 exit(1);
 309         }
 310
 311         whitespace = " \t";
 312
 313         while (fgets(buffer, sizeof(buffer), stdin) != NULL) {
 314                 length = strlen(buffer);
 315
 316                 if (buffer[length - 1] != '\n') {
 317                         printf("line to long (%lu max), ignored\n",
 318                                (unsigned long)sizeof(buffer) - 2);
 319                         continue;
 320                 }
 321
 322                 buffer[length - 1] = '\0';
 323
 324                 command = buffer + strspn(buffer, whitespace);
 325
 326                 if (*command == '#')
 327                         continue;
 328
 329                 arg = strpbrk(command, whitespace);
 330                 if (arg != NULL) {
 331                         *arg++ = '\0';
 332                         arg += strspn(arg, whitespace);
 333                 }
 334
 335                 length = strlen(command);
 336                 if (*command != '\0') {
 337                         if (CMDCHECK("add")) {
 338                                 name = create_name(arg);
 339                                 if (name != NULL) {
 340                                         printf("adding name %s\n", arg);
 341                                         result = dns_rbt_addname(rbt,
 342                                                                  name, name);
 343                                         PRINTERR(result);
 344                                 }
 345
 346                         } else if (CMDCHECK("delete")) {
 347                                 name = create_name(arg);
 348                                 if (name != NULL) {
 349                                         printf("deleting name %s\n", arg);
 350                                         result = dns_rbt_deletename(rbt, name,
 351                                                                     ISC_FALSE);
 352                                         PRINTERR(result);
 353                                         delete_name(name, NULL);
 354                                 }
 355
 356                         } else if (CMDCHECK("nuke")) {
 357                                 name = create_name(arg);
 358                                 if (name != NULL) {
 359                                         printf("nuking name %s "
 360                                                "and its descendants\n", arg);
 361                                         result = dns_rbt_deletename(rbt, name,
 362                                                                     ISC_TRUE);
 363                                         PRINTERR(result);
 364                                         delete_name(name, NULL);
 365                                 }
 366
 367                         } else if (CMDCHECK("search")) {
 368                                 name = create_name(arg);
 369                                 if (name != NULL) {
 370                                         printf("searching for name %s ... ",
 371                                                arg);
 372
 373                                         dns_fixedname_init(&fixedname);
 374                                         foundname =
 375                                                 dns_fixedname_name(&fixedname);
 376                                         data = NULL;
 377
 378                                         result = dns_rbt_findname(rbt, name, 0,
 379                                                                   foundname,
 380                                                                   &data);
 381                                         switch (result) {
 382                                         case ISC_R_SUCCESS:
 383                                                 printf("found exact: ");
 384                                                 print_name(data);
 385                                                 putchar('\n');
 386                                                 break;
 387                                         case DNS_R_PARTIALMATCH:
 388                                                 printf("found parent: ");
 389                                                 print_name(data);
 390                                                 printf("\n\t(foundname: ");
 391                                                 print_name(foundname);
 392                                                 printf(")\n");
 393                                                 break;
 394                                         case ISC_R_NOTFOUND:
 395                                                 printf("NOT FOUND!\n");
 396                                                 break;
 397                                         case ISC_R_NOMEMORY:
 398                                                 printf("OUT OF MEMORY!\n");
 399                                                 break;
 400                                         default:
 401                                                 printf("UNEXPECTED RESULT\n");
 402                                         }
 403
 404                                         delete_name(name, NULL);
 405                                 }
 406
 407                         } else if (CMDCHECK("check")) {
 408                                 /*
 409                                  * Or "chain".  I know, I know.  Lame name.
 410                                  * I was having a hard time thinking of a
 411                                  * name (especially one that did not have
 412                                  * a conflicting first letter with another
 413                                  * command) that would differentiate this
 414                                  * from the search command.
 415                                  *
 416                                  * But it is just a test program, eh?
 417                                  */
 418                                 name = create_name(arg);
 419                                 if (name != NULL) {
 420                                         detail(rbt, name);
 421
 422                                         delete_name(name, NULL);
 423                                 }
 424
 425                         } else if (CMDCHECK("forward")) {
 426                                 iterate(rbt, ISC_TRUE);
 427
 428                         } else if (CMDCHECK("backward")) {
 429                                 iterate(rbt, ISC_FALSE);
 430
 431                         } else if (CMDCHECK("print")) {
 432                                 if (arg == NULL || *arg == '\0')
 433                                         dns_rbt_printall(rbt);
 434                                 else
 435                                         printf("usage: print\n");
 436
 437                         } else if (CMDCHECK("quit")) {
 438                                 if (arg == NULL || *arg == '\0')
 439                                         break;
 440                                 else
 441                                         printf("usage: quit\n");
 442                         } else {
 443                                 printf("a(dd) NAME, d(elete) NAME, "
 444                                        "s(earch) NAME, p(rint), or q(uit)\n");
 445
 446                         }
 447                 }
 448
 449         }
 450
 451         dns_rbt_destroy(&rbt);
 452
 453         if (show_final_mem)
 454                 isc_mem_stats(mctx, stderr);
 455
 456         return (0);
 457 }