salloc.c 2.6 KB

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