+
+/* Return the int64 number as a string. If the --human-readable option was
+ * specified, we may output the number in K, M, or G units. We can return
+ * up to 4 buffers at a time. */
+char *human_num(int64 num)
+{
+ static char bufs[4][128]; /* more than enough room */
+ static unsigned int n;
+ char *s;
+
+ n = (n + 1) % (sizeof bufs / sizeof bufs[0]);
+
+ if (human_readable) {
+ char units = '\0';
+ int mult = human_readable == 1 ? 1000 : 1024;
+ double dnum = 0;
+ if (num > mult*mult*mult) {
+ dnum = (double)num / (mult*mult*mult);
+ units = 'G';
+ } else if (num > mult*mult) {
+ dnum = (double)num / (mult*mult);
+ units = 'M';
+ } else if (num > mult) {
+ dnum = (double)num / mult;
+ units = 'K';
+ }
+ if (units) {
+ snprintf(bufs[n], sizeof bufs[0], "%.2f%c", dnum, units);
+ return bufs[n];
+ }
+ }
+
+ s = bufs[n] + sizeof bufs[0] - 1;
+ *s = '\0';
+
+ if (!num)
+ *--s = '0';
+ while (num) {
+ *--s = (char)(num % 10) + '0';
+ num /= 10;
+ }
+ return s;
+}
+
+/* Return the double number as a string. If the --human-readable option was
+ * specified, we may output the number in K, M, or G units. We use a buffer
+ * from human_num() to return our result. */
+char *human_dnum(double dnum, int decimal_digits)
+{
+ char *buf = human_num(dnum);
+ int len = strlen(buf);
+ if (isDigit(buf + len - 1)) {
+ /* There's extra room in buf prior to the start of the num. */
+ buf -= decimal_digits + 1;
+ snprintf(buf, len + decimal_digits + 2, "%.*f", decimal_digits, dnum);
+ }
+ return buf;
+}
+
+/* Return the date and time as a string. Some callers tweak returned buf. */
+char *timestring(time_t t)
+{
+ static char TimeBuf[200];
+ struct tm *tm = localtime(&t);
+ char *p;
+
+#ifdef HAVE_STRFTIME
+ strftime(TimeBuf, sizeof TimeBuf - 1, "%Y/%m/%d %H:%M:%S", tm);
+#else
+ strlcpy(TimeBuf, asctime(tm), sizeof TimeBuf);
+#endif
+
+ if ((p = strchr(TimeBuf, '\n')) != NULL)
+ *p = '\0';
+
+ return TimeBuf;
+}
+
+/**
+ * Sleep for a specified number of milliseconds.
+ *
+ * Always returns TRUE. (In the future it might return FALSE if
+ * interrupted.)
+ **/
+int msleep(int t)
+{
+ int tdiff = 0;
+ struct timeval tval, t1, t2;
+
+ gettimeofday(&t1, NULL);
+
+ while (tdiff < t) {
+ tval.tv_sec = (t-tdiff)/1000;
+ tval.tv_usec = 1000*((t-tdiff)%1000);
+
+ errno = 0;
+ select(0,NULL,NULL, NULL, &tval);
+
+ gettimeofday(&t2, NULL);
+ tdiff = (t2.tv_sec - t1.tv_sec)*1000 +
+ (t2.tv_usec - t1.tv_usec)/1000;
+ }
+
+ return True;
+}
+
+/* Determine if two time_t values are equivalent (either exact, or in
+ * the modification timestamp window established by --modify-window).
+ *
+ * @retval 0 if the times should be treated as the same
+ *
+ * @retval +1 if the first is later
+ *
+ * @retval -1 if the 2nd is later
+ **/
+int cmp_time(time_t file1, time_t file2)
+{
+ if (file2 > file1) {
+ if (file2 - file1 <= modify_window)
+ return 0;
+ return -1;
+ }
+ if (file1 - file2 <= modify_window)
+ return 0;
+ return 1;
+}
+
+
+#ifdef __INSURE__XX
+#include <dlfcn.h>
+
+/**
+ This routine is a trick to immediately catch errors when debugging
+ with insure. A xterm with a gdb is popped up when insure catches
+ a error. It is Linux specific.
+**/
+int _Insure_trap_error(int a1, int a2, int a3, int a4, int a5, int a6)
+{
+ static int (*fn)();
+ int ret;
+ char *cmd;
+
+ asprintf(&cmd, "/usr/X11R6/bin/xterm -display :0 -T Panic -n Panic -e /bin/sh -c 'cat /tmp/ierrs.*.%d ; gdb /proc/%d/exe %d'",
+ getpid(), getpid(), getpid());
+
+ if (!fn) {
+ static void *h;
+ h = dlopen("/usr/local/parasoft/insure++lite/lib.linux2/libinsure.so", RTLD_LAZY);
+ fn = dlsym(h, "_Insure_trap_error");
+ }
+
+ ret = fn(a1, a2, a3, a4, a5, a6);
+
+ system(cmd);
+
+ free(cmd);
+
+ return ret;
+}
+#endif
+
+#define MALLOC_MAX 0x40000000
+
+void *_new_array(unsigned long num, unsigned int size, int use_calloc)
+{
+ if (num >= MALLOC_MAX/size)
+ return NULL;
+ return use_calloc ? calloc(num, size) : malloc(num * size);
+}
+
+void *_realloc_array(void *ptr, unsigned int size, unsigned long num)
+{
+ if (num >= MALLOC_MAX/size)
+ return NULL;
+ if (!ptr)
+ return malloc(size * num);
+ return realloc(ptr, size * num);
+}
+
+/* Take a filename and filename length and return the most significant
+ * filename suffix we can find. This ignores suffixes such as "~",
+ * ".bak", ".orig", ".~1~", etc. */
+const char *find_filename_suffix(const char *fn, int fn_len, int *len_ptr)
+{
+ const char *suf, *s;
+ BOOL had_tilde;
+ int s_len;
+
+ /* One or more dots at the start aren't a suffix. */
+ while (fn_len && *fn == '.') fn++, fn_len--;
+
+ /* Ignore the ~ in a "foo~" filename. */
+ if (fn_len > 1 && fn[fn_len-1] == '~')
+ fn_len--, had_tilde = True;
+ else
+ had_tilde = False;
+
+ /* Assume we don't find an suffix. */
+ suf = "";
+ *len_ptr = 0;
+
+ /* Find the last significant suffix. */
+ for (s = fn + fn_len; fn_len > 1; ) {
+ while (*--s != '.' && s != fn) {}
+ if (s == fn)
+ break;
+ s_len = fn_len - (s - fn);
+ fn_len = s - fn;
+ if (s_len == 4) {
+ if (strcmp(s+1, "bak") == 0
+ || strcmp(s+1, "old") == 0)
+ continue;
+ } else if (s_len == 5) {
+ if (strcmp(s+1, "orig") == 0)
+ continue;
+ } else if (s_len > 2 && had_tilde
+ && s[1] == '~' && isDigit(s + 2))
+ continue;
+ *len_ptr = s_len;
+ suf = s;
+ if (s_len == 1)
+ break;
+ /* Determine if the suffix is all digits. */
+ for (s++, s_len--; s_len > 0; s++, s_len--) {
+ if (!isDigit(s))
+ return suf;
+ }
+ /* An all-digit suffix may not be that signficant. */
+ s = suf;
+ }
+
+ return suf;
+}
+
+/* This is an implementation of the Levenshtein distance algorithm. It
+ * was implemented to avoid needing a two-dimensional matrix (to save
+ * memory). It was also tweaked to try to factor in the ASCII distance
+ * between changed characters as a minor distance quantity. The normal
+ * Levenshtein units of distance (each signifying a single change between
+ * the two strings) are defined as a "UNIT". */
+
+#define UNIT (1 << 16)
+
+uint32 fuzzy_distance(const char *s1, int len1, const char *s2, int len2)
+{
+ uint32 a[MAXPATHLEN], diag, above, left, diag_inc, above_inc, left_inc;
+ int32 cost;
+ int i1, i2;
+
+ if (!len1 || !len2) {
+ if (!len1) {
+ s1 = s2;
+ len1 = len2;
+ }
+ for (i1 = 0, cost = 0; i1 < len1; i1++)
+ cost += s1[i1];
+ return (int32)len1 * UNIT + cost;
+ }
+
+ for (i2 = 0; i2 < len2; i2++)
+ a[i2] = (i2+1) * UNIT;
+
+ for (i1 = 0; i1 < len1; i1++) {
+ diag = i1 * UNIT;
+ above = (i1+1) * UNIT;
+ for (i2 = 0; i2 < len2; i2++) {
+ left = a[i2];
+ if ((cost = *((uchar*)s1+i1) - *((uchar*)s2+i2)) != 0) {
+ if (cost < 0)
+ cost = UNIT - cost;
+ else
+ cost = UNIT + cost;
+ }
+ diag_inc = diag + cost;
+ left_inc = left + UNIT + *((uchar*)s1+i1);
+ above_inc = above + UNIT + *((uchar*)s2+i2);
+ a[i2] = above = left < above
+ ? (left_inc < diag_inc ? left_inc : diag_inc)
+ : (above_inc < diag_inc ? above_inc : diag_inc);
+ diag = left;
+ }
+ }
+
+ return a[len2-1];
+}
+
+#define BB_SLOT_SIZE (16*1024) /* Desired size in bytes */
+#define BB_PER_SLOT_BITS (BB_SLOT_SIZE * 8) /* Number of bits per slot */
+#define BB_PER_SLOT_INTS (BB_SLOT_SIZE / 4) /* Number of int32s per slot */
+
+struct bitbag {
+ uint32 **bits;
+ int slot_cnt;
+};
+
+struct bitbag *bitbag_create(int max_ndx)
+{
+ struct bitbag *bb = new(struct bitbag);
+ bb->slot_cnt = (max_ndx + BB_PER_SLOT_BITS - 1) / BB_PER_SLOT_BITS;
+
+ if (!(bb->bits = (uint32**)calloc(bb->slot_cnt, sizeof (uint32*))))
+ out_of_memory("bitbag_create");
+
+ return bb;
+}
+
+void bitbag_set_bit(struct bitbag *bb, int ndx)
+{
+ int slot = ndx / BB_PER_SLOT_BITS;
+ ndx %= BB_PER_SLOT_BITS;
+
+ if (!bb->bits[slot]) {
+ if (!(bb->bits[slot] = (uint32*)calloc(BB_PER_SLOT_INTS, 4)))
+ out_of_memory("bitbag_set_bit");
+ }
+
+ bb->bits[slot][ndx/32] |= 1u << (ndx % 32);
+}
+
+#if 0 /* not needed yet */
+void bitbag_clear_bit(struct bitbag *bb, int ndx)
+{
+ int slot = ndx / BB_PER_SLOT_BITS;
+ ndx %= BB_PER_SLOT_BITS;
+
+ if (!bb->bits[slot])
+ return;
+
+ bb->bits[slot][ndx/32] &= ~(1u << (ndx % 32));
+}
+
+int bitbag_check_bit(struct bitbag *bb, int ndx)
+{
+ int slot = ndx / BB_PER_SLOT_BITS;
+ ndx %= BB_PER_SLOT_BITS;
+
+ if (!bb->bits[slot])
+ return 0;
+
+ return bb->bits[slot][ndx/32] & (1u << (ndx % 32)) ? 1 : 0;
+}
+#endif
+
+/* Call this with -1 to start checking from 0. Returns -1 at the end. */
+int bitbag_next_bit(struct bitbag *bb, int after)
+{
+ uint32 bits, mask;
+ int i, ndx = after + 1;
+ int slot = ndx / BB_PER_SLOT_BITS;
+ ndx %= BB_PER_SLOT_BITS;
+
+ mask = (1u << (ndx % 32)) - 1;
+ for (i = ndx / 32; slot < bb->slot_cnt; slot++, i = mask = 0) {
+ if (!bb->bits[slot])
+ continue;
+ for ( ; i < BB_PER_SLOT_INTS; i++, mask = 0) {
+ if (!(bits = bb->bits[slot][i] & ~mask))
+ continue;
+ /* The xor magic figures out the lowest enabled bit in
+ * bits, and the switch quickly computes log2(bit). */
+ switch (bits ^ (bits & (bits-1))) {
+#define LOG2(n) case 1u << n: return slot*BB_PER_SLOT_BITS + i*32 + n
+ LOG2(0); LOG2(1); LOG2(2); LOG2(3);
+ LOG2(4); LOG2(5); LOG2(6); LOG2(7);
+ LOG2(8); LOG2(9); LOG2(10); LOG2(11);
+ LOG2(12); LOG2(13); LOG2(14); LOG2(15);
+ LOG2(16); LOG2(17); LOG2(18); LOG2(19);
+ LOG2(20); LOG2(21); LOG2(22); LOG2(23);
+ LOG2(24); LOG2(25); LOG2(26); LOG2(27);
+ LOG2(28); LOG2(29); LOG2(30); LOG2(31);
+ }
+ return -1; /* impossible... */
+ }
+ }
+
+ return -1;
+}
+
+void *expand_item_list(item_list *lp, size_t item_size,
+ const char *desc, int incr)
+{
+ /* First time through, 0 <= 0, so list is expanded. */
+ if (lp->malloced <= lp->count) {
+ void *new_ptr;
+ size_t new_size = lp->malloced;
+ if (incr < 0)
+ new_size += -incr; /* increase slowly */
+ else if (new_size < (size_t)incr)
+ new_size += incr;
+ else
+ new_size *= 2;
+ new_ptr = realloc_array(lp->items, char, new_size * item_size);
+ if (verbose >= 4) {
+ rprintf(FINFO, "[%s] expand %s to %.0f bytes, did%s move\n",
+ who_am_i(), desc, (double)new_size * item_size,
+ new_ptr == lp->items ? " not" : "");
+ }
+ if (!new_ptr)
+ out_of_memory("expand_item_list");
+
+ lp->items = new_ptr;
+ lp->malloced = new_size;
+ }
+ return (char*)lp->items + (lp->count++ * item_size);
+}