buf.c 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246
  1. #include "buf.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <errno.h>
  6. #define CATCH(condition, msg, action) \
  7. if (condition) { perror(msg); action; }
  8. static Piece *pieceblk = NULL;
  9. static Piece **freeblk = NULL;
  10. static void pclean()
  11. {
  12. if (freeblk) free(freeblk);
  13. if (pieceblk) free(pieceblk);
  14. }
  15. /* adds `p` to `freeblk` and returns the last added `freeblk` item.
  16. If `p` is NULL, the last added `freeblk` item will be
  17. returned, or NULL if `freeblk` is empty.
  18. `freeblk` is dynamically allocated. */
  19. static Piece *pfree(Piece *p)
  20. {
  21. static size_t nblk = 0, nfree = 0, blksiz = 0;
  22. static const size_t allocsiz = BUFSIZ/sizeof(Piece *);
  23. if (!p) return (nfree == 0) ? NULL : freeblk[--nfree];
  24. if (nfree + 1 > allocsiz * nblk) {
  25. blksiz = (++nblk * allocsiz) * sizeof(Piece *);
  26. freeblk = realloc(freeblk, blksiz);
  27. }
  28. CATCH(!freeblk, "failed to allocate freeblk",
  29. exit(EXIT_FAILURE));
  30. return freeblk[nfree++] = p;
  31. }
  32. /* returns the next available `Piece` item in `pieceblk`.
  33. If `freeblk` is not empty, it's last item pointed to by it
  34. will be returned (recycling `pieceblk` items). The returned
  35. `Piece` will always have it's values set to 0.
  36. `pieceblk` is dynamically allocated. */
  37. static Piece *palloc()
  38. {
  39. Piece *p;
  40. static size_t nblk = 0, nalloc = 0, blksiz = 0;
  41. static const size_t allocsiz = BUFSIZ/sizeof(Piece);
  42. static int hook = 0;
  43. if ( !(p = pfree(NULL)) ) {
  44. if (nalloc + 1 > allocsiz * nblk) {
  45. blksiz = (++nblk * allocsiz) * sizeof(Piece);
  46. pieceblk = realloc(pieceblk, blksiz);
  47. }
  48. CATCH(!pieceblk, "failed to allocate pieceblk",
  49. exit(EXIT_FAILURE));
  50. if (hook == 0) hook = !atexit(pclean);
  51. p = &pieceblk[nalloc++];
  52. }
  53. return memset(p, 0, sizeof(Piece));
  54. }
  55. /* splits `p` into two `Piece` items. The values of `p` will be
  56. modified to fit the first `Piece`; a new `Piece` will be
  57. allocated for the second.
  58. The `prev` and `next` values of these & associated `Piece`
  59. items will be updated to reflect the split.
  60. `offset` should be the offset within `p->len` to split at.
  61. If offset is not within the boundry of `p->len`, then `p`
  62. will be returned. The *first* `Piece` in the split is
  63. returned. */
  64. static Piece *psplit(Piece *p, long int offset)
  65. {
  66. Piece *q = p;
  67. if (offset > 0 && offset <= (int)p->len) {
  68. q = palloc();
  69. memcpy(q, p, sizeof(Piece));
  70. q->off += offset;
  71. q->len -= p->len = offset;
  72. q->next = p->next;
  73. q->prev = p;
  74. p->next = q;
  75. if (q->next) q->next->prev = q;
  76. } else if (offset == 0) {
  77. q = palloc();
  78. q->next = p;
  79. p->prev = q;
  80. }
  81. return q;
  82. }
  83. /* pfind will find the `Piece` which contains index `pos`.
  84. The search starts from `p`, where the index is `idx`.
  85. `p` will be set to the found `Piece`.
  86. The new index will be returned. */
  87. static size_t pfind(Piece **ptr, size_t idx, size_t pos)
  88. {
  89. Piece *p = *ptr;
  90. if (pos >= idx) {
  91. while (pos >= idx + p->len && p->next) {
  92. idx += p->len;
  93. p = p->next;
  94. }
  95. } else {
  96. do {
  97. p = p->prev;
  98. idx -= p->len;
  99. } while (pos < idx && p->prev);
  100. }
  101. *ptr = p;
  102. return idx;
  103. }
  104. struct Buf *bufinit(FILE *read, FILE *append)
  105. {
  106. Buf *b = calloc(1, sizeof(Buf));
  107. if (!append) return NULL;
  108. b->read = read;
  109. b->append = append;
  110. b->tail = b->pos = b->head = palloc();
  111. b->pos->f = b->read;
  112. fseek(b->read, 0, SEEK_END);
  113. b->size = b->pos->len = ftell(b->read);
  114. return b;
  115. }
  116. void buffree(Buf *b)
  117. {
  118. Piece *p = b->tail->next;
  119. while (p) {
  120. pfree(p->prev);
  121. p = p->next;
  122. }
  123. free(b);
  124. }
  125. Piece *bufidx(Buf *b, size_t pos)
  126. {
  127. size_t offset, idx = pfind(&b->pos, b->idx, pos);
  128. if (idx != pos || idx == 0) {
  129. offset = (idx >= pos) ? idx - pos : pos - idx;
  130. b->pos = psplit(b->pos, offset);
  131. if (!b->pos->prev) b->tail = b->pos;
  132. if (!b->pos->next) b->head = b->pos;
  133. }
  134. b->idx = pos;
  135. return b->pos;
  136. }
  137. size_t bufins(Buf *b, size_t pos, const char *s)
  138. {
  139. const size_t slen = strlen(s);
  140. Piece *p;
  141. b->pos = bufidx(b, pos)->prev;
  142. if (!b->pos) b->pos = b->tail;
  143. p = palloc();
  144. p->f = b->append;
  145. p->off = ftell(b->append);
  146. p->len = slen;
  147. p->prev = b->pos;
  148. p->next = b->pos->next;
  149. b->pos->next = b->pos->next->prev = p;
  150. fprintf(b->append, "%s", s);
  151. CATCH(ferror(b->append), "bufins: write to append",
  152. { pfree(p); p = 0; });
  153. if (p != 0) {
  154. b->idx += slen;
  155. b->size += slen;
  156. b->pos = p->next;
  157. }
  158. return b->size;
  159. }
  160. size_t bufdel(Buf *b, size_t pos, int num)
  161. {
  162. size_t tmp;
  163. Piece *pre, *post;
  164. if (num < 0) {
  165. if ((int)pos-num < 0)
  166. num = pos;
  167. else {
  168. tmp = abs(num);
  169. num = pos;
  170. pos = (tmp > pos) ? 0 : tmp;
  171. }
  172. }
  173. if (pos+num > b->size) num = b->size - pos;
  174. pre = bufidx(b, pos)->prev;
  175. if (!pre) pre = b->tail;
  176. post = bufidx(b, pos+num);
  177. pre->next = post;
  178. post->prev = pre;
  179. b->idx = pos;
  180. return (b->size -= num);
  181. }
  182. size_t bufout(Buf *b, FILE *f)
  183. {
  184. size_t n, fsiz = 0;
  185. char buf[BUFSIZ];
  186. Piece *p = b->tail;
  187. do {
  188. if (p->len > 0 && p->f) {
  189. if ((size_t)ftell(p->f) != p->off)
  190. fseek(p->f, p->off, SEEK_SET);
  191. n = 0;
  192. do {
  193. buf[0] = '\0';
  194. fread(buf, 1, p->len, p->f);
  195. CATCH(ferror(p->f), "bufout: fread failed", break);
  196. fsiz += fwrite(buf, 1, p->len, f);
  197. CATCH(ferror(f), "bufout: fwrite failed", break);
  198. } while (p->len - (BUFSIZ*n++) > BUFSIZ);
  199. }
  200. p = p->next;
  201. } while(p);
  202. return fsiz;
  203. }