Subversion Repositories pentevo

Rev

Blame | Last modification | View Log | Download | RSS feed | ?url?

  1. /* chunks.c */
  2. /*****************************************************************************/
  3. /* SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only                     */
  4. /*                                                                           */
  5. /* AS-Portierung                                                             */
  6. /*                                                                           */
  7. /* Verwaltung von Adressbereichslisten                                       */
  8. /*                                                                           */
  9. /* Historie: 16. 5.1996 Grundsteinlegung                                     */
  10. /*           16. 8.1998 Min/Max-Ausgabe                                      */
  11. /*                                                                           */
  12. /*****************************************************************************/
  13.  
  14. #include "stdinc.h"
  15.  
  16. #include "strutil.h"
  17.  
  18. #include "chunks.h"
  19.  
  20. /*--------------------------------------------------------------------------*/
  21. /* eine Chunkliste initialisieren */
  22.  
  23. void InitChunk(ChunkList *NChunk)
  24. {
  25.   NChunk->RealLen = 0;
  26.   NChunk->AllocLen = 0;
  27.   NChunk->Chunks = NULL;
  28. }
  29.  
  30. void ClearChunk(ChunkList *NChunk)
  31. {
  32.   if (NChunk->AllocLen > 0)
  33.     free(NChunk->Chunks);
  34.   InitChunk(NChunk);
  35. }
  36.  
  37. /*--------------------------------------------------------------------------*/
  38. /* eine Chunkliste um einen Eintrag erweitern */
  39.  
  40. static Boolean Overlap(LargeWord Start1, LargeWord Len1, LargeWord Start2, LargeWord Len2)
  41. {
  42.   return ((Start1 == Start2)
  43.        || ((Start2 > Start1) && (Start1 + Len1 >= Start2))
  44.        || ((Start1 > Start2) && (Start2 + Len2 >= Start1)));
  45. }
  46.  
  47. static void SetChunk(OneChunk *NChunk,
  48.                      LargeWord Start1, LargeWord Len1,
  49.                      LargeWord Start2, LargeWord Len2)
  50. {
  51.   NChunk->Start  = min(Start1, Start2);
  52.   NChunk->Length = max(Start1 + Len1 - 1, Start2 + Len2 - 1) - NChunk->Start + 1;
  53. }
  54.  
  55. static void IncChunk(ChunkList *NChunk)
  56. {
  57.   if (NChunk->RealLen + 1 > NChunk->AllocLen)
  58.   {
  59.     if (NChunk->RealLen == 0)
  60.       NChunk->Chunks = (OneChunk *) malloc(sizeof(OneChunk));
  61.     else
  62.       NChunk->Chunks = (OneChunk *) realloc(NChunk->Chunks, sizeof(OneChunk) * (NChunk->RealLen + 1));
  63.     NChunk->AllocLen = NChunk->RealLen + 1;
  64.   }
  65. }
  66.  
  67. Boolean AddChunk(ChunkList *NChunk, LargeWord NewStart, LargeWord NewLen, Boolean Warn)
  68. {
  69.   Word z, f1 = 0, f2 = 0;
  70.   Boolean Found;
  71.   LongWord PartSum;
  72.   Boolean Result;
  73.  
  74.   Result = False;
  75.  
  76.   if (NewLen == 0)
  77.     return Result;
  78.  
  79.   /* herausfinden, ob sich das neue Teil irgendwo mitanhaengen laesst */
  80.  
  81.   Found = False;
  82.   for (z = 0; z < NChunk->RealLen; z++)
  83.     if (Overlap(NewStart, NewLen, NChunk->Chunks[z].Start, NChunk->Chunks[z].Length))
  84.     {
  85.       Found = True;
  86.       f1 = z;
  87.       break;
  88.     }
  89.  
  90.   /* Fall 1: etwas gefunden : */
  91.  
  92.   if (Found)
  93.   {
  94.     /* gefundene Chunk erweitern */
  95.  
  96.     PartSum = NChunk->Chunks[f1].Length + NewLen;
  97.     SetChunk(NChunk->Chunks + f1, NewStart, NewLen, NChunk->Chunks[f1].Start, NChunk->Chunks[f1].Length);
  98.     if (Warn)
  99.       if (PartSum != NChunk->Chunks[f1].Length) Result = True;
  100.  
  101.     /* schauen, ob sukzessiv neue Chunks angebunden werden koennen */
  102.  
  103.     do
  104.     {
  105.       Found = False;
  106.       for (z = 1; z < NChunk->RealLen; z++)
  107.         if (z != f1)
  108.          if (Overlap(NChunk->Chunks[z].Start, NChunk->Chunks[z].Length, NChunk->Chunks[f1].Start, NChunk->Chunks[f1].Length))
  109.          {
  110.            Found = True;
  111.            f2 = z; break;
  112.          }
  113.       if (Found)
  114.       {
  115.         SetChunk(NChunk->Chunks + f1, NChunk->Chunks[f1].Start, NChunk->Chunks[f1].Length, NChunk->Chunks[f2].Start, NChunk->Chunks[f2].Length);
  116.         NChunk->Chunks[f2] = NChunk->Chunks[--NChunk->RealLen];
  117.       }
  118.     }
  119.     while (Found);
  120.   }
  121.  
  122.   /* ansonsten Feld erweitern und einschreiben */
  123.  
  124.   else
  125.   {
  126.     IncChunk(NChunk);
  127.  
  128.     NChunk->Chunks[NChunk->RealLen].Length = NewLen;
  129.     NChunk->Chunks[NChunk->RealLen].Start = NewStart;
  130.     NChunk->RealLen++;
  131.   }
  132.  
  133.   return Result;
  134. }
  135.  
  136. /*--------------------------------------------------------------------------*/
  137. /* Ein Stueck wieder austragen */
  138.  
  139. void DeleteChunk(ChunkList *NChunk, LargeWord DelStart, LargeWord DelLen)
  140. {
  141.   Word z;
  142.   LargeWord OStart;
  143.  
  144.   if (DelLen == 0)
  145.     return;
  146.  
  147.   z = 0;
  148.   while (z <= NChunk->RealLen)
  149.   {
  150.     if (Overlap(DelStart, DelLen, NChunk->Chunks[z].Start, NChunk->Chunks[z].Length))
  151.     {
  152.       if (NChunk->Chunks[z].Start >= DelStart)
  153.       {
  154.         if (DelStart + DelLen >= NChunk->Chunks[z].Start + NChunk->Chunks[z].Length)
  155.         {
  156.           /* ganz loeschen */
  157.           NChunk->Chunks[z] = NChunk->Chunks[--NChunk->RealLen];
  158.         }
  159.         else
  160.         {
  161.           /* unten abschneiden */
  162.           OStart = NChunk->Chunks[z].Start;
  163.           NChunk->Chunks[z].Start = DelStart + DelLen;
  164.           NChunk->Chunks[z].Start -= NChunk->Chunks[z].Start - OStart;
  165.         }
  166.       }
  167.       else
  168.        if (DelStart + DelLen >= NChunk->Chunks[z].Start + NChunk->Chunks[z].Length)
  169.        {
  170.          /* oben abschneiden */
  171.          NChunk->Chunks[z].Length = DelStart - NChunk->Chunks[z].Start;
  172.          /* wenn Laenge 0, ganz loeschen */
  173.          if (NChunk->Chunks[z].Length == 0)
  174.          {
  175.            NChunk->Chunks[z] = NChunk->Chunks[--NChunk->RealLen];
  176.          }
  177.        }
  178.        else
  179.        {
  180.          /* teilen */
  181.          IncChunk(NChunk);
  182.          NChunk->Chunks[NChunk->RealLen].Start = DelStart + DelLen;
  183.          NChunk->Chunks[NChunk->RealLen].Length = NChunk->Chunks[z].Start + NChunk->Chunks[z].Length-NChunk->Chunks[NChunk->RealLen].Start;
  184.          NChunk->Chunks[z].Length = DelStart - NChunk->Chunks[z].Start;
  185.        }
  186.     }
  187.     z++;
  188.   }
  189. }
  190.  
  191. /*--------------------------------------------------------------------------*/
  192. /* check whether address is in chunk */
  193.  
  194. Boolean AddressInChunk(ChunkList *NChunk, LargeWord Address)
  195. {
  196.   Word z;
  197.  
  198.   for (z = 0; z < NChunk->RealLen; z++)
  199.   {
  200.     if ((NChunk->Chunks[z].Start <= Address)
  201.      && (NChunk->Chunks[z].Start + NChunk->Chunks[z].Length - 1 >= Address))
  202.       return True;
  203.   }
  204.   return False;
  205. }
  206.  
  207. /*--------------------------------------------------------------------------*/
  208. /* Minimaladresse holen */
  209.  
  210. LargeWord ChunkMin(ChunkList *NChunk)
  211. {
  212.   LongInt z;
  213.   LargeWord t = (LargeWord) -1;
  214.  
  215.   if (NChunk->RealLen == 0)
  216.     return 0;
  217.  
  218.   for (z = 0; z < NChunk->RealLen; z++)
  219.     if (NChunk->Chunks[z].Start < t)
  220.       t = NChunk->Chunks[z].Start;
  221.  
  222.   return t;
  223. }
  224.  
  225. /*--------------------------------------------------------------------------*/
  226. /* Maximaladresse holen */
  227.  
  228. LargeWord ChunkMax(ChunkList *NChunk)
  229. {
  230.   LongInt z;
  231.   LargeWord t = (LargeWord) 0;
  232.  
  233.   if (NChunk->RealLen == 0) return 0;
  234.  
  235.   for (z = 0; z < NChunk->RealLen; z++)
  236.     if (NChunk->Chunks[z].Start + NChunk->Chunks[z].Length - 1 > t)
  237.       t = NChunk->Chunks[z].Start + NChunk->Chunks[z].Length - 1;
  238.  
  239.   return t;
  240. }
  241.  
  242. /*--------------------------------------------------------------------------*/
  243. /* Menge holen */
  244.  
  245. LargeWord ChunkSum(ChunkList *NChunk)
  246. {
  247.   LongInt z;
  248.   LargeWord Sum = 0;
  249.  
  250.   for (z = 0; z < NChunk->RealLen; z++)
  251.     Sum += NChunk->Chunks[z].Length;
  252.  
  253.   return Sum;
  254. }
  255.  
  256. /*--------------------------------------------------------------------------*/
  257. /* sort by address */
  258.  
  259. static int CompareChunk(const void *c1, const void *c2)
  260. {
  261.   const OneChunk *pChunk1 = (const OneChunk*)c1,
  262.                  *pChunk2 = (const OneChunk*)c2;
  263.  
  264.   if (pChunk1->Start < pChunk2->Start)
  265.     return -1;
  266.   else if (pChunk1->Start > pChunk2->Start)
  267.     return 1;
  268.   else
  269.     return 0;
  270. }
  271.  
  272. void SortChunks(ChunkList *NChunk)
  273. {
  274.   qsort(NChunk->Chunks, NChunk->RealLen, sizeof(NChunk->Chunks[0]), CompareChunk);
  275. }
  276.  
  277. void chunks_init(void)
  278. {
  279. }
  280.