/* * Pure Data Packet header file. List class * Copyright (c) by Tom Schouten * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * */ /** * @file list.h * @brief PF list implementation. PF, stealing part of the design of pd, uses typed atoms to represent data elements. An atom can contain scalars (int, float, symbol, atom pointer, generic pointer, forth tokens and pointers, ...) and packets. Atoms (pf_atom_t) can be chained to represent lists. A list head (pf_list_t) can be used to implement stacks, lists, trees and queues. Functions starting with "pf_tree" recurse through sublists. Functions starting with "pf_list" stay at the top level. Some remarks on stale pointer checking for lists and atoms. The first element in list and atom structs will be used by the fastallocator to link them together in the free pool. In order to do some error checking for stale referencing of deleted atoms and lists, this spot is reserved for the free pool and not used by atom and list operations. (i.e. this prevents the freelist to become corrupted if a deleted atom is referenced). Error checking is implemented as follows: pf_fastalloc always initializes memory to zero when new memory is allocated, except for the first sizeof(*) bytes at the start of a struct, which are used to store chaining pointers. By defining all structs in such a way that zero means empty, some checking can be implemented. This can be done conditionally so it only happens in debug mode. */ #ifndef PF_LIST_H #define PF_LIST_H #include #include /** * Atom types. * 0x00 -> 0x3f : scalar types * 0x40 -> 0x7f : list types * 0x80 -> 0xff : c extension types (c objects) * rest can be interpreted as a symbol */ #define LIT(x) ((x) << 2) // #define LIT(x) (x) #define PF_LIST_MASK LIT(0xffffffc0) #define PF_LIST_ID LIT(0x00000040) /* generic atoms */ #define a_undef LIT(0) ///< undefined (no value assigned) #define a_float LIT(1) ///< floating point number #define a_int LIT(2) ///< signed integer #define a_symbol LIT(3) ///< symbol (living in one of the namespaces) #define a_packet LIT(4) ///< a data packet #define a_atom_pointer LIT(5) ///< a pointer to an atom #define a_error LIT(6) ///< integer error code #define a_pointer LIT(7) ///< generic pointer /** forth atoms */ #define a_forth_codefield LIT(8) ///< a pointer to a c function implementing a primitive #define a_forth_xt LIT(9) ///< execution token (resolved dictionary item) #define a_forth_sentinel LIT(10) ///< points to link (list head) #define a_forth_exception LIT(11) ///< a marker containing data stack depth for exception rewind /** LIST SLOT 0x40 -> 0x7f these behave like ordinary lists: data owned by list. identification is necessary for drop and dup to work. */ /** generic list */ #define a_stale LIT(0x3f) #define a_list LIT(0x40) /** c extension types 0x80 -> 0xff */ #define a_extension LIT(0x80) ///< all types greater or equal than this one are c extensions /** * \brief Scalar word union * * Contains all scalar types that can reside in an atom. */ union pf_word { void* w_pointer; ///< typeless pointer float w_float; ///< single precision floating point number int w_int; ///< integer pf_symbol_t* w_symbol; ///< symbol pf_packet_t w_packet; ///< packet pf_list_t* w_list; ///< sublist, mechanism to build trees pf_atom_t* w_atom_pointer; ///< pointer to another atom (variable) pf_word_type_t w_word_type; ///< atom type pf_error_t w_error; ///< error code pf_forth_primitive_t w_primitive; ///< primitive forth word pf_atom_t* w_forth_xt; ///< forth execution token }; /** * \brief Atom * * An atom is a variable storage space. (FIXME: this should be a 'cell') * Atoms are chained in linked lists and are associated (owned) by only * one pf_list structure. */ #define PF_LIST_OLD 1 struct pf_atom { #if PF_LIST_OLD pf_atom_t *next; ///< next element pf_word_type_t t; ///< atom type pf_word_t w; ///< atom content #else pf_atom_t *_next; ///< next element pf_word_type_t _t; ///< atom type pf_word_t _w; ///< atom content #endif }; // value access #if PF_LIST_OLD static inline pf_atom_t* pf_atom_next(pf_atom_t *a) { return a->next; } static inline pf_word_type_t pf_atom_type(pf_atom_t *a) { return a->t; } static inline pf_word_t pf_atom_word(pf_atom_t *a) { return a->w; } #else static inline pf_atom_t* pf_atom_next(pf_atom_t *a) { return a->_next; } static inline pf_word_type_t pf_atom_type(pf_atom_t *a) { return a->_t; } static inline pf_word_t pf_atom_word(pf_atom_t *a) { return a->_w; } #endif // FIXME: mutation access /** * Check if an atom is a list. (nonzero = yes) * Some lists are typed other than a_list (i.e. a_compiled_forthcode, a_poly_forthword). * This function is used to determine if an atom is a list by the pf_tree_* functions. */ static inline int pf_atom_islist(struct pf_atom *a) { return ((pf_atom_type(a) & PF_LIST_MASK) == PF_LIST_ID); } /** * \brief List A list is a header and a chain of atoms. CONVENTION: Trees, Stacks and Lists. * All operations with "list" in them operate on flat lists. all the items contained in the list are either pure atoms (floats, ints, or symbols) or references (packets, pointers, lists). List operations do not care about ownership of referenced data (reference counts). * All operations with "tree" in them, operate on recursive lists (trees). All sublists of the list (tree) are supposed to be owned by the parent list. Tree operations do not care about ownership of other data (pointers and packets). * Forth Stacks are trees (the forth can have a tree on a stack) Operations with "stack" in them treat the data as owned by the stack. (see forth.h) */ struct pf_list { #if PF_LIST_OLD pf_atom_t *first; ///< first atom (for stack read/write usage) pf_atom_t *last; ///< last atom (for queue write usage) int elements; ///< number of elements in list #else pf_atom_t *_first; ///< first atom (for stack read/write usage) pf_atom_t *_last; ///< last atom (for queue write usage) int _elements; ///< number of elements in list #endif }; /* access functions */ #if PF_LIST_OLD static inline pf_atom_t *pf_list_first(pf_list_t *l){return l->first;} static inline pf_atom_t *pf_list_last(pf_list_t *l) {return l->last;} static inline int pf_list_elements(pf_list_t *l){return l->elements;} #else static inline pf_atom_t *pf_list_first(pf_list_t *l){return l->_first;} static inline pf_atom_t *pf_list_last(pf_list_t *l) {return l->_last;} static inline int pf_list_elements(pf_list_t *l){return l->_elements;} #endif char *pf_type(pf_word_type_t t); typedef void* (*pf_closure_atom_t)(void *data, pf_atom_t *a); /** iterators */ /** apply an atom map method to a list */ static inline void* pf_list_iterate (pf_list_t *l, pf_closure_atom_t m, void *data){ pf_atom_t *a = pf_list_first(l); void *x; while (a) { if ((x = m(data, a))) return x; a = pf_atom_next(a); } return 0; } /** same, but recursive */ static inline void* pf_tree_iterate (pf_list_t *l, pf_closure_atom_t m, void *data){ pf_atom_t *a = pf_list_first(l); void *x; while (a){ if (pf_atom_islist(a)) { x = pf_tree_iterate(pf_atom_word(a).w_list, m, data); } else { x = m(data, a); } if (x) return x; a = pf_atom_next(a); } return 0; } /* creation / destruction */ pf_atom_t* pf_atom_new (void); ///< create an atom void pf_atom_free (pf_atom_t *); ///< free an atom pf_list_t* pf_list_new (void); ///< create an empty list pf_list_t* pf_tree_new (void); ///< create an empty tree (alias of pf_list_new) pf_list_t* pf_stack_new (void); ///< create an empty stack (alias of pf_list_new) void pf_list_free (pf_list_t *l); ///< free a list void pf_list_clear (pf_list_t *l); ///< remove all elements from list void pf_tree_free (pf_list_t *l); ///< free a tree void pf_tree_clear (pf_list_t *l); ///< remove all nodes from tree void pf_stack_free (pf_list_t *l); ///< free a tree void pf_stack_clear (pf_list_t *l); ///< remove all nodes from tree // read an atom from current input //pf_atom_t *pf_input_get_atom(void); /* control chars. */ #define PF_PARSE_LIST_LEFT '(' #define PF_PARSE_LIST_RIGHT ')' #define PF_PARSE_COMMENT_LEFT '#' #define PF_PARSE_COMMENT_RIGHT '\n' #define PF_PARSE_QUOTE '"' #define PF_PARSE_ESCAPE '\\' #define PF_PARSE_DECIMAL '.' #define PF_PARSE_RAW 0 /* atom/stack ops these assume lists contained in atoms are stacks */ pf_atom_t *pf_stackatom_dup(pf_atom_t *a); void pf_stackatom_drop(pf_atom_t *a); void pf_stackatom_clear(pf_atom_t *a); /* copy: (reverse) copies a list. */ /* list copy is flat. pointers and packets are copied. so you need to ensure reference consistency yourself. */ pf_list_t* pf_list_copy (pf_list_t *l); ///< copy a list pf_list_t* pf_tree_copy (pf_list_t *l); ///< copy a tree pf_list_t* pf_stack_copy (pf_list_t *l); ///< copy a stack /* information */ //int pf_list_contains (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< does a list contain a certain word? //int pf_list_size (pf_list_t *l); ///< get the list size /* access */ void pf_list_push (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< add a word to the front of the list void pf_list_queue (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< add a word to the back of the list // void pf_stack_push (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< add a word to the front of the stack (dups) // void pf_stack_queue (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< add a word to the back of the stack (dups) //void pf_list_add_to_set (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< add a word if it's not already in there //void pf_list_remove (pf_list_t *l, pf_word_type_t t, pf_word_t w); ///< remove a word from the list void pf_list_push_atom(pf_list_t *l, pf_atom_t *a); ///< add an atom to the front of the list void pf_list_queue_atom(pf_list_t *l, pf_atom_t *a); ///< add an atom to the back of the list void pf_stack_push_atom(pf_list_t *l, pf_atom_t *a); ///< add an atom to the front of the stack (dups) void pf_stack_queue_atom(pf_list_t *l, pf_atom_t *a); ///< add an atom to the back of the stack (dups) void pf_list_insert_atom(pf_list_t *l, int n, pf_atom_t *a); ///< add an atom to the back of the stack (dups) /* these don't do error checking. out of bound == error */ pf_atom_t *pf_list_pop_atom (pf_list_t *l); ///< extract the first atom from the list. (no checking.) pf_word_t pf_list_pop (pf_list_t *l); ///< extract the first word from the list. pf_word_t pf_list_index (pf_list_t *l, int index); ///< get word at index //void pf_list_pop_push (pf_list_t *source, pf_list_t *dest); ///< pop source, push dest /* util */ void pf_list_reverse(pf_list_t *l); ///< reverse a list (in place) //void pf_list_cat (pf_list_t *l, pf_list_t *tail); ///< concatinate: copy tail and add it to the first list void pf_list_join (pf_list_t *l, pf_list_t *tail); ///< join elements of 2 lists (this deletes the tail list) /* generic atom iterator */ #define PF_ATOM_IN(list,atom) \ for (atom = FIRST(list) ; atom ; atom = NEXT(atom)) ///< iterate over list /* fast single type iterators */ #define PF_WORD_IN(list, atom, word, type) \ for (atom=list->first ;atom && ((word = atom -> w . type) || 1); atom=atom->next) ///< generic word iterator /* type specific */ #define PF_POINTER_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_pointer) ///< pointer iterator #define PF_INT_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_int) ///< int iterator #define PF_FLOAT_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_float) ///< float iterator #define PF_SYMBOL_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_symbol) ///< symbol iterator #define PF_PACKET_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_packet) ///< packet iterator #define PF_LIST_IN(list, atom, x) PF_WORD_IN(list, atom, x, w_list) ///< list iterator /* atom access */ #define PF_LIST_ATOM_0(x) (pf_list_first(x)) #define PF_LIST_ATOM_1(x) (pf_atom_next(PF_LIST_ATOM_0(x))) #define PF_LIST_ATOM_2(x) (pf_atom_next(PF_LIST_ATOM_1(x))) #define PF_LIST_ATOM_3(x) (pf_atom_next(PF_LIST_ATOM_2(x))) #define PF_LIST_ATOM_4(x) (pf_atom_next(PF_LIST_ATOM_3(x))) #define PF_ATOM_FLAGMASK 0xff ///< an atom can have one byte of flags /** * Check atom flags. Atoms are allowed to have flags, * which are application specific. Used by packet forth to mark writable atoms. * If the bits outside of the PF_ATOM_FLAGMASK are nonzero, it is a stale * atom (part of a freelist). */ //static inline int pf_atom_stale(pf_atom_t *a){return ((a->flags) & (~PF_ATOM_FLAGMASK));} static inline int pf_atom_stale(pf_atom_t *a){return 0;} // disabled /* atom -> type symbol */ struct pf_symbol *pf_atom_typesymbol(pf_atom_t *a); pf_atom_t *pf_atom_from_typesymbol(struct pf_symbol *s); /* type specific shortcuts push = add to front queue = add to back pop = remove from front */ #define MAKE_QUEUE_FUNC(kind, type) \ static inline void pf_list_queue_##kind \ (pf_list_t *l, type thing) { \ pf_word_t w; \ w.w_##kind = thing; \ pf_list_queue(l, a_##kind, w); \ } // pf_list_queue(l, a_##kind, ((pf_word_t)thing));} //(pf_list_t *l, type thing) {pf_list_queue(l, a_##kind, (pf_word_t)((type)thing));} MAKE_QUEUE_FUNC(symbol, struct pf_symbol*) //MAKE_QUEUE_FUNC(symbol, pf_symbol_t*) MAKE_QUEUE_FUNC(list, pf_list_t*) MAKE_QUEUE_FUNC(float, float) MAKE_QUEUE_FUNC(int, int) MAKE_QUEUE_FUNC(packet, pf_packet_t) MAKE_QUEUE_FUNC(pointer, void*) #define MAKE_PUSH_FUNC(kind, type) \ static inline void pf_list_push_##kind \ (pf_list_t *l, type thing) { \ pf_word_t w; \ w.w_##kind = thing; \ pf_list_push(l, a_##kind, w); \ } //{pf_list_push(l, a_##kind, (pf_word_t)(type)thing);} MAKE_PUSH_FUNC(symbol, struct pf_symbol*) MAKE_PUSH_FUNC(list, pf_list_t*) MAKE_PUSH_FUNC(float, float) MAKE_PUSH_FUNC(int, int) MAKE_PUSH_FUNC(packet, pf_packet_t) MAKE_PUSH_FUNC(pointer, void*) MAKE_PUSH_FUNC(atom_pointer, pf_atom_t*) MAKE_PUSH_FUNC(forth_xt, pf_atom_t*) #endif