+/*
+ * When a program attempts "storage compaction" as mentioned in the
+ * old malloc man page, it realloc's an already freed block. Usually
+ * this is the last block it freed; occasionally it might be farther
+ * back. We have to search all the free lists for the block in order
+ * to determine its bucket: 1st we make one pass thru the lists
+ * checking only the first block in each; if that fails we search
+ * ``realloc_srchlen'' blocks in each list for a match (the variable
+ * is extern so the caller can modify it). If that fails we just copy
+ * however many bytes was given to realloc() and hope it's not huge.
+ */
+#ifndef lint
+int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
+
+#endif /* lint */
+
+ptr_t
+realloc(cp, nbytes)
+ ptr_t cp;
+ size_t nbytes;
+{
+#ifndef lint
+ register U_int onb;
+ union overhead *op;
+ char *res;
+ register int i;
+ int was_alloced = 0;
+
+ if (cp == NULL)
+ return (malloc(nbytes));
+ op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead)));
+ if (op->ov_magic == MAGIC) {
+ was_alloced++;
+ i = op->ov_index;
+ }
+ else
+ /*
+ * Already free, doing "compaction".
+ *
+ * Search for the old block of memory on the free list. First, check the
+ * most common case (last element free'd), then (this failing) the last
+ * ``realloc_srchlen'' items free'd. If all lookups fail, then assume
+ * the size of the memory block being realloc'd is the smallest
+ * possible.
+ */
+ if ((i = findbucket(op, 1)) < 0 &&
+ (i = findbucket(op, realloc_srchlen)) < 0)
+ i = 0;
+
+ onb = ALIGN(nbytes + ALIGN(sizeof(union overhead)) + RSLOP);
+
+ /* avoid the copy if same size block */
+ if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2))))
+ return ((ptr_t) cp);
+ if ((res = malloc(nbytes)) == NULL)
+ return ((ptr_t) 0);
+ if (cp != res) /* common optimization */
+ bcopy(cp, res, nbytes);
+ if (was_alloced)
+ free(cp);
+ return (res);
+#else
+ if (cp && nbytes)
+ return ((ptr_t) 0);
+ else
+ return ((ptr_t) 0);
+#endif /* !lint */
+}
+
+
+
+#ifndef lint
+/*
+ * Search ``srchlen'' elements of each free list for a block whose
+ * header starts at ``freep''. If srchlen is -1 search the whole list.
+ * Return bucket number, or -1 if not found.
+ */
+static int
+findbucket(freep, srchlen)
+ union overhead *freep;
+ int srchlen;