utils.cc

柯老师网站上找到的

      (heap_o_ll + LL_HEAPSIZE - 1)->next = NULL;
   }

   /* Have a workable heap.  Splice off top and return pointer. */
   temp_pointer = heap_o_ll;
   heap_o_ll = heap_o_ll->next;
   temp_pointer->next = NULL;
   return temp_pointer;
}

void Free_ll(ll freeMe)
{
   freeMe->next = heap_o_ll;
   heap_o_ll = freeMe;
}


int ll_build(ll *buildMe, char *buildFromMe)
{
 /* Takes string of form [a, b, c, d, e] and builds linked list with
    elements from the string.  Malloc's space for new linked list element
    strings. */

    char *end, *start, *data, *temp;

    data = (char *) malloc(sizeof(char) * (strlen(buildFromMe)+1));
    if (data == NULL)
    {
      fprintf(stderr, "Out of memory in ll_build!\n");
      return 0;
    }
    strcpy(data, buildFromMe);
    start = end = data + 1;
    
    while ((*end != ']') && (*end != '\0'))
    {
      while (*start == ' ')
      {
        start++;  end++;
      }

      if (*end == ',')
      {
          *end = '\0';
          temp = (char *) (malloc(sizeof(char) * (strlen(start)+1)));
          if (temp == NULL)
          {
             fprintf(stderr, "Out of memory in ll_build!\n");
             return 0;
          }
          strcpy(temp, start);
          ll_add_to_end(buildMe, (void *) temp);
          start = end + 1;
      }
      end++;
    }
    *end = '\0';
    temp = (char *) (malloc(sizeof(char) * (strlen(start)+1)));
    if (temp == NULL)
    {
       fprintf(stderr, "Out of memory in ll_build!\n");
       return 0;
    }
    strcpy(temp, start);
    ll_add_to_end(buildMe, (void *) temp);
    free(data);
    return 1;
}

/****************** Hash table routines *****************/

int chained_hash_create(int num_slots, hash_table *rt)
{
   hash_table  retval;
   hash_el    *sArray;
   int i;

   /* Creating a chained hash table is as simple as allocating room
      for all of the slots. */
   
   sArray = retval.slot_array = (hash_el *) malloc(num_slots*sizeof(hash_el));
   if (retval.slot_array == NULL)
      return -1;

   retval.num_elements = num_slots;
   *rt = retval;

   /* Initialize all slots to have a null entry */
   for (i=0; i<num_slots; i++)
     sArray[i] = NULL;

   return 0;
}

int chained_hash_destroy(hash_table ht, deletor d)
{
   int      i, numEl;
   hash_el *sArray;

   /* Destroying a hash table first implies destroying all of the
      lists in the table, then freeing the table itself. */

   for (i=0, numEl=ht.num_elements, sArray=ht.slot_array; i<numEl; i++)
   {
      if (sArray[i] != NULL)
      {
         /* We must destroy the list in this slot */
         ll_destroy(&(sArray[i]), d);
         sArray[i] = NULL;
      }
   }
   free(sArray);
   return 0;
}

int chained_hash_insert(hash_table ht, void *element, hash_function f)
{
   int  slotnum;
   ll  *slotList;

   slotnum = f(element, ht.num_elements);
   if (! ((slotnum >= 0) && (slotnum < ht.num_elements)) )
     return -1;   /* f is bad */

   slotList = &(ht.slot_array[slotnum]);
   if (ll_add_to_start(slotList, element) != 1)
     return -1;   /* list insert failed */

   return 0;
}

void *chained_hash_search(hash_table ht, void *element, hash_function f,
                          sc_comparator c)
{
   ll   *slotList, foundEl;
   int   slotnum;

#ifdef DEBUG
   printf("chained_hash_search: about to f element, numelements %d\n", ht.num_elements);
#endif

   slotnum = f(element, ht.num_elements);

#ifdef DEBUG
   printf("f() returned slotnum %d\n", slotnum);
#endif

   if (! ((slotnum >= 0) && (slotnum < ht.num_elements)) )
     return NULL;  /* f is bad */

#ifdef DEBUG
   printf("in chs: slotnum %d\n", slotnum);
#endif
   slotList = &(ht.slot_array[slotnum]);
   if (slotList == NULL)
     return NULL;  /* no list, no element */

#ifdef DEBUG
   printf("about to ll_find on slotList.\n");
#endif
   foundEl = ll_find(slotList, element, c);
   if (foundEl == NULL)
     return NULL;
   return foundEl->data;
}

int chained_hash_delete(hash_table ht, void *element, hash_function f,
                          deletor d, sc_comparator c)
{
   ll   *slotList;
   int   slotnum;

   slotnum = f(element, ht.num_elements);
   if (! ((slotnum >= 0) && (slotnum < ht.num_elements)) )
     return 0;  /* f is bad */

   slotList = &(ht.slot_array[slotnum]);
   if (slotList == NULL)
     return 0;  /* no list, no element */

   return ll_del(slotList, element, c, d);
}

/************************************************
 Filename:  AVL_code.c                          *
 DEFINITELY NOT NOT NOT THREAD SAFE             *
 ***********************************************/

#define AVL_ALLOC_NUM 200  /* number of elements to allocate per heap chunk */

/*** global variables ***/

/*** Local function prototypes ***/
AVL_tree Allocate_AVL_tree(void);
void     Free_AVL_tree(AVL_tree freeMe);

/*** Publically accessible functions ***/

int Tree_Add(AVL_tree *addToMe, void *addMe, AVL_comparator theComp)
{
    static int       checkBalance = FALSE;
    static AVL_tree	 parent = NULL;
    AVL_tree        *addTree = addToMe;

    if (*addTree == NULL)  /* Add in a new leaf... */
    {
        *addTree = Allocate_AVL_tree();
        (*addTree)->data = addMe;
        (*addTree)->bal = 0;
        (*addTree)->left = (*addTree)->right = NULL;
        (*addTree)->parent = parent;
        checkBalance = TRUE; /* whether balance should be checked */
        parent = NULL;
        return 0;
    }
    else
        if ( theComp( (*addTree)->data, addMe) > 0 )   // ie. (*addTree)->data > addMe
        {   
            parent = *addTree;
            if ( Tree_Add(&((*addTree)->left), addMe, theComp) != 0 )
            {   checkBalance = FALSE;    return -1;  }
            if (checkBalance == TRUE)  /* CHECK FOR REBALANCING -
                                          LEFT INSERTION */
            {
                switch( (*addTree)->bal) {
                    case 1 :  (*addTree)->bal = 0;
                              checkBalance = FALSE;  return 0;
                    case 0 :  (*addTree)->bal = -1;
                              checkBalance = TRUE;  return 0;
                    case -1:
                    {  AVL_tree p = (*addTree)->left;
                       switch (p->bal) {
                           case -1: {  /* LL ROTATION */
                                AVL_tree q = *addTree;
                                AVL_tree r = p->right;
                                p->parent = q->parent;
                                p->right = q;
                                q->parent = p; q->left = r;
                                if (r != NULL)
                                    r->parent = q;
                                *addTree = p;  (*addTree)->bal = 0;
                                q->bal = 0;  checkBalance = FALSE;
                                return 0;  }
                           case 1: {  /* LR ROTATION */
                                AVL_tree m = *addTree;
                                AVL_tree q = p->right;
                                AVL_tree s = q->left;
                                AVL_tree u = q->right;
                                q->parent = m->parent;
                                m->parent = q;
                                p->parent = q;
                                if (s != NULL)
                                   s->parent = p;
                                if (u != NULL)
                                   u->parent = m;
                                p->right = s;  q->left = p;
                                q->right = m;  m->left = u;
                                *addTree = q;
                                if (q->bal == 0)
                                {
                                   q->bal = 0;
                                   p->bal = 0;
                                   m->bal = 0;
                                }
                                else if (q->bal == -1)
                                {
                                   q->bal = 0;
                                   p->bal = 0;
                                   m->bal = 1;
                                   
                                }
                                else if (q->bal == 1)
                                {
                                   q->bal = 0;
                                   p->bal = -1;
                                   m->bal = 0;
                                }
                                checkBalance = FALSE;  return 0; }
                           default: exit(1);
                     } } }
            }
            else
            {   checkBalance = FALSE;  return 0; }
        }
        else
        if ( theComp( (*addTree)->data, addMe) < 0 ) /* ie. (*addTree)->data < addMe */
        {
            parent = *addTree;
            if ( Tree_Add(&((*addTree)->right), addMe, theComp) != 0 )
            {  checkBalance = FALSE;  return -1; }
            if (checkBalance == TRUE)
            {    /* Check for rebalancing - right insertion */
                switch ( (*addTree)->bal) {
                    case -1:  (*addTree)->bal = 0;
                              checkBalance = FALSE;  return 0;
                    case 0 :  (*addTree)->bal = 1;
                              checkBalance = TRUE;  return 0;
                    case 1 :
                    {  AVL_tree p = (*addTree)->right;
                       switch (p->bal) {
                           case -1: {  /*i RL ROTATION */
                             AVL_tree m = *addTree;
                             AVL_tree q = p->left;
                             AVL_tree r = q->right;
                             AVL_tree s = q->left;
                             q->parent = m->parent;
                             m->parent = q;
                             p->parent = q;
                             if (s != NULL)
                                s->parent = m;
                             if (r != NULL)
                                r->parent = p;
                             m->right = s;  q->left = m;
                             q->right = p;  p->left = r;
                             (*addTree) = q;
                                if (q->bal == 0)
                                {
                                   q->bal = 0;
                                   p->bal = 0;
                                   m->bal = 0;
                                }
                                else if (q->bal == -1)
                                {
                                   q->bal = 0;
                                   p->bal = 1;
                                   m->bal = 0;
                                   
                                }
                                else if (q->bal == 1)
                                {
                                   q->bal = 0;
                                   p->bal = 0;
                                   m->bal = -1;
                                }
                             checkBalance = FALSE;
                             return 0; }
                           case 1: {  /* RR ROTATION */
                             AVL_tree q = (*addTree);
                             AVL_tree r = p->left;
                             p->parent = q->parent;
                             q->parent = p;
                             if (r != NULL)
                                r->parent = q;
                             p->left = q;  q->right = r;
                             (*addTree) = p;  (*addTree)->bal = 0;
                             q->bal = 0;  checkBalance = FALSE;
                             return 0; }
                       }
                    }
                }
            }
            else
            {  checkBalance = FALSE;  return 0; }
        }
        else    /* key already exists - bomb out */
        {  checkBalance = FALSE;  return -1;  }

    return 0;
}

int      Tree_Delete(AVL_tree *deleteFromMe, void *deleteMe,
                     AVL_comparator theComp, AVL_deletor theDel)
{
   /* A simplified version of an AVL_delete algorithm.  This procedure will
      instead do a regular binary tree deletion  */

    AVL_tree         tempTree, tempTreeX, Z;
    static AVL_tree *root = NULL;

    Z = *deleteFromMe;

    if (*deleteFromMe == NULL)  /* hit a leaf.  bomb out */
    {    root = NULL;
         return -1;
    }

    if (root == NULL)
        root = deleteFromMe;

    if ( theComp((*deleteFromMe)->data, deleteMe) > 0 ) /* ie. (*deleteFromMe)->data > deleteMe */
       return Tree_Delete(&((*deleteFromMe)->left), deleteMe, theComp, theDel);
    else
    {
        if ( theComp((*deleteFromMe)->data, deleteMe) < 0) /* ie. (*deleteFromMe)->data < deleteMe */ 
           return Tree_Delete(&((*deleteFromMe)->right), deleteMe, theComp, theDel);
        else
        {
            theDel((*deleteFromMe)->data);   /* Call the deletor function */
            
            /* we've found the node to delete - three cases */
            if (  (((*deleteFromMe)->left) == NULL) ||
                  (((*deleteFromMe)->right) == NULL) )
                tempTree = *deleteFromMe;
            else
                tempTree = Tree_Next(*deleteFromMe);

            if ( tempTree->left != NULL)
                tempTreeX = tempTree->left;
            else
                tempTreeX = tempTree->right;

            if (tempTreeX != NULL)
                tempTreeX->parent = tempTree->parent;

            if (tempTree->parent == NULL)   /* ie root, replace all */
                *root = tempTreeX;
            else
            {
                if ( tempTree == ((tempTree->parent)->left) )
                    ((tempTree->parent)->left) = tempTreeX;
                else
                    ((tempTree->parent)->right) = tempTreeX;
            }

            if (tempTree != Z)
            {
              /* splice successor back in */
              (*deleteFromMe)->data = tempTree->data;
            }

            Free_AVL_tree(tempTree);
            root = NULL;
            return 0;

        }
    }
}

int Tree_Destroy(AVL_tree *destroyMe, AVL_deletor theDel)
{
   if (*destroyMe == NULL)
      return 0;
   
   Tree_Destroy( &((*destroyMe)->left), theDel);
   Tree_Destroy( &((*destroyMe)->right), theDel);
   
   theDel( (*destroyMe)->data );
   Free_AVL_tree(*destroyMe);
   *destroyMe = NULL;
   return 0;
}

AVL_tree Tree_Search(AVL_tree searchMe, void *searchForMe, AVL_comparator theComp)
{
    if (searchMe == NULL)  /* didn't find it! */
       return NULL;

    if (theComp(searchMe->data, searchForMe) > 0 ) /* ie. searchMe->data > searchForMe */
       return Tree_Search(searchMe->left, searchForMe, theComp);

    if (theComp(searchMe->data, searchForMe) < 0 ) /* ie. searchMe->data < searchForMe */
       return Tree_Search(searchMe->right, searchForMe, theComp);

    /* aha! found correct key */
    return searchMe;
}

AVL_tree Tree_First(AVL_tree searchMe)
{
   AVL_tree retTree = searchMe;
   
   if (retTree == NULL)
      return NULL;
   
   while (retTree->left != NULL)
      retTree = retTree->left;
   
   return retTree;
}

AVL_tree Tree_Last(AVL_tree searchMe)
{
   AVL_tree retTree = searchMe;
   
   if (retTree == NULL)
      return NULL;
   
   while (retTree->right != NULL)
      retTree = retTree->right;
   
   return retTree;
}

AVL_tree Tree_Next(AVL_tree searchMe)
{
    AVL_tree    tempTree;

    if ((searchMe->right) != NULL) /* aha! swoop down to min  of right subtree */
    {
        tempTree = searchMe->right;
        while ((tempTree->left) != NULL)
           tempTree = tempTree->left;
        return tempTree;
    }
   
    /* right is null - find lowest ancestor whose left child is also ancestor of x */
    tempTree = searchMe->parent;
    while ( (tempTree != NULL) && (searchMe == tempTree->right) )
    {
       searchMe = tempTree;
       tempTree = tempTree->parent;
    }
    return tempTree;
}


/****** 
  Local functions - heap maintenance code
******/

AVL_tree Allocate_AVL_tree(void)
{
    AVL_tree  temp_pointer;

    temp_pointer = (AVL_tree) malloc(sizeof(AVL_tree_element));
    if (temp_pointer == NULL) {
      fprintf(stderr, "Out of memory in Allocate_AVL_tree!\n");
      exit(-1);
    }
    return temp_pointer;
}

void Free_AVL_tree(AVL_tree freeMe)
{
    /* assume that data has been freed */
    if (freeMe == NULL)
       return;

    free(freeMe);
}