#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <math.h>
#include <string.h>
#include "problem.h"
#include "report.h"
Defines | |
| #define | UNIFORM 1 |
| Uniform distribution of random strings. | |
| #define | WEIGHTED 2 |
| Weighted distribution of random strings (not implemented). | |
Functions | |
| void | construct (int sz) |
| Method to construct the initial search structure to contain 'sz' elements. | |
| void | insert (char *s) |
| Method to insert an integer element into the search structure. | |
| int | search (char *target, int(*cmp)(const char *, const char *)) |
| Method to search for an integer element in the search structure. | |
| int | stringComp (const char *a1, const char *a2) |
| comparator function to use for all searches. | |
| static char * | elt (int size, int k) |
| generate the kth element from s. | |
| static char ** | materializeStrings () |
| Materialize in order the full set of strings in the n = 2^k set. | |
| void | rotate (char *str) |
| Given a string, rotate from the right, rolling over at 254, back to 1. | |
| static void | constructSearchList () |
| Construct search list based on distribution type. | |
| void | prepareInput (int size, int argc, char **argv) |
| Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents. | |
| void | postInputProcessing (long usecs) |
| Report properly formatted for table. | |
| void | execute () |
| Execute by invoking malloc(numElements) a total of numT times. | |
| void | problemUsage () |
| No specific problem usage. | |
Variables | |
| int | verbose |
| Determine whether output is to be printed as the computation progresses. | |
| char ** | searchList |
| information will be stored as pointer of strings. | |
| static int | elementSize = 6 |
| Element size of strings to be used. | |
| static float | p = 0.25 |
| Likelihood that target will be in the collection being searched. | |
| static int | distrib = UNIFORM |
| Distribution method to use (UNIFORM is only supported for now). | |
| static int | first = 0 |
| Should the target always be the first element. | |
| static int | z = 50 |
| Collection Size: default is 50. | |
| static int | numFound = 0 |
| Computed number found. | |
| static char * | firstInserted = 0 |
| Record the first string inserted, to use with -f option. | |
| static char ** | elementsInC |
| Build up a collection of strings known to be in the collection. | |
Build up an array of Strings.
Required Input:
Expected methods
External API
| #define UNIFORM 1 |
Uniform distribution of random strings.
| #define WEIGHTED 2 |
Weighted distribution of random strings (not implemented).
| void construct | ( | int | n | ) |
Method to construct the initial search structure to contain 'sz' elements.
Allocate array of 'n' elements for 'ds'.
| static void constructSearchList | ( | ) | [static] |
Construct search list based on distribution type.
Here n=numElements is equal to z^2 and we intend to fill up the elements of searchList with all elements from ds. Draw the elements themselves from elementsInC.
p can be one of {0.0,0.25,0.5,0.75,1.0} and we deal with accordingly in this method. Note there is no need to be random about anything since we are going to aggregate over all elements in the set C and everyone will eventually be searched for.
the searchlist is randomly shuffled 12*z times to ensure some bit of randomness...
| static char* elt | ( | int | size, | |
| int | k | |||
| ) | [static] |
generate the kth element from s.
| void execute | ( | ) |
Execute by invoking malloc(numElements) a total of numT times.
.numElements
output sum to be sure is correct.
| void insert | ( | char * | s | ) |
Method to insert an integer element into the search structure.
In our case, we insert the elements into a non-balancing tree.
| s | Value to be inserted. |
| static char** materializeStrings | ( | ) | [static] |
Materialize in order the full set of strings in the n = 2^k set.
| void postInputProcessing | ( | long | usecs | ) |
Report properly formatted for table.
| void prepareInput | ( | int | size, | |
| int | argc, | |||
| char ** | argv | |||
| ) |
Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.
use character-swapping algorithm from strfry.c in glibc
http://www.koders.com/c/fidBD83E492934F9F671DE79B11E6AC0277F9887CF5.aspx
| void problemUsage | ( | ) |
No specific problem usage.
| void rotate | ( | char * | str | ) |
Given a string, rotate from the right, rolling over at 254, back to 1.
Ensures that str[0] is never 'a' or 'b'.
| int search | ( | char * | target, | |
| int(*)(const char *, const char *) | cmp | |||
| ) |
Method to search for an integer element in the search structure.
| int stringComp | ( | const char * | a1, | |
| const char * | a2 | |||
| ) |
comparator function to use for all searches.
int distrib = UNIFORM [static] |
Distribution method to use (UNIFORM is only supported for now).
char** elementsInC [static] |
Build up a collection of strings known to be in the collection.
int elementSize = 6 [static] |
Element size of strings to be used.
int first = 0 [static] |
Should the target always be the first element.
char* firstInserted = 0 [static] |
Record the first string inserted, to use with -f option.
int numFound = 0 [static] |
Computed number found.
float p = 0.25 [static] |
Likelihood that target will be in the collection being searched.
| char** searchList |
information will be stored as pointer of strings.
| int verbose |
Determine whether output is to be printed as the computation progresses.
int z = 50 [static] |
Collection Size: default is 50.
Algorithm Development Kit 1.0