Changeset View
Changeset View
Standalone View
Standalone View
usr.sbin/config/hp2sat.h
- This file was added.
/*- | |||||
* Copyright (c) 2021 Hans Petter Selasky. All rights reserved. | |||||
* | |||||
* Redistribution and use in source and binary forms, with or without | |||||
* modification, are permitted provided that the following conditions | |||||
* are met: | |||||
* 1. Redistributions of source code must retain the above copyright | |||||
* notice, this list of conditions and the following disclaimer. | |||||
* 2. Redistributions in binary form must reproduce the above copyright | |||||
* notice, this list of conditions and the following disclaimer in the | |||||
* documentation and/or other materials provided with the distribution. | |||||
* | |||||
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |||||
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |||||
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |||||
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |||||
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |||||
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |||||
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |||||
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |||||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |||||
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |||||
* SUCH DAMAGE. | |||||
*/ | |||||
#ifndef _HP2SAT_H_ | |||||
#define _HP2SAT_H_ | |||||
#include <stdio.h> | |||||
#include <stddef.h> | |||||
#include <stdint.h> | |||||
#include <stdbool.h> | |||||
#include <assert.h> | |||||
#include <sys/queue.h> | |||||
#include <iostream> | |||||
class ANDMAP; | |||||
typedef TAILQ_CLASS_HEAD(ANDMAP_HEAD, ANDMAP) ANDMAP_HEAD_t; | |||||
typedef TAILQ_CLASS_ENTRY(ANDMAP) ANDMAP_ENTRY_t; | |||||
extern char *hp2sat_option_dup(const char *str); | |||||
class OPTION { | |||||
public: | |||||
char *option; | |||||
OPTION() { | |||||
option = hp2sat_option_dup(""); /* false */ | |||||
}; | |||||
OPTION(const OPTION &other) { | |||||
option = hp2sat_option_dup(other.option); | |||||
}; | |||||
OPTION(const char *str) { | |||||
option = hp2sat_option_dup(str); | |||||
}; | |||||
~OPTION() { | |||||
if (isInverted() == false) | |||||
toggleInverted(); | |||||
delete [] option; | |||||
}; | |||||
OPTION *dup(void) const { | |||||
return (new OPTION(*this)); | |||||
}; | |||||
bool isZero(void) const { | |||||
return (option[0] == '\0'); | |||||
}; | |||||
bool isOne(void) const { | |||||
return (option[0] == '!' && option[1] == '\0'); | |||||
}; | |||||
bool isInverted() const { | |||||
return (option[0] == '!'); | |||||
}; | |||||
OPTION & toggleInverted() { | |||||
if (option[0] == '!') | |||||
option++; | |||||
else { | |||||
option--; | |||||
assert(option[0] == '!'); | |||||
} | |||||
return (*this); | |||||
}; | |||||
bool contains(const OPTION & other) const { | |||||
return (compare(other, true) == 0); | |||||
}; | |||||
OPTION & operator =(const OPTION &other) { | |||||
if (this == &other) | |||||
return (*this); | |||||
if (isInverted() == false) | |||||
toggleInverted(); | |||||
delete [] option; | |||||
option = hp2sat_option_dup(other.option); | |||||
return (*this); | |||||
}; | |||||
bool expand_all(const OPTION *pval, size_t num) const { | |||||
for (size_t x = 0; x != num; x++) { | |||||
if (contains(pval[x])) | |||||
return (pval[x].isInverted() != isInverted()); | |||||
} | |||||
return (false); | |||||
}; | |||||
void print(std::ostream &out = std::cout) const { | |||||
out << option; | |||||
}; | |||||
int compare(const OPTION & other, bool skip_value = false) const { | |||||
const char *str_a = option; | |||||
const char *str_b = other.option; | |||||
if (skip_value) { | |||||
if (str_a[0] == '!') | |||||
str_a++; | |||||
if (str_b[0] == '!') | |||||
str_b++; | |||||
} | |||||
return (strcmp(str_a, str_b)); | |||||
}; | |||||
bool operator >(const OPTION & other) const { | |||||
return (compare(other) > 0); | |||||
}; | |||||
bool operator <(const OPTION & other) const { | |||||
return (compare(other) < 0); | |||||
}; | |||||
bool operator >=(const OPTION & other) const { | |||||
return (compare(other) >= 0); | |||||
}; | |||||
bool operator <=(const OPTION & other) const { | |||||
return (compare(other) <= 0); | |||||
}; | |||||
bool operator == (const OPTION & other) const { | |||||
return (compare(other) == 0); | |||||
}; | |||||
bool operator !=(const OPTION & other) const { | |||||
return (compare(other) != 0); | |||||
}; | |||||
}; | |||||
class ANDMAP { | |||||
public: | |||||
ANDMAP_ENTRY_t entry; | |||||
OPTION options[2]; | |||||
uint8_t nummaps; | |||||
ANDMAP() { | |||||
nummaps = 0; | |||||
}; | |||||
ANDMAP(const ANDMAP &other) { | |||||
nummaps = 0; | |||||
*this = other; | |||||
}; | |||||
ANDMAP(const OPTION &other) { | |||||
options[0] = other; | |||||
nummaps = 1; | |||||
}; | |||||
ANDMAP(const char *str) { | |||||
options[0] = OPTION(str); | |||||
nummaps = 1; | |||||
}; | |||||
ANDMAP *dup(void) const { | |||||
return (new ANDMAP(*this)); | |||||
}; | |||||
bool isOne() const { | |||||
return (nummaps == 0); | |||||
}; | |||||
bool isZero() const { | |||||
for (uint8_t x = 0; x != nummaps; x++) { | |||||
if (options[x].isZero()) | |||||
return (true); | |||||
} | |||||
return (false); | |||||
}; | |||||
bool contains(const OPTION & other) const { | |||||
for (uint8_t x = 0; x != nummaps; x++) { | |||||
if (options[x].contains(other)) | |||||
return (true); | |||||
} | |||||
return (false); | |||||
}; | |||||
ANDMAP & operator =(const ANDMAP &other) { | |||||
if (this == &other) | |||||
return (*this); | |||||
options[0] = other.options[0]; | |||||
options[1] = other.options[1]; | |||||
nummaps = other.nummaps; | |||||
return (*this); | |||||
}; | |||||
ANDMAP & operator &=(const ANDMAP &other) { | |||||
ANDMAP temp; | |||||
uint8_t x = 0; | |||||
uint8_t y = 0; | |||||
temp.nummaps = 0; | |||||
/* keep it sorted */ | |||||
while (x != nummaps && y != other.nummaps) { | |||||
if (options[x] > other.options[y]) { | |||||
temp.options[temp.nummaps++] = other.options[y++]; | |||||
} else if (options[x] < other.options[y]) { | |||||
temp.options[temp.nummaps++] = options[x++]; | |||||
} else { | |||||
temp.options[temp.nummaps++] = options[x]; | |||||
x++; | |||||
y++; | |||||
} | |||||
} | |||||
while (x != nummaps) | |||||
temp.options[temp.nummaps++] = options[x++]; | |||||
while (y != other.nummaps) | |||||
temp.options[temp.nummaps++] = other.options[y++]; | |||||
*this = temp; | |||||
return (*this); | |||||
}; | |||||
ANDMAP operator &(const ANDMAP &other) const { | |||||
ANDMAP temp(*this); | |||||
temp &= other; | |||||
return (temp); | |||||
}; | |||||
ANDMAP & expand(const OPTION &other, bool value) { | |||||
for (uint8_t x = 0; x != nummaps; ) { | |||||
if (options[x].contains(other) == false) { | |||||
x++; | |||||
continue; | |||||
} | |||||
if (options[x].isInverted() == value) { | |||||
nummaps = 1; | |||||
options[0] = OPTION(); /* false */ | |||||
return (*this); | |||||
} | |||||
for (uint8_t y = x + 1; y != nummaps; y++) | |||||
options[y - 1] = options[y]; | |||||
nummaps--; | |||||
} | |||||
return (*this); | |||||
}; | |||||
bool expand_all(const OPTION *pval, size_t num) const { | |||||
bool retval = true; | |||||
for (uint8_t x = 0; x != nummaps; x++) | |||||
retval &= options[x].expand_all(pval, num); | |||||
return (retval); | |||||
}; | |||||
void print(std::ostream &out = std::cout) const { | |||||
if (isOne()) { | |||||
out << "true"; | |||||
} else if (isZero()) { | |||||
out << "false"; | |||||
} else { | |||||
for (uint8_t x = 0; x != nummaps; x++) { | |||||
out << "("; | |||||
options[x].print(out); | |||||
out << ")"; | |||||
if (x + 1 != nummaps) | |||||
out << "&"; | |||||
} | |||||
} | |||||
}; | |||||
ANDMAP & insert_tail(ANDMAP_HEAD_t *phead){ | |||||
TAILQ_INSERT_TAIL(phead, this, entry); | |||||
return (*this); | |||||
}; | |||||
ANDMAP & insert_head(ANDMAP_HEAD_t *phead){ | |||||
TAILQ_INSERT_HEAD(phead, this, entry); | |||||
return (*this); | |||||
}; | |||||
ANDMAP *remove(ANDMAP_HEAD_t *phead){ | |||||
#ifdef DEBUG | |||||
for (ANDMAP *pa = TAILQ_FIRST(phead); pa != this; pa = pa->next()) | |||||
assert(pa); | |||||
#endif | |||||
TAILQ_REMOVE(phead, this, entry); | |||||
return (this); | |||||
}; | |||||
ANDMAP *prev() const { | |||||
return (TAILQ_PREV(this, ANDMAP_HEAD, entry)); | |||||
}; | |||||
ANDMAP *next() const { | |||||
return (TAILQ_NEXT(this, entry)); | |||||
}; | |||||
int compare(const ANDMAP & other) const { | |||||
uint8_t x; | |||||
if (nummaps > other.nummaps) | |||||
return (1); | |||||
else if (nummaps < other.nummaps) | |||||
return (-1); | |||||
for (x = 0; x != nummaps; x++) { | |||||
const int ret = options[x].compare(other.options[x]); | |||||
if (ret) | |||||
return (ret); | |||||
} | |||||
return (0); | |||||
}; | |||||
bool operator >(const ANDMAP & other) const { | |||||
return (compare(other) > 0); | |||||
}; | |||||
bool operator <(const ANDMAP & other) const { | |||||
return (compare(other) < 0); | |||||
}; | |||||
bool operator >=(const ANDMAP & other) const { | |||||
return (compare(other) >= 0); | |||||
}; | |||||
bool operator <=(const ANDMAP & other) const { | |||||
return (compare(other) <= 0); | |||||
}; | |||||
bool operator == (const ANDMAP & other) const { | |||||
return (compare(other) == 0); | |||||
}; | |||||
bool operator !=(const ANDMAP & other) const { | |||||
return (compare(other) != 0); | |||||
}; | |||||
}; | |||||
extern void hp2sat_free(ANDMAP_HEAD_t *); | |||||
extern bool hp2sat_sort_ored(ANDMAP_HEAD_t *); | |||||
extern void hp2sat_multiply(const ANDMAP_HEAD_t *, const ANDMAP_HEAD_t *, ANDMAP_HEAD_t *); | |||||
extern bool hp2sat_solve(ANDMAP_HEAD_t *, OPTION *, size_t, OPTION *); | |||||
#endif /* _HP2SAT_H_ */ |