1 /*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 2019-2020 The DragonFly Project. All rights reserved. 5 * 6 * This code is derived from software contributed to The DragonFly Project 7 * by Aaron LI <aly@aaronly.me> 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 3. Neither the name of The DragonFly Project nor the names of its 20 * contributors may be used to endorse or promote products derived 21 * from this software without specific, prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * Reference: 37 * Calendrical Calculations, The Ultimate Edition (4th Edition) 38 * by Edward M. Reingold and Nachum Dershowitz 39 * 2018, Cambridge University Press 40 */ 41 42 #include <err.h> 43 #include <math.h> 44 #include <stdbool.h> 45 #include <stddef.h> 46 #include <stdio.h> 47 #include <stdlib.h> 48 #include <string.h> 49 50 #include "utils.h" 51 52 53 /* 54 * Calculate the polynomial: c[0] + c[1] * x + ... + c[n-1] * x^(n-1) 55 */ 56 double 57 poly(double x, const double *coefs, size_t n) 58 { 59 double p = 0.0; 60 double t = 1.0; 61 for (size_t i = 0; i < n; i++) { 62 p += t * coefs[i]; 63 t *= x; 64 } 65 return p; 66 } 67 68 /* 69 * Use bisection search to find the inverse of the given angular function 70 * $f(x) at value $y (degrees) within time interval [$a, $b]. 71 * Ref: Sec.(1.8), Eq.(1.36) 72 */ 73 double 74 invert_angular(double (*f)(double), double y, double a, double b) 75 { 76 static const double eps = 1e-6; 77 double x; 78 79 do { 80 x = (a + b) / 2.0; 81 if (mod_f(f(x) - y, 360) < 180.0) 82 b = x; 83 else 84 a = x; 85 } while (fabs(a-b) >= eps); 86 87 return x; 88 } 89 90 91 /* 92 * Like malloc(3) but exit if allocation fails. 93 */ 94 void * 95 xmalloc(size_t size) 96 { 97 void *ptr = malloc(size); 98 if (ptr == NULL) 99 errx(1, "mcalloc(%zu): out of memory", size); 100 return ptr; 101 } 102 103 /* 104 * Like calloc(3) but exit if allocation fails. 105 */ 106 void * 107 xcalloc(size_t number, size_t size) 108 { 109 void *ptr = calloc(number, size); 110 if (ptr == NULL) 111 errx(1, "xcalloc(%zu, %zu): out of memory", number, size); 112 return ptr; 113 } 114 115 /* 116 * Like realloc(3) but exit if allocation fails. 117 */ 118 void * 119 xrealloc(void *ptr, size_t size) 120 { 121 ptr = realloc(ptr, size); 122 if (ptr == NULL) 123 errx(1, "xrealloc: out of memory (size: %zu)", size); 124 return ptr; 125 } 126 127 /* 128 * Like strdup(3) but exit if fail. 129 */ 130 char * 131 xstrdup(const char *str) 132 { 133 char *p = strdup(str); 134 if (p == NULL) 135 errx(1, "xstrdup: out of memory (length: %zu)", strlen(str)); 136 return p; 137 } 138 139 140 /* 141 * Linked list implementation 142 */ 143 144 struct node { 145 char *name; 146 void *data; 147 struct node *next; 148 }; 149 150 /* 151 * Create a new list node with the given $name and $data. 152 */ 153 struct node * 154 list_newnode(char *name, void *data) 155 { 156 struct node *newp; 157 158 newp = xcalloc(1, sizeof(*newp)); 159 newp->name = name; 160 newp->data = data; 161 162 return newp; 163 } 164 165 /* 166 * Add $newp to the front of list $listp. 167 */ 168 struct node * 169 list_addfront(struct node *listp, struct node *newp) 170 { 171 newp->next = listp; 172 return newp; 173 } 174 175 /* 176 * Lookup the given $name in the list $listp. 177 * The $cmp function compares two names and return 0 if they equal. 178 * Return the associated data with the found node, otherwise NULL. 179 */ 180 bool 181 list_lookup(struct node *listp, const char *name, 182 int (*cmp)(const char *, const char *), void **data_out) 183 { 184 for ( ; listp; listp = listp->next) { 185 if ((*cmp)(name, listp->name) == 0) { 186 if (data_out) 187 *data_out = listp->data; 188 return true; 189 } 190 } 191 192 return false; 193 } 194 195 /* 196 * Free all nodes of list $listp. 197 */ 198 void 199 list_freeall(struct node *listp, 200 void (*free_name)(void *), 201 void (*free_data)(void *)) 202 { 203 struct node *cur; 204 205 while (listp) { 206 cur = listp; 207 listp = listp->next; 208 if (free_name) 209 (*free_name)(cur->name); 210 if (free_data) 211 (*free_data)(cur->data); 212 free(cur); 213 } 214 } 215