void *xrealloc (void *ptr, size_t bytes)
#endif
{
    void *cp;

	MALLOC_CHECK();
#ifdef _DEBUG
    if (!ptr)
		cp = _malloc_dbg(bytes?bytes:1,_NORMAL_BLOCK,file,line);
	else
		cp = _realloc_dbg(ptr, bytes,_NORMAL_BLOCK,file,line);
#else
    if (!ptr)
		cp = malloc (bytes?bytes:1);
	else
		cp = realloc(ptr, bytes);
#endif

    if (cp == NULL)
    {
		char buf[80];
		sprintf (buf, "out of memory; can not reallocate %lu bytes",
			(unsigned long) bytes);
		error (1, 0, buf);
    }
	MALLOC_CHECK();
    return (cp);
}

list_node *add_list_node(list_node *head, void *pdata, size_t len)
{
    list_node *last_node, *new_node;

    /* create new head */
    if (head->data == NULL)
    {
        head->data = malloc(len);
        MALLOC_CHECK(head->data);
        memcpy(head->data, pdata, len);

        new_node = head;
    }
    else
    {
        last_node = head;
        while (last_node->next)
            last_node = last_node->next;

        new_node = (list_node *) calloc(1, sizeof(list_node));
        MALLOC_CHECK(new_node);
        new_node->data = malloc(len);
        MALLOC_CHECK(new_node->data);
        memcpy(new_node->data, pdata, len);

        /* link in new node */
        last_node->next = new_node;
    }
    
    return new_node;
}

//tries to add an entry into the dictionary
void DAdd(void* data, char* key){
   
   int num = hash(key);
   if (dict->start == NULL){//first element; dictionary empty
      MYASSERT(dict->end == NULL);
      dict->start = dict->end = (DNODE *)NEW(DNODE);
      MALLOC_CHECK(dict->start);
      dict->start->prev = dict->start->next = NULL;
      dict->hash[num] = dict->start;
      dict->start->data = data;
      BZERO(dict->start->key, KEY_LENGTH);
      strncpy(dict->start->key, key, KEY_LENGTH);
   }

   else{
      DNODE *d;
 
      if (dict->hash[num] == NULL){//non-collision case
	 d = NEW(DNODE);
	 dict->hash[num] = d;
	 d->next = NULL;
	 d->prev = dict->end;
	 dict->end->next = d;
	 dict->end = d;
	 BZERO(d->key, KEY_LENGTH);
	 strncpy(d->key, key, KEY_LENGTH);
	 d->data = data;
      }
      else {//collision case
	 int unique = TRUE;
	 DNODE *temp = dict->hash[num];
	 //as long as the hashes are the same, keep going
	 while (hash(temp->key) == num){
	    //check for matches
	    if (strncmp(temp->key, key, MAX_URL_LENGTH) == 0)
	       unique = FALSE;
	    if (temp->next == NULL || unique == FALSE)
	       break;//reached the end or we know it's not unique
	    temp = temp->next;
	 }
	 //only add if we didn't find the url in the list
	 if (unique == TRUE){
	    temp = temp->prev;
	    DNODE *d = NEW(DNODE);
	    MALLOC_CHECK(d);
	    d->next = temp->next;
	    d->prev = temp;
	    if (d->next == NULL)//for the case that hash[num] is at the end
	       dict->end = d;
	    else
	       temp->next->prev = d;
	    temp->next = d;
	    BZERO(d->key, KEY_LENGTH);
	    strncpy(d->key, key, KEY_LENGTH);
	    d->data = data;
	 }
      }
   }
}

// tweaked version of update index to insert an element into the index along with with the frequency
int insertElementIntoIndex(char* word, int documentId, int frequency, INVERTED_INDEX* index) {
	int hashIndex = hash1(word)%MAX_HASH_SLOT;
	// something is in there already
	if ((index->hash[hashIndex]) != NULL) {
		DocumentNode* init;
		init = (index->hash[hashIndex])->page;
		
		if(init->document_id == documentId) {
			init->page_word_frequency = frequency;
			(index->hash[hashIndex])->page = init;
		}
		else {
			DocumentNode* d;
			
			if(index->hash[hashIndex]) {
				int flag = 0;
				
				d = (index->hash[hashIndex])->page;
				while ((d->next) != NULL) {
					d = d->next;
					if(d->document_id == documentId) {
						//we found the same documentId
						d->page_word_frequency = frequency;
						flag = 1;
						break;
					}
				}
				
				if (flag == 0) {
					// documentId not present
					DocumentNode* dd = (DocumentNode*)malloc(sizeof(DocumentNode));
					MALLOC_CHECK(dd);
					dd->next = NULL;
					dd->document_id = documentId;
					dd->page_word_frequency = frequency;
					
					if (d->next == NULL) {
						d->next = dd;
					}
				}
			}
		}
		
		return 1;
	}
	// nothing is in there already
	else {		
		DocumentNode* doc = malloc(sizeof(DocumentNode));
		MALLOC_CHECK(doc);
		doc->document_id = documentId;
		doc->page_word_frequency = frequency;
		doc->next = NULL;
		
		// add element into the index
		IndexAdd(index, (void*)doc, word);
		return 1;	
	}
}

char *
digsyl(int range, int width)
{
	int i,
		base = 1,
		target;
	static char *new_dig = NULL;
	static int last_width = 0;

	if (range <= 0 || width < 0)
		return(NULL);
	
	if (width == 0) 
		{
		base=1;width=1;
		while(base <= range/10)
			{
			width++;
			base *= 10 ;
			}
		} 
	else  
		{
		for (i=0; i < width - 1; i++)
			base *= 10;
		}
	
	if (new_dig == NULL)
		{
		new_dig = (char *)malloc(sizeof(char) * SYL_WIDTH * width + 1);
		MALLOC_CHECK(new_dig);
		last_width = width;
		}
	else
		{
		new_dig[0] = '\0';
		if (last_width < width)
			{
			new_dig = 
				(char *)realloc(new_dig, width * sizeof(char) * SYL_WIDTH + 1);
			MALLOC_CHECK(new_dig);
			last_width = width;
			}
		}

	for (i=0; i < width * SYL_WIDTH; i += SYL_WIDTH)
		{
		target = range - (range % base);
		target /= base;
		strcpy(new_dig + i, digsyllables[target % 10]);
		range -= base * target;
		base /= 10;
		}

	return(new_dig);
}

// TODO: move to util
interp_workspace *new_interp_workspace(int upsample_ratio, interp_stats *stats) {
  interp_workspace *w = (interp_workspace *)malloc(sizeof(interp_workspace));
  MALLOC_CHECK(w);
  w->input = gsl_vector_alloc(NUM_STENCIL_POINTS);
  MALLOC_CHECK(w->input);
  w->output = gsl_vector_alloc((upsample_ratio+1)*(upsample_ratio+1));
  MALLOC_CHECK(w->output);
  w->stats = stats;
  return w;
}

/* Automatically null the pointer after freeing it */
void xfree_s(void **ptr)
{
	MALLOC_CHECK();
	if(*ptr)
	{
		free(*ptr);
		MALLOC_CHECK();
	}
	*ptr=NULL;
}

/*
 * Routine: ProcessNames
 * Purpose: Parse the name vector
 * Algorithm:
 * Data Structures:
 *
 * Params:
 * Returns:
 * Called By:
 * Calls:
 * Assumptions:
 * Side Effects:
 * TODO: None
 */
int
ProcessNames (char *stmt, token_t * tokens)
{
    char *szResult = NULL;
    char *cp;
    int nCount = 0,
        nWordLength = 0;

    /* get the names */
    while ((cp = strtok (NULL, "=( ,);:")) != NULL)
    {
        if (nCount == 0)
        {
            nWordLength = strlen(cp);
            szResult = malloc(nWordLength + 1);
            MALLOC_CHECK(szResult);
            nCount = nWordLength + 1;
            strcpy(szResult, cp);
        }
        else
        {
            nWordLength = strlen(cp);
            szResult = realloc(szResult, nCount + nWordLength + 1);
            strcpy(szResult + nCount, cp);
            nCount += nWordLength + 1;

        }
    }

    pCurrentIndexEntry->dist->names = szResult;
    return (nCount);
}

// Function to write the webpage to a file.
int WriteFile(WebPage *wp, char *path, int pageID) {
	// Declare and initialize a filename variable.
	char *filename = (char *)malloc(20);
    	MALLOC_CHECK(stderr,filename);
    
    	// Write to the filename variable.
	if (sprintf(filename, "%s/%d", path, pageID) == EOF) {
    		printf("There is an error with the directory path.\n");
    		return 0;
    	}
    
    	// Declare and open a filepath with the filename.
    	FILE *fp;
    	fp = fopen(filename, "w+"); // Open a new file by the filename.
	
	// Check that there were no errors opening the file.
   	if (fp == NULL) {
    		printf("Error reading file.\n");
    		return 0;
    	}
    
    	// Write to each file of an html.
    	fprintf(fp, "%s\n%d\n%s", wp->url, wp->depth, wp->html);
    
    	// Cleanup.
	fclose(fp);
	free(filename);
	return 1;
}

//takes in an array of search terms, gets the docID, score, and which list it should be added in
//and passes the information to the function addScoreToList to be added to the list
//
//PSEUDO CODE
//for all searchterms
//    get the docIDs associated with the word and add the score to the list but factor in a WEIGHT
//    if the prev searchterm is not OR
//	 add to list with weight
//    else
//	 add to the list
void processSearchTerms(INVERTED_INDEX* index, char* searchterms) {
    int docID;
    int score;
    char* prevterm = NULL;
    char* currentterm;
    int pos;
    DOCNODE* d;
    while (searchterms != NULL) {
        currentterm = searchterms;
        pos = 0;
        if(isSearchTerm(currentterm) == TRUE) { //if it's a search term, normalize it and search for it
            NormalizeWord(currentterm);
            while((d = getDoc(index, currentterm, &pos)) != NULL) {
                docID = d->doc_id;
                score = d->page_word_freq;
                if(isNotOR(prevterm) == TRUE) { //add with weighteded score because it must be ADD
                    addScoreToList(querylist, TRUE, docID, (score*WEIGHT));
                }
                else//add with regular score
                    addScoreToList(querylist, FALSE, docID, score);
            }
        }
        prevterm = currentterm;
        searchterms = strtok(NULL, " "); //get next searchterm
    }
    if (querylist->start != NULL) {
        slist = NEW(SORTLIST);
        MALLOC_CHECK(slist);
        BZERO(slist, sizeof(SORTLIST));
        sortList(slist, querylist);
        printList(slist);
    }
}

/*
* re-set default output file names 
*/
int
set_files (int i, int pload)
{
	char line[80], *new_name;
	
	if (table & (1 << i))
child_table:
	{
		if (pload != -1)
			sprintf (line, "%s.%d", tdefs[i].name, pload);
		else
		{
			printf ("Enter new destination for %s data: ",
				tdefs[i].name);
			if (fgets (line, sizeof (line), stdin) == NULL)
				return (-1);;
			if ((new_name = strchr (line, '\n')) != NULL)
				*new_name = '\0';
			if (strlen (line) == 0)
				return (0);
		}
		new_name = (char *) malloc (strlen (line) + 1);
		MALLOC_CHECK (new_name);
		strcpy (new_name, line);
		tdefs[i].name = new_name;
		if (tdefs[i].child != NONE)
		{
			i = tdefs[i].child;
			tdefs[i].child = NONE;
			goto child_table;
		}
	}
	
	return (0);
}

long *
permute_dist(distribution *d, long stream)
	{
	static distribution *dist = NULL;
	int i;
	
	if (d != NULL)
		{
		if (d->permute == (long *)NULL)
			{
			d->permute = (long *)malloc(sizeof(long) * (DIST_SIZE(d)));
			MALLOC_CHECK(d->permute);
			for (i=0; i < (DIST_SIZE(d)); i++) 
				*(d->permute + i) = i;
			}
		dist = d;
		return(permute(dist->permute, DIST_SIZE(dist), stream));
		}
	
	
	if (dist != NULL)
		return(permute(NULL, DIST_SIZE(dist), stream));
	else
		INTERNAL_ERROR("Bad call to permute_dist");	
	}

/*
* Routine: MakePermutation(int nSize)
* Purpose: Permute the integers in [1..nSize]
* Algorithm:
* Data Structures:
*
* Params:
* Returns:
* Called By: 
* Calls: 
* Assumptions:
* Side Effects:
* TODO: None
*/
int *
makePermutation(int *nNumberSet, int nSize, int nStream)
{
	int i,
		nTemp,
		nIndex,
		*pInt;

	if (nSize <= 0)
		return(NULL);

	if (!nNumberSet)
	{
		nNumberSet = (int *)malloc(nSize * sizeof(int));
		MALLOC_CHECK(nNumberSet);
		pInt = nNumberSet;
		for (i=0; i < nSize; i++)
			*pInt++ = i;
	}

	for (i=0; i < nSize; i++)
	{
		nIndex = genrand_integer(NULL, DIST_UNIFORM, 0, nSize - 1, 0, nStream);
		nTemp = nNumberSet[i];
		nNumberSet[i] = nNumberSet[nIndex];
		nNumberSet[nIndex] = nTemp;
	}

	return(nNumberSet);
}

//initializes the querylist
void initQueryList() {
    querylist = NEW(QUERYLIST);
    MALLOC_CHECK(querylist);
    BZERO(querylist, sizeof(QUERYLIST));
    querylist->start = querylist->end = NULL;
    for (int i = 0; i < MAX_HASH_SLOT; i++)
        querylist->hash[i] = NULL;
}

int
getopt(int ac, char **av, char *opt)
{
    static char *nextchar = NULL;
    char *cp;
    char hold;

    if (optarg == NULL)
        {
        optarg = (char *)malloc(BUFSIZ);
        MALLOC_CHECK(optarg);
        }

    if (!nextchar || *nextchar == '\0')
        {
        optind++;
        if (optind == ac)
            return(-1);
        nextchar = av[optind];
        if (*nextchar != '-')
            return(-1);
        nextchar +=1;
        }

    if (nextchar && *nextchar == '-')   /* -- termination */
        {
        optind++;
        return(-1);
        }
    else        /* found an option */
        {
        cp = strchr(opt, *nextchar);
        nextchar += 1;
        if (cp == NULL) /* not defined for this run */
            return('?');
        if (*(cp + 1) == ':')   /* option takes an argument */
            {
            if (*nextchar)
                {
                hold = *cp;
                cp = optarg;
                while (*nextchar)
                    *cp++ = *nextchar++;
                *cp = '\0';
                *cp = hold;
                }
            else        /* white space separated, use next arg */
                {
                if (++optind == ac)
                    return('?');
                strcpy(optarg, av[optind]);
                }
            nextchar = NULL;
            }
        return(*cp);
        }
}

// initializes the index
INVERTED_INDEX* InitIndex() {
	INVERTED_INDEX* index = (INVERTED_INDEX*)malloc(sizeof(INVERTED_INDEX));
	MALLOC_CHECK(index);
	index->start = index->end = NULL;
	
	for (int i = 0; i< MAX_HASH_SLOT; i++) {
		index->hash[i] = NULL;
	}
	return index;
}

DocumentNode *DNode(int docID, int freq) {
    DocumentNode *node = (DocumentNode *)calloc(1, sizeof(DocumentNode));
    MALLOC_CHECK(stderr, node);
    
    node->next = NULL;
    node->docID = docID;
    node->freq = freq;
    
    return node;
    
}

// updateIndex takes a word, a document_id, and an index.  It adds the document to the index,
// and the word itself if it's not already contained in the index.  Returns 0 if success, 1 if failure.
int updateIndex(char* word, int document_id, INVERTED_INDEX* in_index)
{
	DocumentNode* docnode;
	WordNode* wordnode;
	DocumentNode* current_doc_node;

	int page_node_exists;

	page_node_exists = 0;

// creates a DocumentNode from the doc_id
	docnode = malloc(sizeof(DocumentNode));
  	MALLOC_CHECK(docnode);
  	docnode->document_id = document_id;
  	docnode->page_word_frequency = 1;
	docnode->next = NULL;

// makes it lower case (necessary for the query system)
	NormalizeWord(word);

	if(addData(in_index, docnode, word))	// if the wordnode already exists
	{
		wordnode = getData(in_index, word);

		if(wordnode != NULL)
		{
			current_doc_node = wordnode->data;

			while(current_doc_node != NULL)
			{
				if((current_doc_node->document_id) == document_id)
				{
					page_node_exists = 1;
					current_doc_node->page_word_frequency = (current_doc_node->page_word_frequency)+1;
					free(docnode);
					break;
				}
				else
					if(current_doc_node->next == NULL)
						break;
					else
						current_doc_node = current_doc_node->next;
			}

			if(!page_node_exists)
			{
				current_doc_node->next = docnode;
			}
		}			
	}

	return 0;
}

//takes in QUERYLIST and adds a QUERYNODE
//to the ANDORLIST if the docID is unique, or updates the score of th QUERYNODE containing
//the docID if the docID already exists in the list
void addScoreToList(QUERYLIST* querylist, int isAND, int docID, int score) {
    char ID[DOCLEN];
    sprintf(ID, "%d", docID);
    int num = hash(ID);

    QUERYNODE* l = querylist->hash[num];
    int addNew = TRUE;
    while(1) {
        if (l == NULL)
            break;
        if (strncmp(ID, l->docID, DOCLEN) == 0) {
            addNew = FALSE;
            break;
        }
        else if (l->next == NULL || hash(l->docID) != num)
            break;
        l = l->next;
    }
    if (addNew == TRUE) {
        QUERYNODE* ll = NEW(QUERYNODE);
        MALLOC_CHECK(ll);
        BZERO(ll, sizeof(QUERYNODE));
        ll->score = score;
        strncpy(ll->docID, ID, DOCLEN);

        if (querylist->start == NULL) { //first node case
            querylist->start = querylist->end = ll;
            ll->next = ll->prev = NULL;
        }
        else if (l != NULL && l->next != NULL) { //this and the next are collision cases
            ll->prev = l;
            ll->next = l->next;
            l->next->prev = ll;
            l->next = ll;
        }
        else if (l != NULL) {
            ll->prev = querylist->end;
            ll->next = NULL;
            querylist->end = ll;
        }
        else { //inserting into new hash slot
            querylist->hash[num] = ll;
            ll->prev = querylist->end;
            ll->next = NULL;
            querylist->end->next = ll;
            querylist->end = ll;
        }
    }
    else
        l->score = score + l->score;
}

bit_array_t *upsample(double **grid, int ny, int nx, double alpha, int M, int upsample_ratio, interp_stats *stats) {
  gsl_matrix *interp = create_interp_matrix(alpha, M, upsample_ratio);
  bit_array_t *upsampled = new_bit_array((ny-1)*upsample_ratio+1, (nx-1)*upsample_ratio+1);
  MALLOC_CHECK(upsampled);
  int r,c,x,y;
  interp_workspace *w = new_interp_workspace(upsample_ratio, stats);
  for (r = 0 ; r < ny - 3 ; r++) {
    for (c = 0 ; c < nx - 3 ; c++) {
      interpolate(grid, upsampled, r, c, ny, nx, upsample_ratio, interp, w);
    }
  }
  free_interp_workspace(w);
  return upsampled;
}