# dklibs 1.23.1

- Overview
- Download
- Installation
- Installation from source on Windows systems
- Usage
- FAQ
- Change log
- Other projects
- Tutorial
- Developer docu
- stc
- tracecc and trana
- tracecc GUI
- tracecc PDF man.
- API: sort and search
- API: Generic I/O
- Preferences
- File search
- Font configuration
- LaTeX encodings
- Security

## API: sort and search

- Overview
- Example
- Example program usage
- Example program code

### Overview

Sorting and searching uses containers of ``dk_storage_t'' and container iterators of type ``dk_storage_iterator_t''.
After creating a container by calling dksto_open() assign a an evaluation function or a comparison function to it before you insert object pointers.
An additional criteria can be used in evaluation or comparison functions to decide how to evaluate/compare.

### Example

#### Example program usage

The stotest.c program stores information about persons:

- surname
- name
- age

The program reads input line by line, each input line is a command. The following commands can be used:

- add surname name age
  adds a new record for a person.
- del f name
  removes the record(s) for the given name.
- del s surname
  removes the record(s) for the given surname.
- del a age
  removes the record(s) for the given age.
- read filename
  reads an input file containing further commands.
- print
  prints the contents of all storages from the current record until the end of the storage. The current record is the record previously found by find or the first record in the storage.
- tree
  prints the tree structure of the container.
- find f name
  searches for a record matching the specified name. The matching record (if any) and all following records are printed.
- find s surname
  searches for a record matching the specified surname. The matching record (if any) and all following records are printed.
- find a age
  searches for a record matching the specified age. The matching record (if any) and all following records are printed.
- quit
  exits the application.

Input to the program might look like:

    add	Erwin	Unsinn		30
    add	David	Zeppelin	40
    add	Johann	Unfug		50
    add	Alter	Sack		99
    add	Bla	Blubb		33
    print
    find	a	40
    find	a	45
    del	s	Johann
    print
    tree
    quit

Output produced by this input might look like:

    Sorted by family name:
    Bla Blubb 33

    Alter Sack 99

    Johann Unfug 50

    Erwin Unsinn 30

    David Zeppelin 40

    Sorted by surname:
    Alter Sack 99

    Bla Blubb 33

    David Zeppelin 40

    Erwin Unsinn 30

    Johann Unfug 50

    Sorted by age:
    Erwin Unsinn 30

    Bla Blubb 33

    David Zeppelin 40

    Johann Unfug 50

    Alter Sack 99

    Unsorted:
    Bla Blubb 33

    Alter Sack 99

    Johann Unfug 50

    David Zeppelin 40

    Erwin Unsinn 30

    David Zeppelin 40

    Followers:
    Johann Unfug 50

    Alter Sack 99

    Followers:
    Johann Unfug 50

    Alter Sack 99

    Sorted by family name:
    Bla Blubb 33

    Alter Sack 99

    Erwin Unsinn 30

    David Zeppelin 40

    Sorted by surname:
    Alter Sack 99

    Bla Blubb 33

    David Zeppelin 40

    Erwin Unsinn 30

    Sorted by age:
    Erwin Unsinn 30

    Bla Blubb 33

    David Zeppelin 40

    Alter Sack 99

    Unsorted:
    Bla Blubb 33

    Alter Sack 99

    David Zeppelin 40

    Erwin Unsinn 30

    Sorted by family name:
    +     0 (3) Erwin  Unsinn  30 	parent:
      l     1 (3) Alter  Sack  99 	parent: Erwin Unsinn  30
        l     2 (0) Bla  Blubb  33 	parent: Alter Sack  99
      r     1 (0) David  Zeppelin  40 	parent: Erwin Unsinn  30
    Sorted by surname:
    +     0 (1) Bla  Blubb  33 	parent:
      l     1 (0) Alter  Sack  99 	parent: Bla Blubb  33
      r     1 (3) Erwin  Unsinn  30 	parent: Bla Blubb  33
        l     2 (0) David  Zeppelin  40 	parent: Erwin Unsinn  30
    Sorted by age:
    +     0 (3) David  Zeppelin  40 	parent:
      l     1 (1) Erwin  Unsinn  30 	parent: David Zeppelin  40
        r     2 (0) Bla  Blubb  33 	parent: Erwin Unsinn  30
      r     1 (0) Alter  Sack  99 	parent: David Zeppelin  40
    Unsorted:

#### Example program code

- At the beginning of the program code we have the copyright notice.

      /*
      Copyright (c) 2000-2008, Dirk Krause
      All rights reserved.

      Redistribution and use in source and binary forms,
      with or without modification, are permitted provided
      that the following conditions are met:

      * Redistributions of source code must retain the above
        copyright notice, this list of conditions and the
        following disclaimer.
      * Redistributions in binary form must reproduce the above
        opyright notice, this list of conditions and the following
        disclaimer in the documentation and/or other materials
        provided with the distribution.
      * Neither the name of the Dirk Krause nor the names of
        its contributors may be used to endorse or promote
        products derived from this software without specific
        prior written permission.

      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
      CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
      INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
      MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
      DISCLAIMED.
      IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
      EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
      LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
      LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
      HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
      OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
      SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
      DAMAGE.
      */

      /* Test and demo program for storage containers */

- We need to include some header files.

- The ``Person'' struct describes one person.

      typedef struct {
        char *famname;	/**> Family name */
        char *surname;	/**> Surname */
        unsigned long age;	/**> Age in years */
      } Person;

- We have several storages, containing pointers/references to the records sorted by different criteria.

      /*Sorted by family name. */
      static dk_storage_t *s1;

      /*Sorted by surname. */
      static dk_storage_t *s2;

      /* Sorted by age. */
      static dk_storage_t *s3;

      /* Unsorted. */
      static dk_storage_t *s4;

- To traverse the storages (retrieve record pointers) we need storage iterators.

      static dk_storage_iterator_t *i1, *i2, *i3, *i4;

- The can_continue flag is set as long as there is no reason yet to exit the application (end of input or any error).

      static int can_continue;

- The stdin_is_tty variable is set to a non-zero value if we retrieve input from standard input.

      static int stdin_is_tty = 1;

- Declaration of the read_file() function defined later. This function is used to read an input file.

      static void read_file(FILE *);

- The age_fct() function evaluates a struct ``Person'' or an unsigned long data (a pointer to the data is passed to the function).
  If cr is 1 the pointer p is a pointer to an unsigned long variable. If cr has any other value p points to a struct ``Person''.
  The function returns an unsigned long value, either the age field of a struct ``Person'' or the contents of the variable.

      unsigned long age_fct(void *p, int cr)
      {
        unsigned long back;
        switch(cr) {
          case 1: {
            back = *((unsigned long *)p);
          } break;
          default: {
            back = ((Person *)p)->age;
          } break;
        }
        return back;
      }

- The compare_fct() function compares either to structs ``Person'' (one against the other) or one struct ``Person'' against a text. This function is used both when inserting records into a storage and when searching for a specific record.
  When inserting a record the new record is compared against records already containted in the storage. When searching for a specific record the family name field or surname field of the record is compared against a given text (specified as argument to the dksto_it_find_like() function).

  cr | p1 | p2 | Comparison
  0 | pointer to struct Person | pointer to struct Person | by family name
  1 | pointer to struct Person | pointer to text | family name compared against text
  2 | pointer to struct Person | pointer to struct Person | by surname
  3 | pointer to struct Person | pointer to text | surname compared against text

  The function returns a positive value if the left pointer is larger. The function returns a negative value if the left pointer is smaller. The function returns 0 to indicate equal texts.

      int compare_fct(void *p1, void *p2, int cr)
      {
        int back = 0;
        switch(cr) {
          case 0: {
            back = strcmp(((Person *)p1)->famname, ((Person *)p2)->famname);
          } break;
          case 1: {
            back = strcmp(((Person *)p1)->famname, (char *)p2);
          } break;
          case 2: {
            back = strcmp(((Person *)p1)->surname, ((Person *)p2)->surname);
          } break;
          case 3: {
            back = strcmp(((Person *)p1)->surname, (char *)p2);
          } break;
        }
        return back;
      }

- The print_prompt() function prints a prompt.

      static void print_prompt(void)
      {
        if(stdin_is_tty) {
          printf("\nstotest: ");
        }
      }

- The print_person() function prints one record to a file.

      static void print_person(Person *pers, FILE *fout)
      {
        fprintf(
          fout,
          "%s %s %lu\n",
          ((pers->surname) ? pers->surname : "-"),
          ((pers->famname) ? pers->famname : "-"),
          pers->age
        );
      }

- The print_it() function prints all records from an iterators current position until the end of the container to a file.

      static void print_it(dk_storage_iterator_t *i, FILE *fout)
      {
        void *p;
        dksto_it_reset(i);
        while((p = dksto_it_next(i)) != NULL) {
          print_person((Person *)p, fout);
          fprintf(fout, "\n");
        }
      }

- The print_node() function prints a storage tree node and the subtree to a file.
  This function is used here to show the tree structure.
  In you applications you should not access the internal members of a dk_storage_t or dk_storage_node_t directly.

      void print_node(dk_storage_node_t *n, int num, FILE *f, char c)
      {
        int i;
        Person *pers;
        if(n) {
          for(i = 0; i > num; i++) {
            fprintf(f, "  ");
          }
          fprintf(f, "%c %5d (%d)", c, num, n->b);
          pers = (Person *)(n->o);
          if(pers) {
            if(pers->surname) fprintf(f, " %s ", pers->surname);
            else fprintf(f, " - ");
            if(pers->famname) fprintf(f, " %s ", pers->famname);
            else fprintf(f, " - ");
            fprintf(f, " %lu", pers->age);
          }
          fprintf(f, " \tparent:");
          if(n->p) {
            if((n->p)->o) {
      	pers = (Person *)((n->p)->o);
      	if(pers->surname) fprintf(f, " %s ", pers->surname);
      	else fprintf(f, " - ");
      	if(pers->famname) fprintf(f, "%s ", pers->famname);
      	else fprintf(f, "- ");
      	fprintf(f, " %lu", pers->age);
            }
          }
          fprintf(f, "\n");
          print_node(n->l, (num+1), f, 'l');
          print_node(n->r, (num+1), f, 'r');
        }
      }

- The print_tree() function shows the tree structure used in a container. In your applications you should not access the internal members of a dk_storage_t or dk_storage_node_t structure directly.

      void print_tree(dk_storage_t *s, FILE *f)
      {
        if((s->h) && (s->t)) {
          print_node(s->r, 0, f, '+');
        }
      }

- The free_person() function releases the memory used by a struct Person.

      static void free_person(Person *pers)
      {
        char *cptr;
        if(pers) {
          cptr = pers->famname;
          if(cptr) { dkmem_free(cptr); }
          cptr = pers->surname;
          if(cptr) { dkmem_free(cptr); }
          pers->famname = pers->surname = NULL;
          dkmem_free(pers);
        }
      }

- The handle_cmd_1() function handles commands without arguments.

      static
      void
      handle_cmd_1(char *str)
      {
        if(strcasecmp(str, "quit") == 0) {
          can_continue = 0;
        }
        if(strcasecmp(str, "print") == 0) {
          fprintf(stdout, "Sorted by family name:\n");
          print_it(i1, stdout);
          fprintf(stdout, "Sorted by surname:\n");
          print_it(i2, stdout);
          fprintf(stdout, "Sorted by age:\n");
          print_it(i3, stdout);
          fprintf(stdout, "Unsorted:\n");
          print_it(i4, stdout);
        }
        if(strcasecmp(str, "tree") == 0) {
          fprintf(stdout, "Sorted by family name:\n");
          print_tree(s1, stdout);
          fprintf(stdout, "Sorted by surname:\n");
          print_tree(s2, stdout);
          fprintf(stdout, "Sorted by age:\n");
          print_tree(s3, stdout);
          fprintf(stdout, "Unsorted:\n");
          print_tree(s4, stdout);
        }
      }

- The handle_cmd_2() function handles commands with one argument.

      static void handle_cmd_2(char *cmd, char *arg1)
      {
        if(strcasecmp(cmd, "read") == 0) {
          FILE *in;
          in = fopen(arg1, "r");
          if(in) {
            read_file(in);
            fclose(in);
          }
        }
      }

- The handle_cmd_3() function handles commands with 2 arguments.

      static void handle_cmd_3(char *cmd, char *arg1, char *arg2)
      {
        void *p;
        if(strcasecmp(cmd, "find") == 0) {
          if(strcasecmp(arg1, "f") == 0) {
            p = dksto_it_find_like(i1, arg2, 1);
            if(p) {
      	print_person(p,stdout); printf("\n");
            }
            printf("Followers:\n");
            while((p = (Person *)dksto_it_next(i1)) != NULL) {
      	print_person(p,stdout); printf("\n");
            }
          }
          if(strcasecmp(arg1, "s") == 0) {
            p = dksto_it_find_like(i2, arg2, 3);
            if(p) {
      	print_person(p,stdout); printf("\n");
            }
            printf("Followers:\n");
            while((p = (Person *)dksto_it_next(i2)) != NULL) {
      	print_person(p,stdout); printf("\n");
            }
          }
          if(strcasecmp(arg1, "a") == 0) {
            unsigned long age;
            if(sscanf(arg2, "%lu", &age) == 1) {
      	p = dksto_it_find_like(i3, (void *)(&age), 1);
      	if(p) {
      	  print_person(p,stdout); printf("\n");
      	}
      	printf("Followers:\n");
      	while((p = (Person *)dksto_it_next(i3)) != NULL) {
      	  print_person(p,stdout); printf("\n");
      	}
            }
          }
        }
        if(strcasecmp(cmd, "del") == 0) {
          if(strcasecmp(arg1, "f") == 0) {
            while((p = dksto_it_find_like(i1, arg2, 1)) != NULL) {
      	dksto_remove(s1,p);
      	dksto_remove(s2,p);
      	dksto_remove(s3,p);
      	dksto_remove(s4,p);
      	free_person(p);
            }
          }
          if(strcasecmp(arg1, "s") == 0) {
            while((p = dksto_it_find_like(i2, arg2, 3)) != NULL) {
      	dksto_remove(s1,p);
      	dksto_remove(s2,p);
      	dksto_remove(s3,p);
      	dksto_remove(s4,p);
      	free_person(p);
            }
          }
          if(strcasecmp(arg1, "a") == 0) {
            unsigned long age;
            if(sscanf(arg2, "%lu", &age) == 1) {
      	while((p = dksto_it_find_like(i3, (void *)(&age), 1)) != NULL) {
      	  dksto_remove(s1,p);
      	  dksto_remove(s2,p);
      	  dksto_remove(s3,p);
      	  dksto_remove(s4,p);
      	  free_person(p);
      	}
            }
          }
        }
      }

- The handle_cmd_4() function handles commands with 3 arguments.

      static void handle_cmd_4(char *cmd, char *arg1, char *arg2, char *arg3)
      {
        if(strcasecmp(cmd, "add") == 0) {
          unsigned long age;
          Person *pers;
          if(sscanf(arg3, "%lu", &age) == 1) {
            pers = dk_new(Person,1);
            if(pers) {
      	pers->famname = dkstr_dup(arg2);
      	pers->surname = dkstr_dup(arg1);
      	pers->age = age;
      	if(!((pers->famname) && (pers->surname))) {
      	  free_person(pers);
      	} else {
      	  if(!dksto_add(s4, (void *)pers)) {
      	    free_person(pers);
      	  } else {
      	    dksto_add(s1, (void *)pers);
      	    dksto_add(s2, (void *)pers);
      	    dksto_add(s3, (void *)pers);
      	  }
      	}
            }
          }
        }
      }

- The read_file() function processes an input file.

      void read_file(FILE *in)
      {

        char line[1024];
        char *lbegin;
        int i;
        char str1[sizeof(line)];
        char str2[sizeof(line)];
        char str3[sizeof(line)];
        char str4[sizeof(line)];
        int old_can_continue;
        old_can_continue = can_continue;
        can_continue = 1;
        while(can_continue) {
          if(in == stdin) print_prompt();
          if(fgets(line, sizeof(line), in)) {
            lbegin = dkstr_start(line, NULL);
            if(lbegin) {
              dkstr_chomp(lbegin, NULL);
      	printf("# Processing \"%s\"\n", lbegin);
              i = sscanf(lbegin, "%s %s %s %s", str1, str2, str3, str4);
              switch(i) {
                case 1: {
                  handle_cmd_1(str1);
                } break;
                case 2: {
                  handle_cmd_2(str1, str2);
                } break;
                case 3: {
                  handle_cmd_3(str1, str2, str3);
                } break;
                case 4: {
                  handle_cmd_4(str1, str2, str3, str4);
                } break;
              }
            }
          } else {
      	  can_continue = 0;
          }
        }
        can_continue = old_can_continue;
      }

- The main() function allocates the storages and iterators which are released before exiting the program.
  The read_file() function is called to process standard input.

      int main(int argc, char *argv[])
      {
        void *p; Person *pers; char *cptr;
        /* Check whether or not we are connected to a terminal */
        stdin_is_tty = dksf_echo_test_tty();
        /* Create storage containers */
        s1 = dksto_open(0);
        s2 = dksto_open(0);
        s3 = dksto_open(0);
        s4 = dksto_open(0);
        /* Check whether all containers were created successfully */
        if(s1 && s2 && s3 && s4) {
          /* Set comparison and evaluation functions */
          dksto_set_comp(s1, compare_fct, 0);
          dksto_set_comp(s2, compare_fct, 2);
          dksto_set_eval_ul(s3, age_fct, 0);
          /* Create storage container iterators */
          i1 = dksto_it_open(s1);
          i2 = dksto_it_open(s2);
          i3 = dksto_it_open(s3);
          i4 = dksto_it_open(s4);
          /* Check whether all iterators were created successfully */
          if(i1 && i2 && i3 && i4) {
            /* Process input */
            read_file(stdin);
            /* Release all the records */
            dksto_it_reset(i4);
            while((p = dksto_it_next(i4)) != NULL) {
      	free_person((Person *)p);
            }
          }
        }
        /* Release the iterators */
        if(i1) dksto_it_close(i1);
        if(i2) dksto_it_close(i2);
        if(i3) dksto_it_close(i3);
        if(i4) dksto_it_close(i4);
        /* Release the storage containers */
        if(s1) dksto_close(s1);
        if(s2) dksto_close(s2);
        if(s3) dksto_close(s3);
        if(s4) dksto_close(s4);
        exit(0); return 0;
      }