MolLib/Missing.c

   1 /*
   2  *  Missing.c
   3  *  Molby
   4  */
   5
   6 #pragma mark ====== Below codes are distributed under GPL ======
   7
   8 /*
   9  *  Created by Toshi Nagata on 08/11/06.
  10  *  Copyright 2008 Toshi Nagata. All rights reserved.
  11
  12  This program is free software; you can redistribute it and/or modify
  13  it under the terms of the GNU General Public License as published by
  14  the Free Software Foundation version 2 of the License.
  15
  16  This program is distributed in the hope that it will be useful,
  17  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  GNU General Public License for more details.
  20  */
  21
  22 #include "Missing.h"
  23
  24 /*
  25  *  Utility function
  26  *  Filename handling
  27  */
  28 #if defined(__WXMSW__) || defined(__CMDMSW__)
  29 #include <windows.h>
  30 void
  31 translate_char(char *p, int from, int to)
  32 {
  33         while (*p != 0) {
  34                 if ((unsigned char)*p == from)
  35                         *p = to;
  36                 p = CharNext(p);
  37         }
  38 }
  39 void
  40 fix_dosish_path(char *p)
  41 {
  42         translate_char(p, '/', '\\');
  43 }
  44 #else
  45 void
  46 translate_char(char *p, int from, int to)
  47 {
  48 }
  49 void
  50 fix_dosish_path(char *p)
  51 {
  52 }
  53 #endif
  54
  55 #if MISSING_STRDUP
  56
  57 char *
  58 _strdup(const char *src)
  59 {
  60         char *s = (char *)malloc(strlen(src) + 1);
  61         if (s != NULL)
  62                 strcpy(s, src);
  63         return s;
  64 }
  65
  66 wchar_t *
  67 _wcsdup(const wchar_t *src)
  68 {
  69         wchar_t *dst;
  70         size_t len;
  71
  72         len = wcslen(src) + 1;
  73         dst = (wchar_t *)malloc(len * sizeof(wchar_t));
  74         if (dst == NULL)
  75                 return NULL;
  76         wmemcpy(dst, src, len);
  77         return dst;
  78 }
  79 char *strdup(const char *src) { return _strdup(src); }
  80 wchar_t *wcsdup(const wchar_t *src) { return _wcsdup(src); }
  81
  82 #endif
  83
  84 #if MISSING_STRSEP
  85
  86 char *
  87 strpbrk(const char *cs, const char *ct)
  88 {
  89         const char *sc1,*sc2;
  90
  91         for (sc1 = cs; *sc1 != '\0'; sc1++) {
  92                 for (sc2 = ct; *sc2 != '\0'; sc2++) {
  93                         if (*sc1 == *sc2)
  94                                 return (char *)sc1;
  95                 }
  96         }
  97         return NULL;
  98 }
  99
 100 char *
 101 strsep(char **stringp, const char *delim)
 102 {
 103         char *start = *stringp;
 104         char *ptr;
 105
 106         if (!start)
 107                 return NULL;
 108
 109         if (!*delim)
 110                 ptr = start + strlen(start);
 111         else {
 112                 ptr = strpbrk(start, delim);
 113                 if (!ptr) {
 114                         *stringp = NULL;
 115                         return start;
 116         }
 117     }
 118
 119         *ptr = '\0';
 120         *stringp = ptr + 1;
 121
 122         return start;
 123 }
 124
 125 #endif
 126
 127 #if MISSING_ASPRINTF
 128 #include <stdlib.h>
 129 #include <stdio.h>
 130 #include <errno.h>
 131
 132 int
 133 vasprintf(char **ret, const char *fmt, va_list ap)
 134 {
 135         int size = 128;
 136         char *buf;
 137         buf = (char *)malloc(size);
 138         if (buf == NULL) {
 139                 *ret = NULL;
 140                 errno = ENOMEM;
 141                 return -1;
 142         }
 143         while (1) {
 144                 int n = vsnprintf(buf, size, fmt, ap);
 145                 if (n < 0)
 146                         break;
 147                 if (n >= size) {
 148                         size *= 2;
 149                         buf = (char *)realloc(buf, size);
 150                         if (buf == NULL)
 151                                 break;
 152                         continue;
 153                 } else {
 154                         *ret = buf;
 155                         return n;
 156                 }
 157         }
 158         *ret = NULL;
 159         errno = ENOMEM;
 160         return -1;
 161 }
 162
 163 int
 164 asprintf(char **ret, const char *fmt, ...)
 165 {
 166         int retval;
 167         va_list ap;
 168         va_start(ap, fmt);
 169         retval = vasprintf(ret, fmt, ap);
 170         va_end(ap);
 171         return (retval);
 172 }
 173
 174 #endif /* MISSING_ASPRINTF */
 175
 176 #pragma mark ====== Below codes are distributed under the BSD License =======
 177
 178 #if MISSING_STRTOK_R
 179 #include <string.h>
 180 /*-
 181  * Copyright (c) 1998 Softweyr LLC.  All rights reserved.
 182  *
 183  * strtok_r, from Berkeley strtok
 184  * Oct 13, 1998 by Wes Peters <wes@softweyr.com>
 185  *
 186  * Copyright (c) 1988, 1993
 187  *      The Regents of the University of California.  All rights reserved.
 188  *
 189  * Redistribution and use in source and binary forms, with or without
 190  * modification, are permitted provided that the following conditions
 191  * are met:
 192  * 1. Redistributions of source code must retain the above copyright
 193  *    notices, this list of conditions and the following disclaimer.
 194  * 2. Redistributions in binary form must reproduce the above copyright
 195  *    notices, this list of conditions and the following disclaimer in the
 196  *    documentation and/or other materials provided with the distribution.
 197  * 3. All advertising materials mentioning features or use of this software
 198  *    must display the following acknowledgement:
 199  *      This product includes software developed by Softweyr LLC, the
 200  *      University of California, Berkeley, and its contributors.
 201  * 4. Neither the name of the University nor the names of its contributors
 202  *    may be used to endorse or promote products derived from this software
 203  *    without specific prior written permission.
 204  *
 205  * THIS SOFTWARE IS PROVIDED BY SOFTWEYR LLC, THE REGENTS AND CONTRIBUTORS
 206  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 207  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 208  * PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL SOFTWEYR LLC, THE
 209  * REGENTS, OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 210  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 211  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 212  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 213  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 214  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 215  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 216  */
 217
 218 char *
 219 strtok_r(char *s, const char *delim, char **last)
 220 {
 221         char *spanp, *tok;
 222         int c, sc;
 223
 224         if (s == NULL && (s = *last) == NULL)
 225                 return (NULL);
 226
 227         /*
 228          * Skip (span) leading delimiters (s += strspn(s, delim), sort of).
 229          */
 230 cont:
 231         c = *s++;
 232         for (spanp = (char *)delim; (sc = *spanp++) != 0;) {
 233                 if (c == sc)
 234                         goto cont;
 235         }
 236
 237         if (c == 0) {           /* no non-delimiter characters */
 238                 *last = NULL;
 239                 return (NULL);
 240         }
 241         tok = s - 1;
 242
 243         /*
 244          * Scan token (scan for delimiters: s += strcspn(s, delim), sort of).
 245          * Note that delim must have one NUL; we stop if we see that, too.
 246          */
 247         for (;;) {
 248                 c = *s++;
 249                 spanp = (char *)delim;
 250                 do {
 251                         if ((sc = *spanp++) == c) {
 252                                 if (c == 0)
 253                                         s = NULL;
 254                                 else
 255                                         s[-1] = '\0';
 256                                 *last = s;
 257                                 return (tok);
 258                         }
 259                 } while (sc != 0);
 260         }
 261         /* NOTREACHED */
 262 }
 263 #endif /* MISSING_STRTOK_R */
 264
 265 #if MISSING_MERGESORT
 266 /*-
 267  * Copyright (c) 1992, 1993
 268  *      The Regents of the University of California.  All rights reserved.
 269  *
 270  * This code is derived from software contributed to Berkeley by
 271  * Peter McIlroy.
 272  *
 273  * Redistribution and use in source and binary forms, with or without
 274  * modification, are permitted provided that the following conditions
 275  * are met:
 276  * 1. Redistributions of source code must retain the above copyright
 277  *    notice, this list of conditions and the following disclaimer.
 278  * 2. Redistributions in binary form must reproduce the above copyright
 279  *    notice, this list of conditions and the following disclaimer in the
 280  *    documentation and/or other materials provided with the distribution.
 281  * 3. All advertising materials mentioning features or use of this software
 282  *    must display the following acknowledgement:
 283  *      This product includes software developed by the University of
 284  *      California, Berkeley and its contributors.
 285  * 4. Neither the name of the University nor the names of its contributors
 286  *    may be used to endorse or promote products derived from this software
 287  *    without specific prior written permission.
 288  *
 289  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 290  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 291  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 292  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 293  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 294  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 295  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 296  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 297  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 298  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 299  * SUCH DAMAGE.
 300  */
 301
 302 #if defined(LIBC_SCCS) && !defined(lint)
 303 static char sccsid[] = "@(#)merge.c     8.2 (Berkeley) 2/14/94";
 304 #endif /* LIBC_SCCS and not lint */
 305 //#include <sys/cdefs.h>
 306 //__FBSDID("$FreeBSD: src/lib/libc/stdlib/merge.c,v 1.6 2002/03/21 22:48:42 obrien Exp $");
 307
 308 /*
 309  * Hybrid exponential search/linear search merge sort with hybrid
 310  * natural/pairwise first pass.  Requires about .3% more comparisons
 311  * for random data than LSMS with pairwise first pass alone.
 312  * It works for objects as small as two bytes.
 313  */
 314
 315 #define NATURAL
 316 #define THRESHOLD 16    /* Best choice for natural merge cut-off. */
 317
 318 /* #define NATURAL to get hybrid natural merge.
 319  * (The default is pairwise merging.)
 320  */
 321
 322 #include <sys/types.h>
 323
 324 #include <errno.h>
 325 #include <stdlib.h>
 326 #include <string.h>
 327
 328 typedef unsigned char u_char;
 329
 330 static void setup(u_char *, u_char *, size_t, size_t, int (*)());
 331 static void insertionsort(u_char *, size_t, size_t, int (*)());
 332
 333 #define ISIZE sizeof(int)
 334 #define PSIZE sizeof(u_char *)
 335 #define ICOPY_LIST(src, dst, last)                              \
 336 do                                                      \
 337 *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;    \
 338 while(src < last)
 339 #define ICOPY_ELT(src, dst, i)                                  \
 340 do                                                      \
 341 *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;  \
 342 while (i -= ISIZE)
 343
 344 #define CCOPY_LIST(src, dst, last)              \
 345 do                                      \
 346 *dst++ = *src++;                \
 347 while (src < last)
 348 #define CCOPY_ELT(src, dst, i)                  \
 349 do                                      \
 350 *dst++ = *src++;                \
 351 while (i -= 1)
 352
 353 /*
 354  * Find the next possible pointer head.  (Trickery for forcing an array
 355  * to do double duty as a linked list when objects do not align with word
 356  * boundaries.
 357  */
 358 /* Assumption: PSIZE is a power of 2. */
 359 #define EVAL(p) (u_char **)                                             \
 360 ((u_char *)0 +                                                  \
 361 (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
 362
 363 /*
 364  * Arguments are as for qsort.
 365  */
 366 int
 367 mergesort(base, nmemb, size, cmp)
 368 void *base;
 369 size_t nmemb;
 370 size_t size;
 371 int (*cmp)(const void *, const void *);
 372 {
 373         int i, sense;
 374         int big, iflag;
 375         u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
 376         u_char *list2, *list1, *p2, *p, *last, **p1;
 377
 378         if (size < PSIZE / 2) {         /* Pointers must fit into 2 * size. */
 379                 errno = EINVAL;
 380                 return (-1);
 381         }
 382
 383         if (nmemb == 0)
 384                 return (0);
 385
 386         /*
 387          * XXX
 388          * Stupid subtraction for the Cray.
 389          */
 390         iflag = 0;
 391         if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
 392                 iflag = 1;
 393
 394         if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
 395                 return (-1);
 396
 397         list1 = base;
 398         setup(list1, list2, nmemb, size, cmp);
 399         last = list2 + nmemb * size;
 400         i = big = 0;
 401         while (*EVAL(list2) != last) {
 402             l2 = list1;
 403             p1 = EVAL(list1);
 404             for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
 405                 p2 = *EVAL(p2);
 406                 f1 = l2;
 407                 f2 = l1 = list1 + (p2 - list2);
 408                 if (p2 != last)
 409                         p2 = *EVAL(p2);
 410                 l2 = list1 + (p2 - list2);
 411                 while (f1 < l1 && f2 < l2) {
 412                         if ((*cmp)(f1, f2) <= 0) {
 413                                 q = f2;
 414                                 b = f1, t = l1;
 415                                 sense = -1;
 416                         } else {
 417                                 q = f1;
 418                                 b = f2, t = l2;
 419                                 sense = 0;
 420                         }
 421                         if (!big) {     /* here i = 0 */
 422                                         while ((b += size) < t && cmp(q, b) >sense)
 423                                         if (++i == 6) {
 424                                                 big = 1;
 425                                                 goto EXPONENTIAL;
 426                                         }
 427                         } else {
 428                                 EXPONENTIAL:                    for (i = size; ; i <<= 1)
 429                                         if ((p = (b + i)) >= t) {
 430                                                 if ((p = t - size) > b &&
 431                                                     (*cmp)(q, p) <= sense)
 432                                                         t = p;
 433                                                 else
 434                                                         b = p;
 435                                                 break;
 436                                         } else if ((*cmp)(q, p) <= sense) {
 437                                                 t = p;
 438                                                 if (i == size)
 439                                                         big = 0;
 440                                                 goto FASTCASE;
 441                                         } else
 442                                                 b = p;
 443                                         while (t > b+size) {
 444                                         i = (((t - b) / size) >> 1) * size;
 445                                         if ((*cmp)(q, p = b + i) <= sense)
 446                                                 t = p;
 447                                         else
 448                                                 b = p;
 449                                 }
 450                                 goto COPY;
 451                                 FASTCASE:                       while (i > size)
 452                                         if ((*cmp)(q,
 453                                                            p = b + (i >>= 1)) <= sense)
 454                                                 t = p;
 455                                         else
 456                                                 b = p;
 457                                 COPY:                           b = t;
 458                         }
 459                         i = size;
 460                         if (q == f1) {
 461                                 if (iflag) {
 462                                         ICOPY_LIST(f2, tp2, b);
 463                                         ICOPY_ELT(f1, tp2, i);
 464                                 } else {
 465                                         CCOPY_LIST(f2, tp2, b);
 466                                         CCOPY_ELT(f1, tp2, i);
 467                                 }
 468                         } else {
 469                                 if (iflag) {
 470                                         ICOPY_LIST(f1, tp2, b);
 471                                         ICOPY_ELT(f2, tp2, i);
 472                                 } else {
 473                                         CCOPY_LIST(f1, tp2, b);
 474                                         CCOPY_ELT(f2, tp2, i);
 475                                 }
 476                         }
 477                 }
 478                 if (f2 < l2) {
 479                         if (iflag)
 480                                 ICOPY_LIST(f2, tp2, l2);
 481                         else
 482                                 CCOPY_LIST(f2, tp2, l2);
 483                 } else if (f1 < l1) {
 484                         if (iflag)
 485                                 ICOPY_LIST(f1, tp2, l1);
 486                         else
 487                                 CCOPY_LIST(f1, tp2, l1);
 488                 }
 489                 *p1 = l2;
 490             }
 491             tp2 = list1;        /* swap list1, list2 */
 492             list1 = list2;
 493             list2 = tp2;
 494             last = list2 + nmemb*size;
 495         }
 496         if (base == list2) {
 497                 memmove(list2, list1, nmemb*size);
 498                 list2 = list1;
 499         }
 500         free(list2);
 501         return (0);
 502 }
 503
 504 #define swap(a, b) {                                    \
 505 s = b;                                  \
 506 i = size;                               \
 507 do {                                    \
 508 tmp = *a; *a++ = *s; *s++ = tmp; \
 509 } while (--i);                          \
 510 a -= size;                              \
 511 }
 512 #define reverse(bot, top) {                             \
 513 s = top;                                        \
 514 do {                                            \
 515 i = size;                               \
 516 do {                                    \
 517 tmp = *bot; *bot++ = *s; *s++ = tmp; \
 518 } while (--i);                          \
 519 s -= size2;                             \
 520 } while(bot < s);                               \
 521 }
 522
 523 /*
 524  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
 525  * increasing order, list2 in a corresponding linked list.  Checks for runs
 526  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
 527  * is defined.  Otherwise simple pairwise merging is used.)
 528  */
 529 void
 530 setup(list1, list2, n, size, cmp)
 531 size_t n, size;
 532 int (*cmp)(const void *, const void *);
 533 u_char *list1, *list2;
 534 {
 535         int i, length, size2, tmp, sense;
 536         u_char *f1, *f2, *s, *l2, *last, *p2;
 537
 538         size2 = size*2;
 539         if (n <= 5) {
 540                 insertionsort(list1, n, size, cmp);
 541                 *EVAL(list2) = (u_char*) list2 + n*size;
 542                 return;
 543         }
 544         /*
 545          * Avoid running pointers out of bounds; limit n to evens
 546          * for simplicity.
 547          */
 548         i = 4 + (n & 1);
 549         insertionsort(list1 + (n - i) * size, i, size, cmp);
 550         last = list1 + size * (n - i);
 551         *EVAL(list2 + (last - list1)) = list2 + n * size;
 552
 553 #ifdef NATURAL
 554         p2 = list2;
 555         f1 = list1;
 556         sense = (cmp(f1, f1 + size) > 0);
 557         for (; f1 < last; sense = !sense) {
 558                 length = 2;
 559                 /* Find pairs with same sense. */
 560                 for (f2 = f1 + size2; f2 < last; f2 += size2) {
 561                         if ((cmp(f2, f2+ size) > 0) != sense)
 562                                 break;
 563                         length += 2;
 564                 }
 565                 if (length < THRESHOLD) {               /* Pairwise merge */
 566                         do {
 567                                 p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
 568                                 if (sense > 0)
 569                                         swap (f1, f1 + size);
 570                         } while ((f1 += size2) < f2);
 571                 } else {                                /* Natural merge */
 572                         l2 = f2;
 573                         for (f2 = f1 + size2; f2 < l2; f2 += size2) {
 574                                 if ((cmp(f2-size, f2) > 0) != sense) {
 575                                         p2 = *EVAL(p2) = f2 - list1 + list2;
 576                                         if (sense > 0)
 577                                                 reverse(f1, f2-size);
 578                                         f1 = f2;
 579                                 }
 580                         }
 581                         if (sense > 0)
 582                                 reverse (f1, f2-size);
 583                         f1 = f2;
 584                         if (f2 < last || cmp(f2 - size, f2) > 0)
 585                                 p2 = *EVAL(p2) = f2 - list1 + list2;
 586                         else
 587                                 p2 = *EVAL(p2) = list2 + n*size;
 588                 }
 589         }
 590 #else           /* pairwise merge only. */
 591         for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
 592                 p2 = *EVAL(p2) = p2 + size2;
 593                 if (cmp (f1, f1 + size) > 0)
 594                         swap(f1, f1 + size);
 595         }
 596 #endif /* NATURAL */
 597 }
 598
 599 /*
 600  * This is to avoid out-of-bounds addresses in sorting the
 601  * last 4 elements.
 602  */
 603 static void
 604 insertionsort(a, n, size, cmp)
 605 u_char *a;
 606 size_t n, size;
 607 int (*cmp)(const void *, const void *);
 608 {
 609         u_char *ai, *s, *t, *u, tmp;
 610         int i;
 611
 612         for (ai = a+size; --n >= 1; ai += size)
 613                 for (t = ai; t > a; t -= size) {
 614                         u = t - size;
 615                         if (cmp(u, t) <= 0)
 616                                 break;
 617                         swap(u, t);
 618                 }
 619 }
 620 #endif /* MISSING_MERGESORT */