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.
The stotest.c program stores information about persons:
The program reads input line by line, each input line is a command. The following commands can be used:
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:
/* 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 */
typedef struct { char *famname; /**> Family name */ char *surname; /**> Surname */ unsigned long age; /**> Age in years */ } Person;
/*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;
static dk_storage_iterator_t *i1, *i2, *i3, *i4;
static int can_continue;
static int stdin_is_tty = 1;
static void read_file(FILE *);
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; }
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 |
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; }
static void print_prompt(void) { if(stdin_is_tty) { printf("\nstotest: "); } }
static void print_person(Person *pers, FILE *fout) { fprintf( fout, "%s %s %lu\n", ((pers->surname) ? pers->surname : "-"), ((pers->famname) ? pers->famname : "-"), pers->age ); }
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"); } }
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'); } }
void print_tree(dk_storage_t *s, FILE *f) { if((s->h) && (s->t)) { print_node(s->r, 0, f, '+'); } }
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); } }
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); } }
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); } } }
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); } } } } }
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); } } } } } }
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; }
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; }