Lecture Notes for SE 598, Data Structures and Algorithms

12 July 2000, List Applications

1. heap storage management

   1. dynamic storage - new() and (usually) free()

   2. dynamically managed storage comes from a big block of storage called the heap

   3. each call to new() chips off a piece of storage of the proper size from the heap

   4. calls to free() return a piece of storage back to the heap

   5. new() and free() calls may occur in any order

   6. heaps tend to become fragmented with gaps of allocated but not yet freed storage

   7. lists are a useful data structure for implementing heaps

      1. can expand and shrink to keep up with the heap size

      2. can delete (new()) and insert (free()) new entries anywhere in the list

      3. each allocated piece has a header to keep track of its location in the heap

         1. struct header {
              char *   block;
              unsigned size;
              };
            

      4. the heap itself is a list of headers

         1. typedef list
             Heap;
            Heap hp;
            

      5. to allocate a block new(size)

         1. find a piece big enough to fill the request

            1. Heap::iterator i;
               for (i = hp.begin(); i != hp.end(); i++)
                 if ((*i).size >= size) break;
               

         2. if no such piece exists, return 0; otherwise carve off a piece

            1. if (i == hp.end())
                 return 0;
               char * b = (*i).block;
               (*i).block += size;
               (*i).size -= size;
               

         3. if the left-over piece is empty, delete it

            1. if ((*i).size == 0)
                 hp.erase(i);
               

      6. to free an allocated block free(b)

         1. find out where the block fits in the list and insert it

            1. Heap::iterator i;
               for (i = hp.begin(); i != hp.end(); i++)
                 if (b.block < (*i).block) break;
               i = hp.insert(i, b);
               

         2. coalesce adjacent blocks into a single, bigger block

            1. if (i != hp.begin()) {
                 Heap::iterator previous = i;
                 previous--;
                 if ((*previous).block + (*previous).size == (*i).block) {
                   (*previous).size += (*i).size;
                   hp.erase(i);
                   i = previous;
                   }
                 }
               
               Heap::iterator next = i;
               next++;
               if (next != hp.end())
                 if ((*i).block + (*i).size == (*next).block) {
                   (*i).size += (*next).size;
                   hp.erase(next);
                   }
               

2. sparse matrices

   1. matrices are a useful way to model the world

      1. schedules - class schedules, train schedules

   2. real-world matrix models are often huge - 100,000 on a side

   3. but, real-world matrix models are often sparse

      1. a vast majority of the matrix elements contain the same value

      2. consider the train schedule

   4. a sparse-matrix representation encodes only the non-common values, saving vast amounts of space

   5. a list containing the columns of the sparse matrix

   6. each column is a list containing the values in the rows for that column

      1. template <typename T>
         class sparse_matrix {
         
           private:
         
             template <typename CellT> 
             struct Cell {
               int   coord;
               CellT value;
               };
         
             typedef list<Cell<T> > column;
             typedef list<Cell<column> > columns;
         
             columns sm;
           };
         

   7. each sparse matrix has a default value representing the majority value

      1. sparse_matrix(T & default);
         

   8. to read a value, return the value if it exists, otherwise return the default value

   9. to write a value, make sure the corresponding cell exists, then store the value

This page last modified on 11 July 2000.