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