/****************************************************************************** MODULE list.c DESCRIPTION XDME Command Module An alternative to AVL Trees are lists ... however they are very slow to be searched over, but they are needed for GTB, since Gadtools needs Lists to be connected with Listview gadgets ... the current implementation is sort of overkill to this need, since it also implements parts of a hierarchy with recursive lists ... NOTES BUGS none known - never tested TODO * variable interface * conversion of Texts, RefPaths EXAMPLES SEE ALSO AUTHOR Bernd "0" Noll (b_noll@informatik.uni-kl.de) HISTORY 12-11-94 b_noll created 24-11-94 b_noll continued 24-11-94 b_noll fixes 25-11-94 b_noll fixes 03-12-94 b_noll removed 'defs.h' 05-12-94 b_noll added *Name*|*Value* ******************************************************************************/ /************************************** Includes **************************************/ /* #include "defs.h" */ #include "xdme_base.h" #include "HL.h" /************************************** Global Variables **************************************/ //ULONG HL_Dispose (struct HNode *n); /************************************** Internal Defines & Structures **************************************/ #define HL_SPLITNAME '/' #define HL_INDEXNAME '#' #define IsXLLNode(n) 1 #define IsReadOnly(n) !IsWriteable(n) #define MakeWritable(n) #define IsWriteable(n) 1 #define HL_IsSysEntry(n) ((n)->Flags & XLF_SYSENTRY) /* xl error codes */ #define HL_OK 0 #define HL_ERROR 1 #define HL_NOMEM 2 #define HL_NOLIST 3 #define HL_DUPTREENODE 4 #define HL_ILLEGALNAME 5 #define HL_NOSUCHLIST 6 #define HL_POSITION2FAR 7 #define HL_UNKNOWNPOSITION 8 #define HL_MODIFYCONSTLIST 9 #define HL_NESTEDLIST 10 #define HL_REDEFINEDLIST 11 #define HL_NOTFOUND 12 #define HL_SYSLIST 13 #define HL_NOVALUE 14 /* xlnode.Flags */ #define XLF_SYSENTRY 1 struct Locker { struct SNode Node; struct Locker *Base; APTR Gadget; ULONG Attr; }; /* struct */ /************************************** Internal Variables **************************************/ extern struct HNode *HL_Root; /************************************** Internal Prototypes **************************************/ extern int GTB_Notify(APTR, ULONG, APTR, APTR); struct HLASubs *HL_InstSubs (struct HNode *base); struct HLAValue *HL_InstValue (struct HNode *base); /************************************** Macros **************************************/ #define ToAssign(cp) do{ while ((*cp) && (*cp != '=')) cp++; if (*cp) cp++; }while(0) #define PROC void* /************************************** Implementation **************************************/ /* ---- send a notification */ int HL_Notify (struct HNode *gadget, ULONG attr, APTR value, struct HNode *base) { //puts ("HL_Notify"); return GTB_Notify(gadget, attr, value, base); } /* HL_Notify */ /* ---- notify all partners which are listening 2 attr */ void HL_NotifyLocks (struct HNode *base, ULONG attr, APTR value) { struct Locker *l; if (base) for (l = (APTR)base->Locks.Head; l; l = (APTR)l->Node.Succ) if (l->Attr && (l->Attr == attr)) { l->Attr = 0; HL_Notify (l->Gadget, attr, value, base); l->Attr = attr; } } /* HL_NotifyLocks */ /* ---- remove a certain lock from base */ void HL_RemoveLock (struct Locker *l, struct HNode *base) { //puts ("remlock"); SLL_Remove (&base->Locks, &l->Node); HL_Notify (l->Gadget, l->Attr, NULL, NULL); free(l); } /* HL_RemoveLock */ /* ---- strip all locks from base */ void HL_RemoveLocks (struct HNode *base) { SLL_Scan(&base->Locks, (PROC)HL_RemoveLock, base); } /* HL_RemoveLocks */ /* ---- build a connection between base and its partner */ ULONG HL_Connect (struct HNode *base, struct HNode *partner, ULONG attr) { struct Locker *l; if (attr != HLA_Name && attr != HLA_Labels && attr != HLA_Value) return 0; if ((l = malloc(sizeof (*l)))) { bzero(l, sizeof (*l)); SLL_AddHead(&base->Locks, &l->Node); l->Gadget = partner; l->Attr = attr; //if (attr == HLA_Name) // HL_Notify(partner, attr, base->Name, base); //if (attr == HLA_Value) // HL_Notify(partner, attr, v->Value, base); if (attr == HLA_Labels) { struct HLASubs *s; s = HL_InstSubs(base); if (!s) return HL_NOLIST; HL_Notify(partner, attr, &s->Subs, base); } return 1; } /* if */ return 0; } /* HL_Connect */ #if 0 /* ---- Find a Lock between base and its partner */ struct Locker *HL_FindLock (struct HNode *base, APTR partner) { struct Locker *l; //puts ("findlock"); if (base) for (l = (APTR)base->Locks.Head; l; l = (APTR)l->Node.Succ) /* 1 */ if (l->Gadget == partner) return l; return NULL; } /* HL_FindLock */ /* ---- remove all connections between base and its partner */ int HL_Disconnect (struct HNode *base, struct HNode *partner) { struct Locker *l; //puts ("disconnecting"); if (base && partner) while ((l = HL_FindLock(base, partner))) { /* line 2 */ HL_RemoveLock(l, base); } return HL_OK; } /* HL_Disconnect */ #endif static int HL_SetNodeValue (struct HNode *n, const char *value) { /* strictly speaking we should surround this with Parent->Unlock ... Parent->lock */ struct HLAValue *v; v = HL_InstValue(n); if (!v) return HL_NOVALUE; v->Value = strrep (v->Value, value); if (n->Locks.Head) HL_NotifyLocks (n, HLA_Value, v->Value); return HL_OK; } /* HL_SetNodeValue */ /* ---- create a new entry */ static struct HNode *HL__recent_created; static int HL_NewNode (const char *name, struct HNode *parent, const char *value) { struct HNode *n; int rv; if ((n = HL_New(name, parent, HLF_SUBCARRIER|HLF_VALUE))) { HL__recent_created = n; rv = HL_SetNodeValue (n, value); if (rv != HL_OK) HL_Dispose(n); return rv; } /* if */ return HL_NOMEM; } /* HL_NewNode */ static int HL_CheckNode (struct HNode *a, const char *c) { return stricmp (a->Name, c); } /* HL_CheckNode */ static int HL_CompareNodes (struct HNode *a, struct HNode *b) { return stricmp (a->Name, b->Name); } /* HL_CompareNodes */ static UBYTE *HL__FindNameSplit (UBYTE *name) { return strchr (name, HL_SPLITNAME); } /* HL__FindNameSplit */ static struct HNode *HL_LockSubNode (struct HNode *base, UBYTE *name) { UBYTE *nextpart; do { if (!base) return NULL; /* seek only with Lists */ //if (!IsXLLNode(base)) // return NULL; nextpart = HL__FindNameSplit (name); if (nextpart) *nextpart = 0; /* amigoid ... */ if (name == nextpart) { base = base->Parent; } else { struct HLASubs *s; s = HL_InstSubs(base); if (!s) return NULL; if (*name != HL_INDEXNAME) base = (struct HNode *)DLL_Find (&s->Subs, (PROC)HL_CheckNode, name); else base = (struct HNode *)DLL_NumToNode(&s->Subs, atoi(name + 1)); } /* if */ if (nextpart) { *nextpart = HL_SPLITNAME; name = nextpart + 1; } /* if */ } while (nextpart); return base; } /* HL_LockSubNode */ /*************************************************** COMMAND INTERFACE ***************************************************/ void HL_Error (ULONG code, UBYTE **av) { switch (code) { case HL_OK: return ; //RET_SUCC; case HL_ERROR: error ("XL Module:\nShoot the programmer!"); break; case HL_NOMEM: nomemory(); break; case HL_NOLIST: error ("%s:\nTry list access a non-list", av[0]); break; case HL_DUPTREENODE: error ("%s:\nTry to add a node with an already\npresent name into a tree!", av[0]); break; case HL_ILLEGALNAME: error ("%s:\n'/' is not allowed in a name", av[0]); break; case HL_NOSUCHLIST: error ("%s:\nList not found", av[0]); break; case HL_POSITION2FAR: error ("%s:\nPosition not in list", av[0]); break; case HL_UNKNOWNPOSITION: error ("%s:\nGiven an unknown position", av[0]); break; case HL_MODIFYCONSTLIST: error ("%s:\nTried to modify CONST list", av[0]); break; case HL_NOTFOUND: error ("%s:\nNode or List not found", av[0]); break; case HL_REDEFINEDLIST: error ("%s:\nList has already been defined", av[0]); break; case HL_SYSLIST: error ("%s:\nSystemlists are read only!", av[0]); break; case HL_NOVALUE: error ("%s:\nTry to change a non-existant value!", av[0]); break; default: error ("%s:\nUnknown error in List module", av[0]); } /* switch */ //return RET_FAIL; } /* HL_Error */ APTR HL_LockNode (UBYTE *name) { return HL_LockSubNode (HL_Root, name); } /* HL_LockNode */ static int HL__LockNodeRel (UBYTE *bname, UBYTE *where, BOOL truenode, struct HNode **base, struct HNode **pos) { struct HLASubs *s; *base = *pos = NULL; if (bname) { if (!(*base = HL_LockSubNode (HL_Root, bname))) return HL_NOSUCHLIST; if (HL_IsSysEntry(*base) /* || (((*base)->Parent) && (HL_IsSysEntry((*base)->Parent))) */ ) return HL_SYSLIST; s = HL_InstSubs(*base); if (!s) return HL_NOLIST; switch (*where | 32) { case 'i': /* index */ ToAssign (where); case '0': /* number */ case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': *pos = (struct HNode *)DLL_NumToNode (&s->Subs, atol (where)); break; case 'h': /* head */ *pos = (struct HNode *)(truenode? (DLL_GetHead(&s->Subs)): (&s->Subs.Head)); break; case 't': /* tail */ *pos = (struct HNode *)DLL_GetTail(&s->Subs); break; case 'n': /* name */ ToAssign (where); case HL_INDEXNAME: *pos = HL_LockSubNode (*base, where); break; default: return HL_UNKNOWNPOSITION; } /* switch */ if (!*pos) return HL_POSITION2FAR; return HL_OK; } /* if */ return HL_ERROR; } /* HL__LockNodeRel */ /*DEFHELP #cmd lists ADDNODE list where name value - add a node to a list */ DEFUSERCMD("AddNode", 4, CF_VWM|CF_ICO|CF_COK, void, do_addnode, (void), ) { extern int HL_AddMember(struct HNode*, struct HNode *, struct HNode *); extern int HL_RemMember(struct HNode*, struct HNode *); int rv = HL_OK; if (HL__FindNameSplit(av[2])) { rv = HL_ILLEGALNAME; } else { struct HNode *base, *pos, *this; rv = HL__LockNodeRel (av[1], av[2], 0, &base, &pos); if (rv == HL_OK) { rv = HL_NewNode (av[3], base, av[4]); if (rv == HL_OK) { struct HLASubs *s; s = HL_InstSubs(base); this = DLL_GetTail (&s->Subs); rv == HL_RemMember (base, this); if (rv == HL_OK) { rv = HL_AddMember (base, this, pos); } /* if */ } /* if */ } /* if */ } /* if */ HL_Error(rv, av); } /* do_addnode */ /*DEFHELP #cmd lists REMNODE list where - delete a node inside a list */ DEFUSERCMD("RemNode", 2, CF_VWM|CF_ICO|CF_COK, void, do_remnode, (void), ) { int rv = HL_OK; if (HL__FindNameSplit(av[2])) { rv = HL_ILLEGALNAME; } else { struct HNode *base, *pos; rv = HL__LockNodeRel (av[1], av[2], 1, &base, &pos); if (rv == HL_OK) { rv = HL_Dispose (pos); } /* if */ } /* if */ HL_Error(rv, av); } /* do_remnode */ /*DEFHELP #cmd lists DEFLIST name - create a list */ DEFUSERCMD("DefList", 1, CF_VWM|CF_ICO|CF_COK, void, do_deflist, (void), ) { struct HNode *n; int rv = HL_OK; if (HL__FindNameSplit(av[1])) { rv = HL_NESTEDLIST; } else if ((n = HL_LockSubNode (HL_Root, av[1]))) { rv = HL_REDEFINEDLIST; } else { rv = HL_NewNode (av[1], HL_Root, ""); } /* if */ HL_Error(rv, av); } /* do_deflist */ /*DEFHELP #cmd lists DROPLIST name - delete a list */ DEFUSERCMD("DropList", 1, CF_VWM|CF_ICO|CF_COK, void, do_droplist, (void), ) { struct HNode *n; int rv = HL_OK; if (HL__FindNameSplit(av[1])) { rv = HL_NESTEDLIST; } else if (!(n = HL_LockSubNode (HL_Root, av[1]))) { rv = HL_NOTFOUND; } else { if (!HL_IsSysEntry(n)) rv = HL_Dispose (n); else rv = HL_SYSLIST; } /* if */ HL_Error (rv, av); } /* do_droplist */ /****************************************************************************** ***** END list.c ******************************************************************************/ /* debugging purposes */ static void __showlist (struct HNode *n, APTR dummy, int i) { extern int printf(const char *, ...); printf ("entry # %d == `%s'\n", i, n->Name); } /* __showlist */ DEFUSERCMD("_Showlist", 1, CF_VWM|CF_ICO|CF_COK, void, do_showlist, (void),) { struct HLASubs *s; struct HNode *base; if (!(base = HL_LockSubNode (HL_Root, av[1]))) HL_Error(HL_NOSUCHLIST, av); else { //printf ("base=%08lx/%s\n", base, base->Name); s = HL_InstSubs(base); //printf (" s=%08lx\n", s); HL_Scan(base, __showlist, NULL); } } /*DEFHELP #node lists */ /*DEFLONG #long DEFLIST,DROPLIST,ADDNODE,REMNODE preliminary interface to xdme lists ... "/" and "#" are special characters in a meaning, that they must not be used in the name of a list or a node (in fact "/" is used as a separator between listname and nodename, and "#" is a special name to indicate numbered access ) There are currently some ReadOnly system lists: "*RefPaths*" - list of the Paths to check with tags/refs use ADDPATH/REMPATH to modify "*MenuStrips*" - list of available Menustrips use NEWMENUSTRIP/DELMENUSTRIP to modify "*KeyTables*" - list of available Keytables use NEWKEYTABLE/DELKEYTABLE to modify a "*AppIcons*" list is to be introduced as soon, as multiple Appicons are allowed ... the Lists GTBProjects, MenuItems and all user defined Lists are prepared for nested usage, but this feature is not yet enabled Currently the lists are pretty unusable (execpt for use in connection with the GTB module, since it is possible to connect any list with a number of GTB Listview gadgets, which are automatically updated if the list is changed ...) The User interface to Modifyable lists contains currently: "DEFLIST name" and "DROPLIST name" for rootlevel list management, and "ADDNODE list where name value" and "REMNODE list where" for node manipulation; in that case "where" can be "tail", "head", a number (perhaps preceeded by "idx=") or "name=" followed by the name of an entry in the list ... Variable Interface is done via the following mechanism: $(//*Value*) -> a node's value (if exists) $(//*Name*) -> a node's name (always) please note, that a name starting with a "#" is internally treated as a number, so "#z" is Node no.0 and "#10" is node number 10 - this indexname is also usable after the "name=" directive in ADD/REM-NODE or as a Name in the variable access ... (so You can e.g. say "title (First Text is $(*Texts*\/#0\/*Name*))") */ DEFVARTREE( 80, "LNODE_", VAR_LN, 6, 6, VF_COP, NULL, NULL, SetLNode, GetLNode ) Prototype int SetLNode (UBYTE *name, UBYTE *value); int SetLNode (UBYTE *name, UBYTE *value) { struct HNode *n; UBYTE *lastpart; int query = HLA_Value; lastpart = strrchr(name, HL_SPLITNAME); if (lastpart) { *lastpart = 0; if (!strcmp (lastpart + 1, "*Value*")) query = HLA_Value; else { *lastpart = HL_SPLITNAME; lastpart = NULL; } } n = HL_LockNode (name); if (lastpart) *lastpart = HL_SPLITNAME; if (!n) return 0; if (query == HLA_Value) if (HL_SetNodeValue(n, value) == HL_OK) return 1; return 0; } /* SetLNode */ #ifndef HLA_Index #define HLA_Index 99 #endif Prototype UBYTE *GetLNode (UBYTE *name); UBYTE *GetLNode (UBYTE *name) { struct HNode *n; struct HLAValue *v; UBYTE *lastpart; int query = HLA_Value; lastpart = strrchr(name, HL_SPLITNAME); if (lastpart) { *lastpart = 0; if (!strcmp (lastpart + 1, "*Value*")) query = HLA_Value; else if (!strcmp (lastpart + 1, "*Name*")) query = HLA_Name; else if (!strcmp (lastpart + 1, "*Index*")) query = HLA_Index; else { *lastpart = HL_SPLITNAME; lastpart = NULL; } } n = HL_LockNode (name); if (lastpart) *lastpart = HL_SPLITNAME; if (!n) return NULL; if (query == HLA_Name) return n->Name; if (query == HLA_Index) { int ri = 0; struct HLASubs *s; if (n->Parent) if ((s = HL_InstSubs(n->Parent))) { ri = DLL_NodeToNum(&s->Subs, &n->Node); return ltostr(ri); } } if (query == HLA_Value) { v = HL_InstValue(n); return v ? v->Value : NULL; } return NULL; } /* GetLNode */