+struct uid_gid {
+ unsigned int name_off;
+ union {
+ uid_t uid;
+ gid_t gid;
+ };
+};
+
+struct trie_node {
+ /* this node's first child */
+ unsigned int child_idx;
+ /* the next child of our parent node's child list */
+ unsigned int next_child_idx;
+ /* this node's last child (shortcut for append) */
+ unsigned int last_child_idx;
+ unsigned int value_off;
+ unsigned short value_len;
+ unsigned char key;
+};
+
+struct udev_rules {
+ struct udev *udev;
+ int resolve_names;
+
+ /* every key in the rules file becomes a token */
+ struct token *tokens;
+ unsigned int token_cur;
+ unsigned int token_max;
+
+ /* all key strings are copied to a single string buffer */
+ char *buf;
+ size_t buf_cur;
+ size_t buf_max;
+ unsigned int buf_count;
+
+ /* during rule parsing, strings are indexed to find duplicates */
+ struct trie_node *trie_nodes;
+ unsigned int trie_nodes_cur;
+ unsigned int trie_nodes_max;
+
+ /* during rule parsing, uid/gid lookup results are cached */
+ struct uid_gid *uids;
+ unsigned int uids_cur;
+ unsigned int uids_max;
+ struct uid_gid *gids;
+ unsigned int gids_cur;
+ unsigned int gids_max;
+};
+
+/* KEY=="", KEY!="", KEY+="", KEY="", KEY:="" */
+enum operation_type {
+ OP_UNSET,
+
+ OP_MATCH,
+ OP_NOMATCH,
+ OP_MATCH_MAX,
+
+ OP_ADD,
+ OP_ASSIGN,
+ OP_ASSIGN_FINAL,
+};
+
+enum string_glob_type {
+ GL_UNSET,
+ GL_PLAIN, /* no special chars */
+ GL_GLOB, /* shell globs ?,*,[] */
+ GL_SPLIT, /* multi-value A|B */
+ GL_SPLIT_GLOB, /* multi-value with glob A*|B* */
+ GL_SOMETHING, /* commonly used "?*" */
+ GL_FORMAT,
+};
+
+/* tokens of a rule are sorted/handled in this order */
+enum token_type {
+ TK_UNSET,
+ TK_RULE,
+
+ TK_M_ACTION, /* val */
+ TK_M_DEVPATH, /* val */
+ TK_M_KERNEL, /* val */
+ TK_M_DEVLINK, /* val */
+ TK_M_NAME, /* val */
+ TK_M_ENV, /* val, attr */
+ TK_M_SUBSYSTEM, /* val */
+ TK_M_DRIVER, /* val */
+ TK_M_WAITFOR, /* val */
+ TK_M_ATTR, /* val, attr */
+
+ TK_M_PARENTS_MIN,
+ TK_M_KERNELS, /* val */
+ TK_M_SUBSYSTEMS, /* val */
+ TK_M_DRIVERS, /* val */
+ TK_M_ATTRS, /* val, attr */
+ TK_M_PARENTS_MAX,
+
+ TK_M_TEST, /* val, mode_t */
+ TK_M_PROGRAM, /* val */
+ TK_M_IMPORT_FILE, /* val */
+ TK_M_IMPORT_PROG, /* val */
+ TK_M_IMPORT_PARENT, /* val */
+ TK_M_RESULT, /* val */
+ TK_M_MAX,
+
+ TK_A_IGNORE_DEVICE,
+ TK_A_STRING_ESCAPE_NONE,
+ TK_A_STRING_ESCAPE_REPLACE,
+ TK_A_NUM_FAKE_PART, /* int */
+ TK_A_DEVLINK_PRIO, /* int */
+ TK_A_OWNER, /* val */
+ TK_A_GROUP, /* val */
+ TK_A_MODE, /* val */
+ TK_A_OWNER_ID, /* uid_t */
+ TK_A_GROUP_ID, /* gid_t */
+ TK_A_MODE_ID, /* mode_t */
+ TK_A_ENV, /* val, attr */
+ TK_A_NAME, /* val */
+ TK_A_DEVLINK, /* val */
+ TK_A_EVENT_TIMEOUT, /* int */
+ TK_A_IGNORE_REMOVE,
+ TK_A_ATTR, /* val, attr */
+ TK_A_RUN, /* val, bool */
+ TK_A_GOTO, /* size_t */
+ TK_A_LAST_RULE,
+
+ TK_END,
+};
+
+/* we try to pack stuff in a way that we take only 12 bytes per token */
+struct token {
+ union {
+ unsigned char type; /* same as in rule and key */
+ struct {
+ unsigned char type;
+ unsigned char flags;
+ unsigned short token_count;
+ unsigned int label_off;
+ unsigned short filename_off;
+ unsigned short filename_line;
+ } rule;
+ struct {
+ unsigned char type;
+ unsigned char flags;
+ unsigned char op;
+ unsigned char glob;
+ unsigned int value_off;
+ union {
+ unsigned int attr_off;
+ int ignore_error;
+ int i;
+ unsigned int rule_goto;
+ mode_t mode;
+ uid_t uid;
+ gid_t gid;
+ int num_fake_part;
+ int devlink_prio;
+ int event_timeout;
+ };
+ } key;
+ };
+};
+
+#define MAX_TK 64
+struct rule_tmp {
+ struct udev_rules *rules;
+ struct token rule;
+ struct token token[MAX_TK];
+ unsigned int token_cur;
+};
+
+#ifdef DEBUG
+static const char *operation_str(enum operation_type type)