salloc.c 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. /*
  2. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  3. * See the copyright notice in the ACK home directory, in the file "Copyright".
  4. *
  5. * Author: Hans van Staveren
  6. */
  7. /*
  8. * Package for string allocation and garbage collection.
  9. * Call salloc(size) to get room for string.
  10. * Every now and then call garbage_collect() from toplevel.
  11. */
  12. #include <stdlib.h>
  13. #include "assert.h"
  14. #include "param.h"
  15. #include "tables.h"
  16. #include "types.h"
  17. #include <cgg_cg.h>
  18. #include "data.h"
  19. #include "result.h"
  20. #include "extern.h"
  21. #include "utils.h"
  22. #include "salloc.h"
  23. #define MAXSTAB 1500
  24. #define THRESHOLD 200
  25. char *stab[MAXSTAB];
  26. int nstab=0;
  27. string myalloc(int size)
  28. {
  29. string p;
  30. p = (string) malloc((unsigned)size);
  31. if (p==0)
  32. fatal("Out of memory");
  33. return(p);
  34. }
  35. void myfree(string p)
  36. {
  37. free(p);
  38. }
  39. void popstr(int nnstab)
  40. {
  41. int i;
  42. for (i=nnstab;i<nstab;i++)
  43. myfree(stab[i]);
  44. nstab = nnstab;
  45. }
  46. char *salloc(int size)
  47. {
  48. char *p;
  49. if (nstab==MAXSTAB)
  50. fatal("String table overflow");
  51. p = myalloc(size+1); /* extra room for terminating zero */
  52. stab[nstab++] = p;
  53. return(p);
  54. }
  55. int compar(const void *vp1, const void *vp2)
  56. {
  57. char **p1 = (char **)vp1;
  58. char **p2 = (char **)vp2;
  59. assert(*p1 != *p2);
  60. if (*p1 < *p2)
  61. return(-1);
  62. return(1);
  63. }
  64. void garbage_collect()
  65. {
  66. int i;
  67. struct emline *emlp;
  68. token_p tp;
  69. tkdef_p tdp;
  70. struct reginfo *rp;
  71. char **fillp,**scanp;
  72. char used[MAXSTAB]; /* could be bitarray */
  73. if (nstab<THRESHOLD)
  74. return;
  75. qsort((char *)stab,nstab,sizeof (char *),compar);
  76. for (i=0;i<nstab;i++)
  77. used[i]= FALSE;
  78. for(emlp=emlines;emlp<emlines+nemlines;emlp++)
  79. chkstr(emlp->em_soper,used);
  80. for (tp= fakestack;tp<&fakestack[stackheight];tp++) {
  81. if (tp->t_token== -1)
  82. continue;
  83. tdp = &tokens[tp->t_token];
  84. for (i=0;i<TOKENSIZE;i++)
  85. if (tdp->t_type[i] == EV_ADDR)
  86. chkstr(tp->t_att[i].aa.ea_str,used);
  87. }
  88. for (rp= machregs+1; rp<machregs+NREGS; rp++) {
  89. tp = &rp->r_contents;
  90. assert(tp->t_token != -1);
  91. tdp= &tokens[tp->t_token];
  92. for (i=0;i<TOKENSIZE;i++)
  93. if (tdp->t_type[i] == EV_ADDR)
  94. chkstr(tp->t_att[i].aa.ea_str,used);
  95. }
  96. for (i=0;i<nstab;i++)
  97. if (!used[i]) {
  98. myfree(stab[i]);
  99. stab[i]=0;
  100. }
  101. fillp=stab;
  102. for (scanp=stab;scanp<stab+nstab;scanp++)
  103. if (*scanp != 0)
  104. *fillp++ = *scanp;
  105. nstab = fillp-stab;
  106. }
  107. void chkstr(string str, char used[])
  108. {
  109. int low,middle,high;
  110. low=0; high=nstab-1;
  111. while (high>low) {
  112. middle= (low+high)>>1;
  113. if (str==stab[middle]) {
  114. used[middle]=1;
  115. return;
  116. }
  117. if (str<stab[middle])
  118. high = middle-1;
  119. else
  120. low = middle+1;
  121. }
  122. if (low==high) {
  123. if (str==stab[low]) {
  124. used[low]=1;
  125. }
  126. return;
  127. }
  128. }