home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / a_arrays.zip / ASSOC.CPP next >
Text File  |  1994-10-31  |  14KB  |  333 lines
  1. /***************************************************************
  2.  * file: ASSOC.CPP
  3.  * purpose: template class for associative arrays
  4.  * contains:
  5.  *      ASSOCIATION_BASE - core routines for the ASSOCIATION template
  6.  *      ASSOCIATION - association between strings and data objects
  7.  * copyright: 1994 by David Weber.  Unlimited use granted in EXE, OBJ,
  8.  *  or LIB formats.  Do not sell as source without asking first.
  9.  * environment:
  10.  *  tested Borland C++ 4.01 and Zortech C++ 3.1r2
  11.  * history:
  12.  *  10-02-94 - initial code, based on an earlier C module
  13.  **************************************************************/
  14.  
  15. #include "assoc.hpp"
  16.  
  17.  
  18. /************************************************
  19.  * function: ASSOCIATION_BASE::ASSOCIATION_BASE(unsigned int data_size,unsigned int estimated_size)
  20.  *  Constructor for an associative array
  21.  * parameters: byte size of a data element and the estimated size of array
  22.  * returns: nothing
  23.  ************************************************/
  24. ASSOCIATION_BASE::ASSOCIATION_BASE(unsigned int data_size,unsigned int estimated_size)
  25.     {
  26.     clear_pointers();                   // preset as invalid
  27.     sizeofdata = data_size;             // set up sizes
  28.     array_size = estimated_size;
  29.     fill_level = 0;                     // empty to start
  30.     allocate_array();                   // allocate space
  31.     }
  32.  
  33.  
  34. /************************************************
  35.  * function: ASSOCIATION_BASE::~ASSOCIATION_BASE()
  36.  *  Destructor for an associative array
  37.  * parameters: none
  38.  * returns: nothing
  39.  ************************************************/
  40. ASSOCIATION_BASE::~ASSOCIATION_BASE()
  41.     {
  42.     delete_pointers();                  // delete storage
  43.     clear_pointers();                   // just for tidiness
  44.     }
  45.  
  46.  
  47. /************************************************
  48.  * function: ASSOCIATION_BASE::ASSOCIATION_BASE(const ASSOCIATION_BASE &original)
  49.  *  copy constructor for class
  50.  * parameters: previous associative array to copy
  51.  * returns: nothing
  52.  ************************************************/
  53. ASSOCIATION_BASE::ASSOCIATION_BASE(const ASSOCIATION_BASE &original)
  54.     {
  55.     clear_pointers();                   // no heap to start
  56.     *this = original;                   // piggyback on assignment operator
  57.     }
  58.  
  59.  
  60. /************************************************
  61.  * function: ASSOCIATION_BASE & ASSOCIATION_BASE::operator=(const ASSOCIATION_BASE &original)
  62.  *  assigment operator for class
  63.  * parameters: previous associative array to copy
  64.  * returns: *this
  65.  ************************************************/
  66. ASSOCIATION_BASE & ASSOCIATION_BASE::operator=(const ASSOCIATION_BASE &original)
  67.     {
  68.     delete_pointers();                  // remove old storage
  69.     clear_pointers();                   // no heap to start
  70.     array_size = original.array_size;   // essential data
  71.     fill_level = original.fill_level;
  72.     sizeofdata = original.sizeofdata;
  73.     allocate_array();                   // allocate heap
  74.     if (!*this)                         // valid?
  75.         return *this;
  76.     // copy hash, keys, links and data; this only works cuz linkage is via offsets
  77.     memcpy(hash_list,original.hash_list,array_size * sizeof(unsigned int));
  78.     memcpy(key_list,original.key_list,fill_level * sizeof(const char *));
  79.     memcpy(link_list,original.link_list,fill_level * sizeof(unsigned int));
  80.     memcpy(data_list,original.data_list,array_size * sizeofdata);
  81.     return *this;
  82.     }
  83.  
  84.  
  85. /************************************************
  86.  * function: ASSOCIATION_BASE::ASSOCIATION_BASE(const char **keys,const char *data,unsigned int data_size,unsigned int count)
  87.  *  static initialization constructor, build an associative array with
  88.  *  pre-existing key and data arrays.
  89.  * parameters: pointer to an array of keys, pointer to an array of data
  90.  *             expressed as chars, size of array in elements
  91.  * returns: nothing
  92.  ************************************************/
  93. ASSOCIATION_BASE::ASSOCIATION_BASE(const char **keys,const char *data,unsigned int data_size,unsigned int count)
  94.     {
  95.     unsigned int i;
  96.  
  97.     clear_pointers();                   // mark storage as invalid
  98.     sizeofdata = data_size;             // set up sizes
  99.     array_size = count;
  100.     fill_level = 0;                     // empty to start
  101.     allocate_array();                   // allocate space
  102.     if (!*this)                         // valid?
  103.         return;
  104.     for (i = 0 ; i < count ; i++, keys++, data += sizeofdata)
  105.         insert(*keys,data);             // add info
  106.     }
  107.  
  108.  
  109. /************************************************
  110.  * function: int ASSOCIATION_BASE::insert(const char *key,const char *data)
  111.  *  Insert an entry into the associative array.  The caller is responsible for
  112.  *  storage of the key;
  113.  * parameters: const pointer to key string and const or non const pointer to data
  114.  * returns: 1 if inserted OK or 0 if a bad key
  115.  ************************************************/
  116. int ASSOCIATION_BASE::insert(const char *key,const char *data)
  117.     {
  118.     unsigned int index,k;
  119.  
  120.     if (key == 0)                       // no null keys allowed
  121.         return 0;
  122.     if (fill_level >= array_size)
  123.         if (!expand_array())
  124.             return 0;
  125.     index = hash(key);                  // find start in array
  126.     for (k = hash_list[index] ; k != ASSOC_NULL ; k = link_list[k])
  127.         {                               // see if already exists
  128.         if (ASSOC_STRCMP(key,key_list[k]) == 0)
  129.             {                           // replace current data
  130.             memcpy(data_list+k*sizeofdata,data,sizeofdata);
  131.             return 1;
  132.             }
  133.         }
  134.     key_list[fill_level] = key;         // put in new data
  135.     link_list[fill_level] = hash_list[index];
  136.     hash_list[index] = fill_level;
  137.     memcpy(data_list+fill_level*sizeofdata,data,sizeofdata);
  138.     fill_level++;
  139.     return 1;
  140.     }
  141.  
  142.  
  143. /************************************************
  144.  * function: int ASSOCIATION_BASE::remove(const char *key)
  145.  *  Remove an entry from the associative array
  146.  * parameters: const pointer to the key string
  147.  * returns: 1 if removed or 0 if not found in the array
  148.  ************************************************/
  149. int ASSOCIATION_BASE::remove(const char *key)
  150.     {
  151.     unsigned int k,*l;
  152.  
  153.     if (key == 0)                       // no null keys allowed
  154.         return 0;
  155.     for (l=hash_list+hash(key), k=*l ; k != ASSOC_NULL ; l=link_list+k, k=*l)
  156.         {                               // find entry
  157.         if (ASSOC_STRCMP(key,key_list[k]) == 0)
  158.             {
  159.             *l = link_list[k];          // unlink
  160.             fill_level--;               // level shrinks
  161.             key_list[k] = key_list[fill_level];// move top of pile into "removed"
  162.             link_list[k] = link_list[fill_level];
  163.             memcpy(data_list+k*sizeofdata,data_list+fill_level*sizeofdata,sizeofdata);
  164.             for (l = hash_list+hash(key_list[k]) ; *l != ASSOC_NULL ; l = link_list + *l)
  165.                 if (*l == fill_level)
  166.                     {                   // fix link to what was top of pile
  167.                     *l = k;
  168.                     break;
  169.                     }
  170.             return 1;
  171.             }
  172.         }
  173.     return 0;                           // doesn't exist
  174.     }
  175.  
  176.  
  177. /************************************************
  178.  * function: char *ASSOCIATION_BASE::find(const char *key)
  179.  *  Lookup an entry in the associative array and return a non const pointer
  180.  * parameters: const pointer to the key string
  181.  * returns:non const pointer to the data associated with the key
  182.  ************************************************/
  183. char *ASSOCIATION_BASE::find(const char *key)
  184.     {
  185.     unsigned int k;
  186.  
  187.     if (key == 0)                       // no null keys allowed
  188.         return 0;
  189.     for (k = hash_list[hash(key)] ; k != ASSOC_NULL ; k = link_list[k])
  190.         {                               // follow chain in array
  191.         if (ASSOC_STRCMP(key,key_list[k]) == 0)
  192.             return data_list + k * sizeofdata;
  193.         }
  194.     return 0;                           // not found
  195.     }
  196.  
  197.  
  198. /************************************************
  199.  * function: const char *ASSOCIATION_BASE::first(void)
  200.  *  Find the first key string in the array.  Follow this by
  201.  *  next() calls until a 0 is returned.  Inserting or Removing
  202.  *  from an array while you are iterating will invalidate the
  203.  *  iteration sequence (but doesn't mess up the array).
  204.  * parameters: none
  205.  * returns: first key string encountered or 0 if none
  206.  ************************************************/
  207. const char *ASSOCIATION_BASE::first(void)
  208.     {
  209.     iteration = 0;                      // start from beginning
  210.     return next();                      // and search
  211.     }
  212.  
  213. /************************************************
  214.  * function: const char *ASSOCIATION_BASE::next(void)
  215.  *  Find the next key string in the array, call first()
  216.  *  to start iteration.
  217.  * parameters: nothing
  218.  * returns: next key string encountered or 0 if all done
  219.  ************************************************/
  220. const char *ASSOCIATION_BASE::next(void)
  221.     {
  222.     while (iteration < fill_level)      // until end of data
  223.         return key_list[iteration++];   // return key
  224.     return 0;
  225.     }
  226.  
  227.  
  228. /************************************************
  229.  * function: char *ASSOCIATION_BASE::reference(const char *key)
  230.  *  find a key and return a reference to its data if it is there
  231.  *  otherwise insert a place for it and return a reference to the
  232.  *  zeroed out hole
  233.  * parameters: const pointer to the key string
  234.  * returns: pointer to associated data (which may be zeroed out)
  235.  ************************************************/
  236. char *ASSOCIATION_BASE::reference(const char *key)
  237.     {
  238.     unsigned int k,index;
  239.  
  240.     if (key == 0)                       // no null keys allowed
  241.         return 0;
  242.     index = hash(key);
  243.     for (k = hash_list[index] ; k != ASSOC_NULL ; k = link_list[k])
  244.         {                               // follow chain in array
  245.         if (ASSOC_STRCMP(key,key_list[k]) == 0)
  246.             return data_list + k * sizeofdata;  // found it
  247.         }
  248.     if (fill_level >= array_size)       // expand if necessary
  249.         if (!expand_array())
  250.             return 0;
  251.     key_list[fill_level] = key;         // put in hole for new data
  252.     link_list[fill_level] = hash_list[index];
  253.     hash_list[index] = fill_level;
  254.     memset(data_list+sizeofdata*fill_level,0,sizeofdata);
  255.     return data_list + sizeofdata*fill_level++;// return pointer to hole
  256.     }
  257.  
  258.  
  259. /************************************************
  260.  * function: unsigned int ASSOCIATION_BASE::hash(const char *key)
  261.  *  local function calculates a hash.  Designed to minimize clustering.
  262.  * parameters: key string
  263.  * returns: hash value clipped to array size
  264.  ************************************************/
  265. unsigned int ASSOCIATION_BASE::hash(const char *key)
  266.     {
  267.     unsigned int index;
  268.     const unsigned char *k;
  269.  
  270.     for (index=0x5555, k=ASSOC_CAST(const unsigned char *,key) ; *k != 0 ; k++)
  271.         index = (index << 1) ^ ASSOC_MAP(*k);// hash key
  272.     return index % array_size;          // fit in array
  273.     }
  274.  
  275.  
  276. /************************************************
  277.  * function: void ASSOCIATION_BASE::allocate_array(void)
  278.  *  local function allocates and initializes the array
  279.  * parameters: none
  280.  * returns: nothing
  281.  ************************************************/
  282. void ASSOCIATION_BASE::allocate_array(void)
  283.     {
  284.     unsigned int i;
  285.  
  286.     hash_list = new unsigned int[array_size];   // allocate hash array
  287.     key_list = new const char *[array_size];    // allocate key pointers
  288.     link_list = new unsigned int[array_size];   // allocate key linkage
  289.     data_list = new char[array_size*sizeofdata];// allocate storage for data
  290.     ASSOC_MEM_CHECK(hash_list);                 // validate resources
  291.     ASSOC_MEM_CHECK(key_list);
  292.     ASSOC_MEM_CHECK(link_list);
  293.     ASSOC_MEM_CHECK(data_list);
  294.     for (i = 0 ; i < array_size ; i++)
  295.         hash_list[i] = ASSOC_NULL;              // preset with nothing
  296.     }
  297.  
  298.  
  299. /************************************************
  300.  * function: int ASSOCIATION_BASE::expand_array(void)
  301.  *  double the size of the array
  302.  * parameters: none
  303.  * returns: 1 if expanded OK or 0 if failed
  304.  ************************************************/
  305. int ASSOCIATION_BASE::expand_array(void)
  306.     {                                   // if array full, increase size
  307.     const char **old_key;
  308.     char *old_data;
  309.     unsigned int i,index;
  310.  
  311.     old_key = key_list;                 // save old data
  312.     old_data = data_list;
  313.     delete [] hash_list;                // remove pointer storage
  314.     hash_list = 0;
  315.     delete [] link_list;
  316.     link_list = 0;
  317.     array_size <<= 1;                   // new size
  318.     allocate_array();                   // new array
  319.     if (!*this)                         // valid?
  320.         return 0;
  321.     memcpy(key_list,old_key,fill_level*sizeof(const char *));
  322.     memcpy(data_list,old_data,sizeofdata*fill_level);
  323.     for (i = 0 ; i < fill_level ; i++)
  324.         {                               // rehash old data into new array
  325.         index = hash(old_key[i]);
  326.         link_list[i] = hash_list[index];
  327.         hash_list[index] = i;
  328.         }
  329.     delete [] old_key;                  // blow away old storage
  330.     delete [] old_data;
  331.     return 1;
  332.     }
  333.