home *** CD-ROM | disk | FTP | other *** search
/ Chip 1998 February / CHIP_2_98.iso / misc / src / install / libfdisk / alloc.c next >
Encoding:
C/C++ Source or Header  |  1997-11-07  |  40.4 KB  |  1,263 lines
  1. /* handles automatic allocation of space for requested new partitions */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <unistd.h>
  6. #include <malloc.h>
  7. #include <string.h>
  8.  
  9. #include "libfdisk.h"
  10.  
  11.  
  12. /* these routines manipulate a space map - can be used or free space */
  13. /* the space map is a array of structures, each structure indicating */
  14. /* the start and size of a chunk of  space */
  15. /* if the size is 0, then it is an UNUSED entry in the free space table */
  16.  
  17. /* initialze a space map data type */
  18. int fdiskSpaceMapInit( SpaceMap **map ) {
  19.     *map = (SpaceMap *) malloc( sizeof(SpaceMap) );
  20.     (*map)->len = 0;
  21.     (*map)->num = 0;
  22.     (*map)->entry = NULL;
  23.     return FDISK_SUCCESS;
  24. }
  25.  
  26. /* reduce # entries to smallest possible number by combining */
  27. /* touching/overlapping entries                              */
  28. /* fuzz introduced because can't allocate space in less than */
  29. /* that size chunk ususally                                  */
  30. int fdiskSpaceMapKrunch( SpaceMap *map, unsigned int fuzz ) {
  31.     unsigned int start;
  32.     unsigned int end;
  33.     unsigned int maxend;
  34.     unsigned int tmpend;
  35.     unsigned int i, j;
  36.     
  37.     for (i=0; i < map->num-1; ) {
  38.  
  39.     start  = map->entry[i].start;
  40.     end    = start + map->entry[i].size;
  41.     maxend = end;
  42.  
  43.     /* see if next partition can merge with existing */
  44.     if (map->entry[i+1].start <= end+fuzz) {
  45.         /* find last space which starts inside existing space */
  46.         for (j=i+1; j < map->num; )
  47.         if (map->entry[j].start <= end+fuzz) {
  48.             tmpend=map->entry[j].start+map->entry[j].size;
  49.             if (tmpend > maxend)
  50.             maxend = tmpend;
  51.             
  52.             fdiskSpaceMapDel( map, j );
  53.             continue;
  54.         } else
  55.             break;
  56.  
  57.         /* adjust first space to contain all */
  58.         map->entry[i].size = maxend - map->entry[i].start;
  59.     } else {
  60.         /* move to the next entry and keep going */
  61.         i++;
  62.     }
  63.     }
  64.     
  65.     return FDISK_SUCCESS;
  66. }
  67.  
  68. /* add an entry to a map */
  69. /* fuzz is the smallest chunk we can allocate, used to close up holes */
  70. /* in the space map which are not usable                              */
  71. int fdiskSpaceMapAdd( SpaceMap *map, SpaceMapEntry *entry, unsigned int fuzz ){
  72.     int i;
  73.     int spot;
  74.     int num, len;
  75.  
  76.     /* see if anything exists yet */
  77.     if (map->entry) {
  78.     /* we want to keep map space sorted by start */
  79.     num = map->num;
  80.     len = map->len;
  81.     if (num == 0) {
  82.         spot = -1;
  83.     } else if (entry->start < map->entry[0].start) {
  84.         spot = -1;
  85.     } else if (entry->start > map->entry[num-1].start) {
  86.         spot = num;
  87.     } else {
  88.         /* NEW CODE (Nov 7 1997) WATCH CLOSELY! */
  89.         for (spot=0; spot < num-1; spot++)
  90.         if (entry->start >= map->entry[spot].start &&
  91.             entry->start <= map->entry[spot+1].start)
  92.             break;
  93.     }
  94.     } else {
  95.     /* new list */
  96.     num = 0;
  97.     len = 0;
  98.     spot = -1;
  99.     }
  100.  
  101.     /* are we simply adjusting an existing chunk, or creating a new one ? */
  102.     /* if its a new entry at end of list we skip this check altogether    */
  103.     if (spot > -1 && spot != num && entry->start == map->entry[spot].start){
  104.     /* editting existing entry */
  105.     if (entry->size > map->entry[spot].size)
  106.         map->entry[spot].size = entry->size;
  107.     } else {
  108.         /* insert into list */
  109.     map->num++;
  110.     if (map->num > len) {
  111.         len += SpaceMapChunk;
  112.         map->len = len;
  113.         map->entry = (SpaceMapEntry *) realloc(map->entry,
  114.                            len*sizeof(SpaceMapEntry));
  115.         memset(&map->entry[map->num-1], 0, len*sizeof(SpaceMapEntry));
  116.     }
  117.     
  118.     for (i=map->num-1; i >= 0 && i > spot; i--)
  119.         memcpy(&map->entry[i], &map->entry[i-1], sizeof(SpaceMapEntry));
  120.  
  121.     if (spot != num)
  122.         memcpy(&map->entry[spot+1], entry, sizeof(SpaceMapEntry));
  123.     else
  124.         memcpy(&map->entry[spot], entry, sizeof(SpaceMapEntry));
  125.     }
  126.  
  127.     /* go thru and consolidate to smallest set of entries          */
  128.     /* for now lets not use fuzz, as it erases spaces where we may */
  129.     /* actually want to put an EPT, for example                    */
  130.     /* fdiskSpaceMapKrunch( map, fuzz );                           */
  131.     fdiskSpaceMapKrunch( map, 0 );
  132.     
  133.     return FDISK_SUCCESS;
  134. }
  135.  
  136.  
  137. /* delete an entry from a map, index by position in list */
  138. int fdiskSpaceMapDel( SpaceMap *map, unsigned int n ) {
  139.     int i;
  140.  
  141.     /* see if anything exists yet */
  142.     if (!map->entry || n < 0 || n > map->num-1)
  143.     return FDISK_ERR_BADNUM;
  144.  
  145.     for (i=n; i<map->num-1; i++)
  146.     memcpy(&map->entry[i], &map->entry[i+1], sizeof(SpaceMapEntry));
  147.  
  148.     memset(&map->entry[map->num-1], 0, sizeof(SpaceMapEntry));
  149.     map->num--;
  150.     return FDISK_SUCCESS;
  151. }
  152.  
  153.  
  154. int fdiskSpaceMapFree( SpaceMap *map ) {
  155.  
  156.     if (!map)
  157.     return FDISK_ERR_BADPTR;
  158.  
  159.     if (map->entry)
  160.     free(map->entry);
  161.  
  162.     free(map);
  163.     return FDISK_SUCCESS;
  164. }
  165.  
  166.         
  167.  
  168. /*                                                                        */
  169. /* END OF SPACE MAP MANAGEMENT ROUTINES                                   */
  170. /*                                                                        */
  171.  
  172.  
  173.  
  174. /*                                                                        */
  175. /* These routines handle making maps of used and free space on a given hd */
  176. /*                                                                        */
  177.  
  178. /*                                                                        */
  179. /* Routine  to build a 'used' space map for the given hard drive          */
  180. /*                                                                        */
  181. int fdiskUsedMapGen( HardDrive *hd, SpaceMap **map ) {
  182.     unsigned int i, first, last;
  183.     int          status;
  184.     unsigned int diskempty=0;
  185.     Partition    *p, *ep;
  186.     SpaceMapEntry m;
  187.     
  188.     /* find range of partitions to include                  */
  189.     /* if no partitions then its easy to compute free space */
  190.     if ((status=fdiskFirstPartition( hd, &first )) )
  191.     if (status != FDISK_ERR_BADNUM)
  192.         return status;
  193.     else
  194.         diskempty = 1;
  195.  
  196.     if (diskempty) {
  197.     first = 0;
  198.     last  = 0;
  199.     } else {
  200.     if ((status=fdiskLastPartition( hd, &last   )))
  201.         return status;
  202.     }
  203.     
  204.     fdiskSpaceMapInit( map );
  205.  
  206.     /* insert the Master Boot record */
  207.     m.start = 0;
  208.     m.size  = hd->geom.sectors;
  209.     fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  210.  
  211.     /* if no partitions we're free to go */
  212.     if (diskempty)
  213.     return FDISK_SUCCESS;
  214.  
  215.     /* otherwise go thru list and figure allocated space */
  216.     for (i=first; i <= last; i++) {
  217.     status = fdiskGetAttrPartition( hd, i, &p );
  218.     if (!status) {
  219.         if (i<5) {
  220.         /* this is a primary partition */
  221.         /* is it an extended partition? */
  222.         if (!fdiskIsExtended( p->type.current )) {
  223.             m.start = p->start.current;
  224.             m.size  = p->size.current;
  225.         } else {
  226.             /* this is the PEP */
  227.             /* we insert a used region for the PEPT */
  228.             m.start = p->start.current;
  229.             m.size  = hd->geom.sectors;
  230.         }
  231.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  232.         } else {
  233.         /* this is a  logical/extended partition pair.     */
  234.         /* We take into account the space used by the EPT  */
  235.         /* and the logical partition                       */
  236.  
  237.         /* first the EPT */
  238.         fdiskGetAttrExtended( hd, i, &ep );
  239.         m.start = ep->start.current;
  240.         m.size  = hd->geom.sectors;  /* EPT takes 1 sector but */
  241.                                              /* usually takes 1 head   */
  242.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  243.  
  244.         /* now the logical partition */
  245.         /* see if the offset is due to a true offset, or because */
  246.         /* of cyl/head/sector stuff  */
  247.         /* could probably use p->offset.current but not sure */
  248.         /* that is setup correctly (yet) */
  249.         if ((p->start.current-ep->start.current)<=hd->geom.sectors) {
  250.             m.start = ep->start.current;
  251.             m.size  = p->size.current +
  252.             (p->start.current-ep->start.current);
  253.         } else {
  254.             m.start = p->start.current;
  255.             m.size  = p->size.current;
  256.         }
  257.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  258.         free(ep);
  259.         }
  260.         free(p);
  261.     }
  262.     }
  263.         
  264.     return FDISK_SUCCESS;
  265. }
  266.  
  267. /*                                                                        */
  268. /* Routine  to build a 'free' space map for the given hard drive          */
  269. /*                                                                        */
  270. int fdiskFreeMapGen( HardDrive *hd, SpaceMap **map ) {
  271.     unsigned int    i, first, diff;
  272.     int             status;
  273.     SpaceMapEntry   m;
  274.     SpaceMap        *umap;
  275.  
  276.     /* make a 'used' map, and invert it */
  277.     if ((status=fdiskUsedMapGen( hd, &umap )))
  278.     return status;
  279.     
  280.     fdiskSpaceMapInit( map );
  281.     
  282.     /* start with first sector, find first used sector */
  283.     /* and keep building free space map that way.      */
  284.     first = 0;
  285.     for (i=0; i < umap->num; i++) {
  286.     diff = umap->entry[i].start - first;
  287.     if (diff) {
  288.         m.start = first;
  289.         m.size  = diff;
  290.         fdiskSpaceMapAdd( *map, &m, 0 ); /* no fuzz needed */
  291.     }
  292.  
  293.     /* move over used block to next possible free space */
  294.     first = umap->entry[i].start + umap->entry[i].size;
  295.     }
  296.  
  297.     /* now handle the end */
  298.     diff = hd->totalsectors - first;
  299.     if (diff) {
  300.     m.start = first;
  301.     m.size  = diff;
  302.     fdiskSpaceMapAdd( *map, &m, 0 ); /* no fuzz needed */
  303.     }
  304.  
  305.     return FDISK_SUCCESS;
  306. }
  307.  
  308.  
  309. /* given a partition describing a request and a candidate freespace entry  */
  310. /* determine if the space will work                                        */
  311. /* Handles aligning to cylinder boundaries                                 */
  312. /* modifies partition p if the constraints worked out ok                   */
  313. /* Returns FDISK_ERR_NOFREE if nothing found                               */
  314. int fdiskCheckConstraints( HardDrive *hd, SpaceMapEntry *freespace,
  315.                Partition *p, unsigned int type ) {
  316.  
  317.     unsigned int lsize,  msize,  csize, size;
  318.     unsigned int lstart, mstart, cstart, start;
  319.     unsigned int lcyl,   mcyl,   ccyl, cyl;
  320.     unsigned int end;
  321.     unsigned int extstart, extsize, extend;
  322.     unsigned int tmp1, tmp2;
  323.     unsigned int fuzz;
  324.     unsigned int inpep;
  325.     unsigned int satisfied, satis1, satis2, pass;
  326.  
  327.     /* see if we're looking for a logical partition or not */
  328.     fuzz  = 0;
  329.     inpep = 0;
  330.     if (type & LOGICAL)
  331.     if (!hd->pep)
  332.         return FDISK_ERR_NOPEP;
  333.     else {
  334.         fuzz  = hd->geom.sectors;
  335.         inpep = 1;
  336.         fdiskQueryPEP( hd, &extstart, &extsize );
  337.         extend = extstart + extsize - 1;
  338.     }
  339.     else if (type & PRIMARY_EXTENDED)
  340.     fuzz = 32;
  341.     
  342.     /* setup all of the constrains                                     */
  343.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  344.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  345.     fdiskQueryConstraint(&p->endcyl, &ccyl, &lcyl,   &mcyl,
  346.                FDISK_ENDCYL_MIN,  FDISK_ENDCYL_MAX );
  347.     fdiskQueryConstraint(&p->start,  &cstart, &lstart,  &mstart,
  348.                FDISK_START_MIN,  FDISK_START_MAX );
  349.     
  350.     /* we have several constraints to satisfy, here we are interested  */
  351.     /* in the size and start requirements of the partition             */
  352.     /* First see if we have a big enough chunk of free space           */
  353.     size  = freespace->size;
  354.     start = freespace->start;
  355.     end   = start + size - 1;
  356.     
  357.     /* handle cylinder boundaries here */
  358.     fdiskRoundStartToCylinder(hd, &start);
  359.     fdiskRoundEndToCylinder(hd, &end);
  360.     size = end - start + 1;
  361.     
  362.     pass = 0;
  363.     satis1 = satis2 = 0;
  364.     while (pass < 2) {
  365.     /* make sure its big enough and is inside PEP if so desired */
  366.     satisfied = 0;
  367.     if (size  >= lsize && (!inpep || (start>=extstart && start<=extend))) {
  368.         end = start + lsize - 1;
  369.  
  370.         /* round end to the cylinder boundary */
  371.         fdiskRoundEndToCylinder( hd, &end );
  372.         
  373.         /* now check that we can satisfy and start/end contraints */
  374.         satisfied = 1;
  375.         if (fdiskConstraintIsActive( &p->endcyl )) {
  376.         fdiskSectorToCHS(hd,end,&cyl,&tmp1,&tmp2);
  377.         satisfied = satisfied && (cyl >= lcyl) && (cyl <= mcyl );
  378.         if (!pass && !satisfied && LastAllocStat != ALLOC_UNDEF)
  379.             LastAllocStat = ALLOC_CYL;
  380.         }
  381.         
  382.         if (fdiskConstraintIsActive( &p->start )) {
  383.         satisfied = satisfied && (start>=lstart) && (start<=mstart);
  384.         if (!pass && !satisfied && LastAllocStat != ALLOC_UNDEF)
  385.             LastAllocStat = ALLOC_START;
  386.         }
  387.         
  388.         if (inpep) {
  389.         satisfied = satisfied && (end <= extend);
  390.         }
  391.     } else {
  392.         if (!pass && LastAllocStat != ALLOC_UNDEF)
  393.         LastAllocStat = ALLOC_SIZE;
  394.     }
  395.  
  396.     /* did we pass all the tests? */
  397.     if (pass == 0) {
  398.         satis1 = satisfied;
  399.         if (satisfied) {
  400.         /* save working params into partition entry */
  401.         p->size.current  = end - start + 1;
  402.         p->start.current = start;
  403.  
  404.         LastAllocStat = ALLOC_OK;
  405.         
  406.         /* now lets get greedy and grab extra cylinder    */
  407.         /* this makes up for the fact that we almost      */
  408.         /* always grab a little less space than requested */
  409.         /* due to overhead of partition tables            */
  410.         pass++;
  411.         lsize += hd->geom.heads*hd->geom.sectors;
  412.         if (lsize > size)
  413.             lsize = size;
  414.         } else {
  415.         pass = 3;
  416.         }
  417.     } else {
  418.         satis2 = satisfied;
  419.         if (satisfied) {
  420.         /* save working params into partition entry */
  421.         p->size.current  = end - start + 1;
  422.         p->start.current = start;
  423.  
  424.         /* we're done */
  425.         pass = 3;
  426.         } else {
  427.         /* we're done */
  428.         pass = 3;
  429.         }
  430.     }
  431.     }
  432.     
  433.     if (satis1 || satis2)
  434.     return FDISK_SUCCESS;
  435.     else
  436.     return FDISK_ERR_NOFREE;
  437. }
  438.  
  439. /* Looking at current partition table of drive hd, find a chunk of         */
  440. /* free space that will contain the partition p with all its constraints   */
  441. /* if inpep!=0, we look in pep area only, and add some space required      */
  442. /* for logical partitions over their requested size.                       */
  443. /* Handles aligning to cylinder boundaries                                 */
  444. /* Returns FDISK_ERR_NOFREE if nothing found                               */
  445. int fdiskFindFreeSlot( HardDrive *hd, SpaceMap *freespace, Partition *p,
  446.                unsigned int type, unsigned int *freeslot ) {
  447.  
  448.     unsigned int done, j;
  449.     
  450.     /* we have several constraints to satisfy, here we are interested  */
  451.     /* in the size and start requirements of the partition             */
  452.     /* First see if we have a big enough chunk of free space           */
  453.     done = 0;
  454.     for (j=0; j<freespace->num && !done; j++) {
  455.     if (fdiskCheckConstraints(hd, &freespace->entry[j],
  456.                   p, type ) == FDISK_SUCCESS) {
  457.         done = 1;
  458.         *freeslot = j;
  459.     }
  460.     }
  461.     
  462.     if (done) {
  463.     return FDISK_SUCCESS;
  464.     } else {
  465.     LastAllocStat = ALLOC_SIZE;
  466.     return FDISK_ERR_NOFREE;
  467.     }
  468. }
  469.  
  470. /* characteristics of primary are handled in constraints in p        */
  471. /* if pri < 0, autoallocate primary slot                             */
  472. int fdiskMakeNewPrimary( HardDrive *hd, int pri, Partition *p ) {
  473.     
  474.     unsigned int lsize,  msize,  csize;
  475.     unsigned int lstart, mstart, cstart;
  476.     unsigned int lcyl,   mcyl,   ccyl;
  477.     int          status;
  478.     
  479.     Partition *pt;
  480.  
  481.     /* See if we need to auto-allocate the partition */
  482.     if (pri < 0)
  483.     if (fdiskFindFreePrimary( hd, &pri ) == FDISK_ERR_NOFREEPRIM) {
  484.         LastAllocStat = ALLOC_FREEPRI;
  485.         return FDISK_ERR_NOFREEPRIM;
  486.     }
  487.     
  488.     /* setup all of the constrains                                     */
  489.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  490.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  491.     fdiskQueryConstraint(&p->endcyl, &ccyl, &lcyl,   &mcyl,
  492.                FDISK_ENDCYL_MIN,  FDISK_ENDCYL_MAX );
  493.     fdiskQueryConstraint(&p->start,  &cstart, &lstart,  &mstart,
  494.                FDISK_START_MIN,  FDISK_START_MAX );
  495.     
  496.     status=fdiskCreatePrimary( hd, pri );
  497.     if (status != FDISK_SUCCESS) {
  498.     LastAllocStat = ALLOC_FREEPRI;
  499.     return status;
  500.     }
  501.     
  502.     fdiskGetAttrPartition( hd, 1, &pt );
  503.     fdiskSetConstraint( &pt->size,  csize,  lsize,  msize,
  504.             fdiskConstraintIsActive(&p->size) );
  505.     fdiskSetConstraint( &pt->start, cstart, lstart, mstart,
  506.             fdiskConstraintIsActive(&p->start) );
  507.     fdiskSetFixedConstraint( &pt->type,   p->type.current    );
  508.     fdiskSetFixedConstraint( &pt->active, p->active.current  );
  509.     fdiskSetFixedConstraint( &pt->offset, 0                  );
  510.     fdiskDeactivateAllDriveSet( &pt->drive );
  511.     fdiskActivateDriveSet( &pt->drive,  hd->num );
  512.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  513.     fdiskSetFixedConstraint( &pt->num,    pri                );
  514.     pt->status = ALLOCATED;
  515.  
  516.     fdiskSetAttrPartition( hd, pri, pt );
  517.  
  518.     /* store current value in the partition we were passed */
  519.     fdiskSetCurrentConstraint(&p->num, pri);
  520.     fdiskSetCurrentDriveSet(&p->drive, hd->num);
  521.     fdiskSetCurrentConstraint(&p->size, csize);
  522.     fdiskSetCurrentConstraint(&p->start, cstart);
  523.     
  524.     free(pt);
  525.  
  526.     return FDISK_SUCCESS;
  527. }    
  528.  
  529. /* if no primary extended partition exists, this routine will do it */
  530. int fdiskMakeNewPrimaryExtended(HardDrive *hd,
  531.                 int          pep,
  532.                 unsigned int freestart,
  533.                 unsigned int freesize ) {
  534.  
  535.     unsigned int extstart, extend, extsize;
  536.     int          status;
  537.  
  538.     Partition *pt;
  539.     
  540.     /* no primary extended partition (yet)                            */
  541.     /* lets make one the size of the free space block we're putting   */
  542.     /* the requested partition in                                     */
  543.     /* then we make our logical partition                             */
  544.     if (pep < 0)
  545.     if (fdiskFindFreePrimary( hd, &pep ) == FDISK_ERR_NOFREEPRIM) {
  546.         LastAllocStat = ALLOC_FREEPRI;
  547.         return FDISK_ERR_NOFREEPRIM;
  548.     }
  549.     
  550.     hd->pep = pep;
  551.     if ((status=fdiskCreatePrimary( hd, pep )) != FDISK_SUCCESS) {
  552.     LastAllocStat = ALLOC_FREEPRI;
  553.     return status;
  554.     }
  555.     
  556.     fdiskGetAttrPartition( hd, pep, &pt );
  557.     
  558.     /* we need to make size/start that of the free block we're using */
  559.     /* and NOT the size of the logical partition we want to make     */
  560.     /* We DO NOT set the size/start constraints ACTIVE, since we may */
  561.     /* want to grow them later.                                      */
  562.     extstart = freestart;
  563.     extend   = freestart + freesize - 1;
  564.     
  565.     /* handle cylinder boundaries here */
  566.     fdiskRoundStartToCylinder(hd, &extstart);
  567.     fdiskRoundEndToCylinder(hd, &extend);
  568.     extsize = extend - extstart + 1;
  569.     
  570.     fdiskSetConstraint( &pt->size, extsize,  extsize,  FDISK_SIZE_MAX, 0 );
  571.     fdiskSetConstraint( &pt->start,extstart, extstart, FDISK_START_MAX, 0);
  572.     fdiskSetFixedConstraint( &pt->type,   DOS_EXTENDED_PARTITION );
  573.     fdiskSetFixedConstraint( &pt->active, 0 );
  574.     fdiskSetFixedConstraint( &pt->offset, 0 );
  575.     fdiskDeactivateAllDriveSet( &pt->drive );
  576.     fdiskActivateDriveSet( &pt->drive,  hd->num  );
  577.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  578.     fdiskSetFixedConstraint( &pt->num,    pep );
  579.     pt->status = ALLOCATED;
  580.     
  581.     fdiskSetAttrPartition( hd, pep, pt );
  582.     free(pt);
  583.  
  584.     return FDISK_SUCCESS;
  585. }
  586.  
  587. /* Make an extended partition within the specified region */
  588. /* Must have a PEP before this call will work.            */
  589. /* The size and start of the partition p are used         */
  590. /* However, the user data is offset because there is a EPT*/
  591. /* at the start of this space                             */
  592. int fdiskMakeNewLogical( HardDrive *hd, Partition *p ) {
  593.     int status;
  594.  
  595.     unsigned int lp, pep;
  596.  
  597.     unsigned int cstart, lstart, mstart;
  598.     unsigned int csize,  lsize,  msize;
  599.     unsigned int extstart, extend, extsize;
  600.     unsigned int sector_offset;
  601.     
  602.     Partition *pt, *ept;
  603.  
  604.     /* see if pep exists */
  605.     pep = hd->pep;
  606.     if (!pep)
  607.     return FDISK_ERR_NOPEP;
  608.     
  609.     /* use it as a template for the extented partition part of the */
  610.     /* EP/LP pair we are creating                                  */
  611.     if ((status=fdiskAppendLogical( hd, &lp )) != FDISK_SUCCESS)
  612.     return status;
  613.  
  614.  
  615.     /* setup all of the constrains                              */
  616.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  617.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  618.     fdiskQueryConstraint(&p->start, &cstart, &lstart,  &mstart,
  619.                FDISK_START_MIN,  FDISK_START_MAX );
  620.     
  621.     /* get initial starting points for extended and logical entries */
  622.     fdiskGetAttrPartition( hd, lp,  &pt );
  623.     fdiskGetAttrPartition( hd, pep, &ept );
  624.     
  625.     /* since we are creating a logical partition from scratch,  */
  626.     /* we can make the offset anything we like. The existing    */
  627.     /* 'fdisk' program makes the offset equal to one head       */
  628.     sector_offset = hd->geom.sectors;
  629.  
  630.     /* setup the extended partition first */
  631.     /* it describes the partition which the logical is IN       */
  632.     extstart = cstart;
  633.     extend   = cstart + csize + sector_offset - 1;
  634.     
  635.     /* handle cylinder boundaries here */
  636.     fdiskRoundStartToCylinder(hd, &extstart);
  637.     fdiskRoundEndToCylinder(hd, &extend);
  638.     extsize = extend - extstart + 1;
  639.     
  640.     fdiskSetConstraint( &ept->size, extsize,  extsize,  FDISK_SIZE_MAX, 0 );
  641.     fdiskSetConstraint( &ept->start,extstart, extstart, FDISK_START_MAX, 0);
  642.     fdiskSetFixedConstraint( &ept->type,   DOS_EXTENDED_PARTITION );
  643.     fdiskSetFixedConstraint( &ept->active, 0 );
  644.     fdiskSetFixedConstraint( &ept->offset, 0 );
  645.     fdiskDeactivateAllDriveSet( &ept->drive );
  646.     fdiskActivateDriveSet( &ept->drive,  hd->num  );
  647.     fdiskSetCurrentDriveSet( &ept->drive, hd->num );
  648.     fdiskSetFixedConstraint( &ept->num,  lp );
  649.     ept->status = ALLOCATED;
  650.     
  651.     fdiskSetAttrExtended( hd, lp, ept );
  652.     free(ept);
  653.     
  654.     /* now the logical partition                                */
  655.     fdiskSetConstraint( &pt->size,
  656.             extsize-sector_offset,
  657.             lsize, msize, fdiskConstraintIsActive(&p->size) );
  658.     fdiskSetConstraint( &pt->start,
  659.             extstart+sector_offset,
  660.             lstart, mstart,fdiskConstraintIsActive(&p->start) );
  661.     fdiskSetFixedConstraint( &pt->type,   p->type.current );
  662.     fdiskSetFixedConstraint( &pt->active, p->active.current );
  663.     fdiskSetFixedConstraint( &pt->offset, 0 );
  664.     fdiskDeactivateAllDriveSet( &pt->drive );
  665.     fdiskActivateDriveSet( &pt->drive,  hd->num  );
  666.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  667.     fdiskSetFixedConstraint( &pt->num,    lp );
  668.     pt->status = ALLOCATED;
  669.     
  670.     /* store current value in the partition we were passed */
  671.     fdiskSetCurrentConstraint(&p->num, lp);
  672.     fdiskSetCurrentDriveSet(&p->drive, hd->num);
  673.     fdiskSetCurrentConstraint(&p->size, extsize-sector_offset);
  674.     fdiskSetCurrentConstraint(&p->start, extstart+sector_offset);
  675.     
  676.     fdiskSetAttrPartition( hd, lp, pt );
  677.     free(pt);
  678.  
  679.     return FDISK_SUCCESS;
  680. }
  681.  
  682.  
  683. /*                                                                        */
  684. /* These routines handle inserting a desired partition into an existing   */
  685. /* partition table on a hard drive.                                       */
  686. /*                                                                        */
  687. /* We pass an array of HardDrive's, each of which is considered for the   */
  688. /* possible home of the partition.                                        */
  689. /* HardDrive's are assumed to be in arranged in increasing number         */
  690. /* Note that the index of the drive in the HardDrive array IS NOT the same*/
  691. /* as its actual 'num'.                                                   */
  692. int fdiskAutoInsertPartition(HardDrive **hdarr,
  693.                  unsigned int nhd,
  694.                  Partition *p ) {
  695.     
  696.     unsigned int drive;
  697.     unsigned int extstart, extsize;
  698.     unsigned int i;
  699.     unsigned int freeslot, freedrive;
  700.  
  701.     unsigned int extExists, priExists, noneExists;
  702.     unsigned int extCreate, priCreate, logCreate;
  703.     unsigned int extTried,  priTried, logTried;
  704.     unsigned int done, donesearch, errsearch, lasttry, trynext;
  705.     int status;
  706.  
  707.     HardDrive *hd;
  708.     SpaceMap  **freespace;
  709.     DriveSet  drives;
  710.     Partition *ptmp;
  711.  
  712.     /* first lets generate free space maps for all possible drives */
  713.     /* also figure out what range of drives exist                  */
  714.     /* index of freespace[] will be the same as for accessing      */
  715.     /* the entries of the hdarr[] of HardDrive's                   */
  716.     freespace = (SpaceMap **) alloca((nhd)*sizeof(SpaceMap));
  717.     fdiskDeactivateAllDriveSet( &drives );
  718.     for (drive=0; drive < nhd; drive++) {
  719.     fdiskFreeMapGen( hdarr[drive], &freespace[drive] );
  720.     fdiskActivateDriveSet( &drives, hdarr[drive]->num );
  721.     }
  722.  
  723.     /* loop over all the drives which are valid to consider            */
  724.     /* For each drive, go through a list of 'preferable' places to put */
  725.     /* the new partition.                                              */
  726.     /*                                                                 */
  727.     /* Rules:                                                          */
  728.     /*                                                                 */
  729.     /*     If No Partitions Exist                                      */
  730.     /*        Create New Primary                                       */
  731.     /*        DONE                                                     */
  732.     /*     Else If No Extended Exists                                  */
  733.     /*        Create Extended in largest hole fitting all constraints  */
  734.     /*        DONE                                                     */
  735.     /*     Else                                                        */
  736.     /*        Try to create a logical partition                        */
  737.     /*        If Success                                               */
  738.     /*           DONE                                                  */
  739.     /*        Else                                                     */
  740.     /*           Try to create a primary partition                     */
  741.     /*           If Success                                            */
  742.     /*              DONE                                               */
  743.     /*           Else                                                  */
  744.     /*              FAIL                                               */
  745.     /*                                                                 */
  746.     done = 0;
  747.     LastAllocStat = ALLOC_UNDEF;
  748.     for (drive = 0; drive < nhd && !done; drive++) {
  749.     hd = hdarr[drive];
  750.     if (!fdiskThisDriveSetIsActive( &p->drive, hd->num ))
  751.         continue;
  752.     
  753.     /* Figure out what partitions currently exist on this drive */
  754.     extExists  = (hd->pep != 0);
  755.     priExists = 0;
  756.     for (i=1; i<4; i++) {
  757.         if (fdiskGetAttrPrimary(hd, i, &ptmp) != FDISK_SUCCESS)
  758.         continue;
  759.         priExists |= !fdiskIsExtended(ptmp->type.current);
  760.     }
  761. /*    priExists  = !(fdiskLastPartition( hd, &tmp1 ) == FDISK_ERR_BADNUM); */
  762.     noneExists = !(extExists || priExists);
  763.  
  764.     /* Keeps trying strategies for placing new partition in existing */
  765.     /* scheme until we hit a solution we like                        */
  766.     donesearch = 0;
  767.     errsearch  = 0;
  768.     lasttry    = 0;
  769.     trynext    = 0;
  770.     extTried   = 0;
  771.     logTried   = 0;
  772.     priTried   = 0;
  773.     while (!donesearch && !errsearch && !lasttry && !trynext) {
  774.         priCreate  = 0;
  775.         extCreate  = 0;
  776.         logCreate  = 0;
  777.         
  778.         if (noneExists || !priExists) {
  779.         /* gonna make a primary partition */
  780.         priCreate = 1;
  781.         if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  782.                       PRIMARY,&freeslot)) != FDISK_SUCCESS)
  783.             trynext = 1;
  784.         else {
  785.             freedrive  = drive;
  786.             lasttry = 1;
  787.         }
  788.         } else if (!extExists) {
  789.  
  790.         if (!extTried) {
  791.             /* let try to make a primary extended partition */
  792.             extCreate = 1;
  793.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  794.                           PRIMARY_EXTENDED,
  795.                           &freeslot)) != FDISK_SUCCESS)
  796.             trynext = 1;
  797.             else {
  798.             freedrive  = drive;
  799.             }
  800.         } else if (!priTried) {
  801.             /* couldnt make extended work, try to make another PP */
  802.             priCreate = 1;
  803.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  804.                       PRIMARY,&freeslot)) != FDISK_SUCCESS)
  805.             trynext = 1;
  806.             else {
  807.             freedrive  = drive;
  808.             lasttry    = 1;
  809.             }
  810.         } else
  811.             /* nothing else to try */
  812.             trynext = 1;
  813.         } else {
  814.         /* try to make a logical first, then a primary */
  815.         if (!logTried) {
  816.             logCreate = 1; 
  817.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  818.                       LOGICAL,&freeslot)) != FDISK_SUCCESS) {
  819.             if (!priTried) {
  820.                 priCreate = 1;
  821.                 if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  822.                               PRIMARY,&freeslot)) != FDISK_SUCCESS)
  823.                 trynext = 1;
  824.                 else {
  825.                 freedrive  = drive;
  826.                 lasttry    = 1;
  827.                 }
  828.             } else {
  829.             trynext = 1;
  830.             }
  831.             } else {
  832.             freedrive  = drive;
  833.             }
  834.         } else
  835.             /* nothing else to try */
  836.             trynext = 1;
  837.         }
  838.  
  839.         /* move on to next drive */
  840.         if (trynext)
  841.         continue;
  842.         
  843.         if (!errsearch) {
  844.         /* now try to create whatever we decided was the best choice */
  845.         /* parameters of the allocated partition are in the partition*/
  846.         /* structure 'p'                                             */
  847.         if (priCreate) {
  848.             priTried = 1;
  849.             if ((status=fdiskMakeNewPrimary(hd,-1,p))==FDISK_SUCCESS)
  850.             donesearch = 1;
  851.         } else if (extCreate) {
  852.             extTried = 1;
  853.             if (!extExists) {
  854.             /* gotta make a PEP */
  855.             extstart = freespace[drive]->entry[freeslot].start;
  856.             extsize  = freespace[drive]->entry[freeslot].size;
  857.             status=fdiskMakeNewPrimaryExtended(hd, -1,
  858.                                extstart,extsize);
  859.             if (status == FDISK_SUCCESS) {
  860.                 extExists = 1;
  861.                 status=fdiskMakeNewLogical(hd, p);
  862.                 if (status == FDISK_SUCCESS)
  863.                 donesearch = 1;
  864.             }
  865.             }
  866.         } else if (logCreate) {
  867.             logTried = 1;
  868.             if (!extExists) {
  869.             status = FDISK_ERR_NOPEP;
  870.             errsearch = 1;
  871.             } else {
  872.             status=fdiskMakeNewLogical(hd, p);
  873.             if (status == FDISK_SUCCESS)
  874.                 donesearch = 1;
  875.             }
  876.         }            
  877.         } else {
  878.         printf("Error searching was %d, aborting\n", status);
  879.         return status;
  880.         }
  881.     }
  882.  
  883.     if (donesearch)
  884.         done = 1;
  885.     }
  886.         
  887.     /* did we find an acceptable location?                  */
  888.     /* if not we SHOULD try reshuffling existing partitions */
  889.     /* but for now we just give up                          */
  890.     if (!done) {
  891.     return FDISK_ERR_NOFREE;
  892.     }
  893.  
  894.     return FDISK_SUCCESS;
  895. }
  896.  
  897.  
  898. /* not sure what this will be good for yet */
  899. #if 0
  900.  
  901. /* moves a non-extended primary partition to new location specified in */
  902. /* the partition p                                                     */
  903. int fdiskMovePrimary( HardDrive *hd, unsigned int num, Partition *p ) {
  904.  
  905.     fdiskSetAttrPartition( hd, num, &p);
  906.  
  907. }
  908.  
  909. /* krunch partition table so all moveable partitions form contiguous block */
  910. /* will not slide logical partitions out of an extended partition, instead */
  911. /* the extended partition start is slid and logical partitions move inside */
  912. /* the extended partition. This way the # of primary partition slots used  */
  913. /* is kept constant.                                                       */
  914. /* we try to push available free space towards the start of the disk       */
  915. int fdiskKrunchPartitionTable( HardDrive *hd ) {
  916.  
  917.     unsigned int last, first, cur;
  918.     unsigned int csize,  lsize,  msize, asize;
  919.     unsigned int cstart, lstart, mstart, astart;
  920.     unsigned int endfree, startfree, sizefree;
  921.     unsigned lastfree;
  922.     int      i;
  923.     SpaceMap *freespace;
  924.     SpaceMapEntry testentry;
  925.     Partition tstp;
  926.     Partition *p, *ep;
  927.  
  928.     /* make sure there are any partitions to process */
  929.     if (fdiskLastPartition(hd, &last ) == FDISK_ERR_BADNUM)
  930.     return FDISK_ERR_BADNUM;
  931.     
  932.     /*  - look through freespace list                                    */
  933.     /*  - if adjacent, movable partition exists, slide to close space    */
  934.     /*    otherwise, find movable partitions to move to close   space    */
  935.     /*  - if we made any changes, recompute freespace map                */
  936.     /*  - keep going till we change nothing                              */
  937.     /*                                                                   */
  938.     /* First look at primary partitions, shift/relocate them if possible */
  939.     done      = 0;
  940.     lastfree  = hd->totalsectors;
  941.     freespace = NULL;
  942.     while (!done) {
  943.  
  944.     /* get a freespace map for the drive first */
  945.     fdiskFreeMapGen( hd, &freespace );
  946.     if (!freespace->num)
  947.         break;
  948.  
  949.     /* locate next free space to consider */
  950.     for (i=0; i < freespace->num; i++)
  951.         if (freespace->entry[i].start < lastfree)
  952.         break;
  953.  
  954.     /* couldnt find any more freespace to consider */
  955.     if (i == freespace->num)
  956.         break;
  957.     
  958.     /* locate primary partition closest to freespace on the high side */
  959.     startfree = freespace->entry[i].start;
  960.     sizefree = freespace->entry[i].size;
  961.     endfree   = startfree + sizefree - 1;
  962.  
  963.     mindiff = FDISK_SIZE_MAX;
  964.     minnum  = 0;
  965.     for (cur=1; cur <=4; cur++) {
  966.         if (fdiskGetAttrPartition( hd, cur, &p))
  967.         continue;
  968.  
  969.         if (p->immutable) {
  970.         free(p);
  971.         continue;
  972.         }
  973.         
  974.         fdiskGetConstraint(&p->start,&cstart,&lstart,&mstart,&astart );
  975.         fdiskGetConstraint(&p->size, &csize, &lsize, &msize, &asize  );
  976.  
  977.         if (cstart < startfree) {
  978.         tmpdiff = startfree - cstart;
  979.         if (tmpdiff < mindiff) {
  980.             mindiff = tmpdiff;
  981.             minnum  = cur;
  982.         }
  983.         }
  984.         free(p);
  985.     }
  986.  
  987.     /* see if we found anything */
  988.     if ( minnum != 0 ) {
  989.         fdiskGetAttrPartition( hd, minnum, &p);
  990.  
  991.         if (!fdiskIsExtended(p->type.current)) {
  992.         /* its a simple primary partition               */
  993.         /* see if we can move the partition and satisfy */
  994.         /* any constraints if may have on its location  */
  995.         /* if it works, move the partition and update   */
  996.         /* last free considered                         */
  997.         fdiskGetConstraint(&p->start,&cstart,
  998.                    &lstart,&mstart,&astart );
  999.         fdiskGetConstraint(&p->size, &csize,
  1000.                    &lsize, &msize, &asize  );
  1001.         startfree = freespace->entry[minnum].start;
  1002.         sizefree  = freespace->entry[minnum].size;
  1003.         endfree   = startfree + sizefree - 1;
  1004.  
  1005.         /* setup new location and round to a cyl boundary */
  1006.         /* if rounding makes the partition smaller, move  */
  1007.         /* start back another cylinder and try again      */
  1008.         /* primary partitions always start on a cylinder  */
  1009.         /* boundary (except for the one containing the MBR*/
  1010.         testentry.start = endfree - csize;
  1011.         fdiskRoundStartToCylinder( hd, &cstart );
  1012.         testentry.size  = endfree - cstart + 1;
  1013.         if (testentry.size < csize)
  1014.             testentry.start -= hd->geom.sectors*hd->geom.heads;
  1015.         testentry.size  = csize;
  1016.         
  1017.         if (fdiskCheckContraints(hd, &testentry,
  1018.                      p, PRIMARY ) == FDISK_SUCCESS) {
  1019.             fdiskMovePrimary(hd, minnum, p);
  1020.             fdiskGetConstraint(&p->start,&cstart,
  1021.                        &lstart,&mstart,&astart );
  1022.             fdiskGetConstraint(&p->size, &csize,
  1023.                        &lsize, &msize, &asize  );
  1024.             lastfree = cstart + csize;
  1025.         }
  1026.         } else {
  1027.         /* its a primary extended partition, lots more to do!  */
  1028.         /* have to also relocate all logical partitions inside */
  1029.         if (fdiskCheckContraints(hd, &freespace->entry[i],
  1030.                      p, EXTENDED ) == FDISK_SUCCESS) {
  1031.             fdiskMovePrimaryExtended( hd, minnum, p );
  1032.             fdiskGetConstraint(&p->start,&cstart,
  1033.                        &lstart,&mstart,&astart );
  1034.             fdiskGetConstraint(&p->size, &csize,
  1035.                        &lsize, &msize, &asize  );
  1036.             lastfree = cstart + csize;
  1037.         }
  1038.  
  1039.         }
  1040.     } else {
  1041.         done = 1;
  1042.     }
  1043.     
  1044.     /* anything left allocated? */
  1045.     if (freespace != NULL) {
  1046.         fdiskSpaceMapFree( freespace );
  1047.         freespace = NULL;
  1048.     }
  1049.     }
  1050.  
  1051.     /* anything left allocated? */
  1052.     if (freespace != NULL) {
  1053.     fdiskSpaceMapFree( freespace );
  1054.     freespace = NULL;
  1055.     }
  1056.     
  1057. }
  1058. #endif
  1059.  
  1060.  
  1061. /* given a list of requested partitions, take hdarr as starting point.  */
  1062. /* stick partitions into nhdarr                                         */
  1063. /* wecare controls whether we record reason for failures or not         */
  1064. int fdiskAutoInsertPartitions( HardDrive **hdarr,    unsigned int numhd,
  1065.                    HardDrive **newhdarr, int wecare, 
  1066.                    PartitionSpec *spec ) {
  1067.     unsigned int i;
  1068.     int          status;
  1069.     /* copy existing hard drive structure into the new hard drive struct */
  1070.     for (i=0; i < numhd; i++) 
  1071.     memcpy(newhdarr[i], hdarr[i], sizeof(HardDrive));
  1072.  
  1073.     /* start inserting the partitions */
  1074.     /* set the last alloc error to undef */
  1075.     LastAllocStat = ALLOC_UNDEF;
  1076.     for (i=0; i<spec->num; i++) {
  1077.     if (spec->entry[i].status != REQUEST_ORIGINAL) {
  1078.         status = fdiskAutoInsertPartition( newhdarr, numhd,
  1079.                            &spec->entry[i].partition );
  1080.         if (status == FDISK_SUCCESS) {
  1081.         spec->entry[i].status = REQUEST_GRANTED;
  1082.         if (wecare)
  1083.             spec->entry[i].reason = ALLOC_OK;
  1084.         } else {
  1085.         spec->entry[i].status = REQUEST_DENIED;
  1086.         if (wecare)
  1087.             spec->entry[i].reason = LastAllocStat;
  1088.         }
  1089.     }
  1090.     }
  1091.     
  1092.     return FDISK_SUCCESS;
  1093. }
  1094.  
  1095. /*                                                                   */
  1096. /* growing routines                                                  */
  1097. /* these routines take an existing array for drives and a partspec   */
  1098. /* and grow the partitions marked for growth to fill available space */
  1099.  
  1100. /* this should work but is VERY messy!!!!! */
  1101. /* uses internals of partitions and partitions specs too much */
  1102. /* needs to be rewritten to use functions to get/set values   */
  1103. int fdiskGrowPartitions( HardDrive **hdarr, unsigned int numhd,
  1104.              HardDrive **newhdarr, 
  1105.              PartitionSpec *spec ) {
  1106.  
  1107.     PartitionSpec trialspec, startspec, origspec;
  1108.     Partition     *p;
  1109.     unsigned int  *freespace, *usedbygrow;
  1110.     unsigned int  min, max, cur, dif, ldif;
  1111.     int           j, k, l;
  1112.     int           statcur;
  1113.     float         f;
  1114.     
  1115.     /* copy existing partition spec in a safe place  */
  1116.     /* we make new copies of the 'names' field, since its malloc'd */
  1117.     memcpy(&startspec, spec, sizeof(PartitionSpec));
  1118.     for (j=0; j<spec->num; j++) {
  1119.     /* copy the name */
  1120.     if (spec->entry[j].name)
  1121.         startspec.entry[j].name = strdup(spec->entry[j].name);
  1122.  
  1123.     /* if request was granted, lock partition to drive its on currently */
  1124.     if (spec->entry[j].status == REQUEST_GRANTED) {
  1125.         startspec.entry[j].status = REQUEST_PENDING;
  1126.         p = &startspec.entry[j].partition;
  1127.         fdiskDeactivateAllDriveSet( &p->drive );
  1128.         fdiskActivateDriveSet( &p->drive, p->drive.current );
  1129.     }    
  1130.     }
  1131.  
  1132.     /* go thru and weed out the denied partitions */
  1133.     for (j=0; j<spec->num; j++)
  1134.     if (spec->entry[j].status == REQUEST_DENIED)
  1135.         fdiskDeletePartitionSpec(&startspec, spec->entry[j].name);
  1136.         
  1137.     /* make array of freespace left on each drive */
  1138.     freespace  = (unsigned int *) alloca(numhd*sizeof(unsigned int));
  1139.     usedbygrow = (unsigned int *) alloca(numhd*sizeof(unsigned int));
  1140.     for (j=0; j<numhd; j++) {
  1141.     freespace[j] = hdarr[j]->totalsectors;
  1142.     usedbygrow[j] = 0;
  1143.     }
  1144.     
  1145.     for (j=0; j<startspec.num; j++) {
  1146.     p = &startspec.entry[j].partition;
  1147.     if (fdiskIsExtended(p->type.current))
  1148.         continue;
  1149.         
  1150.     for (k=0; k<numhd; k++)
  1151.         if (hdarr[k]->num == p->drive.current)
  1152.         break;
  1153.  
  1154.     if (k==numhd) /* shouldnt happen */
  1155.         continue;
  1156.     
  1157.     freespace[k] -= p->size.current;
  1158.  
  1159.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1160.         continue;
  1161.     usedbygrow[k] += p->size.current;
  1162.     }
  1163.  
  1164.     /* now grow them */
  1165.     memcpy(&trialspec, &startspec, sizeof(PartitionSpec));
  1166.     for (j=0; j<startspec.num; j++) {
  1167.     p = &startspec.entry[j].partition;
  1168.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1169.         continue;
  1170.     
  1171.     for (k=0; k<numhd; k++)
  1172.         if (hdarr[k]->num == p->drive.current)
  1173.         break;
  1174.  
  1175.     if (k==numhd) /* shouldnt happen */
  1176.         continue;
  1177.  
  1178.     /* OK, this is the ugliest binary search ever coded. */
  1179.     min = 0;
  1180.     if (usedbygrow[k] != 0)
  1181.         f = ((float)p->size.current/(float)usedbygrow[k]);
  1182.     else
  1183.         f = 0; /* shouldnt happen */
  1184.     max = (unsigned int)((f*(float)freespace[k])+0.5);
  1185.     cur = max - (max-min)/2; /* might help with rounding */
  1186.     dif = max - min;
  1187.     ldif = 0;
  1188.  
  1189.     while (min != max && ldif != dif) {
  1190.         trialspec.entry[j].status   = REQUEST_PENDING;
  1191.         trialspec.entry[j].partition.size.min =
  1192.         startspec.entry[j].partition.size.min + cur;
  1193.         statcur = fdiskAutoInsertPartitions(hdarr, numhd, newhdarr, 0,
  1194.                            &trialspec);
  1195.  
  1196.         /* check to see if any partitions got lost, if so thats bad */
  1197.         for (l=0; l<trialspec.num; l++)
  1198.         if (trialspec.entry[l].status == REQUEST_DENIED) {
  1199.             statcur = FDISK_ERR_NOFREE;
  1200.             break;
  1201.         }
  1202.     
  1203.         if (statcur != FDISK_SUCCESS)
  1204.         max = cur;
  1205.         else
  1206.         min = cur;
  1207.  
  1208.         cur = max - (max-min)/2;
  1209.         ldif = dif;
  1210.         dif  = max - min;
  1211.     }
  1212.  
  1213.     /* store the final working size in trialspec */
  1214.     /* max COULD have failed, so we have to look */
  1215.     /* at result of last try with it to see if   */
  1216.     /* we should use it instead of min. Min val  */
  1217.     /* SHOULD always be a successful size.       */
  1218.     trialspec.entry[j].status   = REQUEST_PENDING;
  1219.     trialspec.entry[j].partition.size.min =
  1220.         startspec.entry[j].partition.size.min +
  1221.         ((statcur == FDISK_SUCCESS) ? cur : min);
  1222.     }
  1223.  
  1224.     /* we're done, copy into original partition spec and */
  1225.     /* insert one last time                              */
  1226.     memcpy(&origspec, spec, sizeof(PartitionSpec));
  1227.     for (j=0; j<startspec.num; j++) {
  1228.     p = &startspec.entry[j].partition;
  1229.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1230.         continue;
  1231.  
  1232.     for (k=0; k<spec->num; k++)
  1233.         if (!strcmp(trialspec.entry[j].name,spec->entry[k].name))
  1234.         break;
  1235.  
  1236.     if (k == spec->num) /* shouldnt happen */
  1237.         continue;
  1238.  
  1239.     spec->entry[k].partition.size.min=trialspec.entry[j].partition.size.min;
  1240.     spec->entry[k].status = REQUEST_PENDING;
  1241.     }
  1242.  
  1243.     fdiskAutoInsertPartitions(hdarr, numhd, newhdarr, 0, spec );
  1244.  
  1245.     /* now put the 'min' size back to what the user wanted */
  1246.     for (j=0; j<spec->num; j++) {
  1247.     p = &spec->entry[j].partition;
  1248.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1249.         continue;
  1250.  
  1251.     spec->entry[j].partition.size.min=origspec.entry[j].partition.size.min;
  1252.     }
  1253.     
  1254.     
  1255.     /* now clean up and leave */
  1256.     for (j=0; j<startspec.num; j++)
  1257.     free(startspec.entry[j].name);
  1258.     
  1259.     return FDISK_SUCCESS;
  1260. }
  1261.     
  1262.     
  1263.