#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