/* -*-c-*-
*
- * $Id: class.c,v 1.5 1997/08/20 16:16:13 mdw Exp $
+ * $Id: class.c,v 1.6 1997/09/17 10:14:56 mdw Exp $
*
* Handling classes of things nicely
*
/*----- Revision history --------------------------------------------------*
*
* $Log: class.c,v $
- * Revision 1.5 1997/08/20 16:16:13 mdw
+ * Revision 1.6 1997/09/17 10:14:56 mdw
+ * Complete rewrite to support class trees. Makes the behaviour of the set
+ * operators much more logical.
+ *
+ * Revision 1.5 1997/08/20 16:16:13 mdw
* Patch memory leak. Don't try to trace when tracing's turned off.
*
* Revision 1.4 1997/08/07 09:56:37 mdw
#include "become.h"
#include "class.h"
-#include "set.h"
#include "sym.h"
#include "utils.h"
/*----- Global variables --------------------------------------------------*/
-static classdef class__all = { clType_all, -1, 0 };
-classdef *class_all = &class__all;
+static class_node class__all = { clType_all | clNode_any, -1, { 0 }};
+class_node *class_all = &class__all;
+
+static class_node class__none = { clType_all | clNode_any, -1, { 0 }};
+class_node *class_none = &class__none;
/*----- Wildcard matching -------------------------------------------------*/
return (27); /* Nyahaha */
p++;
} while (*p);
- return (0);
+ return (pat[1] == 0);
} else if (*pat == '?' || *pat == *p)
p++, pat++;
else
}
}
-/*----- Main code ---------------------------------------------------------*/
+/*----- Creating new class nodes ------------------------------------------*/
+
+/* --- @class_fromString@ --- *
+ *
+ * Arguments: @unsigned type@ = a type field
+ * @const char *s@ = pointer to string to copy
+ *
+ * Returns: A pointer to a class node containing that string, typed to
+ * be the right thing.
+ *
+ * Use: Given a string, wrap a class node around it. The node has
+ * one reference (the one you get returned). The string is
+ * copied, so you can get rid of your original one if you like.
+ */
+
+class_node *class_fromString(unsigned type, const char *s)
+{
+ class_node *c = xmalloc(sizeof(*c));
+ c->type = type | clNode_immed;
+ if (s[strcspn(s, "*?")] == 0)
+ c->type |= clFlag_friendly;
+ c->ref = 1;
+ c->v.s = xstrdup(s);
+ return (c);
+}
-/* --- @class_create@ --- *
+/* --- @class_fromUser@ --- *
*
- * Arguments: @unsigned type@ = type of the class to create
- * @sym_table *t@ = pointer to symbol table which stores info
+ * Arguments: @unsigned type@ = a type field
+ * @uid_t u@ = a user-id number
*
- * Returns: Pointer to a @classdef@ which maintains the class's info.
+ * Returns: A pointer to a class node containing the uid, typed to be
+ * the thing you asked for. Hopefully this will be
+ * @clType_user@.
*
- * Use: Creates a new class definition. The new definition has one
- * reference attached to it (which is the one you get returned).
+ * Use: Given a uid, wrap a class node around it.
*/
-classdef *class_create(unsigned type, sym_table *t)
+class_node *class_fromUser(unsigned type, uid_t u)
{
- classdef *c = xmalloc(sizeof(*c));
- c->type = type;
+ class_node *c = xmalloc(sizeof(*c));
+ c->type = type | clNode_immed | clFlag_friendly;
c->ref = 1;
- c->t = t;
+ c->v.u = u;
return (c);
}
+/*----- Reference counter tricks ------------------------------------------*/
+
/* --- @class_inc@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Arguments: @class_node *c@ = pointer to a class block
*
* Returns: ---
*
* Use: Adds a reference to the class definition.
*/
-void class_inc(classdef *c)
+void class_inc(class_node *c)
{
- if (c != class_all)
+ if (c != class_all && c != class_none)
c->ref++;
}
/* --- @class_dec@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Arguments: @class_node *c@ = pointer to a class block
*
* Returns: ---
*
* Use: Removes a reference to a class block.
*/
-void class_dec(classdef *c)
+void class_dec(class_node *c)
{
- if (c != class_all && !--c->ref) {
- sym_destroyTable(c->t);
- free(c->t);
+ class_node *cc;
+
+ for (cc = 0; c; c = cc, cc = 0) {
+ if (c == class_all || c == class_none || --c->ref)
+ continue;
+ switch (c->type & clNode_mask) {
+ case clNode_any:
+ /* Nothing to do */
+ break;
+ case clNode_immed:
+ if (c->type & (clType_host | clType_command))
+ free(c->v.s);
+ break;
+ case clNode_hash:
+ sym_destroyTable(&c->v.t);
+ break;
+ case clNode_union:
+ case clNode_diff:
+ case clNode_isect:
+ class_dec(c->v.c.l);
+ cc = c->v.c.r;
+ break;
+ }
free(c);
}
}
-/* --- @class_userMatch@ --- *
+/* --- @class_mod@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
- * @int u@ = uid number to check against
+ * Arguments: @class_node *c@ = pointer to a class node
*
- * Returns: Zero if no match, nonzero if it matched.
+ * Returns: A pointer to a class node, maybe the same one, maybe not,
+ * with a reference count of 1, containing the same data.
*
- * Use: Looks to see if a user is in a group.
+ * Use: Gives you a node which you can modify. Don't call this
+ * for @class_all@ or @class_none@.
*/
-int class_userMatch(classdef *c, int u)
+class_node *class_mod(class_node *c)
{
- if (~c->type & clType_user)
- return (0);
- else if (c == class_all) {
- T( trace(TRACE_CHECK, "check: user %i matched by all", u); )
- return (1);
- } else {
- sym_base *s = sym_find(c->t, (char *)&u, sizeof(u), 0, 0);
- T( trace(TRACE_CHECK,
- s ? "check: user %i matched" : "check: user %i not matched",
- u); )
- return (s != 0);
+ class_node *cc;
+
+ if (c->ref == 1)
+ return (c);
+
+ cc = xmalloc(sizeof(*cc));
+ cc->type = c->type;
+ cc->ref = 1;
+ switch (c->type & clNode_mask) {
+ case clNode_any:
+ die("internal error: class_mod called on non-modifiable class node");
+ break;
+
+ case clNode_immed:
+ if (c->type & clType_user)
+ cc->v.u = c->v.u;
+ else
+ cc->v.s = xstrdup(c->v.s);
+ break;
+
+ case clNode_hash: {
+ sym_iter i;
+ sym_base *b;
+
+ sym_createTable(&cc->v.t);
+ for (sym_createIter(&i, &c->v.t); (b = sym_next(&i)) != 0; )
+ sym_find(&cc->v.t, b->name, b->len, sizeof(sym_base), 0);
+ } break;
+
+ case clNode_union:
+ case clNode_diff:
+ case clNode_isect:
+ cc->v.c.l = c->v.c.l;
+ cc->v.c.r = c->v.c.r;
+ class_inc(cc->v.c.l);
+ class_inc(cc->v.c.r);
+ break;
}
+
+ class_dec(c);
+ return (cc);
}
-/* --- @class_commandMatch@ --- *
+/*----- Some weirder operations on classes --------------------------------*/
+
+/* --- @class__hashify@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
- * @const char *p@ = pointer to command string to match
+ * Arguments: @class_node *c@ = pointer to a node
*
- * Returns: Zero for no match, nonzero if it matched.
+ * Returns: A pointer to a hash node containing the node's value.
*
- * Use: Tries to match a string against the wildcard patterns in the
- * given class. Note that this involves examining all the
- * items, so it's not too quick. Then again, you don't have
- * big command classes, do you...?
+ * Use: The original node must have type `immediate', and it must
+ * be friendly. The old reference is discarded -- you get this
+ * one instead.
*/
-int class_commandMatch(classdef *c, const char *p)
+static class_node *class__hashify(class_node *c)
{
- sym_iter i;
- sym_base *s;
+ /* --- Some sanity checking --- */
- if (~c->type & clType_command)
- return (0);
- else if (c == class_all) {
- T( trace(TRACE_CHECK, "check: command `%s' matched by all", p); )
- return (1);
+ if (~c->type & clFlag_friendly)
+ die("internal error: class__hashify can't hashify unfriendly nodes");
+ if ((c->type & clNode_mask) != clNode_immed)
+ die("internal error: class__hashify can't hashify non-immediate nodes");
+
+ /* --- Split off a private copy of the node --- */
+
+ c = class_mod(c);
+
+ c->type = (c->type & clType_mask) | clNode_hash | clFlag_friendly;
+
+ if (c->type & clType_user) {
+ uid_t u = c->v.u;
+ sym_createTable(&c->v.t);
+ sym_find(&c->v.t, (char *)&u, sizeof(u), sizeof(sym_base), 0);
} else {
- for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) {
- if (class__wildMatch(s->name, p)) {
- T( trace(TRACE_CHECK, "check: command `%s' matched by `%s'",
- p, s->name); )
- return (1);
- }
- }
- T( trace(TRACE_CHECK, "check: command `%s' not matched", p); )
- return (0);
+ char *s = c->v.s;
+ sym_createTable(&c->v.t);
+ sym_find(&c->v.t, s, -1, sizeof(sym_base), 0);
+ free(s);
}
+
+ return (c);
}
-/* --- @class_hostMatch@ --- *
+/*----- Arithmetic on classes ---------------------------------------------*/
+
+/* --- @class__binop@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ * @unsigned op@ = the binop code
*
- * Arguments: @classdef *c@ = pointer to class block
- * @struct in_addr addr@ = IP address to match
+ * Returns: A class node representing the result of a binary operation
+ * upon two classes.
*
- * Returns: Zero for no match, nonzero if it matched.
+ * Use: Performs a binary operation on classes. If the types don't
+ * match, then a null pointer is returned. Both @l@ and @r@
+ * may be modified, and will be decremented before they get
+ * returned to you. If you don't want that to happen, ensure
+ * that you've claimed a reference to the original versions.
*
- * Use: Tries to match an IP address against the patterns and masks
- * in the given class.
+ * If both nodes are `friendly' (see below), then an attempt is
+ * made to combine them sensibly using a hashtable.
+ *
+ * If one or both nodes is/are unfriendly, a binop node is
+ * created with type @op@ to allow the matcher to decide on
+ * membership appropriately at match time.
+ *
+ * A friendly node is one which can be placed in a hash table to
+ * speed up searching. It's friendly, because it doesn't mind
+ * living with other nodes. Uid numbers are friendly.
+ * Wildcarded strings aren't. Hashtables are trivially
+ * friendly.
*/
-int class_hostMatch(classdef *c, struct in_addr addr)
+class_node *class__binop(class_node *l, class_node *r, int op)
{
- sym_iter i;
- sym_base *s;
- const char *a;
- struct hostent *he;
- char **p;
+ unsigned type = l->type & r->type & clType_mask;
+ unsigned lnode = l->type & clNode_mask, rnode = r->type & clNode_mask;
+
+ /* --- Check for compatible types --- */
- if (~c->type & clType_host)
+ if (!type) {
+ class_dec(l);
+ class_dec(r);
return (0);
- else if (c == class_all) {
- T( trace(TRACE_CHECK, "check: host %s matched by all",
- inet_ntoa(addr)); )
- return (1);
- } else {
+ }
- /* --- Get the dotted-quad and other names for the address --- */
+ /* --- Handle `friendly' nodes --- */
- if ((a = inet_ntoa(addr)) == 0) {
- T( trace(TRACE_CHECK, "check: couldn't translate address (erk!)"); )
- return (0);
+ if ((l->type & r->type & clFlag_friendly)) {
+
+ /* --- Consider promoting an item to a hash --- *
+ *
+ * If both are immediate nodes, and they're both `friendly', we can
+ * profitably hash them together.
+ *
+ * Life gets complicated when we do subtraction, because it's not
+ * commutative. In this case, I have to promote the left operand anyway.
+ */
+
+ if (lnode == clNode_immed &&
+ (rnode == clNode_immed || op == clNode_diff)) {
+
+ /* --- Quick check for triviality --- *
+ *
+ * There are some more short-cuts I can employ if the values are
+ * the same.
+ */
+
+ if (rnode == clNode_immed) {
+
+ /* --- See whether the two items are equal --- */
+
+ int eq = (type & clType_user ?
+ l->v.u == r->v.u : strcmp(l->v.s, r->v.s) == 0);
+
+ /* --- Now do something appropriate --- */
+
+ switch (op) {
+ case clNode_union:
+ if (eq) {
+ class_dec(r);
+ return (l);
+ }
+ break;
+ case clNode_diff:
+ if (eq) {
+ class_dec(l);
+ class_dec(r);
+ return (class_none);
+ }
+ break;
+ case clNode_isect:
+ if (eq) {
+ class_dec(r);
+ return (l);
+ } else {
+ class_dec(l);
+ class_dec(r);
+ return (class_none);
+ }
+ break;
+ }
+ }
+
+ /* --- Turn @l@ into a hash containing itself --- */
+
+ l = class__hashify(l);
+ lnode = clNode_hash;
}
- if ((he = gethostbyaddr((char *)&addr, sizeof(addr), AF_INET)) == 0)
- T( trace(TRACE_CHECK, "check: couldn't resolve hostname for %s", a); )
+ /* --- Otherwise, make @l@ the hash --- *
+ *
+ * Both @l@ and @r@ are friendly. Since they're not both immediates,
+ * one must be a hash.
+ */
- /* --- Now search the list for a match --- *
+ else if ((l->type & clNode_mask) == clNode_immed) {
+ class_node *tn;
+ unsigned tt;
+
+ tn = l, l = r, r = tn;
+ tt = lnode, lnode = rnode, rnode = tt;
+ }
+
+ /* --- Now merge @r@ with @l@ --- */
+
+ l = class_mod(l);
+
+ switch (op) {
+
+ /* --- The union operation isn't hard --- */
+
+ case clNode_union:
+ if (rnode == clNode_immed) {
+ if (type & clType_user) {
+ sym_find(&l->v.t, (char *)&r->v.u,
+ sizeof(r->v.u), sizeof(sym_base), 0);
+ } else
+ sym_find(&l->v.t, r->v.s, -1, sizeof(sym_base), 0);
+ } else {
+ sym_iter i;
+ sym_base *b;
+
+ for (sym_createIter(&i, &r->v.t); (b = sym_next(&i)) != 0; )
+ sym_find(&l->v.t, b->name, b->len, sizeof(sym_base), 0);
+ }
+ break;
+
+ /* --- Set difference is similar in spirit --- */
+
+ case clNode_diff:
+ if (rnode == clNode_immed) {
+ sym_base *f;
+
+ if (type & clType_user)
+ f = sym_find(&l->v.t, (char *)&r->v.u, sizeof(r->v.u), 0, 0);
+ else
+ f = sym_find(&l->v.t, r->v.s, -1, 0, 0);
+ if (f)
+ sym_remove(&l->v.t, f);
+ } else {
+ sym_iter i;
+ sym_base *b, *f;
+
+ for (sym_createIter(&i, &r->v.t); (b = sym_next(&i)) != 0; ) {
+ if ((f = sym_find(&l->v.t, b->name, b->len, 0, 0)) != 0)
+ sym_remove(&l->v.t, f);
+ }
+ }
+ break;
+
+ /* --- Intersection is wild and wacky --- */
+
+ case clNode_isect:
+ if (rnode == clNode_immed) {
+ sym_base *f;
+
+ if (type & clType_user)
+ f = sym_find(&l->v.t, (char *)&r->v.u, sizeof(r->v.u), 0, 0);
+ else
+ f = sym_find(&l->v.t, r->v.s, -1, 0, 0);
+ if (f) {
+ class_dec(l);
+ return (r);
+ } else {
+ class_dec(l);
+ class_dec(r);
+ return (class_none);
+ }
+ } else {
+ sym_iter i;
+ sym_base *b;
+
+ for (sym_createIter(&i, &l->v.t); (b = sym_next(&i)) != 0; ) {
+ if (!sym_find(&r->v.t, b->name, b->len, 0, 0))
+ sym_remove(&l->v.t, b);
+ }
+ }
+ break;
+ }
+
+ /* --- Now trim the @l@ table to size --- *
*
- * This is almost infinitely slow, I'm afraid.
+ * It may have lost a load of elements. Maybe it can be represented
+ * better as an immediate or even as @class_none@.
*/
- for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) {
+ {
+ sym_iter i;
+ sym_base *b;
- /* --- Check the dotted-quad name first --- */
+ class_dec(r);
- if (class__wildMatch(s->name, a)) {
- T( trace(TRACE_CHECK, "check: host address `%s' matched by `%s'",
- a, s->name); )
- return (1);
+ sym_createIter(&i, &l->v.t);
+ if ((b = sym_next(&i)) == 0) {
+ class_dec(l);
+ return (class_none);
}
+ if (!sym_next(&i)) {
+ if (type & clType_user) {
+ uid_t u = *(uid_t *)b->name;
+ sym_destroyTable(&l->v.t);
+ l->type = (l->type & ~clNode_mask) | clNode_immed;
+ l->v.u = u;
+ } else {
+ char *s = xstrdup(b->name);
+ sym_destroyTable(&l->v.t);
+ l->type = (l->type & ~clNode_mask) | clNode_immed;
+ l->v.s = s;
+ }
+ }
+ }
+
+ /* --- Done --- */
+
+ return (l);
+ }
+
+ /* --- Unfriendly nodes --- *
+ *
+ * Create a binop node and return that. If @l@ is a binop node, and @r@
+ * isn't, and the operation isn't set difference (i.e., it's commutative)
+ * then swap the two over to lessen the depth of recursion later.
+ */
+
+ else {
+ class_node *c = xmalloc(sizeof(*c));
+
+ c->type = type | op;
+ c->ref = 1;
+ if (lnode >= clNode_binop && rnode < clNode_binop && op != clNode_diff) {
+ c->v.c.l = r;
+ c->v.c.r = l;
+ } else {
+ c->v.c.l = l;
+ c->v.c.r = r;
+ }
+ return (c);
+ }
+}
+
+/* --- @class_union@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the union of the two classes.
+ *
+ * Use: Performs the union operation on classes. If the types don't
+ * match, then a null pointer is returned. Both @l@ and @r@
+ * may be modified, and will be decremented before they get
+ * returned to you. If you don't want that to happen, ensure
+ * that you've claimed a reference to the original versions.
+ */
+
+class_node *class_union(class_node *l, class_node *r)
+{
+ /* --- Check for the really simple cases --- */
+
+ if (l == class_all || r == class_all) {
+ class_dec(l);
+ class_dec(r);
+ return (class_all);
+ }
+
+ if (l == class_none)
+ return (r);
+ if (r == class_none)
+ return (l);
- if (he) {
+ /* --- Do the job --- */
+
+ return (class__binop(l, r, clNode_union));
+}
+
+/* --- @class_diff@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the difference of the two classes.
+ *
+ * Use: Performs the set difference operation on classes. If the
+ * types don't match, then a null pointer is returned. Both
+ * @l@ and @r@ may be modified, and will be decremented before
+ * they get returned to you. If you don't want that to happen,
+ * ensure that you've claimed a reference to the original
+ * versions.
+ */
+
+class_node *class_diff(class_node *l, class_node *r)
+{
+ /* --- Check for the really simple cases --- */
+
+ if (l == class_none || r == class_all) {
+ class_dec(l);
+ class_dec(r);
+ return (class_none);
+ }
- /* --- Now try the host's main name --- */
+ if (r == class_none)
+ return (l);
- if (class__wildMatch(s->name, he->h_name)) {
- T( trace(TRACE_CHECK, "check: host name `%s' matched by `%s'",
- he->h_name, s->name); )
+ /* --- Do the job --- */
+
+ return (class__binop(l, r, clNode_diff));
+}
+
+/* --- @class_isect@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the intersection of the two
+ * classes.
+ *
+ * Use: Performs the intersecion operation on classes. If the types
+ * don't match, then a null pointer is returned. Both @l@ and
+ * @r@ may be modified, and will be decremented before they get
+ * returned to you. If you don't want that to happen, ensure
+ * that you've claimed a reference to the original versions.
+ */
+
+class_node *class_isect(class_node *l, class_node *r)
+{
+ /* --- Check for the really simple cases --- */
+
+ if (l == class_none || r == class_none) {
+ class_dec(l);
+ class_dec(r);
+ return (class_none);
+ }
+
+ if (l == class_all)
+ return (r);
+ if (r == class_all)
+ return (l);
+
+ /* --- Do the job --- */
+
+ return (class__binop(l, r, clNode_isect));
+}
+
+/*----- Building the predefined classes -----------------------------------*/
+
+/* --- @class_addUser@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to a class node (may be null)
+ * @uid_t u@ = user id number
+ *
+ * Returns: Pointer to the combined node.
+ *
+ * Use: Adds a user to a node, maybe hashifying it.
+ */
+
+class_node *class_addUser(class_node *c, uid_t u)
+{
+ if (!c)
+ return (class_fromUser(clType_user, u));
+ if ((c->type & clNode_mask) == clNode_immed)
+ c = class__hashify(c);
+ sym_find(&c->v.t, (char *)&u, sizeof(u), sizeof(sym_base), 0);
+ return (c);
+}
+
+/* --- @class_addString@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to a class node (may be null)
+ * @const char *s@ = pointer to a string
+ *
+ * Returns: Pointer to the combined node.
+ *
+ * Use: Adds a user to a node, maybe hashifying it.
+ */
+
+class_node *class_addString(class_node *c, const char *s)
+{
+ class_node *n = class_fromString(clType_host, s); /* hack */
+ if (c)
+ return (class_union(c, n));
+ else
+ return (n);
+}
+
+/*----- Matching functions ------------------------------------------------*/
+
+/* --- @class_matchUser@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @uid_t u@ = user id number
+ *
+ * Returns: Nonzero if it matches, zero if it doesn't.
+ *
+ * Use: Determines whether a user is matched by a class. Assumes
+ * that the types are correct.
+ */
+
+int class_matchUser(class_node *c, uid_t u)
+{
+ class_node *cc;
+
+ for (cc = 0; c; c = cc, cc = 0) {
+ if (c == class_none)
+ return (0);
+ if (c == class_all)
+ return (1);
+ switch (c->type & clNode_mask) {
+ case clNode_immed:
+ return (u == c->v.u);
+ break;
+ case clNode_hash:
+ return (sym_find(&c->v.t, (char *)&u, sizeof(u), 0, 0) != 0);
+ break;
+ case clNode_union:
+ if (class_matchUser(c->v.c.l, u))
return (1);
- }
+ cc = c->v.c.r;
+ break;
+ case clNode_isect:
+ if (!class_matchUser(c->v.c.l, u))
+ return (0);
+ cc = c->v.c.r;
+ break;
+ case clNode_diff:
+ return (class_matchUser(c->v.c.l, u) &&
+ !class_matchUser(c->v.c.r, u));
+ break;
+ }
+ }
+
+ die("internal error: can't get here in class_matchUser");
+ return (0);
+}
+
+/* --- @class_matchCommand@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @const char *s@ = pointer to a string
+ *
+ * Returns: Nonzero if it matches, zero if it doesn't.
+ *
+ * Use: Determines whether a string is matched by a class. Assumes
+ * that the types are correct.
+ */
+
+int class_matchCommand(class_node *c, const char *s)
+{
+ class_node *cc;
- /* --- Now go through all the names --- */
+ for (cc = 0; c; c = cc, cc = 0) {
+ if (c == class_none)
+ return (0);
+ if (c == class_all)
+ return (1);
+ switch (c->type & clNode_mask) {
+ case clNode_immed:
+ return (class__wildMatch(c->v.s, s));
+ break;
+ case clNode_hash:
+ return (sym_find(&c->v.t, s, -1, 0, 0) != 0);
+ break;
+ case clNode_union:
+ if (class_matchCommand(c->v.c.l, s))
+ return (1);
+ cc = c->v.c.r;
+ break;
+ case clNode_isect:
+ if (!class_matchCommand(c->v.c.l, s))
+ return (0);
+ cc = c->v.c.r;
+ break;
+ case clNode_diff:
+ return (class_matchCommand(c->v.c.l, s) &&
+ !class_matchCommand(c->v.c.r, s));
+ break;
+ }
+ }
+
+ die("internal error: can't get here in class_matchCommand");
+ return (0);
+}
+
+/* --- @class_matchHost@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @struct in_addr a@ = IP address to match
+ *
+ * Returns: Nonzero if it matches, zero if it doesn't.
+ *
+ * Use: Determines whether a host matches a host class. Assumes
+ * that the types are correct. The actual mechanism is a bit
+ * odd here, but I think this is the Right Thing. At each stage
+ * I try to match %%@/all/%% of the possible names for the host.
+ * Thus host `splat' with address 1.2.3.4 would fail to match
+ * the class "1.2.*" - "splat". This seems to be what the
+ * author intuitively expects. It's just a bit weird.
+ */
+
+static int class__doMatchHost(class_node *c, const char *ip,
+ const char *name, char **aliases)
+{
+ class_node *cc;
- for (p = he->h_aliases; *p; p++) {
- if (class__wildMatch(s->name, *p)) {
- T( trace(TRACE_CHECK, "check: host alias `%s' matched by `%s'",
- *p, s->name); )
+ for (cc = 0; c; c = cc, cc = 0) {
+ if (c == class_none)
+ return (0);
+ if (c == class_all)
+ return (1);
+ switch (c->type & clNode_mask) {
+ case clNode_immed:
+ if ((ip && class__wildMatch(c->v.s, ip)) ||
+ (name && class__wildMatch(c->v.s, name)))
+ return (1);
+ if (aliases) for (; *aliases; aliases++) {
+ if (class__wildMatch(c->v.s, *aliases))
return (1);
- }
}
- }
+ return (0);
+ break;
+ case clNode_hash:
+ if ((ip && sym_find(&c->v.t, ip, -1, 0, 0)) ||
+ (name && sym_find(&c->v.t, name, -1, 0, 0)))
+ return (1);
+ if (aliases) for (; *aliases; aliases++) {
+ if (sym_find(&c->v.t, *aliases, -1, 0, 0))
+ return (1);
+ }
+ return (0);
+ break;
+ case clNode_union:
+ if (class__doMatchHost(c->v.c.l, ip, name, aliases))
+ return (1);
+ cc = c->v.c.r;
+ break;
+ case clNode_isect:
+ if (!class__doMatchHost(c->v.c.l, ip, name, aliases))
+ return (0);
+ cc = c->v.c.r;
+ break;
+ case clNode_diff:
+ return (class__doMatchHost(c->v.c.l, ip, name, aliases) &&
+ !class__doMatchHost(c->v.c.r, ip, name, aliases));
+ break;
}
+ }
- T( trace(TRACE_CHECK, "check: couldn't match hostname `%s'",
- he->h_name); )
- return (0);
+ die("internal error: can't get here in class_matchUser");
+ return (0);
+}
+
+int class_matchHost(class_node *c, struct in_addr a)
+{
+ char *ip, *name, **aliases;
+ struct hostent *h;
+
+ ip = inet_ntoa(a);
+ if ((h = gethostbyaddr((char *)&a, sizeof(a), AF_INET)) != 0) {
+ name = h->h_name;
+ aliases = h->h_aliases;
+ } else {
+ name = 0;
+ aliases = 0;
}
+
+ return (class__doMatchHost(c, ip, name, aliases));
}
+/*----- Debugging code ----------------------------------------------------*/
+
/* --- @class_dump@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Argumemnts: @class_node *c@ = pointer to root node
+ * @int indent@ = indent depth
*
* Returns: ---
*
- * Use: Dumps the contents of a class to a stream.
+ * Use: Dumps a class to the trace output.
*/
-void class_dump(classdef *c)
+void class_dump(class_node *c, int indent)
{
#ifdef TRACING
- sym_iter i;
- sym_base *s;
-
- /* --- Dump the table --- */
-
- if (c->type != clType_all) {
- for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) {
- switch (c->type) {
- case clType_user:
- trace(TRACE_RULE, " %i", *(int *)s->name);
- break;
- case clType_command:
- case clType_host:
- trace(TRACE_RULE, " `%s'", s->name);
- break;
+
+ static char *types[] = {
+ "<duff>",
+ "user",
+ "command",
+ "<duff>",
+ "host"
+ };
+
+ static char *nodes[] = {
+ "<duff>",
+ "<magical>",
+ "immediate",
+ "hash",
+ "binop: union",
+ "binop: difference",
+ "binop: intersection"
+ };
+
+ /* --- Handle some magical cases --- */
+
+ if (c == class_all) {
+ trace(TRACE_RULE, "rule:%*s class ALL", indent * 2, "");
+ return;
+ }
+ if (c == class_none) {
+ trace(TRACE_RULE, "rule:%*s class NONE", indent * 2, "");
+ return;
+ }
+
+ /* --- Dump basic type information --- */
+
+ trace(TRACE_RULE, "rule:%*s type == [%s], node type == [%s]%s",
+ indent * 2, "",
+ types[c->type & clType_mask],
+ nodes[(c->type & clNode_mask) >> 4],
+ (c->type & clFlag_friendly) ? " Friendly" : "");
+
+ /* --- Now trace the contents --- */
+
+ switch (c->type & clNode_mask) {
+ case clNode_immed:
+ if (c->type & clType_user) {
+ trace(TRACE_RULE, "rule:%*s user %lu",
+ indent * 2, "", (unsigned long)c->v.u);
+ } else
+ trace(TRACE_RULE, "rule:%*s `%s'", indent * 2, "", c->v.s);
+ break;
+ case clNode_hash: {
+ sym_iter i;
+ sym_base *b;
+
+ for (sym_createIter(&i, &c->v.t); (b = sym_next(&i)) != 0; ) {
+ if (c->type & clType_user) {
+ trace(TRACE_RULE, "rule:%*s user %lu",
+ indent * 2, "", (unsigned long)*(uid_t *)b->name);
+ } else
+ trace(TRACE_RULE, "rule:%*s `%s'", indent * 2, "", b->name);
}
- }
+ } break;
+ case clNode_union:
+ case clNode_diff:
+ case clNode_isect:
+ class_dump(c->v.c.l, indent + 1);
+ class_dump(c->v.c.r, indent + 1);
+ break;
}
- else
- trace(TRACE_RULE, " ALL");
+
#endif
}
/* -*-c-*-
*
- * $Id: class.h,v 1.2 1997/08/04 10:24:21 mdw Exp $
+ * $Id: class.h,v 1.3 1997/09/17 10:14:56 mdw Exp $
*
* Handling classes of things nicely
*
/*----- Revision history --------------------------------------------------*
*
* $Log: class.h,v $
+ * Revision 1.3 1997/09/17 10:14:56 mdw
+ * Complete rewrite to support class trees. Makes the behaviour of the set
+ * operators much more logical.
+ *
* Revision 1.2 1997/08/04 10:24:21 mdw
* Sources placed under CVS control.
*
/* --- Class types --- */
enum {
- clType_user = 1, /* Class of users */
- clType_command = 2, /* Class of command strings */
- clType_host = 4, /* Class of host names */
- clType_all = 7, /* All of the above (maintain me) */
- clType__limit /* First undefined class type */
+
+ /* --- Data types (user visible) --- *
+ *
+ * These bits encode what the user can think of as `types'. They get used
+ * for typechecking and things.
+ */
+
+ clType_user = 0x01, /* Class of users */
+ clType_command = 0x02, /* Class of command strings */
+ clType_host = 0x04, /* Class of host names */
+ clType_all = 0x0F, /* All of the above (maintain me) */
+ clType_mask = 0x0F, /* Mask for type flags */
+
+ /* --- Node types --- *
+ *
+ * A class actually looks suspiciously like a tree once things start
+ * getting complicated. These bits encode the type of node we've got here.
+ */
+
+ clNode_any = 0x10, /* Magic type for the `all' class */
+ clNode_immed = 0x20, /* Immediate data item */
+ clNode_hash = 0x30, /* Hashtable of values */
+ clNode_union = 0x40, /* Union of two classes */
+ clNode_binop = 0x50, /* Binary operations start here */
+ clNode_diff = 0x50, /* Difference of two classes */
+ clNode_isect = 0x60, /* Intersection of two classes */
+ clNode_mask = 0xF0, /* Mask for picking these out */
+
+ /* --- Other useful flags --- */
+
+ clFlag_friendly = 0x100 /* Item can be hashed with others */
};
/* --- Class block --- */
-typedef struct classdef {
- unsigned type; /* Type of this class */
+typedef struct class_node {
+ unsigned type; /* Class and node type, and flags */
unsigned ref; /* Reference count */
- sym_table *t; /* Symbol table for this class */
-} classdef;
+ union {
+ uid_t u; /* Immediate user id number */
+ char *s; /* Immediate string value */
+ sym_table t; /* Hash table for this class */
+ struct {
+ struct class_node *l, *r; /* Left and right operands */
+ } c; /* Class operands for binops */
+ } v; /* Value of this class node */
+} class_node;
/*----- Global variables --------------------------------------------------*/
-extern classdef *class_all; /* The match-everything class */
+extern class_node *class_all; /* The match-everything class */
+extern class_node *class_none; /* The match-nothing class */
/*----- Functions provided ------------------------------------------------*/
-/* --- @class_create@ --- *
+/* --- @class_fromString@ --- *
*
- * Arguments: @unsigned type@ = type of the class to create
- * @sym_table *t@ = pointer to symbol table which stores info
+ * Arguments: @unsigned type@ = a type field
+ * @const char *s@ = pointer to string to copy
*
- * Returns: Pointer to a @classdef@ which maintains the class's info.
+ * Returns: A pointer to a class node containing that string, typed to
+ * be the right thing.
*
- * Use: Creates a new class definition. The new definition has one
- * reference attached to it (which is the one you get returned).
+ * Use: Given a string, wrap a class node around it. The node has
+ * one reference (the one you get returned). The string is
+ * copied, so you can get rid of your original one if you like.
*/
-extern classdef *class_create(unsigned /*type*/, sym_table */*t*/);
+extern class_node *class_fromString(unsigned /*type*/, const char */*s*/);
+
+/* --- @class_fromUser@ --- *
+ *
+ * Arguments: @unsigned type@ = a type field
+ * @uid_t u@ = a user-id number
+ *
+ * Returns: A pointer to a class node containing the uid, typed to be
+ * the thing you asked for. Hopefully this will be
+ * @clType_user@.
+ *
+ * Use: Given a uid, wrap a class node around it.
+ */
+
+extern class_node *class_fromUser(unsigned /*type*/, uid_t /*u*/);
/* --- @class_inc@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Arguments: @class_node *c@ = pointer to a class block
*
* Returns: ---
*
* Use: Adds a reference to the class definition.
*/
-extern void class_inc(classdef */*c*/);
+extern void class_inc(class_node */*c*/);
/* --- @class_dec@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Arguments: @class_node *c@ = pointer to a class block
*
* Returns: ---
*
* Use: Removes a reference to a class block.
*/
-extern void class_dec(classdef */*c*/);
+extern void class_dec(class_node */*c*/);
+
+/* --- @class_mod@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to a class node
+ *
+ * Returns: A pointer to a class node, maybe the same one, maybe not,
+ * with a reference count of 1, containing the same data.
+ *
+ * Use: Gives you a node which you can modify. Don't call this
+ * for @class_all@ or @class_none@.
+ */
+
+extern class_node *class_mod(class_node */*c*/);
+
+/* --- @class_union@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the union of the two classes.
+ *
+ * Use: Performs the union operation on classes. If the types don't
+ * match, then a null pointer is returned. Both @l@ and @r@
+ * may be modified, and will be decremented before they get
+ * returned to you. If you don't want that to happen, ensure
+ * that you've claimed a reference to the original versions.
+ */
+
+extern class_node *class_union(class_node */*l*/, class_node */*r*/);
+
+/* --- @class_diff@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the difference of the two classes.
+ *
+ * Use: Performs the set difference operation on classes. If the
+ * types don't match, then a null pointer is returned. Both
+ * @l@ and @r@ may be modified, and will be decremented before
+ * they get returned to you. If you don't want that to happen,
+ * ensure that you've claimed a reference to the original
+ * versions.
+ */
+
+extern class_node *class_diff(class_node */*l*/, class_node */*r*/);
+
+/* --- @class_isect@ --- *
+ *
+ * Arguments: @class_node *l@ = left argument
+ * @class_node *r@ = right argument
+ *
+ * Returns: A class node representing the intersection of the two
+ * classes.
+ *
+ * Use: Performs the intersecion operation on classes. If the types
+ * don't match, then a null pointer is returned. Both @l@ and
+ * @r@ may be modified, and will be decremented before they get
+ * returned to you. If you don't want that to happen, ensure
+ * that you've claimed a reference to the original versions.
+ */
+
+extern class_node *class_isect(class_node */*l*/, class_node */*r*/);
+
+/* --- @class_addUser@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to a class node (may be null)
+ * @uid_t u@ = user id number
+ *
+ * Returns: Pointer to the combined node.
+ *
+ * Use: Adds a user to a node, maybe hashifying it.
+ */
+
+extern class_node *class_addUser(class_node */*c*/, uid_t /*u*/);
+
+/* --- @class_addString@ --- *
+ *
+ * Arguments: @class_node *c@ = pointer to a class node (may be null)
+ * @const char *s@ = pointer to a string
+ *
+ * Returns: Pointer to the combined node.
+ *
+ * Use: Adds a user to a node, maybe hashifying it.
+ */
+
+extern class_node *class_addString(class_node */*c*/, const char */*s*/);
-/* --- @class_userMatch@ --- *
+/* --- @class_matchUser@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
- * @int u@ = uid number to check against
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @uid_t u@ = user id number
*
- * Returns: Zero if no match, nonzero if it matched.
+ * Returns: Nonzero if it matches, zero if it doesn't.
*
- * Use: Looks to see if a user is in a group.
+ * Use: Determines whether a user is matched by a class. Assumes
+ * that the types are correct.
*/
-extern int class_userMatch(classdef */*c*/, int /*u*/);
+extern int class_matchUser(class_node */*c*/, uid_t /*u*/);
-/* --- @class_commandMatch@ --- *
+/* --- @class_matchCommand@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
- * @const char *p@ = pointer to command string to match
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @const char *s@ = pointer to a string
*
- * Returns: Zero for no match, nonzero if it matched.
+ * Returns: Nonzero if it matches, zero if it doesn't.
*
- * Use: Tries to match a string against the wildcard patterns in the
- * given class. Note that this involves examining all the
- * items, so it's not too quick. Then again, you don't have
- * big command classes, do you...?
+ * Use: Determines whether a string is matched by a class. Assumes
+ * that the types are correct.
*/
-extern int class_commandMatch(classdef */*c*/, const char */*p*/);
+extern int class_matchCommand(class_node */*c*/, const char */*s*/);
-/* --- @class_hostMatch@ --- *
+/* --- @class_matchHost@ --- *
*
- * Arguments: @classdef *c@ = pointer to class block
- * @struct in_addr addr@ = IP address to match
+ * Arguments: @class_node *c@ = pointer to root class node
+ * @struct in_addr a@ = IP address to match
*
- * Returns: Zero for no match, nonzero if it matched.
+ * Returns: Nonzero if it matches, zero if it doesn't.
*
- * Use: Tries to match an IP address against the patterns and masks
- * in the given class.
+ * Use: Determines whether a host matches a host class. Assumes
+ * that the types are correct. The actual mechanism is a bit
+ * odd here, but I think this is the Right Thing. At each stage
+ * I try to match %%@/all/%% of the possible names for the host.
+ * Thus host `splat' with address 1.2.3.4 would fail to match
+ * the class "1.2.*" - "splat". This seems to be what the
+ * author intuitively expects. It's just a bit weird.
*/
-extern int class_hostMatch(classdef */*c*/, struct in_addr /*addr*/);
+extern int class_matchHost(class_node */*c*/, struct in_addr /*a*/);
/* --- @class_dump@ --- *
*
- * Arguments: @classdef *c@ = pointer to a class block
+ * Argumemnts: @class_node *c@ = pointer to root node
+ * @int indent@ = indent depth
*
* Returns: ---
*
- * Use: Dumps the contents of a class to a stream.
+ * Use: Dumps a class to the trace output.
*/
-extern void class_dump(classdef */*c*/);
+extern void class_dump(class_node */*c*/, int /*indent*/);
/*----- That's all, folks -------------------------------------------------*/
~mdw / become / commitdiff