/*
 *  btree64k.c
 *
 *  Binary tree routines for jimslide
 *  copyright Jim Leonard 1999
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "btree64k.h"



size_t bt_entrySize;
size_t bt_keySize;
size_t bt_nodeSize;
int BT_SetBTAttributes(size_t entrySize, size_t keySize)
   {
   bt_entrySize = entrySize;
   bt_keySize = keySize;
   bt_nodeSize = SIZE_BT_POINTER + SIZE_BT_POINTER + entrySize;
   return 1;
   }


 /*
 *  Function:     BT_Init
 *
 *  Parameters:
 *       entrysize - size of the structure that is added to the btree
 *       keysize   - length of the key value on an entry.  The key must
 *                   be the first part of the structure
 *
 *  Returns:   pointer to root of a new binary tree or NULL if failure
 *
 *  Comments:
 */
BTree *BT_Init(int numEntries)
   {
   BTree *btree;

   if (0 != (btree = (BTree *)malloc(SIZE_BT_HEADER + numEntries * bt_nodeSize)))
      {
      btree->entries = 0;
      btree->maxEntries = numEntries;
      btree->nextNode = (BT_Node *)btree->data;
      return btree;
      }
   return NULL;
   }

void BT_Reset(BTree *btree)
   {
   btree->entries = 0;
   btree->nextNode = (BT_Node *)btree->data;
   }

unsigned char *sl_init_slptr;

void sl_copy(BT_Node *curNode)
   {

   if (curNode->lt_node)
      sl_copy(curNode->lt_node);

   memcpy(sl_init_slptr, curNode->entry, bt_entrySize);
   sl_init_slptr += bt_entrySize;

   if (curNode->gt_node)
      sl_copy(curNode->gt_node);
   }

SList *SL_Init(BTree *btree)
   {
   SList *slist;

   BT_Node *rootNode = (BT_Node *)btree->data;


   if (NULL == (slist = (SList *)malloc(SIZE_SL_HEADER + btree->entries * bt_entrySize)))
      return NULL;

   slist->entries = btree->entries;

   sl_init_slptr = slist->data;

   if (rootNode->lt_node)
      sl_copy(rootNode->lt_node);

   memcpy(sl_init_slptr, rootNode->entry, bt_entrySize);
   sl_init_slptr += bt_entrySize;

   if (rootNode->gt_node)
      sl_copy(rootNode->gt_node);
   return slist;
   }

void SL_Reset(BTree *btree, SList *slist)
   {
   BT_Node *rootNode = (BT_Node *)btree->data;


   slist->entries = btree->entries;

   sl_init_slptr = slist->data;

   if (rootNode->lt_node)
      sl_copy(rootNode->lt_node);

   memcpy(sl_init_slptr, rootNode->entry, bt_entrySize);
   sl_init_slptr += bt_entrySize;

   if (rootNode->gt_node)
      sl_copy(rootNode->gt_node);
   }

BT_Node *bt_cvt_firstNode;
BT_Node *bt_cvt_lastNode;

void bt_cvt(BT_Node *curNode)
   {
   if (curNode->lt_node)
      bt_cvt(curNode->lt_node);

   curNode->lt_node = bt_cvt_lastNode;

   if (bt_cvt_lastNode)
      bt_cvt_lastNode->gt_node = curNode;
   else
      bt_cvt_firstNode = curNode;

   bt_cvt_lastNode = curNode;

   if (curNode->gt_node)
      bt_cvt(curNode->gt_node);
   }


/*
 *  Converts a binary tree to a linked list.
 *  btree->nextNode becomes a pointer to the
 *  first (lowest) entry in the list
 */
void BT_CvtToLL(BTree *btree)
   {
   BT_Node *curNode = (BT_Node *)btree->data;

   bt_cvt_lastNode = NULL;

   if (curNode->lt_node)
      bt_cvt(curNode->lt_node);

   curNode->lt_node = bt_cvt_lastNode;

   if (bt_cvt_lastNode)
      bt_cvt_lastNode->gt_node = curNode;
   else
      bt_cvt_firstNode = curNode;

   bt_cvt_lastNode = curNode;

   if (curNode->gt_node)
      bt_cvt(curNode->gt_node);

   bt_cvt_lastNode->gt_node = NULL;

   btree->nextNode = bt_cvt_firstNode;
   }


SList *SL_Malloc(int numEntries)
   {
   return (SList *)malloc(SIZE_SL_HEADER + numEntries * bt_entrySize);
   }

BTree *BT_Realloc(BTree *btree)
   {
   BTree *newBtree;

   newBtree = realloc(btree, SIZE_BT_HEADER + btree->entries * bt_nodeSize);
   if (newBtree == NULL)
      return btree;
   else
      return newBtree;
   }

int BT_NumEntries(BTree *btree)
   {
   return btree->entries;
   }

int SL_NumEntries(SList *slist)
   {
   return slist->entries;
   }

size_t BT_SizeBtree (BTree *btree)
   {
   return btree->entries * bt_nodeSize + SIZE_BT_HEADER;
   }

size_t SL_SizeSlist (SList *slist)
   {
   return slist->size + SIZE_SL_HEADER;
   }

size_t SL_UncompressedSizeSlist (SList *slist)
   {
   return slist->entries * bt_entrySize + SIZE_SL_HEADER;
   }


 /*
 *  Function: BT_Free
 *
 *  Parameters:
 *          btree - pointer to btree to be deallocated
 *  Returns:
 *
 *  Comments:
 */
void BT_Free(BTree *btree)
   {
   free(btree);
   }


void SL_Free(SList *slist)
   {
   free(slist);
   }


/*
 *  Function: BTAddEntry
 *
 *  Parameters:
 *          btree - pointer to base
 *          entry - pointer to item to be added to btree
 *          overwrite - overwrite flag: if set allow overwrite of entries with
 *                      same key.
 *
 *  Returns: 1 if successful new add, 2 if overwrite, 0 if an error occurs, or
 *       -1 if an entry with same key already exists and overwrite flag is not set.
 *       -2 if we've run out of space to add to this tree
 *
 *  Comments:
 */
int BT_AddEntry(BTree *btree, void *entry, int overWrite)
   {
   BT_Node *curNode = (BT_Node *)btree->data;
   int cmpval;

   if (!btree->entries)
      {
      curNode->gt_node = NULL;
      curNode->lt_node = NULL;
      memcpy(curNode->entry, entry, bt_entrySize);
      ++btree->entries;
      btree->nextNode = (BT_Node *)((char *)btree->nextNode + bt_nodeSize);
      return 1;
      }


   while (1)
      {
      cmpval = MEMCMP(entry, curNode->entry, bt_keySize);

      if (cmpval > 0)
         {
         if (curNode->gt_node)
            {
            curNode = curNode->gt_node;
            continue;
            }
         else
            {
            curNode->gt_node = btree->nextNode;
            break;
            }
         }
      if (cmpval < 0)
         {
         if (curNode->lt_node)
            {
            curNode = curNode->lt_node;
            continue;
            }
         else
            {
            curNode->lt_node = btree->nextNode;
            break;
            }
         }

      /* if we're here, the keys must be the same */
      if (overWrite)
         {
         memcpy(curNode->entry, entry, bt_entrySize);
         return 2;
         }
      else
         return -1;
      }

   /* if we're here then we can add an entry */
   if (++btree->entries > btree->maxEntries)
      {
      --btree->entries;
      if (curNode->gt_node == btree->nextNode)
         curNode->gt_node = NULL;
      else
         curNode->lt_node = NULL;
      return -2;
      }

   curNode = btree->nextNode;
   curNode->gt_node = NULL;
   curNode->lt_node = NULL;
   memcpy(curNode->entry, entry, bt_entrySize);
   btree->nextNode = (BT_Node *)((char *)btree->nextNode + bt_nodeSize);
   return 1;
   }
   

/*
 *  Function: BT_FindEntry
 *
 *  Parameters:
 *          bree - base binary tree struct
 *          key - pointer to key value to find
 *          index - returns an index into the structure
 *  Returns: pointer to entry in btree or NULL if key doesn't exist.
 *       The value portion may be updated but the key may not!
 *
 *  Comments: changing the key section of this can be devastating to the
 *       structure!  Don't do it!
 */
void *BT_FindEntry(BTree *btree, void *key)
   {
   BT_Node *curNode = (BT_Node *)btree->data;
   int cmpval;


   if (!btree->entries)
      return NULL;

   while (1)
      {
      cmpval = MEMCMP(key, curNode->entry, bt_keySize);

      if (cmpval > 0)
         {
         if (curNode->gt_node)
            {
            curNode = curNode->gt_node;
            continue;
            }
         else
            {
            return NULL;
            }
         }
      if (cmpval < 0)
         {
         if (curNode->lt_node)
            {
            curNode = curNode->lt_node;
            continue;
            }
         else
            {
            return NULL;
            }
         }

      /* if we're here, the keys must be the same */
      return curNode->entry;
      }
   }


void *SL_FindEntry(SList *slist, void *key)
   {
   int num = slist->entries;
   unsigned char *sldata = slist->data;
   register unsigned char *lo = sldata;
   register unsigned char *hi = sldata + (num - 1) * bt_entrySize;
   register unsigned char *mid;
   unsigned int half;
   int result;

   while (lo <= hi)
      if (half = num / 2)
         {
         mid = lo + (num & 1 ? half : (half - 1)) * bt_entrySize;
         if (!(result = MEMCMP(key, mid, bt_keySize)))
            return(mid);
         else if (result < 0)
            {
            hi = mid - bt_entrySize;
            num = num & 1 ? half : half - 1;
            }
         else
            {
            lo = mid + bt_entrySize;
            num = half;
            }
         }
      else if (num)
         return(MEMCMP(key,lo, bt_keySize) ? NULL : lo);
      else
         break;

   return(NULL);
   }

#if 0

/* if memcmp weren't implemented at the processor level, this would be a good routine */

int Jmemcmp (const void * buf1, const void * buf2, size_t count)
   {
   int temp = count >> 2;  /* temp = count / 4 */

   while (temp)
      {
      if (*(int *)buf1 == *(int *)buf2)
         {
         buf1 = (int *)buf1 + 1;
         buf2 = (int *)buf2 + 1;
         temp--;
         continue;
         }

      /*
       * we can't just return buf1 - buf2 unless we were to cast to
       * something with more bits
       */
      if (*(unsigned int *)buf1 > *(unsigned int *)buf2)
         return 1;
      return -1;
      }

   count &= 3;  /* count = count % 4 */
   if (!count)
      return 0;
   
   /*
    * If we are here then we have 1, 2 or 3 bytes left to compare
    * and everything up to this point is identical.
    */

   if (*(char *)buf1 == *(char *)buf2)
      {
      if (--count && *(++(char *)buf1) == *(++(char *)buf2))
         {
         if (--count)
            return (*(++(unsigned char *)buf1) - *(++(unsigned char*)buf2));
         }
      }
   return (*(unsigned char *)buf1 - *(unsigned char *)buf2);
   }

#endif