Q:

How do I write a simple `completion-at-point-functions` function? 

I'm considering writing a major mode for editing Magic: the Gathering decks. 
Most of it seems pretty straightforward but I have one question.  There are about 15 000 unique Magic cards available (cards with unique names that is).  I would like to be able to complete against them by writing a completion-at-point-function.  I've been looking for some simple, basic example of a capf function that just completes against a set of words to base my mode on but have failed to find anything so far.  Do you know of any good example for this to get started?  And do you believe it would be easy to get good performance or would I have to write my own data structure (I'm thinking like a Trie maybe). 
Obviously I'd need to find a way to sync with new cards etc and in the future maybe even be able to search for cards by other characteristics than just the card name but that can wait. 

A:

Documentation
The API completion at point function can be found in the documentation of completion-at-point-functions

Each function on this hook is called in turns without any argument and
  should return either nil to mean that it is not applicable at point,
  or a function of no argument to perform completion (discouraged), or a
  list of the form (START END COLLECTION .  PROPS) where  START and END
  delimit the entity to complete and should include point, COLLECTION
  is the completion table to use to complete it, and PROPS is a property list 
  for additional information. 

start, end and props are obvious, but I think the format of collection is not defined properly.  For that you can see the documentation of try-completion or all-completions

If COLLECTION is an alist, the keys (cars of elements) are the
  possible completions.   If an element is not a cons cell, then the
  element itself is the possible completion.  If COLLECTION is a
  hash-table, all the keys that are strings or symbols are the possible
  completions.  If COLLECTION is an obarray, the names of all symbols in
  the obarray are the possible completions. 
COLLECTION can also be a function to do the completion itself.  It
  receives three arguments: the values STRING, PREDICATE and nil. 
  Whatever it returns becomes the value of `try-completion'. 

Example
Below is a simple example of completion at point function which uses the words defined in /etc/dictionaries-common/words to complete the words in the buffer
(defvar words (split-string (with-temp-buffer
                              (insert-file-contents-literally "/etc/dictionaries-common/words")
                              (buffer-string))
                            "\n"))

(defun words-completion-at-point ()
  (let ((bounds (bounds-of-thing-at-point 'word)))
    (when bounds
      (list (car bounds)
            (cdr bounds)
            words
            :exclusive 'no
            :company-docsig #'identity
            :company-doc-buffer (lambda (cand)
                                  (company-doc-buffer (format "'%s' is defined in '/etc/dictionaries-common/words'" cand)))
            :company-location (lambda (cand)
                                (with-current-buffer (find-file-noselect "/etc/dictionaries-common/words")
                                  (goto-char (point-min))
                                  (cons (current-buffer) (search-forward cand nil t))))))))

The completion function looks for word at point (the library thingatpt is used to find the bounds of word) and completes it against the words in the /etc/dictionaries-common/words file, the property :exclusive is set to no so that emacs can use other capf functions if our fails.  Finally some additional properties are set to enhance the company-mode integration.  
Performance
The words file on my system had 99171 entries and emacs was able to complete them without any issues, so I guess 15000 entries should not be a problem. 
Integration with company-mode
Company mode integrates very well with completion-at-point-functions using the company-capf backend, so it should work out of the box for you, but you can enhance the completions offered by company by returning additional props in the result of capf function.  The props currently supported are 
:company-doc-buffer - Used by company to display metadata for current candidate
:company-docsig - Used by company to echo metadata about the candidate in the minibuffer
:company-location - Used by company to jump to the location of current candidate

